Boost Graph Library: edge retrieval using edge descriptor between square brackets fails
Hi all, I am wrapping the Boost Graph Library with a thin class, and I am having a problem in retrieving the edge. I use a mechanism similar to the one in here: http://stackoverflow.com/questions/3100146/adding-custom-vertices-to-a-boost... For testing, I add two vertices (suppose pNode1 and pNode2) successfully, and they can be retrieved as well by passing in their vertex descriptors. However, this is not the case for the edges: when I add an edge from pNode1 to pNode2, the edge is correctly stored as the out_edge of pNode1, but when I retrieve the edge using its edge descriptor, which is the (valid) return value of the add_edge() function, the pointer value is NULL. Also, when I debug the code, I find that inside the graph, there are two variables m_edges and m_vertices. The m_vertices correctly contains two vertex descriptors, but the m_edges is empty. So, do I make a mistake here? I have been looking for some information in Boost's archive and other sources (StackOverflow, ...), but so far haven't found anything helpful. I include a snippet at the end of this e-mail. I am using Visual Studio 2008 SP1 on Windows Vista SP2, and Boost 1.44.0 (haven't upgraded yet to 1.45, but the latter doesn't seem to address this issue). Thank you! Best regards, Nicholas Mario Wardhana //--------------------------- snippet ----------------------------- template <class NodeData, class EdgeData> class BoostGraphWrapper : public Graph<NodeData, EdgeData> { typedef boost::adjacency_list<boost::listS, boost::listS, boost::directedS, Node<NodeData>*, Edge<NodeData, EdgeData>*, boost::listS> BoostGraph; typedef typename boost::graph_traits<BoostGraph>::vertex_descriptor BoostVertexDescriptor; typedef typename boost::graph_traits<BoostGraph>::edge_descriptor BoostEdgeDescriptor; //... public: void AddNode(Node<NodeData>* pNode); Edge<NodeData, EdgeData>* AddEdge(Node<NodeData>* pNode1, Node<NodeData>* pNode2); //... private: BoostGraph m_graph; //... }; template <class NodeData, class EdgeData> void BoostGraphWrapper<NodeData, EdgeData>::AddNode(Node<NodeData>* pNode) { Graph<NodeData, EdgeData>::AddNode(pNode); // 1. Get the descriptor BoostVertexDescriptor vertexDescriptor = boost::add_vertex(m_graph); // 2. Fill with the node m_graph[vertexDescriptor] = pNode; // ... } template <class NodeData, class EdgeData> Edge<NodeData, EdgeData>* BoostGraphWrapper<NodeData, EdgeData>::AddEdge( Node<NodeData>* pNode1, Node<NodeData>* pNode2 ) { Graph<NodeData, EdgeData>::AddEdge(pNode1, pNode2); // 1. Get vertex descriptors of the nodes BoostVertexDescriptor vertexDescriptor1 = GetBoostVertexDescriptor(pNode1); BoostVertexDescriptor vertexDescriptor2 = GetBoostVertexDescriptor(pNode2); Node<NodeData>* tempNode = m_graph[vertexDescriptor1]; Node<NodeData>* tempNode2 = m_graph[vertexDescriptor2]; // 2. Add an empty edge BoostEdgeDescriptor edgeDescriptor; bool inGraph = false; boost::tie(edgeDescriptor,inGraph) = boost::add_edge(vertexDescriptor1, vertexDescriptor2, m_graph); if(!inGraph) { return NULL; } assert(BoostEdgeSize() == 1); // successful // 3. Fill the edge with the vertices Edge<NodeData, EdgeData>* temp = m_graph[edgeDescriptor]; assert(NULL != temp); // fails here //.... return pEdge; } void SomeFunction() { BoostGraphWrapper<int, int> graphWrapper; Node<int>* pNode1 = new Node<int>(); Node<int>* pNode2 = new Node<int>(); Edge<int, int>* pEdge; graphWrapper.AddNode(pNode1); graphWrapper.AddNode(pNode2); pEdge = graphWrapper.AddEdge(pNode2, pNode1); // fails here }
Hi, it seems to me, that you are very well adding an edge, but forgetting to insert its properties, that you want to retrieve. Please s. code below. On Wednesday, 12. January 2011 05:53:33 Nicholas Mario Wardhana wrote:
Hi all,
I am wrapping the Boost Graph Library with a thin class, and I am having a problem in retrieving the edge. I use a mechanism similar to the one in here:
http://stackoverflow.com/questions/3100146/adding-custom-vertices-to-a-boos t-graph
For testing, I add two vertices (suppose pNode1 and pNode2) successfully, and they can be retrieved as well by passing in their vertex descriptors. However, this is not the case for the edges: when I add an edge from pNode1 to pNode2, the edge is correctly stored as the out_edge of pNode1, but when I retrieve the edge using its edge descriptor, which is the (valid) return value of the add_edge() function, the pointer value is NULL. Also, when I debug the code, I find that inside the graph, there are two variables m_edges and m_vertices. The m_vertices correctly contains two vertex descriptors, but the m_edges is empty. So, do I make a mistake here? I have been looking for some information in Boost's archive and other sources (StackOverflow, ...), but so far haven't found anything helpful.
I include a snippet at the end of this e-mail. I am using Visual Studio 2008 SP1 on Windows Vista SP2, and Boost 1.44.0 (haven't upgraded yet to 1.45, but the latter doesn't seem to address this issue).
Thank you!
Best regards, Nicholas Mario Wardhana
//--------------------------- snippet -----------------------------
template <class NodeData, class EdgeData> class BoostGraphWrapper : public Graph<NodeData, EdgeData> { typedef boost::adjacency_list<boost::listS, boost::listS, boost::directedS, Node<NodeData>*, Edge<NodeData, EdgeData>*, boost::listS> BoostGraph; typedef typename boost::graph_traits<BoostGraph>::vertex_descriptor BoostVertexDescriptor; typedef typename boost::graph_traits<BoostGraph>::edge_descriptor BoostEdgeDescriptor;
//...
public: void AddNode(Node<NodeData>* pNode); Edge<NodeData, EdgeData>* AddEdge(Node<NodeData>* pNode1, Node<NodeData>* pNode2);
//...
private: BoostGraph m_graph;
//... };
template <class NodeData, class EdgeData> void BoostGraphWrapper<NodeData, EdgeData>::AddNode(Node<NodeData>* pNode) { Graph<NodeData, EdgeData>::AddNode(pNode);
// 1. Get the descriptor BoostVertexDescriptor vertexDescriptor = boost::add_vertex(m_graph);
// 2. Fill with the node m_graph[vertexDescriptor] = pNode;
You correctly insert the properties of the node here.
// ... }
template <class NodeData, class EdgeData> Edge<NodeData, EdgeData>* BoostGraphWrapper<NodeData, EdgeData>::AddEdge( Node<NodeData>* pNode1, Node<NodeData>* pNode2 ) { Graph<NodeData, EdgeData>::AddEdge(pNode1, pNode2);
// 1. Get vertex descriptors of the nodes BoostVertexDescriptor vertexDescriptor1 = GetBoostVertexDescriptor(pNode1); BoostVertexDescriptor vertexDescriptor2 = GetBoostVertexDescriptor(pNode2); Node<NodeData>* tempNode = m_graph[vertexDescriptor1]; Node<NodeData>* tempNode2 = m_graph[vertexDescriptor2];
// 2. Add an empty edge BoostEdgeDescriptor edgeDescriptor; bool inGraph = false; boost::tie(edgeDescriptor,inGraph) = boost::add_edge(vertexDescriptor1, vertexDescriptor2, m_graph);
You do add an edge, but this in the same as for vertices, it is only an edge descriptor. There is no additional information (as the properties) associated with it, yet.
if(!inGraph) { return NULL; } assert(BoostEdgeSize() == 1); // successful
// 3. Fill the edge with the vertices Edge<NodeData, EdgeData>* temp = m_graph[edgeDescriptor];
This information has not yet been set! I would expect the same as in AddNode() here: m_graph[edgeDescriptor] = pEdge; Retrieving this information when first adding an edge is counter-intuitive. Of course you need to pass pEdge as an argument to AddEdge().
assert(NULL != temp); // fails here
//....
return pEdge; }
void SomeFunction() { BoostGraphWrapper<int, int> graphWrapper; Node<int>* pNode1 = new Node<int>(); Node<int>* pNode2 = new Node<int>(); Edge<int, int>* pEdge;
graphWrapper.AddNode(pNode1); graphWrapper.AddNode(pNode2);
pEdge = graphWrapper.AddEdge(pNode2, pNode1); // fails here } _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hope that helps. BTW, have you already thought about using vecS for the VertexList (instead of listS)? It has the advantage of automatically creating vertex indices which are crucial to most BGL algorithms. Best, Cedric
On 12 January 2011 16:36, Cedric Laczny <cedric.laczny@gmx.de> wrote:
Hi,
it seems to me, that you are very well adding an edge, but forgetting to insert its properties, that you want to retrieve.
Please s. code below.
Hi Cedric, Thank you for your quick reply.
You do add an edge, but this in the same as for vertices, it is only an edge descriptor. There is no additional information (as the properties) associated with it, yet.
This information has not yet been set! I would expect the same as in AddNode() here: m_graph[edgeDescriptor] = pEdge; Retrieving this information when first adding an edge is counter-intuitive. Of course you need to pass pEdge as an argument to AddEdge().
My bad! Now I realise that I forget to assign pEdge to the edge descriptor. So at the beginning of the function I add this line, which basically calls the parent class' AddEdge function to retrieve the corresponding Edge information: Edge<NodeData, EdgeData>* pEdge = Graph<NodeData, EdgeData>::AddEdge(pNode1, pNode2); and in Step 3 of BoostGraphWrapper::AddEdge(), I add: m_graph[edgeDescriptor] = pEdge; This solves the problem. Thank you for your suggestion.
Hope that helps. BTW, have you already thought about using vecS for the VertexList (instead of listS)? It has the advantage of automatically creating vertex indices which are crucial to most BGL algorithms.
I think I am clueless about this issue. After searching around, I found about that in http://www.systomath.com/include/Boost-1_36/libs/graph/doc/quick_tour.html I am a new BGL user, and haven't noticed how automatically created vertex indices can be useful. Could you please give some information? Currently I choose listS over vecS because in some operations, listS is faster than vecS, as written in: http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/using_adjacency_list.htm... Thank you for bringing that up.
Best,
Cedric
Best regards, Nicholas Mario Wardhana
On Wednesday, 12. January 2011 11:07:04 Nicholas Mario Wardhana wrote:
On 12 January 2011 16:36, Cedric Laczny <cedric.laczny@gmx.de> wrote:
Hi,
it seems to me, that you are very well adding an edge, but forgetting to insert its properties, that you want to retrieve.
Please s. code below.
Hi Cedric,
Thank you for your quick reply.
You do add an edge, but this in the same as for vertices, it is only an edge descriptor. There is no additional information (as the properties) associated with it, yet.
This information has not yet been set! I would expect the same as in AddNode() here: m_graph[edgeDescriptor] = pEdge; Retrieving this information when first adding an edge is counter-intuitive. Of course you need to pass pEdge as an argument to AddEdge().
My bad! Now I realise that I forget to assign pEdge to the edge descriptor. So at the beginning of the function I add this line, which basically calls the parent class' AddEdge function to retrieve the corresponding Edge information:
Edge<NodeData, EdgeData>* pEdge = Graph<NodeData, EdgeData>::AddEdge(pNode1, pNode2);
and in Step 3 of BoostGraphWrapper::AddEdge(), I add:
m_graph[edgeDescriptor] = pEdge;
This solves the problem. Thank you for your suggestion.
Hope that helps. BTW, have you already thought about using vecS for the VertexList (instead of listS)? It has the advantage of automatically creating vertex indices which are crucial to most BGL algorithms.
I think I am clueless about this issue. After searching around, I found about that in
http://www.systomath.com/include/Boost-1_36/libs/graph/doc/quick_tour.html
I am a new BGL user, and haven't noticed how automatically created vertex indices can be useful. Could you please give some information?
If you look at the algorithms or visitors that the BGL provides (e.g. Dijkstra's shortest path(s) or BFS), these algorithms almost all rely in some way on an indexing of the vertices. I can't really explain you what each algorithm's special purpose of the indices is, but I think that this is not that important right now ;) Probably for sorting or such... However, these algorithm rely on either an internal vertex_index_t, which is automatically created and updated when adding vertices, _if_ vecS is used as the vertex container. At the moment I am not sure how this behaves when removing vertices, so I will leave this out for now (iterator invalidation also plays a role here, just for your notes). If you decide to use listS, setS (or others) you need to maintain a vertex-index on your own, e.g. as an attribute of your wrapper. This index must then be passed to the BFS, as otherwise, it will try to retrieve it automatically via vertex_index_t, which will result in compile errors.
Currently I choose listS over vecS because in some operations, listS is faster than vecS, as written in:
http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/using_adjacency_list.ht ml
I think this is also one of the never-ending stories: Which is best to choose for which purpose. In theory, a list is usually faster than a vector, especially when inserting a lot. This might very well be the case in practice also. I think it strongly depends on your application. However, I did not experience dramatically worse performance using vecS. The STL vector container is probably one of the most optimized linear containers (at least in the STL) and thus is IMHO generally comparable to a list. Do you expect to have very large graphs? I actually work with graphs having around 30k vertices and 500k edges and I use vecS and setS respectively. I did not experience that the traversal of the graph was slow; usually other things (algorithms, copying etc.) require most of the runtime. Except for testing it out yourself for your particular purposes, I don't think there is a way for you to know which choice would be better. Choosing vecS might (conditinal here :) slow down your program while benefiting from the automatic vertex indexing. The automatic indexing of course also costs you space, because the adjacency_list must also store that information. All in all, if you don't have a very critically limited application, vecS would be the best choice IMHO, especially when just starting to work with the BGL.
Thank you for bringing that up.
You are welcome.
Best,
Cedric
Best regards, Nicholas Mario Wardhana
Best, Cedric
On 12 January 2011 18:54, Cedric Laczny <cedric.laczny@gmx.de> wrote:
If you look at the algorithms or visitors that the BGL provides (e.g. Dijkstra's shortest path(s) or BFS), these algorithms almost all rely in some way on an indexing of the vertices. I can't really explain you what each algorithm's special purpose of the indices is, but I think that this is not that important right now ;) Probably for sorting or such... However, these algorithm rely on either an internal vertex_index_t, which is automatically created and updated when adding vertices, _if_ vecS is used as the vertex container. At the moment I am not sure how this behaves when removing vertices, so I will leave this out for now (iterator invalidation also plays a role here, just for your notes). If you decide to use listS, setS (or others) you need to maintain a vertex-index on your own, e.g. as an attribute of your wrapper. This index must then be passed to the BFS, as otherwise, it will try to retrieve it automatically via vertex_index_t, which will result in compile errors.
I think this is also one of the never-ending stories: Which is best to choose for which purpose. In theory, a list is usually faster than a vector, especially when inserting a lot. This might very well be the case in practice also. I think it strongly depends on your application. However, I did not experience dramatically worse performance using vecS. The STL vector container is probably one of the most optimized linear containers (at least in the STL) and thus is IMHO generally comparable to a list.
Do you expect to have very large graphs? I actually work with graphs having around 30k vertices and 500k edges and I use vecS and setS respectively. I did not experience that the traversal of the graph was slow; usually other things (algorithms, copying etc.) require most of the runtime. Except for testing it out yourself for your particular purposes, I don't think there is a way for you to know which choice would be better. Choosing vecS might (conditinal here :) slow down your program while benefiting from the automatic vertex indexing. The automatic indexing of course also costs you space, because the adjacency_list must also store that information. All in all, if you don't have a very critically limited application, vecS would be the best choice IMHO, especially when just starting to work with the BGL.
Best,
Cedric
Hi Cedric, Actually, I will use the wrapper for motion planning for real-time application, therefore searching algorithms like Dijkstra and A* will be heavily used. This is also the reason why I use BGL, as it comes with these searching algorithms. I'm dealing with a huge environment, so I also expect the graph to be big, although maybe not as big as yours, probably with around 1-10k vertices and 50k edges. Of course planning time is crucial here, taking the real-time constraint into account. Nevertheless, I think for now I will just resort to vecS, and I will compare listS and vecS later on. If switching to listS is not worth the implementation effort, considering the performance of vecS, I will stick to vecS. Thank you for the explanation. Best regards, Nicholas Mario Wardhana
On Wednesday, 12. January 2011 13:06:43 Nicholas Mario Wardhana wrote:
On 12 January 2011 18:54, Cedric Laczny <cedric.laczny@gmx.de> wrote:
If you look at the algorithms or visitors that the BGL provides (e.g. Dijkstra's shortest path(s) or BFS), these algorithms almost all rely in some way on an indexing of the vertices. I can't really explain you what each algorithm's special purpose of the indices is, but I think that this is not that important right now ;) Probably for sorting or such... However, these algorithm rely on either an internal vertex_index_t, which is automatically created and updated when adding vertices, _if_ vecS is used as the vertex container. At the moment I am not sure how this behaves when removing vertices, so I will leave this out for now (iterator invalidation also plays a role here, just for your notes). If you decide to use listS, setS (or others) you need to maintain a vertex-index on your own, e.g. as an attribute of your wrapper. This index must then be passed to the BFS, as otherwise, it will try to retrieve it automatically via vertex_index_t, which will result in compile errors.
I think this is also one of the never-ending stories: Which is best to choose for which purpose. In theory, a list is usually faster than a vector, especially when inserting a lot. This might very well be the case in practice also. I think it strongly depends on your application. However, I did not experience dramatically worse performance using vecS. The STL vector container is probably one of the most optimized linear containers (at least in the STL) and thus is IMHO generally comparable to a list.
Do you expect to have very large graphs? I actually work with graphs having around 30k vertices and 500k edges and I use vecS and setS respectively. I did not experience that the traversal of the graph was slow; usually other things (algorithms, copying etc.) require most of the runtime. Except for testing it out yourself for your particular purposes, I don't think there is a way for you to know which choice would be better. Choosing vecS might (conditinal here
:) slow down your program while benefiting from the automatic vertex :indexing.
The automatic indexing of course also costs you space, because the adjacency_list must also store that information. All in all, if you don't have a very critically limited application, vecS would be the best choice IMHO, especially when just starting to work with the BGL.
Best,
Cedric
Hi Cedric,
Actually, I will use the wrapper for motion planning for real-time application, therefore searching algorithms like Dijkstra and A* will be heavily used. This is also the reason why I use BGL, as it comes with these searching algorithms. I'm dealing with a huge environment, so I also expect the graph to be big, although maybe not as big as yours, probably with around 1-10k vertices and 50k edges. Of course planning time is crucial here, taking the real-time constraint into account. Nevertheless, I think for now I will just resort to vecS, and I will compare listS and vecS later on. If switching to listS is not worth the implementation effort, considering the performance of vecS, I will stick to vecS.
Now, real-time applications are of course a quite specific field and rely heavily on the constraint of performance... It would be intersting to see the differences if you are going to swich to listS, therefore it would be kind of you to provide some runtime-results to this mailinglist when you're done :) Changing vecS to listS should be fairly straightforward, basically only requiring a valid vertex index property-map.
Thank you for the explanation.
You are welcome.
Best regards, Nicholas Mario Wardhana
Good luck with your project. Best, Cedric
Now, real-time applications are of course a quite specific field and rely heavily on the constraint of performance... It would be intersting to see the differences if you are going to swich to listS, therefore it would be kind of you to provide some runtime-results to this mailinglist when you're done :) Changing vecS to listS should be fairly straightforward, basically only requiring a valid vertex index property-map.
As I'm still in the early phase now, not to mention my currently basic knowledge in BGL, it may take several weeks/months to get the comparison result. But when I have it done, I will try to post it here.
Good luck with your project.
Thanks Cedric!
Best,
Cedric
Best regards, Nicholas Mario Wardhana
participants (2)
-
Cedric Laczny -
Nicholas Mario Wardhana