🚀 go-pugleaf

From tynor@prism.gatech.EDU (Steve Tynor):
>>   The fact that a subgraph has become detached does not imply that
>>   it is no longer part of a graph.  Not all graphs are fully connected.
>>   Therefore, it isn't possible to release the storage used until there
>>   is some sort of directive which indicates that a given set of nodes
>>   and/or arcs is to be destroyed. 
> 
> But what if _in_this_case_, a detached subgraph is garbage and should
> be deallocated? 

    OK, assume that we do want to kill detached subgraphs.  Which of
    the two (or more) connected components is the one we wish to keep? 
    
    If we assume that there is some distinguished node or arc which
    can never be deleted and which also serves to mark the "permanent"
    connected component, then presumably our graph abstraction will 
    allow us to mark one such node or arc as being endowed with these 
    magic properties.  Now we need an oracle which will tell us if
    a connected component contains the magic node or arc.  The ability
    to determine whether one node (or arc) is reachable if we start at 
    another node or arc is a generally useful capability which should 
    probably be provided to the user anyway, particularly since the 
    algorithm need only be looked up in a standard text on graph theory 
    and typed in.  Since any service which is not explicitly used will 
    be optimized away anyway, the user pays no real price for having the 
    service provided.  Having provided the service to the user anyway, 
    we can now use it ourselves to determine which component to throw 
    away.  Now this is obviously a special-case response to this 
    particular problem, but the problem is also a special case itself. 

    Even if computing it ourselves has the same computational complexity
    as computing it with a garbage collection algorithm, there is still
    a gain in that we can search a specific area at a specific time and
    therefore improve the predictability of our service.  We know that
    there will be no operation whose time complexity will be totally out
    of proportion to the size of our graph because we are paying for all
    garbage everywhere on the machine to be collected.  

    Finally, there is the problem of the GC system repeatedly being
    invoked (at great expense) when the amount of storage remaining
    becomes fairly small.  With a managed system, the user is given
    an opportunity to strategically throw away data structures, and
    thereby free up some space that the garbage collector could not
    possibly take because it is still "in use".
 
 
    Bill Wolfe, wtwolfe@hubcap.clemson.edu