[Ruby] Cycle Detection in a graph

[Aaron Patterson]

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/