Boost logo

Boost :

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-07-24 15:56:11

On Tue, 24 Jul 2001 alexanderdz_at_[hidden] wrote:
> I wrote test program which you can find below and found following
> problems:
> A. The depth_first_search algorithm always calls back_edge method of
> visitor. It happens even if graph has two nodes and one edge linking
> them. What is(are) other method(s) of cycle detection?

If you record predecessors you can check if the edge passed to back_edge()
is really a tree edge. Perhaps this check should be encorporated into
depth_first_search(). Anyways, here's how you could change your
cycle_detector visitor to do this:

template <class ParentMap>
struct cycle_detector : public dfs_visitor<>
  cycle_detector(bool& has_cycle, ParentMap parent_map)
    : m_has_cycle(has_cycle), m_p(parent_map) { }

  template <class Edge, class Graph>
  void tree_edge(Edge e, Graph& g) {
    m_p[target(e, g)] = source(e, g);

  template <class Edge, class Graph>
  void back_edge(Edge e, Graph& g) {
    if (m_p[source(e, g)] != target(e, g))
      m_has_cycle = true;
  bool& m_has_cycle;
  ParentMap m_p;

 Jeremy Siek www:
 Ph.D. Candidate, IU B'ton email: jsiek_at_[hidden]
 Summer Manager, AT&T Research phone: (973) 360-8185

Boost list run by bdawes at, gregod at, cpdaniel at, john at