[Ruby] Cycle Detection in a graph

[Ofer Matan]

Aaron,

A few comments:

1) The algorithm you posted is incorrect - it only does a shallow prune -
here is a simple example:

# B-> A -> D
# A -> D
# D-> E

  am2 = [
    # A, B, C, D, E
    [ 0, 0, 1, 1, 0 ], # A
    [ 1, 0, 0, 0, 0 ], # B
    [ 0, 0, 0, 0, 0 ], # C
    [ 0, 0, 0, 0, 1 ], # D
    [ 0, 0, 0, 0, 0 ], # E
  ]

Which returns 

[[0, 0, 0, 1, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0]]

2) Even if were correct, As Ian mentioned it is not particularly efficient -
it is currently O(V^3) where V is the number or Vertices - though could be
easily fixed to be O(V^2). 

3) A Modified Depth First Search would find a cycle - I found an example on
page 11 at http://www.cs.berkeley.edu/~kamil/sp03/041403.pdf . This is an
O(E) algorithm where E is the number of edges (assuming the graph is not
implemented as a matrix). To modify it to return the cycle just push each
vertex as you enter vist(G,v) onto a stack and pop it when you exit. Then if
detected traverse the last element back to itself.

4) The Ruby Graph Library http://rgl.rubyforge.org/rgl/index.html  has cycle
detection and many other algorithms that seem to use well know efficient
algorithms - I haven't used it.

-Ofer