Re: [boost] another approach to memory management that solves thereferential cycles problem

Subject: Re: [boost] another approach to memory management that solves thereferential cycles problem
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2009-02-27 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 N-1 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" To-Do 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) worst-case 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