c++ boost::graph get parent vertices from directed graph

boost, boost-graph, c++, directed-acyclic-graphs, graph

Solution

`reverse_graph` requires that the adapted graph be a model of `BidirectionalGraph`. If you change your graph to `typedef boost::adjacency_list< boost::setS, boost::vecS, boost::bidirectionalS > Graph;` your program compiles and gives the result:

3
4

############# RGRAPH #############

1

that I believe is what you should expect.

Another way that does not require the `reverse_graph` (but still requires `bidirectionalS`) is to use:

Graph::out_edge_iterator out_begin, out_end;
for (boost::tie(out_begin, out_end) = out_edges(v2,graph); out_begin != out_end; ++out_begin)
{   
    std::cout << target(*out_begin,graph) << std::endl;
}
std::cout << std::endl;

Graph::in_edge_iterator in_begin, in_end;
for (boost::tie(in_begin, in_end) = in_edges(v2,graph); in_begin != in_end; ++in_begin)
{   
    std::cout << source(*in_begin,graph) << std::endl;
}
std::cout << std::endl;

Problem

I have a directed graph (implemented via an adjacency_graph from the boost::graph library) and I'm trying to find the parent vertices of a certain vertex. In the past (via pygraph) I have simply reversed the digraph, then done a neighbours search, but it appears that reversing the graph with boost::reverse_graph turns my digraph into a bidirectional graph, and therefore I can't use the adjacent_vertices method anymore. Is there a better way to get the parent vertices? Thanks. Here's my current example code: ``` #include <boost/graph/adjacency_list.hpp> #include <boost/graph/reverse_graph.hpp> #include <iostream> typedef boost::adjacency_list< boost::setS, boost::vecS, boost::directedS > Graph; typedef boost::reverse_graph<Graph> Rgraph; typedef Graph::vertex_descriptor Vertex; int main() { Graph graph; Vertex v0 = boost::add_vertex(graph); Vertex v1 = boost::add_vertex(graph); Vertex v2 = boost::add_vertex(graph); Vertex v3 = boost::add_vertex(graph); Vertex v4 = boost::add_vertex(graph); Vertex v5 = boost::add_vertex(graph); Vertex v6 = boost::add_vertex(graph); boost::add_edge(v0,v1,graph); boost::add_edge(v1,v2,graph); boost::add_edge(v2,v3,graph); boost::add_edge(v2,v4,graph); boost::add_edge(v3,v5,graph); boost::add_edge(v4,v5,graph); boost::add_edge(v5,v6,graph); Graph::adjacency_iterator ibegin, iend; for (boost::tie(ibegin, iend) = boost::adjacent_vertices(v2, graph); ibegin != iend; ++ibegin) { std::cout << *ibegin << std::endl; } std::cout << std::endl << "############# RGRAPH #############" << std::endl << std::endl; Rgraph rgraph(graph); Rgraph::adjacency_iterator rbegin, rend; for (boost::tie(rbegin, rend) = boost::adjacent_vertices(v2, rgraph); rbegin != rend; ++rbegin) { std::cout << *rbegin << std::endl; } std::cout << std::endl; return 0; } ```

Original source