Dear all, I am implementing my custom algorithm for path discovery (as in a recent post), and I'd like to know one simple thing. My graph is a bidirectional sparse compressed row graph, and I need to represent a *directed* graph with that (I need in and out edges). So, is the order of nodes in an edge guaranteed to generate the correct in/out adjacent nodes? I do not care about ordering of nodes, just distinguishing nodes that belong to in and out edges. For instance, given a directed graph that has node 4 with two out edges to 5 and 6, and 4 in edges from 1, 2, and 3, am I guaranteed that, even if the graph is bidirectional, the in and out edges will be unaffected and won't be swapped? Moreover, when I dump the indices of out edges, the results seem to be right, but when I dump the in edges, results are erroneous. I must be doing something really wrong... And one more thing: I have tried my code with just using the stream output as in http://programmingexamples.net/wiki/CPP/Boost/BGL/DirectedGraph, just using std::cout << neighbors_out.first << std::endl; clang complains: main.cpp:165:19: error: invalid operands to binary expression ('ostream' (aka 'basic_ostream<char>') and 'boost::detail::csr_out_edge_iterator<boost::compressed_sparse_row_graph<boost::bidirectionalS, boost::no_property, boost::no_property, boost::no_property, unsigned long, unsigned long> >') std::cout << neighbors_out.first << std::endl; ~~~~~~~~~ ^ ~~~~~~~~~~~~~~~~~~~ while if I use the following, it compiles just fine (but as I said, the output is wrong): std::cout << neighbors_out.first->idx << std::endl; See the snippet for an example. Thanks & Cheers! typedef boost::compressed_sparse_row_graph<boost::bidirectionalS> boost_graph; typedef boost::graph_traits<boost_graph>::vertex_iterator vertex_iterator; typedef boost::graph_traits<boost_graph>::adjacency_iterator adjacency_iterator; typedef boost::graph_traits<boost_graph>::out_edge_iterator outward_iterator; typedef boost::graph_traits<boost_graph>::in_edge_iterator inward_iterator; // ... std::vector<std::pair<std::size_t, std::size_t>> results; results.push_back(std::make_pair( 0, 1)); results.push_back(std::make_pair( 0, 3)); results.push_back(std::make_pair( 1, 4)); results.push_back(std::make_pair( 2, 4)); results.push_back(std::make_pair( 3, 4)); results.push_back(std::make_pair( 4, 5)); results.push_back(std::make_pair( 4, 6)); results.push_back(std::make_pair( 5, 7)); results.push_back(std::make_pair( 7, 8)); results.push_back(std::make_pair( 8, 9)); results.push_back(std::make_pair( 8, 11)); results.push_back(std::make_pair( 8, 12)); results.push_back(std::make_pair( 9, 10)); results.push_back(std::make_pair(12, 10)); // Create the graph boost_graph graph(boost::edges_are_unsorted_multi_pass, results.begin(), results.end(), 13); std::cout << "Outward adjacents" << std::endl; std::pair<outward_iterator, outward_iterator> neighbors_out; neighbors_out = boost::out_edges(boost::vertex(4, graph), graph); for(; neighbors_out.first != neighbors_out.second; ++neighbors_out.first) { std::cout << neighbors_out.first->idx << std::endl; } std::cout << "Inward adjacents" << std::endl; std::pair<inward_iterator, inward_iterator> neighbors_in; neighbors_in = boost::in_edges(boost::vertex(4, graph), graph); for(; neighbors_in.first != neighbors_in.second; ++neighbors_in.first) { std::cout << neighbors_in.first->idx << std::endl; } == OUTPUT == Outward adjacents 5 6 Inward adjacents 2 3 4
From: >Sensei ... So, is the order of nodes in an edge guaranteed to generate the correct in/out adjacent nodes? I do not care about ordering of nodes, just distinguishing nodes that belong to in and out edges.
For instance, ... std::cout << neighbors_out.first->idx << std::endl; ... std::cout << neighbors_in.first->idx << std::endl;
I am not familiar with the idx member for edge descriptors. But, since you are interested in the target/source of the edge, would it be better to write the following? std::cout << boost::target(*neighbors_out.first, graph) << std::endl; std::cout << boost::source(*neighbors_in.first, graph) << std::endl; Best wishes, Alex
On 3/12/14, 6:33pm, alex wrote:
From: >Sensei ... So, is the order of nodes in an edge guaranteed to generate the correct in/out adjacent nodes? I do not care about ordering of nodes, just distinguishing nodes that belong to in and out edges.
For instance, ... std::cout << neighbors_out.first->idx << std::endl; ... std::cout << neighbors_in.first->idx << std::endl;
I am not familiar with the idx member for edge descriptors. But, since you are interested in the target/source of the edge, would it be better to write the following?
std::cout << boost::target(*neighbors_out.first, graph) << std::endl; std::cout << boost::source(*neighbors_in.first, graph) << std::endl;
Best wishes, Alex
Thanks Alex, that solved the indexing properties! Do you know if in and out edges are preserved even if the graph is declared as bidirectional? I just need this guarantee, that for instance, a graph 1 -> 2 2 -> 3 2 -> 4 will always produce as out edges nodes of 2, the nodes 3 and 4, and as in edge nodes, just 1. AFAIR, in a bidirectional graph there is no distinction between in and out edges, so I am worried BGL could rearrange them for some internal representation reason. By the way, is there the analog index function for edges as far as you know? This code works (the ei->idx), but I fear I'm on the edge of a disaster like I was with the nodes :) std::cout << "Dumping graph" << std::endl; for (boost::tie(ei, ee) = boost::edges(graph); ei != ee; ei++) { std::cout << ei->idx << " : " << boost::source(*ei, graph) << "-" << boost::target(*ei, graph) << std::endl; } Thanks & Cheers!
From: >Sensei in a bidirectional graph there is no distinction between in and out edges, so I am worried BGL could rearrange them for some internal representation reason.
Well, the documentation promises not to do that. And many applications would fail if BGL didn't live up to that promise. http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/BidirectionalGraph.html " For both directed and undirected graphs, the target of an out-edge is required to be vertex v and the source is required to be a vertex that is adjacent to v. " http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/IncidenceGraph.html#1 " For undirected graphs, the edge (u,v) is the same as edge (v,u), so without some extra guarantee an implementation would be free use any ordering for the pair of vertices in an out-edge. For example, if you call out_edges(u, g), and v is one of the vertices adjacent to u, then the implementation would be free to return (v,u) as an out-edge which would be non-intuitive and cause trouble for algorithms. Therefore, the extra requirement is added that the out-edge connecting u and v must be given as (u,v) and not (v,u)."
By the way, is there the analog index function for edges as far as you know? This code works (the ei->idx), but I fear I'm on the edge of a disaster like I was with the nodes :)
Yes it looks like disaster, at least it doesn't seem to be a generic solution. I think the generic approach would be to use an (external or internal) edge index map. So you could do auto index = get(my_index_map, *ei); http://lists.boost.org/boost-users/2010/04/57922.php
On 13/03/14 19:44, alex wrote:
Yes it looks like disaster, at least it doesn't seem to be a generic solution. I think the generic approach would be to use an (external or internal) edge index map. So you could do auto index = get(my_index_map, *ei);
Thanks for your clarification and help, I've now switched to boost::get(boost::edge_index, graph, *edgeiterator). Thank you!
participants (1)
-
alex -
Sensei