Class: BipartiteGraph::AlternatingTree

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

Overview

an alternating tree isn’t a graph in its own right it’s a subgraph - you can’t add things that aren’t in the main graph

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph, root) ⇒ AlternatingTree

Returns a new instance of AlternatingTree.



6
7
8
9
10
11
12
13
 
# File 'lib/bipartite_graph/alternating_tree.rb', line 6

def initialize(graph, root)
  raise "Root can't be nil" if root.nil?
  @root = root
  @graph = graph

  @node_map = {}
  @node_map[root] = [nil, nil]
end

Instance Attribute Details

#graph ⇒ Object

Returns the value of attribute graph.



5
6
7
 
# File 'lib/bipartite_graph/alternating_tree.rb', line 5

def graph
  @graph
end

#root ⇒ Object

Returns the value of attribute root.



5
6
7
 
# File 'lib/bipartite_graph/alternating_tree.rb', line 5

def root
  @root
end

Instance Method Details

#add_edge(edge) ⇒ Object 



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

def add_edge(edge)
  #raise "Tree has no existing node #{edge.from}" unless has_node?(edge.from)
  #raise "Tree already contains node #{edge.to}" if has_node?(edge.to)
  if has_node?(edge.from)
    @node_map[edge.to] = [edge.from, edge]
  elsif has_node?(edge.to)
    @node_map[edge.from] = [edge.to, edge]
  else
    raise "Nodes not in tree: #{edge.from} or #{edge.to}"
  end
end

#has_node?(node) ⇒ Boolean

Returns:

  • (Boolean) 


15
16
17
 
# File 'lib/bipartite_graph/alternating_tree.rb', line 15

def has_node?(node)
  @node_map.has_key?(node)
end

#nodes ⇒ Object 



19
20
21
 
# File 'lib/bipartite_graph/alternating_tree.rb', line 19

def nodes
  @node_map.keys
end

#path_to(leaf) ⇒ Object 



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

def path_to(leaf)
  path = []
  next_node, edge = @node_map[leaf]
  while edge
    path << edge
    next_node, edge = @node_map[next_node]
  end
  path.reverse
end

#sinks ⇒ Object 



26
27
28
 
# File 'lib/bipartite_graph/alternating_tree.rb', line 26

def sinks
  graph.sinks.select {|node| has_node?(node) }
end

#sources ⇒ Object 



23
24
25
 
# File 'lib/bipartite_graph/alternating_tree.rb', line 23

def sources
  graph.sources.select {|node| has_node?(node) }
end