如何获得有向图上给定顶点的输入边?
How can I get input edges of a given vertex on a directed graph?
我有一个有向图,我想获取给定顶点的父节点。
假设我有图 1 -> 2 -> 3
,我持有顶点 2
,我想获得顶点 1
。
我的顶点和图形定义:
struct TreeVertex { int id = -1; };
typedef boost::adjacency_list<
boost::vecS,
boost::vecS,
boost::directedS,
TreeVertex
> tree_t;
显示我想要实现的目标的 MVCE(参见 online here):
int main() {
tree_t tree;
auto v1 = boost::add_vertex( tree );
auto v2 = boost::add_vertex( tree );
auto v3 = boost::add_vertex( tree );
boost::add_edge( v1, v2, tree );
boost::add_edge( v2, v3, tree );
// attempt to get the input edge of v2
auto pair_it_edge = boost::in_edges( v2, tree ); // FAILS TO BUILD
auto v = boost::source( *pair_it_edge.first ); // should be v1
}
Another answer 建议将图形转换为 BidirectionalGraph
但我需要保持它的方向性。
问题:这可能吗?如何获取 v2
的传入边,以便提取 v1
?
如果不使用双向图,您将不得不对所有节点进行强力搜索,寻找以顶点 2 作为其子节点的节点。
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
using namespace std;
using namespace boost;
struct TreeVertex { int id = -1; };
typedef boost::adjacency_list<
boost::vecS,
boost::vecS,
boost::directedS,
TreeVertex
> tree_t;
tree_t tree;
int main() {
auto v1 = boost::add_vertex( tree );
auto v2 = boost::add_vertex( tree );
auto v3 = boost::add_vertex( tree );
boost::add_edge( v1, v2, tree );
boost::add_edge( v2, v3, tree );
int looking_for = 2;
typename graph_traits < tree_t >::out_edge_iterator ei, ei_end;
for( int v = 0; v < num_edges( tree ); v++ )
for (boost::tie(ei, ei_end) = out_edges(v, tree); ei != ei_end; ++ei) {
auto source = boost::source ( *ei, tree );
auto target = boost::target ( *ei, tree );
if( target == looking_for )
std::cout << "There is an edge from " << source << " to " << target << std::endl;
// create an inverted edge tree to search for parents
tree_t invtree;
boost::add_edge( v2, v1, invtree );
boost::add_edge( v1, v3, invtree );
typename graph_traits < tree_t >::adjacency_iterator it, it_end;
for (tie(it, it_end) = adjacent_vertices(v2, invtree ); it != it_end; ++it)
{
std::cout << "There is an inv edge from " << v2
<< " to " << *it << std::endl;
}
return 0;
}
可能值得创建一个具有倒边的临时树作为图的 'copy' 以简化对父节点的搜索。在发布的代码末尾有类似 invtree 的东西。
我有一个有向图,我想获取给定顶点的父节点。
假设我有图 1 -> 2 -> 3
,我持有顶点 2
,我想获得顶点 1
。
我的顶点和图形定义:
struct TreeVertex { int id = -1; };
typedef boost::adjacency_list<
boost::vecS,
boost::vecS,
boost::directedS,
TreeVertex
> tree_t;
显示我想要实现的目标的 MVCE(参见 online here):
int main() {
tree_t tree;
auto v1 = boost::add_vertex( tree );
auto v2 = boost::add_vertex( tree );
auto v3 = boost::add_vertex( tree );
boost::add_edge( v1, v2, tree );
boost::add_edge( v2, v3, tree );
// attempt to get the input edge of v2
auto pair_it_edge = boost::in_edges( v2, tree ); // FAILS TO BUILD
auto v = boost::source( *pair_it_edge.first ); // should be v1
}
Another answer 建议将图形转换为 BidirectionalGraph
但我需要保持它的方向性。
问题:这可能吗?如何获取 v2
的传入边,以便提取 v1
?
如果不使用双向图,您将不得不对所有节点进行强力搜索,寻找以顶点 2 作为其子节点的节点。
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
using namespace std;
using namespace boost;
struct TreeVertex { int id = -1; };
typedef boost::adjacency_list<
boost::vecS,
boost::vecS,
boost::directedS,
TreeVertex
> tree_t;
tree_t tree;
int main() {
auto v1 = boost::add_vertex( tree );
auto v2 = boost::add_vertex( tree );
auto v3 = boost::add_vertex( tree );
boost::add_edge( v1, v2, tree );
boost::add_edge( v2, v3, tree );
int looking_for = 2;
typename graph_traits < tree_t >::out_edge_iterator ei, ei_end;
for( int v = 0; v < num_edges( tree ); v++ )
for (boost::tie(ei, ei_end) = out_edges(v, tree); ei != ei_end; ++ei) {
auto source = boost::source ( *ei, tree );
auto target = boost::target ( *ei, tree );
if( target == looking_for )
std::cout << "There is an edge from " << source << " to " << target << std::endl;
// create an inverted edge tree to search for parents
tree_t invtree;
boost::add_edge( v2, v1, invtree );
boost::add_edge( v1, v3, invtree );
typename graph_traits < tree_t >::adjacency_iterator it, it_end;
for (tie(it, it_end) = adjacent_vertices(v2, invtree ); it != it_end; ++it)
{
std::cout << "There is an inv edge from " << v2
<< " to " << *it << std::endl;
}
return 0;
}
可能值得创建一个具有倒边的临时树作为图的 'copy' 以简化对父节点的搜索。在发布的代码末尾有类似 invtree 的东西。