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

Returns:

  • (Boolean) 


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

Returns:

  • (Boolean) 


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.

Returns:

  • (Boolean) 


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.

Returns:

  • (Boolean) 


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.

Returns:

  • (Boolean) 


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

Returns:

  • (Boolean) 


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