Boost Graph Library: error potencial

Question

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.

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.

Answer 1

Has archivado un error, pero no hiciste el seguimiento allí.

Poco tiempo después, se obtuvo una respuesta:

No está inicializando la propiedad vertex_index de su gráfico. Intente agregar algún código como:

graph_traits :: vertices_size_type i = 0;

BGL_FORALL_VERTICES (v, gráfico, gráfico) put (vertex_index, g, v, i ++);

yo probamos este (que fija el error tipográfico) y funciona bien:

#include <boost/graph/iteration_macros.hpp> 

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

    graph_traits<Graph>::vertices_size_type i = 0; 
    BGL_FORALL_VERTICES(v, g, Graph) put(vertex_index, g, v, i++); 

    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; 
    } 

(al menos, ya que imprime "Trasero" no

)