monora/rgl

require 'test_helper'

require 'rgl/adjacency'

include RGL

class TestCycles < Test::Unit::TestCase

  def setup
    @dg   = DirectedAdjacencyGraph.new(Array)
    edges = [[1, 2], [2, 2], [2, 3], [3, 4], [4, 5], [5, 1], [6, 4], [6, 6], [1, 4], [7, 7], [7, 7]]
    edges.each do |(src, target)|
      @dg.add_edge(src, target)
    end

    @ug = AdjacencyGraph.new(Array)
    @ug.add_edges(*edges)
  end

  # Helper for testing for different permutations of a cycle
  def contains_cycle?(cycles, cycle)
    cycle.size.times do |i|
      return true if cycles.include?(cycle)
      cycle = cycle[1..-1] + [cycle[0]]
    end
  end

  def test_cycles
    d_cycles = @dg.cycles
    assert_equal 6, d_cycles.size
    assert d_cycles.include?([6])
    assert d_cycles.include?([7])
    assert d_cycles.include?([2])
    assert contains_cycle?(d_cycles, [1, 4, 5])
    assert contains_cycle?(d_cycles, [1, 2, 3, 4, 5])

    assert_equal 5, DirectedAdjacencyGraph.new(Set, @dg).cycles.size

    u_cycles = AdjacencyGraph.new(Set, @dg).cycles.sort

    assert u_cycles.include?([2])
    assert u_cycles.include?([6])
    assert u_cycles.include?([7])
    assert contains_cycle?(u_cycles, [1, 2, 3, 4, 5])
    assert contains_cycle?(u_cycles, [1, 5, 4, 3, 2])
    assert contains_cycle?(u_cycles, [1, 4, 3, 2])
    assert contains_cycle?(u_cycles, [1, 4, 5])
    assert contains_cycle?(u_cycles, [1, 5, 4])
    assert contains_cycle?(u_cycles, [1, 5])
    assert contains_cycle?(u_cycles, [1, 2])
    assert contains_cycle?(u_cycles, [1, 2, 3, 4])
    assert contains_cycle?(u_cycles, [2, 3])
    assert contains_cycle?(u_cycles, [1, 4])
    assert contains_cycle?(u_cycles, [3, 4])
    assert contains_cycle?(u_cycles, [4, 5])
    assert contains_cycle?(u_cycles, [4, 6])
    assert_equal 16, u_cycles.size
  end

end