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

Subject: Re: [Boost-users] [BGL] Using pointers as indexes in graphs
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-09-02 17:15:25

On Thu, 2 Sep 2010, Bruno Barberi Gnecco wrote:

>>> 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.

I think you have a much easier solution available: define your plugin 
pointer structure as a graph and then run topological_sort on that.  Do 
you have a list (even as just a vector<Plugin*> that you create) of all of 
the plugins in the system [it is probably a bug in the topological sort 
implementation that it needs that at all]?  If so, you can define the 
appropriate traits classes and functions to model Vertex List Graph and 
Incidence Graph, and use your plugin graph as the graph (without needing 
to build a separate BGL graph).  You just need to define a graph_traits<> 
specialization for some object that represents your plugin graph (it can 
just be a dummy class), and then define six necessary functions; you can 
use associative_property_map or a field within the Plugin class as the 
color map (avoiding the need for a vertex index map).  You might want to 
look at <libs/graph/example/implicit_graph.cpp> in Boost as an example; 
other files you might want to look at are <boost/graph/leda_graph.hpp>, 
<boost/graph/stanford_graph.hpp>, and <boost/graph/vector_as_graph.hpp>. 
Note that you only need to implement the non-mutating functions and don't 
need to handle properties, so your code will be simpler than the full 
adaptors.

> 	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?

The bundled property system in BGL expects the struct itself to be the 
property type, not a pointer to it.  See 
<URL:http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/bundles.html> for 
details.  You might want to use old-style properties (having two 
properties, such as vertex_name and vertex_color), or a separate struct 
with a field for the Plugin* and a field for the color.  Note that having 
an explicit color map will mean that you do not need to pass a vertex 
index map.

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

It is a pointer-to-member type, indicating a field of type "int" in the 
"Plugin" class.

> - does Plugin::id need to be sequential?

Yes -- from 0 to num_vertices(g)-1, inclusive.  Vertex IDs are used to 
index arrays.

-- Jeremiah Willcock