Module: Plexus::UndirectedGraphBuilder::Algorithms

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

Instance Method Summary collapse

Methods included from Comparability

#comparability?, #gamma_decomposition, #transitive_orientation

Methods included from Biconnected

#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

Returns:

  • (Boolean) 


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

Returns:

  • (Boolean) 


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.

Returns:

  • (Boolean) 


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.

Returns:

  • (Boolean) 


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.

Returns:

  • (Boolean) 


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

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