Detecting a cycle in a given array

Question

I have an array of strings like the following:

["a => ", "b => c", "c = > f", "d => a", "e => b", "f =>"]

This represents a partial order such that "c" is before "b", "f" is before "c", "a" is before "d", and "b" is before "e". The order can be realized in a total order such as:

["f", "c", "b", "a", "d", "e"]

If I have an array like this:

["a => ", "b => c", "c = > f", "d => a", "e => ", "f => b"]

it does not represent a partial order, as there is a cycle.

How might I check that this occurs when an array comes into my program?

In technical terms, you're trying to detect cycles in a directed graph. There's lots of good discussion here: http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph and, of course, Google. — Jordan Running, Apr 23 '16 at 01:42
Question is not well stated. What variations are there for the substring that delimits the two nodes, besides `" => "`, `" = > "`, and `" =>"`? Or, did you need to state your question using such contrived format in the first place? Couldn't it be like `[["a", nil], ["b", "c"], ["c", "f"], ...]`? — sawa, Apr 23 '16 at 03:19

score 0 · Answer 1 · answered Apr 23 '16 at 03:45

def cycled? a
  a = a.map{|s| s.match(/(\w+)? ?= ?> ?(\w+)?/).captures}
    .delete_if{|x, y| x.nil? or y.nil?}
  loop do
    nodes = a.flatten.uniq
    b = a.dup
    nodes.each{|e| b.reject!{|x, y| y == e} unless b.any?{|x, y| x == e}}
    nodes.each{|e| b.reject!{|x, y| x == e} unless b.any?{|x, y| y == e}}
    break !b.empty? if b == a
    a = b
  end
end

cycled?(["a => ", "b => c", "c = > f", "d => a", "e => b", "f =>"]) # => false
cycled?(["a => ", "b => c", "c = > f", "d => a", "e => ", "f => b"]) # => true

To return the detected cycle, change the line:

break !b.empty? if b == a

to:

break b if b == a

score 0 · Answer 2 · answered Apr 26 '16 at 01:37

I would do the following.

def circular_dependencies?(arr)
  (2..arr.size).any? { |n| arr.combination(n).any? { |comb| is_cycle?(comb) } }
end

def is_cycle?(comb)
  a = comb.flat_map { |s| s.split /\s+=>\s+/ }.rotate
  a.each_slice(2).all? { |l,f| l==f }
end

arr = ["a =>", "b => c", "c => f", "d => a", "e =>", "f => b"]
circular_dependencies?(arr)
  #=> true

arr = ["a =>", "b => c", "c => f", "d => a", "e =>", "f => a"]
circular_dependencies?(arr)
  #=> false

When

arr = ["a =>", "b => c", "c => f", "d => a", "e =>", "f => b"]

and n = 3

enum = arr.combination(n)
  #=> #<Enumerator: ["a =>", "b => c", "c => f", "d => a", "e =>",
  #                  "f => a"]:combination(3)>

We can convert this enumerator to an array to see the elements that will be passed to it's block:

enum.to_a
  #=> [["a =>", "b => c", "c => f"],
  #    ["a =>", "b => c", "d => a"],
  #    ["a =>", "b => c", "e =>"],
  #    ["a =>", "b => c", "f => b"],
  #    ["a =>", "c => f", "d => a"],
  #    ["a =>", "c => f", "e =>"],
  #    ["a =>", "c => f", "f => b"],
  #    ["a =>", "d => a", "e =>"],
  #    ["a =>", "d => a", "f => b"],
  #    ["a =>", "e =>", "f => b"],
  #    ["b => c", "c => f", "d => a"],
  #    ["b => c", "c => f", "e =>"],
  # ** ["b => c", "c => f", "f => b"],
  #    ["b => c", "d => a", "e =>"],
  #    ["b => c", "d => a", "f => b"],
  #    ["b => c", "e =>", "f => b"],
  #    ["c => f", "d => a", "e =>"],
  #    ["c => f", "d => a", "f => b"],
  #    ["c => f", "e =>", "f => b"],
  #    ["d => a", "e =>", "f => b"]]

When the combination

comb = ["b => c", "c => f", "f => b"]

is passed to is_comb? we compute

a = comb.flat_map { |s| s.split /\s+=>\s+/ }
  #=> ["b", "c", "c", "f", "f", "b"] 
b = a.rotate
  #=> ["c", "c", "f", "f", "b", "b"] 
enum = a.each_slice(2)
  #=> #<Enumerator: ["c", "c", "f", "f", "b", "b"]:each_slice(2)> 
enum.to_a
  #=> [["c", "c"], ["f", "f"], ["b", "b"]] 
enum.all? { |l,f| l==f }
  #=> true

Detecting a cycle in a given array

2 Answers2