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

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

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

#directed? ⇒ Boolean
UndirectedGraph is by definition undirected, always returns false.

#edge_class ⇒ Object
UndirectedGraph uses Edge for the edge class.

#interval? ⇒ Boolean
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.

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

#split? ⇒ Boolean
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.

#triangulated? ⇒ Boolean
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
#balanced?(v) ⇒ Boolean
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 
#chromatic_number ⇒ Object
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 
#degree(v) ⇒ Object
Redefine degree (default was sum)
13 
# File 'lib/plexus/undirected_graph/algorithms.rb', line 13 def degree(v) in_degree(v); end 
#directed? ⇒ Boolean
UndirectedGraph is by definition undirected, always returns false
10 
# File 'lib/plexus/undirected_graph/algorithms.rb', line 10 def directed?() false; end 
#edge_class ⇒ Object
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 
#interval? ⇒ Boolean
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 
#permutation? ⇒ Boolean
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 
#remove_edge!(u, v = nil) ⇒ Object
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 
#split? ⇒ Boolean
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 
#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
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 