Применять алгоритмы с учетом определенного подмножества ребер - PullRequest
Новая
       4

Применять алгоритмы с учетом определенного подмножества ребер

4 голосов
/ 22 апреля 2010

У меня есть огромный граф с напечатанным ребром (то есть ребро со свойством типа).Скажите 

typedef adjacency_list<vecS, vecS, vertex_prop, edge_prop> Graph;

«Тип» ребра является членом edge_prop и имеет значение в {A, B, C, D},
Я бы хотел запустить поиск в ширинуалгоритм, учитывающий только ребра типа A или B.
Как бы вы это сделали?

Ответы [ 3 ]

9 голосов
/ 28 июля 2011

Поскольку трудно найти простой пример, смешивающий различные темы BGL, я публикую ниже полный и рабочий пример с использованием Filter_graph и связанных свойств .:

#include <iostream>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>

using namespace boost;

enum edge_type_e {
  A, B, C, D
};

class edge_property_c {
public:
  edge_property_c(void) : type_m(A) {}
  edge_property_c(edge_type_e type) : type_m(type) {}
  edge_type_e type_m;
};

typedef adjacency_list<vecS, vecS, undirectedS, no_property, edge_property_c> graph_t;
typedef graph_t::edge_descriptor edge_id_t;

class edge_predicate_c {
public:
  edge_predicate_c() : graph_m(0) {}
  edge_predicate_c(graph_t& graph) : graph_m(&graph) {}
  bool operator()(const edge_id_t& edge_id) const {
    edge_type_e type = (*graph_m)[edge_id].type_m;
    return (type == A || type == B);
  }
private:
  graph_t* graph_m;
};

int main() {
  enum { a, b, c, d, e, n };
  const char* name = "abcde";
  graph_t g(n);
  add_edge(a, b, edge_property_c(A), g);
  add_edge(a, c, edge_property_c(C), g);
  add_edge(c, d, edge_property_c(A), g);
  add_edge(c, e, edge_property_c(B), g);
  add_edge(d, b, edge_property_c(D), g);
  add_edge(e, c, edge_property_c(B), g);

  filtered_graph<graph_t, edge_predicate_c> fg(g, edge_predicate_c(g));

  std::cout << "edge set: ";
  print_edges(g, name);
  std::cout << "filtered edge set: ";
  print_edges(fg, name);

  return 0;
}
3 голосов
/ 23 апреля 2010

Наконец, я думаю, что Boost :: Graph способ сделать это состоит в использовании boost: Filter_graph и демо для использования

"Шаблон класса Filter_graph - это адаптер, который создает фильтрованное представление графика. Объекты функции предиката определяют, какие ребра и вершины исходного графика будут отображаться на фильтрованном графике."

Таким образом, вы можете предоставить ребро (или вершину) фильтрующий функтор на основе property_map. В моем случае я использую внутренние связанные свойства. См. Карты свойств из связанных свойств .

0 голосов
/ 22 апреля 2010

Я довольно незнаком с boost :: graph, но я предполагаю, что BFSVisitor - это то, что вы ищете.Это позволяет вам изменить поведение алгоритма, и ваш конкретный случай будет состоять в том, чтобы изменить проверку исходящих ребер после обнаружения вершин и игнорировать те, которые не имеют требуемого «типа» (фактически {A, B, C, D} это значения, насколько я понимаю, а не типы в строгом смысле).

...