Class: GraphUtils::BipartiteGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/GraphUtils.rb

Overview

Represents a bipartite graph.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(x, y, e) ⇒ BipartiteGraph

First argument to the constructor is the first set of values, second argument is the second set. The third argument is a hash which maps elements from the first set to an array of elements from the second set, designating edges (adjancency list).



15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/GraphUtils.rb', line 15

def initialize(x, y, e)
    unless x.kind_of?(Set) and y.kind_of?(Set) and e.kind_of?(Hash) and
	not x.empty? and not y.empty? and not e.empty?
	raise ArgumentError,
	    "Two non-empty sets of values and a hash where key => [value] designates edges must be given!"
    end
    @x = x
    @y = y
    @e = e
    @max_matching = nil
end

Instance Attribute Details

#e ⇒ Object

Returns the value of attribute e.



10
11
12
 
# File 'lib/GraphUtils.rb', line 10

def e
  @e
end

#x ⇒ Object (readonly)

Returns the value of attribute x.



9
10
11
 
# File 'lib/GraphUtils.rb', line 9

def x
  @x
end

#y ⇒ Object

Returns the value of attribute y.



10
11
12
 
# File 'lib/GraphUtils.rb', line 10

def y
  @y
end

Instance Method Details

#maximum_matching ⇒ Object

algorithm to compute maximum matching in O(sqrtV E) taken from Perl package Graph::Bipartite



29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/GraphUtils.rb', line 29

def maximum_matching
    @e_double = @e.dup
    @e.each_key { |k|
	@e[k].each { |v|
	    if not @e_double.has_key?(v)
		@e_double[v] = Set.new
	    end
	    @e_double[v].add(k)
	}
    }
    matching = Hash.new
    @e_double.each_key { |key|
	matching[key] = nil
    }
    if @max_matching.nil?
	recalc = true
    else
	recalc = false
	@max_matching.each { |k,v|
	    if not @e[k].include?(v)
		recalc = true
	    else
		# recompute the new matching based on the old matching
		matching[k] = v
		matching[v] = k
	    end
	}
    end
    if recalc
	level = Hash.new
	while sbfs(matching, level) > 0
	    sdfs(matching, level)
	end
	@max_matching = matching.delete_if { |k,v| @y.include?(k) or v.nil? }
    end
    return @max_matching
end

#removable_values(matching) ⇒ Object

Computes a mapping from x value to a set of y values. Each mapping designates an arc which can be removed because it doesn’t belong to any matching. The method requires a matching as an argument.



70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
 
# File 'lib/GraphUtils.rb', line 70

def removable_values(matching)
    edges = Array.new
    label = Hash.new 
    @e.each_key { |k|
	@e[k].each { |v|
	    if matching.has_key?(k) and matching[k] == v
		edge = DirectedEdge.new(k, v)
		edges << edge
		label[edge] = :used
	    else
		edges << DirectedEdge.new(v, k)
	    end
	}
    }

    # edges in strongly connected components
    GraphUtils::strongly_connected_components(@x | @y, edges).each { |component|
	componentHelper = Hash.new
	component.each { |i| componentHelper[i] = 1 }
	(edges.select { |edge|
	    componentHelper.has_key?(edge.startVertex) and componentHelper.has_key?(edge.endVertex)
	}).each { |edge|
	    label[edge] = :used
	}
    }

    # edges traversed during breadth-first search for m-alternating
    # paths starting at m-free vertices
    ((@x - matching.keys) + (@y - matching.values)).each { |vertex|
	GraphUtils::find_paths(vertex, edges).each { |edge|
	    label[edge] = :used
	}
    }

    pruneMap = Hash.new
    (edges.delete_if { |edge| label.has_key?(edge) }).each { |edge|
	if not pruneMap.has_key?(edge.endVertex)
	    pruneMap[edge.endVertex] = Set.new
	end
	pruneMap[edge.endVertex].add(edge.startVertex)
    }

    return pruneMap
end