Библиотека графов ускорения: потенциальная ошибка

алгоритм BGL depth_first_search иногда вызывает back_edge () для посетителей, даже если на графике нет циклов. По определению заднего края и согласно документации для посетителей DFS Boost , этого не должно происходить. Обратите внимание, что это воспроизводимо только тогда, когда listS используется как представление как для вершин, так и для ребер.

Пример кода ниже (должен компилироваться как есть) строит граф с двумя узлами и одним ребром. Он неправильно печатает "задний край". Я здесь что-то не так делаю? Или это ошибка?

#include 
using namespace std;

#include 
#include 
#include 
using namespace boost;

typedef boost::property VertexProperties;
typedef boost::adjacency_list Graph;  // Graph object type

typedef boost::graph_traits::vertex_descriptor Vertex;
typedef boost::graph_traits::edge_descriptor Edge;

class VisitorClass : public dfs_visitor<> {
 public:
  VisitorClass() {}

  template 
  void back_edge(Edge, const Graph&) const {
    cout << "back edge" << endl;
  }
};

int
main() {
  Graph g;
  Vertex v = add_vertex(g);
  Vertex u = add_vertex(g);

  bool inserted;
  tie(tuples::ignore, inserted) = add_edge(v, u, g);
  assert(inserted);

  VisitorClass vst;
  depth_first_search(g, visitor(vst));
  // Should not print "back edge", but does.

  return 0;
}

Протестировано с Boost 1.46.1 с использованием i686-apple-darwin11-llvm-g ++ - 4.2 в Mac OS 10.7;
Протестировано с Boost 1.42.0 с использованием gcc 4.4.5 в Debian 2.6.32-34squeeze1.

7
задан ali01 13 August 2011 в 16:43
поделиться