Module: Glymour::StructureLearning::GraphAlgorithms

Defined in:
lib/glymour.rb

Instance Method Summary collapse

Instance Method Details

#adjacent_either(a, b) ⇒ Object

Returns a (unique) list of vertices adjacent to vertex a or b. This is denoted “Aab” in Spirtes-Glymour’s paper.



94
95
96
 
# File 'lib/glymour.rb', line 94

def adjacent_either(a, b)
  (adjacent_undirected(a) + adjacent_undirected(b)).uniq
end

#adjacent_undirected(vertex) ⇒ Object 



98
99
100
101
 
# File 'lib/glymour.rb', line 98

def adjacent_undirected(vertex)
  adjacent_sources = vertices.select { |w| adjacent_vertices(w).include?(vertex) }
  adjacent_vertices(vertex) + adjacent_sources
end

#has_edge?(e) ⇒ Boolean

Returns:

  • (Boolean) 


88
89
90
 
# File 'lib/glymour.rb', line 88

def has_edge?(e)
  self.edges.include? e
end

#non_transitive ⇒ Object

Returns a list of ordered 3-tuples (a, b, c) of vertices such that (a, b) are adjacent and (b,c) are adjacent, but (a,c) are not.



121
122
123
124
125
126
127
128
129
130
131
 
# File 'lib/glymour.rb', line 121

def non_transitive
  triples = vertices.product(vertices, vertices)
  
  adjacent_triples = triples.select do |triple|
    adjacent_undirected(triple.first).include?(triple[1]) && adjacent_undirected(triple[1]).include?(triple.last)
  end
  
  adjacent_triples.reject do |triple|
    (adjacent_undirected(triple.first).include? triple.last) || (triple.first == triple.last)
  end
end

#verts_on_paths(current_vertex, t, current_path = [], paths = []) ⇒ Object

Returns an array of all vertices on undirected simple paths between s and t. Modified breadth-first search: keep track of current path, and when t is found, add it to paths. This is denoted “Uab” in Spirtes-Glymour’s paper.



106
107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/glymour.rb', line 106

def verts_on_paths(current_vertex, t, current_path=[], paths=[])
  if current_vertex == t
    paths << current_path + [current_vertex]
  else
    adjacent_undirected(current_vertex).each do |v|
      # Don't recur if we're repeating vertices (i.e. reject non-simple paths)
      verts_on_paths(v, t, current_path + [current_vertex], paths) if current_path.count(current_vertex) == 0
    end
  end
  
  paths.flatten.uniq
end