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