Re: [boost] Subnetworks

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 2001-03-17 16:30:49

Hi,
Ian_Easson_at_[hidden] wrote:

> Is anyone working on, or contemplating working on, enhancing the BGL
> to model subnetworks/subgraphs, so that each vertex in a graph is
> potentially explodeable into a graph of its own?

I'm not working actively on this but I want to point out the basic approach
to deal with modified versions of a graph, independent on whether the result

is a subgraph or are additional edges and nodes, is to just modify the view
to
the graph! That is, a subgraph can eg. be implemented by using property
accessors (I haven't checked whether these are still called that way; I seem

to remember that they were named differently, something involving "map"
if I remember correctly) indicating whether a node or an  edge is present in

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

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

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