Module: Fathom::GeneralGraphTools

Defined in:
lib/fathom/roles/general_graph_tools.rb

Instance Method Summary collapse

Instance Method Details

#add_edge(parent, child) ⇒ Object 



8
9
10
11
 
# 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 ⇒ Object 



4
5
6
 
# File 'lib/fathom/roles/general_graph_tools.rb', line 4

def adjacency_matrix
  @adjacency_matrix ||= AdjacencyMatrix.new
end

#at(parent, child) ⇒ Object Also known as: [] 



18
19
20
 
# File 'lib/fathom/roles/general_graph_tools.rb', line 18

def at(parent, child)
  self.adjacency_matrix[parent, child]
end

#connected? ⇒ Boolean

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.

Returns:

  • (Boolean) 


48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# 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) ⇒ Object

Implemented as an out-degree



29
30
31
32
33
34
 
# 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 ⇒ Object 



40
41
42
 
# 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 ⇒ Object 



36
37
38
 
# File 'lib/fathom/roles/general_graph_tools.rb', line 36

def each_vertex
  self.variables.each {|v| yield v}
end

#edge?(parent, child) ⇒ Boolean

Returns:

  • (Boolean) 


23
24
25
26
 
# 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? ⇒ Boolean

Returns:

  • (Boolean) 


67
68
69
70
71
72
73
 
# 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? ⇒ Boolean

Returns:

  • (Boolean) 


75
76
77
78
79
80
81
82
83
84
 
# 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) ⇒ Object 



13
14
15
16
 
# 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