Module: Plexus::UndirectedGraphBuilder::Algorithms

Includes:
Biconnected, Comparability, Search
Defined in:
lib/plexus/undirected_graph/algorithms.rb

Instance Method Summary collapse

• A vertex of an undirected graph is balanced by definition.

• Redefine degree (default was sum).

• UndirectedGraph is by definition undirected, always returns false.

• UndirectedGraph uses Edge for the edge class.

• An interval graph can have its vertices into one-to-one 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.

• A permutation diagram consists of n points on each of two parallel lines and n straight line segments matchin the points.

• 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.

• A triangulated graph is an undirected perfect graph that every cycle of length greater than three possesses a chord.

#biconnected

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

Raises:

• (NotImplementedError)
 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 one-to-one 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