El algoritmo depth_first_search de BGL a veces llama a back_edge() en los visitantes incluso si no hay ciclos en el gráfico. Por definición de borde posterior, y según Boost DFS Visitor Documentation, esto no debería suceder. Tenga en cuenta que esto solo se puede reproducir cuando listS se utiliza como la representación de vértices y bordes.Boost Graph Library: error potencial
El siguiente ejemplo de código (debe compilar como está) construye un gráfico con dos nodos y un solo borde. Imprime incorrectamente "borde posterior". ¿Estoy haciendo algo mal aquí? ¿O es esto un error?
#include <iostream>
using namespace std;
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/visitors.hpp>
using namespace boost;
typedef boost::property<boost::vertex_index_t,std::size_t> VertexProperties;
typedef boost::adjacency_list<boost::listS,
boost::listS,
boost::bidirectionalS,
VertexProperties> Graph; // Graph object type
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef boost::graph_traits<Graph>::edge_descriptor Edge;
class VisitorClass : public dfs_visitor<> {
public:
VisitorClass() {}
template <typename Edge, typename Graph>
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;
}
probado con Boost 1.46.1 usando i686-manzana-darwin11-llvm-g ++ - 4.2 en Mac OS 10.7;
Probado con Boost 1.42.0 usando gcc 4.4.5 en Debian 2.6.32-34squeeze1.
no debe solicitar esta en la lista de correo de impulso? – Graviton
Envié un informe de error. Pensé que podría preguntar aquí también en caso de que haya algo obviamente mal con la forma en que estoy configurando el gráfico. También enviaré un correo electrónico a la lista de correo de usuarios de boost. – ali01
Informe de error: https://svn.boost.org/trac/boost/ticket/5779 – ali01