Re: [Boost-Users] [BGL] Detection of cycles in graphs

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-07-29 10:23:39

Hi Erik,

On Mon, 29 Jul 2002, Erik Arner wrote:
yg-boo>
yg-boo> Is there an algorithm implemented in BGL that detects whether a
yg-boo> directed graph contains cycles or not? If not, what would be the
yg-boo> best way to implement such an algorithm?

Yes, it is called depth-first search. See the "Cyclic Dependencies"
section of

http://www.boost.org/libs/graph/doc/file_dependency_example.html

and the example file

libs/graph/example/file_dependencies.cpp

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------