Class: Spoom::Poset

Inherits:
Object
  • Object
show all
Extended by:
T::Generic, T::Sig
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.

Defined Under Namespace

Classes: Element, Error

Constant Summary collapse

E = 
type_member { { upper: Object } }

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Poset

Returns a new instance of Poset.



18
19
20
 
# File 'lib/spoom/poset.rb', line 18

def initialize
  @elements = T.let({}, T::Hash[E, Element[E]])
end

Instance Method Details

#[](value) ⇒ Object

Raises:



26
27
28
29
30
31
 
# File 'lib/spoom/poset.rb', line 26

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

  element
end

#add_direct_edge(from, to) ⇒ Object 



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
85
86
87
88
 
# File 'lib/spoom/poset.rb', line 54

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 



35
36
37
38
39
40
 
# File 'lib/spoom/poset.rb', line 35

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

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

#direct_edge?(from, to) ⇒ Boolean

Returns:

  • (Boolean) 


101
102
103
 
# File 'lib/spoom/poset.rb', line 101

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

#edge?(from, to) ⇒ Boolean

Returns:

  • (Boolean) 


92
93
94
95
96
97
 
# File 'lib/spoom/poset.rb', line 92

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

  from_element.ancestors.include?(to)
end

#element?(value) ⇒ Boolean

Returns:

  • (Boolean) 


44
45
46
 
# File 'lib/spoom/poset.rb', line 44

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

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



107
108
109
110
111
112
 
# File 'lib/spoom/poset.rb', line 107

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 



116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
# File 'lib/spoom/poset.rb', line 116

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 # rubocop:disable Style/Next
      element.ancestors.each do |ancestor|
        dot << "  \"#{value}\" -> \"#{ancestor}\" [style=dotted];\n"
      end
    end
  end
  dot << "}\n"
end