Multipartite or layered graph

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