
Boost : 
Subject: Re: [boost] another approach to memory management that solves thereferential cycles problem
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 20090227 09:45:00
Achilleas Margaritis wrote:
> > I would interpret this statement in the way that you think that it
> > will be difficult to solve the scaling problem.
>
> Indeed.
>
> The scaling problem depends solely on the configuration of the graph of
> objects. The worst case is to have N objects pointing to all other
> objects, i.e. N objects having N1 pointers to all other objects.
>
> I am not well versed into graph theory, so perhaps someone else can
> enlighten us if some sort of shortest path discovery algorithm exists
> that can be applied to this case. Perhaps some algorithm that applies
> weights over the paths of the graph?
This reminds me of the "Dynamic graph algorithms" ToDo item from the Boost Graph Library:
http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/challenge.html
The task at hand seems to be related to the "Dynamic Connectivity" problem. The given references seem to be from 1998 and 1999, but skimming over them gives hope that the problem is not as unsolvable as it seems at first glance: "The currently best theoretic bounds are achieved by a data structure invented by Henzinger and King [13] and improced by Henzinger and Thorup [14]. It achieves O(log n) worstcase deterministic query time and O(log^2 n) amortized expected update time ..."
I haven't yet looked at your other proposed solutions, but perhaps I will do this later.
Regards,
Thomas
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk