Boost DFS back_edge

Question

Я пытаюсь найти все ребра, которые являются частью любого цикла в неориентированном Графе. Используя Boost's depth_first_search и мое понимание back edges, я не понимаю, почему метод back_edge вызывается для обоих ребер в образце Graph, который не содержит циклов.

#include <boost/config.hpp> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/depth_first_search.hpp> 

using namespace std; 
using namespace boost; 

typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> > Graph; 
typedef graph_traits<Graph>::edge_descriptor Edge; 

class MyVisitor : public default_dfs_visitor { 
    public: void back_edge(Edge e, const Graph& g) const { 
     // should only be called when cycle found, right? 
     cerr << "back_edge " << e << endl; 
     return; 
    } 
}; 

int main() { 
    Graph g; 
    add_edge(0, 1, g); 
    add_edge(0, 2, g); 

    MyVisitor vis; 
    depth_first_search(g, visitor(vis)); 
    return 0; 
} 

Answer 1

Поскольку ваш график неориентирован, любой край дерева также является задним краем. documentation for DFSVisitor не может не упомянуть об этом.

Для неориентированного графа существует некоторая неоднозначность между краями деревьев и задней кромок, так как край (U, V) и (V, U) такие же края, но оба tree_edge() и back_edge() функции будут вызываться.

Один из способов устранения этой двусмысленности - записать ребра дерева, а затем игнорировать обратные края, которые уже отмечены как ребра дерева. Простым способом записи ребер дерева является запись предшественников в точке события tree_edge.

Реализация этого наиболее простым способом: Live on Coliru

#include <boost/config.hpp> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/depth_first_search.hpp> 

namespace { 
    using namespace boost; 

    typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> > Graph; 
    typedef graph_traits<Graph>::edge_descriptor Edge; 
    typedef std::set<Edge> EdgeSet; 
} 

struct MyVisitor : default_dfs_visitor { 
    MyVisitor(EdgeSet& tree_edges) : tree_edges(tree_edges) {} 

    void tree_edge(Edge e, const Graph& g) const { 
     std::cerr << "tree_edge " << e << std::endl; 
     tree_edges.insert(e); 
    } 
    void back_edge(Edge e, const Graph& g) const { 
     if (tree_edges.find(e) == tree_edges.end()) 
      std::cerr << "back_edge " << e << std::endl; 
    } 

    private: 
    EdgeSet& tree_edges; 
}; 

int main() { 
    Graph g; 
    add_edge(0, 1, g); 
    add_edge(0, 2, g); 

    std::set<Edge> tree_edges; 
    MyVisitor vis(tree_edges); 

    depth_first_search(g, visitor(vis)); 
}