class BipartiteGraph::AlternatingTree

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

Attributes

graph[RW]
root[RW]

Public Class Methods

new(graph, root) click to toggle source
# 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

Public Instance Methods

add_edge(edge) click to toggle source
# 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) click to toggle source
# File lib/bipartite_graph/alternating_tree.rb, line 15
def has_node?(node)
  @node_map.has_key?(node)
end
nodes() click to toggle source
# File lib/bipartite_graph/alternating_tree.rb, line 19
def nodes
  @node_map.keys
end
path_to(leaf) click to toggle source
# 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() click to toggle source
# File lib/bipartite_graph/alternating_tree.rb, line 26
def sinks
  graph.sinks.select {|node| has_node?(node) }
end
sources() click to toggle source
# File lib/bipartite_graph/alternating_tree.rb, line 23
def sources
  graph.sources.select {|node| has_node?(node) }
end