Module: GRATR::Graph::Comparability

Included in:
UndirectedGraph
Defined in:
lib/gratr/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) 


35
 
# File 'lib/gratr/comparability.rb', line 35

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



44
45
46
47
48
49
50
51
52
53
 
# File 'lib/gratr/comparability.rb', line 44

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 &&= gratr_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) 


57
58
59
 
# File 'lib/gratr/comparability.rb', line 57

def transitive_orientation(digraph_class=Digraph)
  raise NotImplementError
end