#!/usr/bin/ruby

$:.unshift File.join(File.dirname(__FILE__), "..", "lib")

require 'test/unit'
require 'GraphUtils'
require 'set'

module GraphUtils
    class BipartiteGraphTest < Test::Unit::TestCase
	def testConstructor
	    assert_raise(ArgumentError) { BipartiteGraph.new }
	    assert_raise(ArgumentError) { BipartiteGraph.new(nil, nil, nil) }
	    assert_raise(ArgumentError) { BipartiteGraph.new(Set.new, Set.new, Hash.new) }
	    assert_nothing_raised { BipartiteGraph.new(["a"].to_set, [1].to_set, { "a" => [1] }) }
	end

	def testMaximumMatchingCovering
	    graph = BipartiteGraph.new(["x","y","z"].to_set, [1,2,3].to_set,
		  { "x" => [1,3].to_set, "y" => [2,3].to_set, "z" => [2].to_set })
	    matching = graph.maximum_matching
	    assert_equal(3, matching.size)
	    assert_equal(1, matching["x"])
	    assert_equal(3, matching["y"])
	    assert_equal(2, matching["z"])
	end

	def testMaximumMatchingNotCovering
	    graph = BipartiteGraph.new(["x","y","z"].to_set, [1,2].to_set,
		  { "x" => [1,2].to_set, "y" => [1,2].to_set, "z" => [1,2].to_set })
	    matching = graph.maximum_matching
	    assert_equal(2, matching.size)
	end

	def testMaximumMatchingRecalc
	    graph = BipartiteGraph.new(["x","y","z"].to_set, [1,2,3,4].to_set,
		  { "x" => [1,2,3].to_set, "y" => [2,3,4].to_set, "z" => [2,3].to_set })
	    matching = graph.maximum_matching
	    assert_equal(true, matching.eql?(graph.maximum_matching))
	    graph.e["x"] = [2,3].to_set
	    matching = graph.maximum_matching
	    assert_equal(3, matching.size)
	    assert_equal(2, matching["x"])
	    assert_equal(4, matching["y"])
	    assert_equal(3, matching["z"])
	end

	def testRemovableValues
	    graph = BipartiteGraph.new(["x","y","z"].to_set, [1,2,3].to_set,
		  { "x" => [1,3].to_set, "y" => [2,3].to_set, "z" => [2].to_set })
	    matching = graph.maximum_matching
	    assert_equal({ "x" => [ 3 ].to_set, "y" => [ 2 ].to_set },
			 graph.removable_values(matching))
	end
    end

    class GraphUtilsTest < Test::Unit::TestCase
	def testStronglyConnectedComponents
	    assert_equal([],
			 GraphUtils::strongly_connected_components([ 1, 2 ], [ DirectedEdge.new(1, 2) ]))

	    graph = [ DirectedEdge.new(1, 2), DirectedEdge.new(1, 3),
		DirectedEdge.new(2, 1), DirectedEdge.new(3, 2),
		DirectedEdge.new(3, 4), DirectedEdge.new(4, 5),
		DirectedEdge.new(5, 4) ]
	    assert_equal([[ 4, 5 ], [ 1, 2, 3 ]],
			 GraphUtils::strongly_connected_components([ 1, 2, 3, 4, 5 ], graph))

	    assert_equal([["y", 2, "z", 3]],
			 GraphUtils::strongly_connected_components([ "x", "y", "z", 1, 2, 3 ],
							[ DirectedEdge.new("x", 1), DirectedEdge.new(3, "x"),
							  DirectedEdge.new("y", 2), DirectedEdge.new(3, "y"),
							  DirectedEdge.new("z", 3), DirectedEdge.new(2, "z") ]))
	end

	def testFindPaths
	    graph = [ DirectedEdge.new(1, 2), DirectedEdge.new(2, 3),
		      DirectedEdge.new(3, 2), DirectedEdge.new(4, 3) ]
	    assert_equal(graph[0..2].to_set, GraphUtils::find_paths(1, graph).to_set)
	    assert_equal(graph[1..3].to_set, GraphUtils::find_paths(4, graph).to_set)
	end
    end
end