# Module: Plexus::Comparability

Included in:
UndirectedGraphBuilder::Algorithms
Defined in:
lib/plexus/comparability.rb

## Instance Method Summary collapse

• A comparability graph is an UndirectedGraph that has a transitive orientation.

• Returns an array with two values, the first being a hash of edges with a number containing their class assignment, the second valud is a boolean which states whether or not the graph is a comparability graph.

• Returns one of the possible transitive orientations of the UndirectedGraph as a Digraph.

## Instance Method Details

### #comparability? ⇒ Boolean

A comparability graph is an UndirectedGraph that has a transitive orientation. This returns a boolean that says if this graph is a comparability graph.

Returns:

• (Boolean)
 ``` 7``` ```# File 'lib/plexus/comparability.rb', line 7 def comparability?() gamma_decomposition; end ```

### #gamma_decomposition ⇒ Object

Returns an array with two values, the first being a hash of edges with a number containing their class assignment, the second valud is a boolean which states whether or not the graph is a comparability graph

Complexity in time O(d*|E|) where d is the maximum degree of a vertex Complexity in space O(|V|+|E|)

 ``` 16 17 18 19 20 21 22 23 24 25``` ```# File 'lib/plexus/comparability.rb', line 16 def gamma_decomposition k = 0; comparability=true; classification={} edges.map {|edge| [edge.source,edge.target]}.each do |e| if classification[e].nil? k += 1 classification[e] = k; classification[e.reverse] = -k comparability &&= plexus_comparability_explore(e, k, classification) end end; [classification, comparability] end ```

### #transitive_orientation(digraph_class = Digraph) ⇒ Object

Returns one of the possible transitive orientations of the UndirectedGraph as a Digraph

Raises:

• (NotImplementError)
 ``` 29 30 31``` ```# File 'lib/plexus/comparability.rb', line 29 def transitive_orientation(digraph_class=Digraph) raise NotImplementError end ```