Module: Plexus::Comparability

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

Instance Method Summary collapse

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[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

Raises:

  • (NotImplementError) 


29
30
31
 
# File 'lib/plexus/comparability.rb', line 29

def transitive_orientation(digraph_class=Digraph)
  raise NotImplementError
end