C ++ Boost :: Graph получить родительские вершины из ориентированного графа

У меня есть ориентированный граф (реализованный с помощью adjacency_graph из библиотеки boost :: graph), и я пытаюсь найти родительские вершины определенной вершины.

В прошлом (с помощью pygraph) я просто переворачивал орграф, затем выполнял поиск соседей, но кажется, что при перестановке графа с помощью boost :: reverse_graph мой орграф превращается в двунаправленный граф, и поэтому я не могу использовать методопатический соседний_вертик. больше.

Есть ли лучший способ получить родительские вершины?

Благодарю.

Вот мой текущий пример кода:

#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;
}

2

Решение

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;
7

Другие решения

Других решений пока нет …