Re: [boost] Graphs: need to merge vertices

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-05-03 08:10:35

Hi Art,

On Thu, 3 May 2001, Artur Wisz wrote:

gagate> Hello again,
gagate> I have a practical problem and try to solve it with BGL.
gagate> Some topological algorithms for calculating symbolic
gagate> determinants of an admittance matrix (Electrical Circuits)

Sounds like fun!

gagate> require a vertices merge operation, that is vertex u is
gagate> merged with vertex v to become vertex v. It consists of
gagate> these steps:
gagate> - remove (u,v) and (v,u) edges;
gagate> - merge all u and v out-edges with common targets;
gagate> - merge all u and v in-edges with common sources;
gagate> - move the rest of u out-edges to v;
gagate> - move the rest of u in-edges to v;

gagate> Merging edges means merging their properties (mainly names
gagate> and weights) and can be done with a user supplied functor.
gagate> Moving an edge means creating a new edge and copying the
gagate> edge properties to the new edge properties.
gagate> Finding out-edges/in-edges with common targets/sources can
gagate> be done with set_intersection with predicate, provided
gagate> that the edges are sorted. This should be true with
gagate> associative containers, but not the others, like lists or
gagate> vectors. So here is the first problem: in the graph
gagate> interface currently there is no way to sort
gagate> edges/out-edges/in-edges of a graph. The workaround is to
gagate> make a copy of those sets, sort them and then find the
gagate> intersections. This has its time and space overhead.

There are currently no graph concepts that include the requirement
for sorted out-edges, but the adjacency_list with EdgeList=setS
does provide sorted out-edges. I am very open to adding a concept
to describe graphs with sorted out-edges.

gagate> Another problem is accessing all edge properties at once,
gagate> i.e. for copying them. Now properties can be accessed only
gagate> in one dimension, and the property has to be explicitly
gagate> specified. There is no generic way of manipulating all
gagate> element properties as a whole, while adhering to the
gagate> concept that a property can be anything, although there
gagate> are already types edge_property_type and
gagate> vertex_property_type in the MutablePropertyGraph concept.
gagate> Therefore a user has to supply a function object for doing
gagate> things like copying properties of one element to another,
gagate> which is a pretty generic operation. Perhaps the
gagate> MutablePropertyGraph concept could be extended somehow to
gagate> allow such manipulations. What do you think ? Thanks, Your
gagate> use of Yahoo! Groups is subject to
gagate> http://docs.yahoo.com/info/terms/

The current release has an experimental solution for this.
I've created two tags, vertex_all_t and edge_all_t which
can be used with adjacency_list to get a property map for
accessing an object containing all the internal properties
of the graph. My plan is to add this to the MutablepropertyGraph
interface.

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