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

Returns:

  • (Boolean)


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

Returns:

  • (Boolean)


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.

Returns:

  • (Boolean)


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.

Returns:

  • (Boolean)


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.

Returns:

  • (Boolean)


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

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