module Fathom::GeneralGraphTools
Public Instance Methods
add_edge(parent, child)
click to toggle source
# File lib/fathom/roles/general_graph_tools.rb, line 8 def add_edge(parent, child) self.variables |= [parent, child] self.adjacency_matrix[parent, child] = 1 end
adjacency_matrix()
click to toggle source
# File lib/fathom/roles/general_graph_tools.rb, line 4 def adjacency_matrix @adjacency_matrix ||= AdjacencyMatrix.new end
at(parent, child)
click to toggle source
# File lib/fathom/roles/general_graph_tools.rb, line 18 def at(parent, child) self.adjacency_matrix[parent, child] end
Also aliased as: []
connected?()
click to toggle source
Find whether the graph is connected, based on notes here: www.ics.uci.edu/~eppstein/161/960201.html This assumes that all variables in the network have been added to the adjacency matrix.
# File lib/fathom/roles/general_graph_tools.rb, line 48 def connected? x = self.variables[0] # Arbitrary first node reachable_vertices = [x] vertices_to_explore = [x] while !vertices_to_explore.empty? y = vertices_to_explore.shift self.each_edge do |parent, child| unless reachable_vertices.include?(child) vertices_to_explore << child reachable_vertices << child end end end reachable_vertices.size < self.variables.size ? false : true end
degree(node)
click to toggle source
Implemented as an out-degree
# File lib/fathom/roles/general_graph_tools.rb, line 29 def degree(node) found = self.adjacency_matrix.select do |(parent, child), value| parent == node end found.size end
each_edge() { |parent, child| ... }
click to toggle source
# File lib/fathom/roles/general_graph_tools.rb, line 40 def each_edge self.adjacency_matrix.each {|(parent, child), value| yield parent, child} end
each_vertex() { |v| ... }
click to toggle source
# File lib/fathom/roles/general_graph_tools.rb, line 36 def each_vertex self.variables.each {|v| yield v} end
edge?(parent, child)
click to toggle source
# File lib/fathom/roles/general_graph_tools.rb, line 23 def edge?(parent, child) return false unless ([parent, child] - self.variables).empty? self.adjacency_matrix[parent, child] == 1 end
euler_circuit?()
click to toggle source
# File lib/fathom/roles/general_graph_tools.rb, line 67 def euler_circuit? return false if !connected? self.each_vertex do |v| return false if degree(v) % 2 != 0 end true end
euler_path?()
click to toggle source
# File lib/fathom/roles/general_graph_tools.rb, line 75 def euler_path? return false if !connected? odd=0 self.each_vertex do |v| if degree(v) % 2 == 1 odd += 1 end end odd <= 2 end
remove_edge(parent, child)
click to toggle source
# File lib/fathom/roles/general_graph_tools.rb, line 13 def remove_edge(parent, child) return false unless self.variables.include?(parent) and self.variables.include?(child) self.adjacency_matrix[parent, child] = 0 end