Re: [Boost-users] Multipartite or layered graph

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-09-06 15:31:08

On Aug 22, 2005, at 5:35 AM, Nicola Vitacolonna wrote:
> I need to implement a graph whose set of vertices is partitioned into
> a certain number of ordered subsets (called layers). Edges join
> vertices from a layer to the next one(s). A critical operation is the
> iteration over the nodes of a given layer.
>
> I think this can be implemented by adding a vertex property to each
> vertex, that specifies the layer each vertex belongs to. But this
> does not seem to me the most (time and space) efficient solution: in
> particular, how can I iterate over the nodes of a given layer without
> checking every node?

Adding the property allows you to determine which layer a given node 
belongs in efficient, but not the other way around...

> I was wondering whether there is a better way to do the job: maybe,
> using a custom VertexList implemented using a vector for each layer
> (in this case, should I write my own functions to add/remove
> vertices? And should I write my own iterators?). Any other idea, or
> pointer to existing code (I am new to Boost)?

I don't know of any other existing code to do this. You could keep 
separate lists of vertices in each layer, perhaps, and then wrap up the 
Boost graph type with those lists to create your own data structure.

Another option is to invent your own data structure that is efficient 
for the operations you are interested in. Then if you want to use the 
BGL algorithms on that data structure, you can implement the functions 
needed by the BGL graph concepts.

        Doug