module Fathom::GeneralGraphTools

Public Instance Methods

[](parent, child)
Alias for: at
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