如何使用Boost Graph Library在有向图中标记后缘以进行循环检测

Question

我可以自己写DFS，但是我使用的代码库一直在使用Boost Graph Library，所以如果我能稍微修改一下就可以了。

这是 https://www.boost.org/doc/libs/1_56_0/libs/graph/doc/file_dependency_example.html#sec:cycles 用于循环检测的代码片段

 struct cycle_detector : public dfs_visitor<>
  {
    cycle_detector( bool& has_cycle) 
      : _has_cycle(has_cycle) { }

    template <class Edge, class Graph>
    void back_edge(Edge, Graph&) {
      _has_cycle = true;
    }
  protected:
    bool& _has_cycle;
  };

我们现在可以调用 BGL depth_first_search() 算法并传入循环检测器访问者。

  bool has_cycle = false;
  cycle_detector vis(has_cycle);
  boost::depth_first_search(g, visitor(vis));
  std::cout << "The graph has a cycle? " << has_cycle << std::endl;

这是我为 back_edge 标记节点的修改：

struct cycle_detector : public dfs_visitor<>
  {
    cycle_detector( bool& has_cycle) 
      : _has_cycle(has_cycle) { }

    template <class Edge, class Graph>
    void back_edge(Edge e, Graph& g) {
       cycleFrom = index[source(e,g)];
       cycleTo = index[target(e,g)];
      _has_cycle = true;
    }
    int& cycleFrom, cycleTo
  protected:
    bool& _has_cycle;
  };

我们现在可以调用 BGL depth_first_search() 算法并传入循环检测器访问者。

  bool has_cycle = false;
  cycle_detector vis(has_cycle);
  boost::depth_first_search(g, visitor(vis));

  if(has_cycle)  std::cout << "The graph has a cycle from " << vis.cycleFrom << " to " << vis.cycleTo << std::endl;

但它标记了这一行（以及带有目标的那一行）：cycleFrom = index[source(e,g)]，突出显示索引并显示 error: overloaded function with no contextual information。我浏览了文档和各种代码片段，但无法弄清楚我应该修改什么以及我应该如何访问检测到循环的back_edge的源和目标顶点的索引

Answer 1

您有一些语法错误，例如在 cycleTo 之后缺少 ;：

  int& cycleFrom, cycleTo
protected:

现在，请注意 int& a, b; 而不是 声明两个引用。它声明 int &a; int b;。这不是你想要的。

接下来，cycleFrom 和 cycleTo 未声明。您是指 cyclefrom 和 cycleto 吗？

接下来，index 未声明。

最后，引用成员需要在构造函数中初始化。

这些是句法问题。即使你解决了它们，当有多个 back-edge 时，也会出现你没有预料到的问题。您只会重复覆盖结果变量。对于 bool _has_cycle 这不是什么大问题（毕竟，它只会变得更真实......）。但是使用 from/to 信息，您可能会丢失信息，或者得到意想不到的答案。

简单修复

只是删除列出的错误：Live On Compiler Explorer

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

using G = boost::adjacency_list<>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;

struct cycle_detector : boost::dfs_visitor<> {
    cycle_detector(bool& has_cycle, V& cyclefrom, V& cycleto)
        : _has_cycle(has_cycle)
        , cyclefrom(cyclefrom)
        , cycleto(cycleto) {}

    void back_edge(E e, G const& g) {
        cyclefrom  = source(e, g);
        cycleto    = target(e, g);
        _has_cycle = true;
    }

    bool& _has_cycle;
    V&    cyclefrom;
    V&    cycleto;
};

int main() {
    boost::adjacency_list<> g;
    add_edge(1, 2, g);
    add_edge(2, 3, g);
    add_edge(4, 5, g);
    add_edge(5, 2, g);

    bool has_cycle = false;
    V    from, to;

    cycle_detector vis(has_cycle, from, to);

    depth_first_search(g, visitor(vis));

    std::cout << "graph has cycle? " << std::boolalpha << has_cycle << "\n";

    // make cycle
    add_edge(3, 4, g);
    depth_first_search(g, visitor(vis));

    std::cout << "graph has cycle? " << std::boolalpha << has_cycle << "\n";
    std::cout << "cycle from: " << from << " to " << to << "\n";
}

