[Boost-users] [Graph] Guarantee on bidirectional graphs

Subject: [Boost-users] [Graph] Guarantee on bidirectional graphs
From: Sensei (senseiwa_at_[hidden])
Date: 2014-03-12 12:06:36

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