3

無向グラフのサイクルの一部であるすべてのエッジを見つけようとしています。Boost のdepth_first_searchとバック エッジback_edgeに関する私の理解を使用すると、サイクルを含まないサンプル グラフの両方のエッジに対してメソッドが呼び出される理由がわかりません。

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

1 に答える 1

2

グラフは無向であるため、ツリー エッジはバック エッジでもあります。DFSVisitorのドキュメントでは、これについて言及されていません。

無向グラフの場合、エッジ (u,v) と (v,u) は同じエッジであるため、ツリー エッジとバック エッジの間に多少のあいまいさがありますが、 関数tree_edge()とback_edge()関数の両方が呼び出されます。

このあいまいさを解決する 1 つの方法は、ツリー エッジを記録し、ツリー エッジとして既にマークされているバック エッジを無視することです。ツリー エッジを記録する簡単な方法は、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));
}
于 2013-10-15T21:32:54.337 に答える