Re: [boost] Newbie question: how to detect cycles in undirected graph

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;
  }
protected:
  bool& m_has_cycle;
  ParentMap m_p;
};

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate, IU B'ton          email: jsiek_at_[hidden]
 Summer Manager, AT&T Research      phone: [phone]
----------------------------------------------------------------------