Module: Fathom::GeneralGraphTools
- Defined in:
- lib/fathom/roles/general_graph_tools.rb
Instance Method Summary collapse
- #add_edge(parent, child) ⇒ Object
- #adjacency_matrix ⇒ Object
- #at(parent, child) ⇒ Object (also: #[])
-
#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.
-
#degree(node) ⇒ Object
Implemented as an out-degree.
- #each_edge ⇒ Object
- #each_vertex ⇒ Object
- #edge?(parent, child) ⇒ Boolean
- #euler_circuit? ⇒ Boolean
- #euler_path? ⇒ Boolean
- #remove_edge(parent, child) ⇒ Object
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.
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
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
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
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 |