Graphs: need to merge vertices

From: Artur Wisz (gagatech_at_[hidden])
Date: 2001-05-03 05:36:08

Hello again,
I have a practical problem and try to solve it with BGL. Some topological
algorithms for calculating symbolic determinants of an admittance matrix
(Electrical Circuits) require a vertices merge operation, that is vertex u
is merged with vertex v to become vertex v. It consists of these steps:
- remove (u,v) and (v,u) edges;
- merge all u and v out-edges with common targets;
- merge all u and v in-edges with common sources;
- move the rest of u out-edges to v;
- move the rest of u in-edges to v;
Merging edges means merging their properties (mainly names and weights) and
can be done with a user supplied functor.
Moving an edge means creating a new edge and copying the edge properties to
the new edge properties.
Finding out-edges/in-edges with common targets/sources can be done with
set_intersection with predicate, provided that the edges are sorted. This
should be true with associative containers, but not the others, like lists
or vectors. So here is the first problem: in the graph interface currently
there is no way to sort edges/out-edges/in-edges of a graph. The workaround
is to make a copy of those sets, sort them and then find the intersections.
This has its time and space overhead.
Another problem is accessing all edge properties at once, i.e. for copying
them. Now properties can be accessed only in one dimension, and the property
has to be explicitly specified. There is no generic way of manipulating all
element properties as a whole, while adhering to the concept that a property
can be anything, although there are already types edge_property_type and
vertex_property_type in the MutablePropertyGraph concept. Therefore a user
has to supply a function object for doing things like copying properties of
one element to another, which is a pretty generic operation. Perhaps the
MutablePropertyGraph concept could be extended somehow to allow such
manipulations.
What do you think ?
Thanks,

Art



--