[Ruby] Cycle Detection in a graph

[Ian Searle]

I haven't had time to study your code in depth.  Here is a partial  
answer on the assumption that something is better than nothing.

Your solution is to walk the graph and prune nodes.  Which, is a  
valid solution.  Though, it involves a copy and more work than is  
necessary.  However, if this is the form of your graph (a matrix),  
and the graphs are small, then it might be appropriate.  For larger  
graphs, a node structure is often used.  And, a depth-first search  
will uncover cycles pretty efficiently without a graph copy.

Cheers,
----------
Ian Searle
ians at potatoplanet.org



On May 25, 2007, at May/25 - 3:40 PM, Aaron Patterson wrote:

> I've got an adjacency matrix for a directed graph and I'd like to find
> out if the graph is cyclic.  Not only that, but I want to know which
> vectors are part of the cycle.
>
> I've come up with a solution, but I was wondering if anyone sees a
> problem with my implementation?  Also if anyone has a shorter/faster
> solution.
>
>   def cyclic_vectors(matrix)
>     am = matrix.dup
>     am.each_with_index do |row, i|
>       am.each { |r| r[i] = 0 } if row.all? { |x| x == 0 }
>     end
>     0.upto(am.first.length - 1) do |i|
>       if am.map { |row| row[i] }.all? { |x| x == 0 }
>         am[i] = [0] * am.first.length
>       end
>     end
>     am
>   end
>
>   # A -> B -> C -> A
>   # A -> D
>   # E -> A
>   am = [
>     # A, B, C, D, E
>     [ 0, 1, 0, 1, 0 ], # A
>     [ 0, 0, 1, 0, 0 ], # B
>     [ 1, 0, 0, 0, 0 ], # C
>     [ 0, 0, 0, 0, 0 ], # D
>     [ 1, 0, 0, 0, 0 ], # E
>   ]
>
>   pp cyclic_vectors(am)
>
>
> Which outputs:
>
>   [[0, 1, 0, 0, 0],
>    [0, 0, 1, 0, 0],
>    [1, 0, 0, 0, 0],
>    [0, 0, 0, 0, 0],
>    [0, 0, 0, 0, 0]]
>
>
> -- 
> Aaron Patterson
> http://tenderlovemaking.com/
> _______________________________________________
> Ruby at zenspider.com - Seattle.rb non-commercial list
> http://www.zenspider.com/seattle.rb
> http://www.zenspider.com/mailman/listinfo/ruby