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

- (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

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

- (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 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

- (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