Module: Plexus::Comparability
 Included in:
 UndirectedGraphBuilder::Algorithms
 Defined in:
 lib/plexus/comparability.rb
Instance Method Summary collapse

#comparability? ⇒ Boolean
A comparability graph is an UndirectedGraph that has a transitive orientation.

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

#transitive_orientation(digraph_class = Digraph) ⇒ Object
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.
7 
# File 'lib/plexus/comparability.rb', line 7 def comparability?() gamma_decomposition[1]; 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
29 30 31 
# File 'lib/plexus/comparability.rb', line 29 def transitive_orientation(digraph_class=Digraph) raise NotImplementError end 