Как получить входные ребра заданной вершины на ориентированном графе?

Question

У меня есть ориентированный граф, и я хочу получить родительский элемент данной вершины.

Скажем, у меня есть график 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?

Answer 1

Без использования двунаправленного графика вам нужно будет выполнить поиск грубой силы всех узлов, ища тот, у которого есть вершина 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; 
} 

Может быть, стоит создать временное дерево с перевернутыми краями как «копия» вашего графа, чтобы упростить поиск родителей. Что-то вроде invtree в конце отправленного кода.