class BipartiteGraph::Graph

Attributes

edges[R]
nodes[R]
sinks[R]
sources[R]

Public Class Methods

new() click to toggle source
# File lib/bipartite_graph/graph.rb, line 4
def initialize
  clear
end

Public Instance Methods

add_edge(from, to, weight=1) click to toggle source
# File lib/bipartite_graph/graph.rb, line 15
def add_edge(from, to, weight=1)
  @sources << from
  @sinks << to
  @nodes = @sources + @sinks

  edge = Edge.new(from, to, weight)
  @edges << edge
  edge
end
clear() click to toggle source
# File lib/bipartite_graph/graph.rb, line 8
def clear
  @nodes   = Set.new
  @sources = Set.new
  @sinks   = Set.new
  @edges   = EdgeSet.new
end
edge_between(a, b) click to toggle source
# File lib/bipartite_graph/graph.rb, line 29
def edge_between(a, b)
  # horrendously inefficient
  @edges.find {|e| e.from == a && e.to == b }
end
max_weight_matching() click to toggle source
# File lib/bipartite_graph/graph.rb, line 34
def max_weight_matching
  HungarianAlgorithm.new(self).solution
end
node_for(key) click to toggle source
# File lib/bipartite_graph/graph.rb, line 25
def node_for(key)
  @nodes[key]
end