版画

graph has cycle? false
graph has cycle? true
cycle from: 5 to 2

改为顶点索引

如果你真的想要顶点索引而不是描述符：Live

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

using G = boost::adjacency_list<>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;

struct cycle_detector : boost::dfs_visitor<> {
    cycle_detector(bool& has_cycle, size_t& cyclefrom, size_t& cycleto)
        : _has_cycle(has_cycle)
        , _cyclefrom_idx(cyclefrom)
        , _cycleto_idx(cycleto) {}

    void back_edge(E e, G const& g) {
        auto index = get(boost::vertex_index, g);
        _cyclefrom_idx  = index[source(e, g)];
        _cycleto_idx    = index[target(e, g)];
        _has_cycle = true;
    }

    bool&   _has_cycle;
    size_t& _cyclefrom_idx;
    size_t& _cycleto_idx;
};

int main() {
    boost::adjacency_list<> g;
    add_edge(1, 2, g);
    add_edge(2, 3, g);
    add_edge(4, 5, g);
    add_edge(5, 2, g);

    bool   has_cycle = false;
    size_t from_idx, to_idx;

    cycle_detector vis(has_cycle, from_idx, to_idx);

    depth_first_search(g, visitor(vis));

    std::cout << "graph has cycle? " << std::boolalpha << has_cycle << "\n";

    // make cycle
    add_edge(3, 4, g);
    depth_first_search(g, visitor(vis));

    std::cout << "graph has cycle? " << std::boolalpha << has_cycle << "\n";
    std::cout << "cycle from indices: " << from_idx << " to " << to_idx << "\n";
}

当然这对于不同的图模型更有意义：https://godbolt.org/z/Ma9nf964v

使其（更多）有用

相反，如果您想以更有用的方式获取信息怎么办？让我们让访问者更简单、更通用：

template <typename Callback>
struct back_edge_collector : boost::dfs_visitor<> {
    Callback _cb;
    back_edge_collector(Callback cb) : _cb(std::move(cb)) {}
    void back_edge(E e, G const&) const { _cb(e); }
};

现在可以直接使用了：https://godbolt.org/z/acsM69vc3

template <typename Callback>
struct back_edge_collector : boost::dfs_visitor<> {
    Callback _cb;
    back_edge_collector(Callback cb) : _cb(std::move(cb)) {}
    void back_edge(E e, G const&) const { _cb(e); }
};

int main() {
    boost::adjacency_list<> g;
    add_edge(1, 2, g);
    add_edge(2, 3, g);
    add_edge(4, 5, g);
    add_edge(5, 2, g);

    bool has_cycle = false;

    back_edge_collector vis([&](E e) {
        has_cycle = true;
        std::cout << "Back-edge: " << e << "\n";
    });

    depth_first_search(g, visitor(vis));

    std::cout << "graph has cycle? " << std::boolalpha << has_cycle << "\n";

    // make cycle
    add_edge(3, 4, g);
    depth_first_search(g, visitor(vis));

    std::cout << "graph has cycle? " << std::boolalpha << has_cycle << "\n";
}

版画

graph has cycle? false
Back-edge: (5,2)
graph has cycle? true

并且因为它使用了控制反转，所以当你想做一些不同的事情时它不会改变：https://godbolt.org/z/3j7n8xz1j

std::set<E> back_edges;
depth_first_search(g, visitor(back_edge_collector([&back_edges](E e) {
                       back_edges.insert(e);
                   })));

std::cout << "graph has " << back_edges.size() << " unique back_edges\n";

输出：

graph has 1 unique back_edges