Class: GRATR::UndirectedGraph

Inherits:
Object
  • Object
show all
Includes:
AdjacencyGraph, Graph::Biconnected, Graph::Comparability, Graph::Search
Defined in:
lib/gratr/undirected_graph.rb

Direct Known Subclasses

UndirectedMultiGraph, UndirectedPseudoGraph

Instance Method Summary collapse

Methods included from Graph::Comparability

#comparability?, #gamma_decomposition, #transitive_orientation

Methods included from Graph::Biconnected

#biconnected

Methods included from Graph::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, #spanning_forest, #topsort, #tree_from_vertex

Methods included from AdjacencyGraph

#add_edge!, #add_vertex!, #adjacent, #edge?, #edges, #graph_adjacent, included, #remove_vertex!, #vertex?, #vertices

Methods included from Graph

#dotty, #to_dot, #to_dot_graph, #write_to_graphic_file

Constructor Details

#initialize(*params) ⇒ UndirectedGraph

Returns a new instance of UndirectedGraph.

Raises:

  • (ArgumentError) 


43
44
45
46
47
48
 
# File 'lib/gratr/undirected_graph.rb', line 43

def initialize(*params)
  raise ArgumentError if params.any? do |p| 
   !(p.kind_of? GRATR::Graph or p.kind_of? Array)
  end if self.class == GRATR::UndirectedGraph
  super(*params)
end

Dynamic Method Handling

This class handles dynamic methods through the method_missing method in the class GRATR::Graph::Search

Instance Method Details

#balanced?(v) ⇒ Boolean

A vertex of an undirected graph is balanced by definition



57
 
# File 'lib/gratr/undirected_graph.rb', line 57

def balanced?(v)  true;  end

#chromatic_number ⇒ Object

Raises:

  • (NotImplementedError) 


91
92
93
94
 
# File 'lib/gratr/undirected_graph.rb', line 91

def chromatic_number
  return triangulated_chromatic_number if triangulated?
  raise NotImplementedError    
end

#degree(v) ⇒ Object

Redefine degree (default was sum)



54
 
# File 'lib/gratr/undirected_graph.rb', line 54

def degree(v)    in_degree(v); end

#directed? ⇒ Boolean

UndirectedGraph is by definition undirected, always returns false



51
 
# File 'lib/gratr/undirected_graph.rb', line 51

def directed?()  false; end

#edge_class ⇒ Object

UndirectedGraph uses Edge for the edge class.



60
 
# File 'lib/gratr/undirected_graph.rb', line 60

def edge_class() @parallel_edges ? GRATR::MultiEdge : GRATR::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.



101
 
# File 'lib/gratr/undirected_graph.rb', line 101

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.



106
 
# File 'lib/gratr/undirected_graph.rb', line 106

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

#remove_edge!(u, v = nil) ⇒ Object 



62
63
64
65
66
67
68
69
 
# File 'lib/gratr/undirected_graph.rb', line 62

def remove_edge!(u, v=nil)
  unless u.kind_of? GRATR::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.



110
 
# File 'lib/gratr/undirected_graph.rb', line 110

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



77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/gratr/undirected_graph.rb', line 77

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