Class: BipartiteGraph

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

Class Method Summary collapse

Class Method Details

.create_augment_flow(graph, path) ⇒ Object 



43
44
45
46
47
48
49
50
 
# File 'lib/bipartite_graph.rb', line 43

def self.create_augment_flow (graph, path)
  edges = graph[:edges]
  path.each do |u, v|
    edges[v] ||= {}
    edges[v][u] = -edges[u][v]
    edges[u].delete v
  end
end

.get_augmenting_path(graph, source = :source, sink = :sink) ⇒ Object 



27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/bipartite_graph.rb', line 27

def self.get_augmenting_path(graph, source = :source, sink = :sink)
  parents = search graph, source, sink
  return nil unless parents[sink]
  path = []
  current_vertex = sink
  until current_vertex == source
    path << [parents[current_vertex], current_vertex]
    current_vertex = parents[current_vertex]

    if path.length > parents.length
      raise "Cannot terminate. Use integral edge weights."
    end
  end
  path.reverse!
end

.graph_matching!(graph, source = :source, sink = :sink) ⇒ Object 



18
19
20
21
22
23
24
25
 
# File 'lib/bipartite_graph.rb', line 18

def self.graph_matching!(graph, source = :source, sink = :sink)
  loop do
    path = get_augmenting_path graph
    break unless path
    create_augment_flow graph, path
  end
  matching_in graph, source, sink
end

.match(left_vertices, right_vertices, edges) ⇒ Object 



3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
# File 'lib/bipartite_graph.rb', line 3

def self.match(left_vertices, right_vertices, edges)
  vertices = left_vertices + right_vertices + [:sink, :source]
  edges[:sink] = {}
  edges[:source] = {}
  
  left_vertices.each do |left_vertice|
    edges[:source][left_vertice] = 0
  end
  right_vertices.each do |right_vertice|
    edges[right_vertice] = { sink: 0 }
  end
  graph = { vertices: vertices, edges: edges }
  matching = graph_matching! graph
end

.matching_in(graph, source = :source, sink = :sink) ⇒ Object 



68
69
70
71
72
 
# File 'lib/bipartite_graph.rb', line 68

def self.matching_in(graph, source = :source, sink = :sink)
  Hash[*((graph[:edges][sink] || {}).keys.map { |matched_vertex|
    [graph[:edges][matched_vertex].keys.first, matched_vertex]
  }.flatten)]
end

.search(graph, source = :source, sink = :sink) ⇒ Object 



52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/bipartite_graph.rb', line 52

def self.search(graph, source = :source, sink = :sink)
  parents = { source => true }
  queue = [source]
  until queue.empty?
    current_vertex = queue.shift
    break if current_vertex == sink
    (graph[:edges][current_vertex] || {}).each do |new_vertex, edge|
      next if parents[new_vertex]
      parents[new_vertex] = current_vertex
      queue << new_vertex
    end
  end

  parents
end