Class: BipartiteGraph::Graph

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



4
5
6
 
# File 'lib/bipartite_graph/graph.rb', line 4

def initialize
  clear
end

Instance Attribute Details

#edges ⇒ Object (readonly)

Returns the value of attribute edges.



3
4
5
 
# File 'lib/bipartite_graph/graph.rb', line 3

def edges
  @edges
end

#nodes ⇒ Object (readonly)

Returns the value of attribute nodes.



3
4
5
 
# File 'lib/bipartite_graph/graph.rb', line 3

def nodes
  @nodes
end

#sinks ⇒ Object (readonly)

Returns the value of attribute sinks.



3
4
5
 
# File 'lib/bipartite_graph/graph.rb', line 3

def sinks
  @sinks
end

#sources ⇒ Object (readonly)

Returns the value of attribute sources.



3
4
5
 
# File 'lib/bipartite_graph/graph.rb', line 3

def sources
  @sources
end

Instance Method Details

#add_edge(from, to, weight = 1) ⇒ Object 



15
16
17
18
19
20
21
22
23
 
# 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 ⇒ Object 



8
9
10
11
12
13
 
# 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) ⇒ Object 



29
30
31
32
 
# 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 ⇒ Object 



34
35
36
 
# File 'lib/bipartite_graph/graph.rb', line 34

def max_weight_matching
  HungarianAlgorithm.new(self).solution
end

#node_for(key) ⇒ Object 



25
26
27
 
# File 'lib/bipartite_graph/graph.rb', line 25

def node_for(key)
  @nodes[key]
end