найти кратные ребра по 2 вершинам в графе BOOST

Я использую библиотеку 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, и между ними есть ребро (node1, node2). Свойство 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;

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

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


c++ boost graph boost-graph
person Pogo    schedule 19.01.2014    source источник

Ответы (1)


arrow_upward
7
arrow_downward

Есть несколько способов сделать это.

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, как страница документации гласит:

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

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

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

person Mikael Persson    schedule 19.01.2014
comment
привет, Микаэль, я только что опубликовал ответ ниже, где я немного застрял. не могли бы вы предложить? - person Pogo; 19.01.2014