[Boost-users] Cycle detection in a directed graph with adjacency_matrix

Subject: [Boost-users] Cycle detection in a directed graph with adjacency_matrix
From: albert kao (albertkao3_at_[hidden])
Date: 2011-04-12 19:19:36

Is it possible to detect any cycle in a directed graph with the
adjacency_matrix of the Boost Graph Library?
My test program has this compile errors:
adjacency_matrix_is_cyclic.cpp:6: error: expected initializer before ‘<’
token
adjacency_matrix_is_cyclic.cpp:9: error: expected class-name before ‘{’
token
adjacency_matrix_is_cyclic.cpp:14: error: ‘edge_t’ has not been declared
adjacency_matrix_is_cyclic.cpp: In function ‘bool has_cycle(const Graph&)’:

adjacency_matrix_is_cyclic.cpp:26: error: ‘generic_dfs_v1’ was not declared
in this scope

$ cat adjacency_matrix_is_cyclic.cpp

#include <iostream>

#include <boost/graph/graph_utility.hpp>

#include <boost/graph/adjacency_matrix.hpp>

typedef boost::adjacency_matrix<boost::directedS> Graph;

typedef graph_traits<Graph>::edge_descriptor edge_t;

struct cycle_detector : public dfs_visitor_default
{
  cycle_detector(bool & cycle): has_cycle(cycle)
  {
  }
  void
  back_edge(edge_t, const Graph &)
  {
    has_cycle = true;
  }
  bool & has_cycle;
};

bool
has_cycle(const Graph & g)
{
  bool has_cycle = false;
  cycle_detector vis(has_cycle);
  generic_dfs_v1(g, vis);
  return has_cycle;
}

enum { A, B, C, D, E, F, N };
const char* name = "ABCDEF";

int main(int argc, char *argv[])
{
  Graph g(N);
  add_edge(B, C, g);
  add_edge(B, F, g);
  add_edge(C, A, g);
  add_edge(C, C, g);
  add_edge(D, E, g);
  add_edge(E, D, g);
  add_edge(F, A, g);

  std::cout << "vertex set: ";
  boost::print_vertices(g, name);
  std::cout << std::endl;

  std::cout << "edge set: ";
  boost::print_edges(g, name);
  std::cout << std::endl;

  std::cout << "out-edges: " << std::endl;
  boost::print_graph(g, name);
  std::cout << std::endl;

  std::cout << "has_cycle(g) " << has_cycle(g) << std::endl;

  return 0;
}