найти несколько ребер, заданных 2 вершинами в графе BOOST

Question

Я использую библиотеку Boost Graph для некоторого проекта, и я хочу найти количество раз, когда ребро повторяется на графике. например,

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Node_Info, Edge_Info > Graph_t; 
//node_info and Edge_info are external node and edge properties (structures) 

Предположим, если у меня есть два узла, node1 и node2 и существует ребро между ними (узел1, узел2). свойство edge для каждого ребра содержит начало временной метки, конец ... и может быть много таких ребер на графике с разными временными метками. например.

edge1 = (node1, node2) with start = 100, end = 200. 
edge2 = (node1, node2) with start = 250, end = 400. 

Я знаю, что в повышающем графе, учитывая две вершины, мы можем найти, существует ли ребро в графе или нет, используя следующее.

std::pair < edge_t, bool > p = boost::edge(node1, node2, myGraph); 
if(p.second == 1) cout << "edge exists!" << endl; 
else cout << " does not exist " << endl; 

Но это может означать, что он будет возвращать только какой-либо один край, даже если несколько ребер существуют с различными краевыми свойствами -> ПРОБЛЕМЫ

кто может предложить идею, как получить такие кратные ребра между двумя данными узлы? Благодаря!

Answer 1

Существует несколько способов сделать это.

1) Просто проверьте затраченных края для всех, которые идут к цели:

boost::graph_traits<Graph_t>::out_edge_iterator ei, ei_end; 
boost::tie(ei, ei_end) = out_edges(node1, myGraph); 
int parallel_count = 0; 
for(; ei != ei_end; ++ei) { 
    if(target(*ei, myGraph) == node2) { 
    cout << "Found edge (node1, node2) with property: " << myGraph[*ei] << endl; 
    ++parallel_count; 
    }; 
}; 
cout << "There are a total of " << parallel_count << " parallel edges." << endl; 

2) Укажите boost::multisetS в качестве OutEdgeListS аргумента шаблона в adjacency_list, это позволит дополнительную функцию, называемую edge_range, которая возвращает диапазон итераторов для всех «параллельно» края выходит из u и вдаваясь в v, как documentation page состояний:

std::pair<out_edge_iterator, out_edge_iterator> 
edge_range(vertex_descriptor u, vertex_descriptor v, 
      const adjacency_list& g) 

Возвращает пару итераторов с внешним краем, которые дают диапазон для всех параллельных ребер от u до v. Эта функция работает только тогда, когда OutEdgeList для adjacency_list представляет собой контейнер, который сортирует внешние края в соответствии с целевой вершиной и позволяет для параллельных ребер. Селектор multisetS выбирает такой контейнер.

Причина, почему эта функция доступна только для multisetS потому, что для того, чтобы обеспечить (легко) ряд итераторы в параллельные края, вам нужно края должны быть сгруппированы вместе, что в случае multisetS, потому что они сортируются по дескриптору вершин, и поэтому все параллельные внешние ребра сгруппированы. Это единственный выбор контейнера, который даст вам это, в противном случае вы должны использовать опцию (1) (примечание: создание filter_iterator (см. docs) может пригодиться, если вы действительно используете это много).