c ++ boost :: graph从有向图获取父顶点 [英] c++ boost::graph get parent vertices from directed graph
问题描述
我有一个有向图(通过boost :: graph库中的adjacency_graph实现),我试图找到某个顶点的父顶点。
在过去(通过pygraph)我简单地颠倒了有向图,然后做邻居搜索,但似乎反向图与boost :: reverse_graph将我的图变成一个双向图,因此我不能使用adjacent_vertices方法。
有更好的方法来获得父顶点吗?
感谢。
以下是我目前的范例程式码:
#include< 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
$ c $
另一种不需要的方式是, 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;
图:: 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屋!