Boost logo

Boost Users :

Subject: [Boost-users] [BGL] Mapping a source Graph to a target Graph
From: Ioannis Nousias (s0238762_at_[hidden])
Date: 2008-10-03 10:08:23

Hello BGL developers,

I'm looking for an algorithm that can map a source graph to a target
graph. The special requirement is that the graphs have a set of vertices
which are differentiated by type(colour if you like). Thus 'red' source
vertices should only map to 'red' target vertices, etc. The mapping
should be 1-to-1 (a 'blue' target vertex can accept one 'blue' source
vertex). I assume the target graph has enough vertices of each
type(colour) to map all vertices of the source graph.

The target graph represents a topology, while the source graph is the
data-graph to map onto that topology. I've briefly looked at the
'layout' specific algorithms provided by BGL. I thought the
'gursoy_atun_layout'could be used, but then I realised it was not
meeting the requirements. The main thing that's missing is the way to
differentiate vertices by type. Also I don't understand why the
'topology' is not a BGL graph as well.

To put it in other words, the layout algorithms in BGL operate on a
homogeneous environment. The source vertices can freely occupy any
'point' or 'position' on the target medium. I'm looking for an algorithm
that operates on a heterogeneous environment, where the target 'slots'
can only accept source vertices of a given type.

Is there any current BGL algorithm that fits that description, or can be
easily modified to cover this case? If not, can somebody point me to an
efficient mapping algorithm that I could base an implementation on.

thanks in advance,

The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at