[Boost-users] [BGL] Mapping a source Graph to a target Graph

Subject: [Boost-users] [BGL] Mapping a source Graph to a target Graph
From: Ioannis Nousias (s0238762_at_[hidden])
Date: 2008-10-04 20:17:55

Hello BGL list members,

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

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