Module: Plexus::UndirectedGraphBuilder::Algorithms
 Includes:
 Biconnected, Comparability, Search
 Defined in:
 lib/plexus/undirected_graph/algorithms.rb
Instance Method Summary (collapse)

 (Boolean) balanced?(v)
A vertex of an undirected graph is balanced by definition.
  (Object) chromatic_number

 (Object) degree(v)
Redefine degree (default was sum).

 (Boolean) directed?
UndirectedGraph is by definition undirected, always returns false.

 (Object) edge_class
UndirectedGraph uses Edge for the edge class.

 (Boolean) interval?
An interval graph can have its vertices into onetoone correspondence with a set of intervals F of a linearly ordered set (like the real line) such that two vertices are connected by an edge of G if and only if their corresponding intervals have nonempty intersection.

 (Boolean) permutation?
A permutation diagram consists of n points on each of two parallel lines and n straight line segments matchin the points.
  (Object) remove_edge!(u, v = nil)

 (Boolean) split?
An undirected graph is defined to be split if there is a partition V = S + K of its vertex set into a stable set S and a complete set K.

 (Boolean) triangulated?
A triangulated graph is an undirected perfect graph that every cycle of length greater than three possesses a chord.
Methods included from Comparability
#comparability?, #gamma_decomposition, #transitive_orientation
Methods included from Biconnected
Methods included from Search
#acyclic?, #astar, #best_first, #bfs, #bfs_spanning_forest, #bfs_tree_from_vertex, #cyclic?, #dfs, #dfs_spanning_forest, #dfs_tree_from_vertex, #lexicograph_bfs, #method_missing, #pre_search_method_missing, #sort, #spanning_forest, #topsort, #tree_from_vertex
Dynamic Method Handling
This class handles dynamic methods through the method_missing method in the class Plexus::Search
Instance Method Details
 (Boolean) balanced?(v)
A vertex of an undirected graph is balanced by definition
16 
# File 'lib/plexus/undirected_graph/algorithms.rb', line 16 def balanced?(v) true; end 
 (Object) chromatic_number
50 51 52 53 
# File 'lib/plexus/undirected_graph/algorithms.rb', line 50 def chromatic_number return triangulated_chromatic_number if triangulated? raise NotImplementedError end 
 (Object) degree(v)
Redefine degree (default was sum)
13 
# File 'lib/plexus/undirected_graph/algorithms.rb', line 13 def degree(v) in_degree(v); end 
 (Boolean) directed?
UndirectedGraph is by definition undirected, always returns false
10 
# File 'lib/plexus/undirected_graph/algorithms.rb', line 10 def directed?() false; end 
 (Object) edge_class
UndirectedGraph uses Edge for the edge class.
19 
# File 'lib/plexus/undirected_graph/algorithms.rb', line 19 def edge_class() @parallel_edges ? Plexus::MultiEdge : Plexus::Edge; end 
 (Boolean) interval?
An interval graph can have its vertices into onetoone correspondence with a set of intervals F of a linearly ordered set (like the real line) such that two vertices are connected by an edge of G if and only if their corresponding intervals have nonempty intersection.
60 
# File 'lib/plexus/undirected_graph/algorithms.rb', line 60 def interval?() triangulated? and complement.comparability?; end 
 (Boolean) permutation?
A permutation diagram consists of n points on each of two parallel lines and n straight line segments matchin the points. The intersection graph of the line segments is called a permutation graph.
65 
# File 'lib/plexus/undirected_graph/algorithms.rb', line 65 def permutation?() comparability? and complement.comparability?; end 
 (Object) remove_edge!(u, v = nil)
21 22 23 24 25 26 27 28 
# File 'lib/plexus/undirected_graph/algorithms.rb', line 21 def remove_edge!(u, v=nil) unless u.kind_of? Plexus::Arc raise ArgumentError if @parallel_edges u = edge_class[u,v] end super(u.reverse) unless u.source == u.target super(u) end 
 (Boolean) split?
An undirected graph is defined to be split if there is a partition V = S + K of its vertex set into a stable set S and a complete set K.
69 
# File 'lib/plexus/undirected_graph/algorithms.rb', line 69 def split?() triangulated? and complement.triangulated?; end 
 (Boolean) triangulated?
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
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 