Re: [boost] Subnetworks

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-03-17 16:42:43

On Sat, 17 Mar 2001, Dietmar Kuehl wrote:
dietma> Hi,
dietma> Ian_Easson_at_[hidden] wrote:
dietma> 
dietma> > Is anyone working on, or contemplating working on, enhancing the BGL
dietma> > to model subnetworks/subgraphs, so that each vertex in a graph is
dietma> > potentially explodeable into a graph of its own?
dietma> 
dietma> I'm not working actively on this but I want to point out
dietma> the basic approach to deal with modified versions of a
dietma> graph, independent on whether the result is a subgraph or
dietma> are additional edges and nodes, is to just modify the view
dietma> to the graph! That is, a subgraph can eg. be implemented
dietma> by using property accessors (I haven't checked whether
dietma> these are still called that way; I seem to remember that
dietma> they were named differently, something involving "map" if
dietma> I remember correctly) indicating whether a node or an edge

Yep, the name we finally settled on was "property map".

dietma> is present in the subgraph. To deal with a subgraph,
dietma> iterator wrappers ignoring non-members in the underlying
dietma> iterator would be used.

I recently added a filtered_graph adaptor to BGL to make it easy to do
this kind of thing. The filtered_graph adaptor takes two predicates: one
for edges and one for vertices, and creates a view of the graph where
edges and vertices appear to be removed based on the predicates.

This approach is not appropriate for all subgraph applications: the cases
where you have lots of small subgraphs. In this case you want traversal of
the subgraphs to take time proportional to the subgraph, not the whole
graph. This is why I've also added a subgraph class to BGL (which is
modelled after the way subgraphs are handled in graphviz).

dietma> Some mutations to graphs are more interesting. For
dietma> example, certain algorithms (eg. the algorithms I have
dietma> seen to do planarity testing) combine two nodes to form a
dietma> new node which is adjacent to all nodes to which the two
dietma> original nodes where adjacent (whether this might result
dietma> in parallel edges depends on the details of the
dietma> algorithm). In this case, each node in the underlying
dietma> representation would store a [probably circular] list
dietma> specifying the other nodes which were joined with the
dietma> particular node. When collapsing two nodes, the lists
dietma> would be merged to form a new one which is then referenced
dietma> from both nodes. If the nodes need to be separated later,
dietma> it might be useful to maintain a stack of lists which can
dietma> then be used to reverse the process.

Interesting!

dietma> One important aspect of temporary mutations to graphs is
dietma> that eg. really erasing an edge will result in loss of
dietma> data if the mutation is later to be undone:
dietma> The attributes of the edge need to be restored from some
dietma> source. Since there is an unknown number of attributes
dietma> associated with an edge (each property accessor adds
dietma> another attribute) this is basically impossible.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------