Module: Plexus::UndirectedGraphBuilder::Algorithms

Includes:

Biconnected, Comparability, Search

Defined in:

lib/plexus/undirected_graph/algorithms.rb

Instance Method Summary (collapse)

• - (Boolean) balanced?(v)

  A vertex of an undirected graph is balanced by definition.

• - (Object) chromatic_number
• - (Object) degree(v)

  Redefine degree (default was sum).

• - (Boolean) directed?

  UndirectedGraph is by definition undirected, always returns false.

• - (Object) edge_class

  UndirectedGraph uses Edge for the edge class.

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

• - (Boolean) permutation?

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

• - (Object) remove_edge!(u, v = nil)
• - (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.

• - (Boolean) triangulated?

  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

#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

16

# File 'lib/plexus/undirected_graph/algorithms.rb', line 16

def balanced?(v)  true;  end

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

13

# File 'lib/plexus/undirected_graph/algorithms.rb', line 13

def degree(v)    in_degree(v); end

10

# File 'lib/plexus/undirected_graph/algorithms.rb', line 10

def directed?()  false; end

19

# File 'lib/plexus/undirected_graph/algorithms.rb', line 19

def edge_class() @parallel_edges ? Plexus::MultiEdge : Plexus::Edge; end

60

# File 'lib/plexus/undirected_graph/algorithms.rb', line 60

def interval?() triangulated? and complement.comparability?; end

65

# File 'lib/plexus/undirected_graph/algorithms.rb', line 65

def permutation?() comparability? and complement.comparability?; end

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

69

# File 'lib/plexus/undirected_graph/algorithms.rb', line 69

def split?() triangulated? and complement.triangulated?; end

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