Boost Graph: edge indices
Hi, In the Boost Graph library, vertices have an index (vertex_index_t), and I was under the impression that edges have one, too. At least, there's a predefined type called edge_index_t. However, I can't figure out how to access an edge's index. For example, consider a graph defined like: typedef adjacency_list<vecS, vecS, directedS, Foo*> MyGraph; typedef graph_traits<MyGraph>::vertex_descriptor Vertex; typedef graph_traits<MyGraph>::edge_descriptor Edge; And let's say I've got a vertex descriptor called "u". I can iterate over u's outgoing edges like this: typedef graph_traits<MyGraph>::out_edge_iterator out_iter; std::pair<out_iter, out_iter> outp; for (outp = out_edges(u, g); outp.first != outp.second; ++outp.first) { Edge e = *outp.first; Vertex v = target(e, g); cout << index[v] << std::endl; // Works fine cout << index[e] << std::endl; // Compiler error } In this example, index[v] works as expected, but index[e] gives me a compiler error: "no match for ‘operator[]’ in ‘index[e]". Perhaps my graph typedef needs to be changed so that its edges have a property map for edge_index_t, although I'm not sure how to do that. (And anyway I wouldn't expect vertices to have indices by default but edges not...) Thanks for any help, Trevor
Hi! The edge_index internal property map is not created by default, so you have to define it explicitly: typedef adjacency_list<vecS, vecS, directedS, Foo*, property<edge_index_t, std::size_t> > MyGraph; typedef property_map<MyGraph, edge_index_t>::type MyEdgeIndexMap; ... // Retrieve the edge index map associated with the graph MyEdgeIndexMap emap = get(edge_index, g); ... // Convert the edge descriptor to an integer value cout << index[ get(emap, e, g) ] << endl; The vertex descriptor is an integer value so it works with operator[], but edge descriptor is an std::pair<>, so you have to convert it to an integer with the appropriate edge index map. This leaves only one question: how do you use bundled edge properties along with edge index map? Cheers, Gabe On Thu, Apr 1, 2010 at 3:19 AM, Trevor Harmon <Trevor.W.Harmon@nasa.gov> wrote:
Hi,
In the Boost Graph library, vertices have an index (vertex_index_t), and I was under the impression that edges have one, too. At least, there's a predefined type called edge_index_t. However, I can't figure out how to access an edge's index. For example, consider a graph defined like:
typedef adjacency_list<vecS, vecS, directedS, Foo*> MyGraph; typedef graph_traits<MyGraph>::vertex_descriptor Vertex; typedef graph_traits<MyGraph>::edge_descriptor Edge;
And let's say I've got a vertex descriptor called "u". I can iterate over u's outgoing edges like this:
typedef graph_traits<MyGraph>::out_edge_iterator out_iter; std::pair<out_iter, out_iter> outp; for (outp = out_edges(u, g); outp.first != outp.second; ++outp.first) { Edge e = *outp.first; Vertex v = target(e, g); cout << index[v] << std::endl; // Works fine cout << index[e] << std::endl; // Compiler error }
In this example, index[v] works as expected, but index[e] gives me a compiler error: "no match for ‘operator[]’ in ‘index[e]".
Perhaps my graph typedef needs to be changed so that its edges have a property map for edge_index_t, although I'm not sure how to do that. (And anyway I wouldn't expect vertices to have indices by default but edges not...)
Thanks for any help,
Trevor
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Thu, 1 Apr 2010, Gábor Szuromi wrote:
Hi!
The edge_index internal property map is not created by default, so you have to define it explicitly:
typedef adjacency_list<vecS, vecS, directedS, Foo*, property<edge_index_t, std::size_t> > MyGraph; typedef property_map<MyGraph, edge_index_t>::type MyEdgeIndexMap; ... // Retrieve the edge index map associated with the graph MyEdgeIndexMap emap = get(edge_index, g); ... // Convert the edge descriptor to an integer value cout << index[ get(emap, e, g) ] << endl;
Note that you need to fill in the edge indices; they are not created automatically for the graph type you have.
The vertex descriptor is an integer value so it works with operator[], but edge descriptor is an std::pair<>, so you have to convert it to an integer with the appropriate edge index map. This leaves only one question: how do you use bundled edge properties along with edge index map?
You don't need an edge index map for bundled edge properties. Your graph doesn't currently have (from what is listed above) bundled edge properties; if it did, you could do just g[e].whatever where "whatever" is a member of your bundled edge property class. -- Jeremiah Willcock
On Thu, 1 Apr 2010, Trevor Harmon wrote:
On Apr 1, 2010, at 6:40 AM, Jeremiah Willcock wrote:
Note that you need to fill in the edge indices; they are not created automatically for the graph type you have.
Which graph type would automatically create them? Thanks,
compressed_sparse_row_graph if you are willing to live with read-only access to the graph structure (properties are still read-write). Some of the generators like grid_graph have edge_index built in as well. The normal mutable graph types don't have them as far as I know, though. -- Jeremiah Willcock
On Apr 1, 2010, at 6:40 AM, Jeremiah Willcock wrote:
Note that you need to fill in the edge indices
Okay, so whenever I add an edge I need to assign it a unique index myself. Here's how I'm doing it for the initial construction of the graph: size_t edgeIndex = 0; for (...) { Vertex u = ... Vertex v = ... Edge edge; bool inserted; tie(edge, inserted) = add_edge(u, v, g); EdgeIndexMap edgeIndexMap = get(edge_index, g); put(edgeIndexMap, edge, edgeIndex++); } Does that look right? It seems to work, but I'm wondering if it's the best way. Trevor
On Thu, 1 Apr 2010, Trevor Harmon wrote:
On Apr 1, 2010, at 6:40 AM, Jeremiah Willcock wrote:
Note that you need to fill in the edge indices
Okay, so whenever I add an edge I need to assign it a unique index myself. Here's how I'm doing it for the initial construction of the graph:
size_t edgeIndex = 0; for (...) { Vertex u = ... Vertex v = ... Edge edge; bool inserted; tie(edge, inserted) = add_edge(u, v, g); EdgeIndexMap edgeIndexMap = get(edge_index, g); put(edgeIndexMap, edge, edgeIndex++); }
Does that look right? It seems to work, but I'm wondering if it's the best way.
That's fine, but you don't need to fetch edgeIndexMap every time -- you can get it outside the loop then use it repeatedly. You can also create the edges without filling in the edge indices then do a loop over edges(g) to fill them all in at once. -- Jeremiah Willcock
On Apr 1, 2010, at 5:31 AM, Gábor Szuromi wrote:
The edge_index internal property map is not created by default, so you have to define it explicitly:
Any particular reason why vertex indices are created (and updated) by default but edge indices are not? Perhaps it was just decided that the former is often needed while the latter not so often...
typedef adjacency_list<vecS, vecS, directedS, Foo*, property<edge_index_t, std::size_t> > MyGraph; typedef property_map<MyGraph, edge_index_t>::type MyEdgeIndexMap; ... // Retrieve the edge index map associated with the graph MyEdgeIndexMap emap = get(edge_index, g); ... // Convert the edge descriptor to an integer value cout << index[ get(emap, e, g) ] << endl;
Thanks for the tip. However, I think that last line is wrong. It should be: cout << index[ get(emap, e) ] << endl; Trevor
On Thu, 1 Apr 2010, Trevor Harmon wrote:
On Apr 1, 2010, at 5:31 AM, Gábor Szuromi wrote:
The edge_index internal property map is not created by default, so you have to define it explicitly:
Any particular reason why vertex indices are created (and updated) by default but edge indices are not? Perhaps it was just decided that the former is often needed while the latter not so often...
Vertex indices are an accident of using a vector as the vertex container -- see another email I posted today about that.
typedef adjacency_list<vecS, vecS, directedS, Foo*, property<edge_index_t, std::size_t> > MyGraph; typedef property_map<MyGraph, edge_index_t>::type MyEdgeIndexMap; ... // Retrieve the edge index map associated with the graph MyEdgeIndexMap emap = get(edge_index, g); ... // Convert the edge descriptor to an integer value cout << index[ get(emap, e, g) ] << endl;
Thanks for the tip. However, I think that last line is wrong. It should be:
cout << index[ get(emap, e) ] << endl;
Yes, you can do either get(emap, e) or get(edge_index, g, e). -- Jeremiah Willcock
On Apr 1, 2010, at 5:31 AM, Gábor Szuromi wrote:
The edge_index internal property map is not created by default, so you have to define it explicitly:
typedef adjacency_list<vecS, vecS, directedS, Foo*, property<edge_index_t, std::size_t> > MyGraph; typedef property_map<MyGraph, edge_index_t>::type MyEdgeIndexMap; ... // Retrieve the edge index map associated with the graph MyEdgeIndexMap emap = get(edge_index, g); ... // Convert the edge descriptor to an integer value cout << index[ get(emap, e, g) ] << endl;
A follow-up question, if I may... It seems like an awful lot of setup is required just to iterate through the edge indices. For example, here's what I'm doing now: typedef property_map<MyGraph, vertex_index_t>::type IndexMap; IndexMap index = get(vertex_index, g); typedef graph_traits<MyGraph>::edge_iterator edge_iter; std::pair<edge_iter, edge_iter> ep; EdgeIndexMap edgeIndexMap = get(edge_index, g); for (ep = edges(g); ep.first != ep.second; ++ep.first) { Edge edge = *ep.first; cout << index[get(edgeIndexMap, edge)] + " "; } Is there any way to simplify the above code? That's a lot of typing for such a basic task... Thanks, Trevor
On Fri, 2 Apr 2010, Trevor Harmon wrote:
On Apr 1, 2010, at 5:31 AM, Gábor Szuromi wrote:
The edge_index internal property map is not created by default, so you have to define it explicitly:
typedef adjacency_list<vecS, vecS, directedS, Foo*, property<edge_index_t, std::size_t> > MyGraph; typedef property_map<MyGraph, edge_index_t>::type MyEdgeIndexMap; ... // Retrieve the edge index map associated with the graph MyEdgeIndexMap emap = get(edge_index, g); ... // Convert the edge descriptor to an integer value cout << index[ get(emap, e, g) ] << endl;
A follow-up question, if I may... It seems like an awful lot of setup is required just to iterate through the edge indices. For example, here's what I'm doing now:
typedef property_map<MyGraph, vertex_index_t>::type IndexMap; IndexMap index = get(vertex_index, g); typedef graph_traits<MyGraph>::edge_iterator edge_iter; std::pair<edge_iter, edge_iter> ep; EdgeIndexMap edgeIndexMap = get(edge_index, g); for (ep = edges(g); ep.first != ep.second; ++ep.first) { Edge edge = *ep.first; cout << index[get(edgeIndexMap, edge)] + " "; }
Is there any way to simplify the above code? That's a lot of typing for such a basic task... Thanks,
#include <boost/graph/iteration_macros.hpp> EdgeIndexMap edgeIndexMap = get(edge_index, g); BGL_FORALL_EDGES(edge, g, MyGraph) { cout << index[get(edgeIndexMap, edge)] + " "; } or (I think) #include <boost/foreach.hpp> EdgeIndexMap edgeIndexMap = get(edge_index, g); BOOST_FOREACH (graph_traits<MyGraph>::edge_descriptor edge, edges(g)) { cout << index[get(edgeIndexMap, edge)] + " "; } -- Jeremiah Willcock
On Wed, 31 Mar 2010, Trevor Harmon wrote:
Hi,
In the Boost Graph library, vertices have an index (vertex_index_t), and I was under the impression that edges have one, too. At least, there's a predefined type called edge_index_t. However, I can't figure out how to access an edge's index. For example, consider a graph defined like:
typedef adjacency_list<vecS, vecS, directedS, Foo*> MyGraph; typedef graph_traits<MyGraph>::vertex_descriptor Vertex; typedef graph_traits<MyGraph>::edge_descriptor Edge;
And let's say I've got a vertex descriptor called "u". I can iterate over u's outgoing edges like this:
typedef graph_traits<MyGraph>::out_edge_iterator out_iter; std::pair<out_iter, out_iter> outp; for (outp = out_edges(u, g); outp.first != outp.second; ++outp.first) { Edge e = *outp.first; Vertex v = target(e, g); cout << index[v] << std::endl; // Works fine cout << index[e] << std::endl; // Compiler error }
In this example, index[v] works as expected, but index[e] gives me a compiler error: "no match for ‘operator[]’ in ‘index[e]".
What is index here? That doesn't appear to be declared.
Perhaps my graph typedef needs to be changed so that its edges have a property map for edge_index_t, although I'm not sure how to do that. (And anyway I wouldn't expect vertices to have indices by default but edges not...)
See Gabor's reply about creating the index map, but note that you need to fill it in. The reason vertices have indices automatically in your graph is that you used vecS as the vertex container and so vertices are just indexes into the vector. If you had used listS for your vertex container you wouldn't have a vertex_index_map either. If you have a read-only graph, compressed_sparse_row_graph provides edge indices automatically. I do not believe any of the read-write graph types have them built-in. -- Jeremiah Willcock
participants (3)
-
Gábor Szuromi -
Jeremiah Willcock -
Trevor Harmon