Class: Spoom::Poset

Inherits:
Object
  • Object
show all
Defined in:
lib/spoom/poset.rb

Overview

A Poset is a set of elements with a partial order relation.

The partial order relation is a binary relation that is reflexive, antisymmetric, and transitive. It can be used to represent a hierarchy of classes or modules, the dependencies between gems, etc.

Signature:

  • [E < Object]

Defined Under Namespace

Classes: Element, Error

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Poset

Returns a new instance of Poset.

Signature:

  • -> void



14
15
16
 
# File 'lib/spoom/poset.rb', line 14

def initialize
  @elements = {} #: Hash[E, Element[E]]
end

Instance Method Details

#[](value) ⇒ Object

Get the POSet element for a given value

Raises if the element is not found

Signature:

  • (E value) -> Element[E]

Raises:



22
23
24
25
26
27
 
# File 'lib/spoom/poset.rb', line 22

def [](value)
  element = @elements[value]
  raise Error, "POSet::Element not found for #{value}" unless element

  element
end

#add_direct_edge(from, to) ⇒ Object

Add a direct edge from one element to another

Transitive edges (transitive closure) are automatically computed. Adds the elements if they don't exist. If the direct edge already exists, nothing is done.

Signature:

  • (E from, E to) -> void



50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
# File 'lib/spoom/poset.rb', line 50

def add_direct_edge(from, to)
  from_element = add_element(from)
  to_element = add_element(to)

  # We already added this direct edge, which means we already computed the transitive closure
  return if from_element.parents.include?(to)

  # Add the direct edges
  from_element.dtos << to_element
  to_element.dfroms << from_element

  # Compute the transitive closure

  from_element.tos << to_element
  from_element.froms.each do |child_element|
    child_element.tos << to_element
    to_element.froms << child_element

    to_element.tos.each do |parent_element|
      parent_element.froms << child_element
      child_element.tos << parent_element
    end
  end

  to_element.froms << from_element
  to_element.tos.each do |parent_element|
    parent_element.froms << from_element
    from_element.tos << parent_element

    from_element.froms.each do |child_element|
      child_element.tos << parent_element
      parent_element.froms << child_element
    end
  end
end

#add_element(value) ⇒ Object

Add an element to the POSet

Signature:

  • (E value) -> Element[E]



31
32
33
34
35
36
 
# File 'lib/spoom/poset.rb', line 31

def add_element(value)
  element = @elements[value]
  return element if element

  @elements[value] = Element.new(value) #: Element[E]
end

#direct_edge?(from, to) ⇒ Boolean

Is there a direct edge from from to to?

Signature:

  • (E from, E to) -> bool

Returns:

  • (Boolean) 


97
98
99
 
# File 'lib/spoom/poset.rb', line 97

def direct_edge?(from, to)
  self[from].parents.include?(to)
end

#edge?(from, to) ⇒ Boolean

Is there an edge (direct or indirect) from from to to?

Signature:

  • (E from, E to) -> bool

Returns:

  • (Boolean) 


88
89
90
91
92
93
 
# File 'lib/spoom/poset.rb', line 88

def edge?(from, to)
  from_element = @elements[from]
  return false unless from_element

  from_element.ancestors.include?(to)
end

#element?(value) ⇒ Boolean

Is the given value a element in the POSet?

Signature:

  • (E value) -> bool

Returns:

  • (Boolean) 


40
41
42
 
# File 'lib/spoom/poset.rb', line 40

def element?(value)
  @elements.key?(value)
end

#show_dot(direct: true, transitive: true) ⇒ Object

Show the POSet as a DOT graph using xdot (used for debugging)

Signature:

  • (?direct: bool, ?transitive: bool) -> void



103
104
105
106
107
108
 
# File 'lib/spoom/poset.rb', line 103

def show_dot(direct: true, transitive: true)
  Open3.popen3("xdot -") do |stdin, _stdout, _stderr, _thread|
    stdin.write(to_dot(direct: direct, transitive: transitive))
    stdin.close
  end
end

#to_dot(direct: true, transitive: true) ⇒ Object

Return the POSet as a DOT graph

Signature:

  • (?direct: bool, ?transitive: bool) -> String



112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/spoom/poset.rb', line 112

def to_dot(direct: true, transitive: true)
  dot = +"digraph {\n"
  dot << "  rankdir=BT;\n"
  @elements.each do |value, element|
    dot << "  \"#{value}\";\n"
    if direct
      element.parents.each do |to|
        dot << "  \"#{value}\" -> \"#{to}\";\n"
      end
    end
    if transitive
      element.ancestors.each do |ancestor|
        dot << "  \"#{value}\" -> \"#{ancestor}\" [style=dotted];\n"
      end
    end
  end
  dot << "}\n"
end