[BGL] Using pointers as indexes in graphs
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? Thanks! #include <iostream> #include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/topological_sort.hpp> class Plugin { public: // some data here int x; Plugin(int a) : x(a) {} }; typedef std::list< std::pair<Plugin *, Plugin *> > EdgeList; typedef boost::adjacency_list<boost::setS, boost::vecS, boost::directedS, Plugin *> PipelineGraph; typedef boost::graph_traits<PipelineGraph>::vertex_descriptor PipelineVertex; void graph(EdgeList edges) { PipelineGraph graph; for (EdgeList::iterator it(edges.begin()); it != edges.end(); it++) { PipelineVertex a(boost::vertex(reinterpret_cast<unsigned long> (it->first), graph)); PipelineVertex b(boost::vertex(reinterpret_cast<unsigned long> (it->second), graph)); boost::add_edge(a, b, graph); } // sort by topology, so we run the plugins in the correct order std::vector<PipelineVertex> sorted; boost::topological_sort(graph, std::back_inserter(sorted)); std::cout << sorted.size() << std::endl; // REVERSE topological order std::vector<PipelineVertex> vl(sorted.rbegin(), sorted.rend()); // loop for (std::vector<PipelineVertex>::iterator it(vl.begin()); it != vl.end(); it++) { Plugin *p = reinterpret_cast<Plugin *>(*it); std::cout << p->x << std::endl; } } int main() { EdgeList edges; Plugin *a = new Plugin(1); Plugin *b = new Plugin(2); Plugin *c = new Plugin(3); Plugin *d = new Plugin(4); edges.push_back(std::pair<Plugin*, Plugin*>(a, b)); edges.push_back(std::pair<Plugin*, Plugin*>(b, c)); edges.push_back(std::pair<Plugin*, Plugin*>(b, d)); graph(edges); return 0; }
On Wed, 1 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. -- Jeremiah Willcock
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!
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
participants (2)
-
Bruno Barberi Gnecco -
Jeremiah Willcock