1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2012 Jean Privat <jean@pryen.org>
5 # Licensed under the Apache License, Version 2.0 (the "License");
6 # you may not use this file except in compliance with the License.
7 # You may obtain a copy of the License at
9 # http://www.apache.org/licenses/LICENSE-2.0
11 # Unless required by applicable law or agreed to in writing, software
12 # distributed under the License is distributed on an "AS IS" BASIS,
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 # See the License for the specific language governing permissions and
15 # limitations under the License.
17 # Pre order sets and partial order set (ie hierarchies)
20 # Pre-order set graph.
21 # This class models an incremental pre-order graph where new nodes and edges can be added (but not removed).
22 # Pre-order graph has two characteristics:
23 # * reflexivity: an element is in relation with itself (ie `self.has(e) implies self.has_edge(e,e)`)
24 # * transitivity: `(self.has_edge(e,f) and self.has_edge(f,g)) implies self.has_edge(e,g)`
26 # Nodes and edges are added to the POSet.
29 # var pos = new POSet[String]
30 # pos.add_edge("A", "B") # add A->B
31 # pos.add_edge("B", "C") # add B->C
32 # pos.add_node("D") # add unconnected node "D"
36 # assert pos.has_edge("A", "B") == true # direct
39 # Since a poset is transitive, direct and indirect edges are considered by default.
40 # Direct edges (transitive-reduction) can also be considered independently.
43 # assert pos.has_edge("A", "C") == true # indirect
44 # assert pos.has_edge("A", "D") == false # no edge
45 # assert pos.has_edge("B", "A") == false # edges are directed
47 # assert pos.has_direct_edge("A", "B") == true # direct
48 # assert pos.has_direct_edge("A", "C") == false # indirect
52 # It means that the transitivity is updated while new nodes and edges are added.
53 # The transitive-reduction (*direct edges*)) is also updated,
54 # so adding new edges can make some direct edge to disappear.
57 # pos.add_edge("A","D")
58 # pos.add_edge("D","B")
59 # pos.add_edge("A","E")
60 # pos.add_edge("E","C")
67 # assert pos.has_edge("D", "C") == true # new indirect edge
68 # assert pos.has_edge("A", "B") == true # still an edge
69 # assert pos.has_direct_edge("A", "B") == false # but no-more a direct one
72 # Thanks to the `[]` method, elements can be considered relatively to the poset.
79 redef type COMPARED: E
is fixed
81 redef fun iterator
do return elements
.keys
.iterator
84 private var elements
= new HashMap[E
, POSetElement[E
]]
86 redef fun has
(e
) do return self.elements
.keys
.has
(e
)
88 # Add a node (an element) to the posed
89 # The new element is added unconnected to any other nodes (it is both a new root and a new leaf).
90 # Return the POSetElement associated to `e`.
91 # If `e` is already present in the POSet then just return the POSetElement (usually you will prefer []) is this case.
92 fun add_node
(e
: E
): POSetElement[E
]
94 if elements
.keys
.has
(e
) then return self.elements
[e
]
95 var poe
= new POSetElement[E
](self, e
, elements
.length
)
98 self.elements
[e
] = poe
102 # Return a view of `e` in the poset.
103 # This allows to view the elements in their relation with others elements.
105 # var poset = new POSet[String]
106 # poset.add_chain(["A", "B", "D"])
107 # poset.add_chain(["A", "C", "D"])
109 # assert a.direct_greaters.has_exactly(["B", "C"])
110 # assert a.greaters.has_exactly(["A", "B", "C", "D"])
111 # assert a.direct_smallers.is_empty
114 fun [](e
: E
): POSetElement[E
]
116 assert elements
.keys
.has
(e
)
117 return self.elements
[e
]
120 # Add an edge from `f` to `t`.
121 # Because a POSet is transitive, all transitive edges are also added to the graph.
122 # If the edge already exists, the this function does nothing.
125 # var pos = new POSet[String]
126 # pos.add_edge("A", "B") # add A->B
127 # assert pos.has_edge("A", "C") == false
128 # pos.add_edge("B", "C") # add B->C
129 # assert pos.has_edge("A", "C") == true
132 # If a reverse edge (from `t` to `f`) already exists, a loop is created.
134 # FIXME: Do something clever to manage loops.
135 fun add_edge
(f
, t
: E
)
139 # Skip if edge already present
140 if fe
.tos
.has
(t
) then return
141 # Add the edge and close the transitivity
142 for ff
in fe
.froms
do
143 var ffe
= self.elements
[ff
]
145 var tte
= self.elements
[tt
]
150 # Update the transitive reduction
151 if te
.tos
.has
(f
) then return # Skip the reduction if there is a loop
153 # Remove transitive edges.
154 # Because the sets of direct is iterated, the list of edges to remove
155 # is stored and is applied after the iteration.
156 # The usual case is that no direct edges need to be removed,
157 # so start with a `null` list of edges.
158 var to_remove
: nullable Array[E
] = null
159 for x
in te
.dfroms
do
160 var xe
= self.elements
[x
]
161 if xe
.tos
.has
(f
) then
162 if to_remove
== null then to_remove
= new Array[E
]
167 if to_remove
!= null then
168 for x
in to_remove
do te
.dfroms
.remove
(x
)
173 var xe
= self.elements
[x
]
174 if xe
.froms
.has
(t
) then
176 if to_remove
== null then to_remove
= new Array[E
]
180 if to_remove
!= null then
181 for x
in to_remove
do fe
.dtos
.remove
(x
)
188 # Add an edge between all elements of `es` in order.
191 # var pos = new POSet[String]
192 # pos.add_chain(["A", "B", "C", "D"])
193 # assert pos.has_direct_edge("A", "B")
194 # assert pos.has_direct_edge("B", "C")
195 # assert pos.has_direct_edge("C", "D")
197 fun add_chain
(es
: SequenceRead[E
])
199 if es
.is_empty
then return
209 # Is there an edge (transitive or not) from `f` to `t`?
213 # Since the POSet is reflexive, true is returned if `f == t`.
216 # var pos = new POSet[String]
218 # assert pos.has_edge("A", "A") == true
220 fun has_edge
(f
,t
: E
): Bool
222 if not elements
.keys
.has
(f
) then return false
223 var fe
= self.elements
[f
]
227 # Is there a direct edge from `f` to `t`?
230 # var pos = new POSet[String]
231 # pos.add_chain(["A", "B", "C"]) # add A->B->C
232 # assert pos.has_direct_edge("A", "B") == true
233 # assert pos.has_direct_edge("A", "C") == false
234 # assert pos.has_edge("A", "C") == true
237 # Note that because of loops, the result may not be the expected one.
238 fun has_direct_edge
(f
,t
: E
): Bool
240 if not elements
.keys
.has
(f
) then return false
241 var fe
= self.elements
[f
]
242 return fe
.dtos
.has
(t
)
245 # Write the POSet as a graphviz digraph.
247 # Nodes are labeled with their `to_s` so homonymous nodes may appear.
248 # Edges are unlabeled.
249 fun write_dot
(f
: Writer)
251 f
.write
"digraph \{\n"
252 var ids
= new HashMap[E
, Int]
253 for x
in elements
.keys
do
256 for x
in elements
.keys
do
257 var xstr
= x
.to_s
.escape_to_dot
259 f
.write
"{nx}[label=\"{xstr}\
"];\n"
260 var xe
= self.elements
[x
]
263 if self.has_edge
(y
,x
) then
264 f
.write
"{nx} -> {ny}[dir=both];\n"
266 f
.write
"{nx} -> {ny};\n"
273 # Display the POSet in a graphical windows.
274 # Graphviz with a working -Txlib is expected.
276 # See `write_dot` for details.
279 var f
= new ProcessWriter("dot", "-Txlib")
285 # Compare two elements in an arbitrary total order.
287 # This function is mainly used to sort elements of the set in an coherent way.
290 # var pos = new POSet[String]
291 # pos.add_chain(["A", "B", "C", "D", "E"])
292 # pos.add_chain(["A", "X", "C", "Y", "E"])
293 # var a = ["X", "C", "E", "A", "D"]
295 # assert a == ["E", "D", "C", "X", "A"]
298 # POSet are not necessarily total orders because some distinct elements may be incomparable (neither greater or smaller).
299 # Therefore this method relies on arbitrary linear extension.
300 # This linear extension is a lawful total order (transitive, anti-symmetric, reflexive, and total), so can be used to compare the elements.
302 # The abstract behavior of the method is thus the following:
305 # if a == b then return 0
306 # if has_edge(b, a) then return -1
307 # if has_edge(a, b) then return 1
308 # return -1 or 1 # according to the linear extension.
311 # Note that the linear extension is stable, unless a new node or a new edge is added.
312 redef fun compare
(a
, b
: E
): Int
314 var ae
= self.elements
[a
]
315 var be
= self.elements
[b
]
316 var res
= ae
.tos
.length
<=> be
.tos
.length
317 if res
!= 0 then return res
318 return elements
[a
].count
<=> elements
[b
].count
321 # Filter elements to return only the smallest ones
324 # var s = new POSet[String]
325 # s.add_edge("B", "A")
326 # s.add_edge("C", "A")
327 # s.add_edge("D", "B")
328 # s.add_edge("D", "C")
329 # assert s.select_smallest(["A", "B"]) == ["B"]
330 # assert s.select_smallest(["A", "B", "C"]) == ["B", "C"]
331 # assert s.select_smallest(["B", "C", "D"]) == ["D"]
333 fun select_smallest
(elements
: Collection[E
]): Array[E
]
335 var res
= new Array[E
]
338 if e
== f
then continue
339 if has_edge
(f
, e
) then continue label
346 # Filter elements to return only the greatest ones
349 # var s = new POSet[String]
350 # s.add_edge("B", "A")
351 # s.add_edge("C", "A")
352 # s.add_edge("D", "B")
353 # s.add_edge("D", "C")
354 # assert s.select_greatest(["A", "B"]) == ["A"]
355 # assert s.select_greatest(["A", "B", "C"]) == ["A"]
356 # assert s.select_greatest(["B", "C", "D"]) == ["B", "C"]
358 fun select_greatest
(elements
: Collection[E
]): Array[E
]
360 var res
= new Array[E
]
363 if e
== f
then continue
364 if has_edge
(e
, f
) then continue label
371 # Sort a sorted array of poset elements using linearization order
373 # var pos = new POSet[String]
374 # pos.add_chain(["A", "B", "C", "D", "E"])
375 # pos.add_chain(["A", "X", "C", "Y", "E"])
376 # var a = pos.linearize(["X", "C", "E", "A", "D"])
377 # assert a == ["E", "D", "C", "X", "A"]
379 fun linearize
(elements
: Collection[E
]): Array[E
] do
380 var lin
= elements
.to_a
385 redef fun clone
do return sub
(self)
387 # Return an induced sub-poset
389 # The elements of the result are those given in argument.
392 # var pos = new POSet[String]
393 # pos.add_chain(["A", "B", "C", "D", "E"])
394 # pos.add_chain(["A", "X", "C", "Y", "E"])
396 # var pos2 = pos.sub(["A", "B", "D", "Y", "E"])
397 # assert pos2.has_exactly(["A", "B", "D", "Y", "E"])
400 # The full relationship is preserved between the provided elements.
403 # for e1 in pos2 do for e2 in pos2 do
404 # assert pos2.has_edge(e1, e2) == pos.has_edge(e1, e2)
408 # Not that by definition, the direct relationship is the transitive
409 # reduction of the full reduction. Thus, the direct relationship of the
410 # sub-poset may not be included in the direct relationship of self because an
411 # indirect edge becomes a direct one if all the intermediates elements
412 # are absent in the sub-poset.
415 # assert pos.has_direct_edge("B", "D") == false
416 # assert pos2.has_direct_edge("B", "D") == true
418 # assert pos2["B"].direct_greaters.has_exactly(["D", "Y"])
421 # If the `elements` contains all then the result is a clone of self.
424 # var pos3 = pos.sub(pos)
426 # assert pos3 == pos.clone
428 fun sub
(elements
: Collection[E
]): POSet[E
]
430 var res
= new POSet[E
]
432 if not elements
.has
(e
) then continue
436 for f
in self[e
].greaters
do
437 if not elements
.has
(f
) then continue
444 # Two posets are equal if they contain the same elements and edges.
447 # var pos1 = new POSet[String]
448 # pos1.add_chain(["A", "B", "C", "D", "E"])
449 # pos1.add_chain(["A", "X", "C", "Y", "E"])
451 # var pos2 = new POSet[Object]
452 # pos2.add_edge("Y", "E")
453 # pos2.add_chain(["A", "X", "C", "D", "E"])
454 # pos2.add_chain(["A", "B", "C", "Y"])
456 # assert pos1 == pos2
458 # pos1.add_edge("D", "Y")
459 # assert pos1 != pos2
461 # pos2.add_edge("D", "Y")
462 # assert pos1 == pos2
465 # assert pos1 != pos2
467 redef fun ==(other
) do
468 if not other
isa POSet[nullable Object] then return false
469 if not self.elements
.keys
.has_exactly
(other
.elements
.keys
) then return false
470 for e
, ee
in elements
do
471 if ee
.direct_greaters
!= other
[e
].direct_greaters
then return false
473 assert hash
== other
.hash
480 for e
, ee
in elements
do
481 if e
== null then continue
483 res
+= ee
.direct_greaters
.length
489 # View of an objet in a poset
490 # This class is a helper to handle specific queries on a same object
492 # For instance, one common usage is to add a specific attribute for each poset a class belong.
496 # var in_some_relation: POSetElement[Thing]
497 # var in_other_relation: POSetElement[Thing]
501 # t.in_some_relation.greaters
503 class POSetElement[E
]
504 # The poset self belong to
507 # The real object behind the view
510 private var tos
= new HashSet[E
]
511 private var froms
= new HashSet[E
]
512 private var dtos
= new HashSet[E
]
513 private var dfroms
= new HashSet[E
]
516 # This attribute is used to force a total order for POSet#compare
517 private var count
: Int
519 # Return the set of all elements `t` that have an edge from `element` to `t`.
520 # Since the POSet is reflexive, element is included in the set.
523 # var pos = new POSet[String]
524 # pos.add_chain(["A", "B", "C", "D"])
525 # assert pos["B"].greaters.has_exactly(["B", "C", "D"])
527 fun greaters
: Collection[E
]
532 # Return the set of all elements `t` that have a direct edge from `element` to `t`.
535 # var pos = new POSet[String]
536 # pos.add_chain(["A", "B", "C", "D"])
537 # assert pos["B"].direct_greaters.has_exactly(["C"])
539 fun direct_greaters
: Collection[E
]
544 # Return the set of all elements `f` that have an edge from `f` to `element`.
545 # Since the POSet is reflexive, element is included in the set.
548 # var pos = new POSet[String]
549 # pos.add_chain(["A", "B", "C", "D"])
550 # assert pos["C"].smallers.has_exactly(["A", "B", "C"])
552 fun smallers
: Collection[E
]
557 # Return the set of all elements `f` that have an edge from `f` to `element`.
560 # var pos = new POSet[String]
561 # pos.add_chain(["A", "B", "C", "D"])
562 # assert pos["C"].direct_smallers.has_exactly(["B"])
564 fun direct_smallers
: Collection[E
]
569 # Is there an edge from `element` to `t`?
572 # var pos = new POSet[String]
573 # pos.add_chain(["A", "B", "C", "D"])
574 # assert pos["B"] <= "D"
575 # assert pos["B"] <= "C"
576 # assert pos["B"] <= "B"
577 # assert not pos["B"] <= "A"
581 return self.tos
.has
(t
)
584 # Is `t != element` and is there an edge from `element` to `t`?
587 # var pos = new POSet[String]
588 # pos.add_chain(["A", "B", "C", "D"])
589 # assert pos["B"] < "D"
590 # assert pos["B"] < "C"
591 # assert not pos["B"] < "B"
592 # assert not pos["B"] < "A"
596 return t
!= self.element
and self.tos
.has
(t
)
599 # The length of the shortest path to the root of the poset hierarchy
602 # var pos = new POSet[String]
603 # pos.add_chain(["A", "B", "C", "D"])
604 # assert pos["A"].depth == 3
605 # assert pos["D"].depth == 0
608 if direct_greaters
.is_empty
then
612 for p
in direct_greaters
do
613 var d
= poset
[p
].depth
+ 1
614 if min
== -1 or d
< min
then