Method: Plexus::UndirectedGraphBuilder::Algorithms#triangulated?

Defined in:
lib/plexus/undirected_graph/algorithms.rb

#triangulated? ⇒ Boolean

A triangulated graph is an undirected perfect graph that every cycle of length greater than three possesses a chord. They have also been called chordal, rigid circuit, monotone transitive, and perfect elimination graphs.

Implementation taken from Golumbic’s, “Algorithmic Graph Theory and Perfect Graphs” pg. 90

Returns:

  • (Boolean) 


36
37
38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/plexus/undirected_graph/algorithms.rb', line 36

def triangulated?
  a = Hash.new {|h,k| h[k]=Set.new}; sigma=lexicograph_bfs
  inv_sigma = sigma.inject({}) {|acc,val| acc[val] = sigma.index(val); acc}
  sigma[0..-2].each do |v|
    x = adjacent(v).select {|w| inv_sigma[v] < inv_sigma[w] }
    unless x.empty?
      u = sigma[x.map {|y| inv_sigma[y]}.min]
      a[u].merge(x - [u])
    end
    return false unless a[v].all? {|z| adjacent?(v,z)}
  end
  true
end