Re: [boost] Graphs: need to merge vertices

From: Lie-Quan Lee (llee1_at_[hidden])
Date: 2001-05-03 10:41:41

At Thu, 3 May 2001 12:36:08 +0200,
Artur Wisz wrote:
> 
> 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.

This is a contraction operation (to contract vertex u into vertex
v). You might already know that sometimes the contraction algorithm to
describe the solution to the problem could be implemented quite
differently. For example, people optimize contraction in minimum
degree algorithm in very different way. 

One possible way is to rebuild the out-edges/in-edges, not just modify
them. Namely, copy original edges of v to new ones and mark them. Then 
when you deal with edges of u, you know whether an edge is already
existing in edges og v or not. You can use a predicate to copy_if all
edges of u's. Anyway, sorting edges to find common targets/sources
might not be a good idea here.

> 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,
> 

--
Lie-Quan Lee
University of Notre Dame