Re: [Boost-users] [BGL] Using pointers as indexes in graphs

Subject: Re: [Boost-users] [BGL] Using pointers as indexes in graphs
From: Bruno Barberi Gnecco (brunobg_at_[hidden])
Date: 2010-09-02 14:53:59

>> Hi,
>>
>> I want to store pointers in a graph. Can I somehow use their pointers
>> as indexes?
>>
>> Here's the code I'm trying to execute. It does not work correctly,
>> however;
>> apparently graph add other nodes in the vector storage (to fill the
>> holes?).
>> I suppose I could use listS instead of vecS, but then I can't get the
>> topological_sort code to work (I know I have to provide some form of
>> indices, but I don't understand how to do that). Any suggestions to
>> solve this?
 >
> Would you rather have your pointers as indices or use listS? If you use
> listS, you get stable pointers as descriptors, but you can't choose the
> pointer; it is allocated by BGL. If you want to use your pointers, you
> will need to either create your own graph type or (more likely) have a
> separate map or unordered_map from your pointers to graph vertices and
> then have the pointer also be a vertex property (for two-way linkage).
> If you can modify the definition of Plugin, you can add a vertex
> descriptor there. Note that you need listS or similar to get stable
> descriptors.
 >
 > As to the topological_sort issue, you have two main options: create your
 > own color map, or create a vertex index map. Since you are setting up
 > your own properties anyway, you might want to have vertex_color as a
 > vertex property and have another property for the Plugin* (using either
 > old-style or bundled properties). You can also use
 > associative_property_map (at some loss in performance) as the color map;
 > that is the easy option. I do not see an obvious example of that around,
 > but
 > 
<URL:http://www.boost.org/doc/libs/1_44_0/libs/property_map/doc/associative_property_map.html> 

 > will give you a start.

        Thanks for the answer. I don't think the choice indices/listS matters to me. I'm looking 
for the most practical solution. Let me state the complete problem, because I'm still 
somewhat at a loss and need some more help...

        Problem: I'm working on a computer vision library (skamleton.sf.net, if anyone is 
interested); the library is composed of several plugins that can be joined into a 
pipeline. Some of these plugins can run in parallel, which is why they form a graph. I'm 
assuming now that each Plugin instance is unique in the graph, which is why the pointer is 
a unique index. So BGL seems a nice solution for this problem: it can handle the 
dependencies and the example of a parallel build is very suited to me. So I can change 
Plugin as I please, as well as any other part of the code.

        It seems that using listS is the cleaner solution, but I'm still in doubt as how to set 
the vertex index. FAQ #5 [http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/faq.html] 
shows an example with internal properties, I can't find an example using bundles and 
pointers. I think it should be something like this:

class Plugin {
public:
        int id; // index for the graph

        Plugin();
};

typedef boost::adjacency_list<boost::setS, boost::listS, boost::directedS, Plugin *> 
PipelineGraph;
typedef boost::graph_traits<PipelineGraph>::vertex_descriptor PipelineVertex;
typedef boost::property_map<PipelineGraph, int Plugin::*>::type VertexIndexMap;

PipelineGraph graph;
VertexIndexMap index_map = get(&Plugin::id, graph);
std::vector<PipelineVertex> topo;
topological_sort(graph, std::back_inserter(topo), boost::vertex_index_map(get(&Plugin::id, 
graph)));

        But:

- using something like "Plugin *::id" (which does not compile) instead of "Plugin::id". 
What would that be?

- I do not understand what "int Plugin::*" means in the VertexIndexMap definition.

- does Plugin::id need to be sequential?
        

        Extra help, please? Thanks!