c ++ boost :: graph从有向图获取父顶点 [英] c++ boost::graph get parent vertices from directed graph

问题描述

我有一个有向图（通过boost :: graph库中的adjacency_graph实现），我试图找到某个顶点的父顶点。

在过去（通过pygraph）我简单地颠倒了有向图，然后做邻居搜索，但似乎反向图与boost :: reverse_graph将我的图变成一个双向图，因此我不能使用adjacent_vertices方法。

有更好的方法来获得父顶点吗？

感谢。

这是我目前的范例程式码：

  #include& lt; boost / graph / adjacency_list.hpp> 
 #include< boost / graph / reverse_graph.hpp> 
 #include< iostream> 
 
 typedef boost :: adjacency_list< boost :: setS，boost :: vecS，boost :: directedS>图形; 
 typedef boost :: reverse_graph< Graph> Rgraph; 
 typedef Graph :: vertex_descriptor Vertex; 
 
 int main（）
 {
图形图; 
 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; 
} 
  

解决方案

reverse_graph 要求自适应图是 BidirectionalGraph 。如果你改变你的图表到 typedef boost :: adjacency_list< boost :: setS，boost :: vecS，boost :: bidirectionalS> Graph; 您的程序编译并给出结果：

  3 
 4 
 
 ############# RGRAPH ############ 
 
 1 
  
 
 
另一种不需要的方式是，  reverse_graph （但仍需要 bidirectionalS ）是使用：
  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; 
  
 
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;
}

解决方案
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;


                        
这篇关于c ++ boost :: graph从有向图获取父顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！