# Module: Plexus::UndirectedGraphBuilder::Algorithms

Includes:
Biconnected, Comparability, Search
Defined in:
lib/plexus/undirected_graph/algorithms.rb

## Instance Method Summary (collapse)

• A vertex of an undirected graph is balanced by definition.

• Redefine degree (default was sum).

• UndirectedGraph is by definition undirected, always returns false.

• UndirectedGraph uses Edge for the edge class.

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

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

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

• A triangulated graph is an undirected perfect graph that every cycle of length greater than three possesses a chord.

#biconnected

## 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```