lib/poset.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2012 Jean Privat <jean@pryen.org>
   4 #
   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
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  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.
  16
  17 # Pre order sets and partial order set (ie hierarchies)
  18 module poset
  19
  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)`
  25 #
  26 # Nodes and edges are added to the POSet.
  27 #
  28 # ~~~
  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"
  33 #
  34 # # A -> B -> C    D
  35 #
  36 # assert pos.has_edge("A", "B") == true  # direct
  37 # ~~~
  38 #
  39 # Since a poset is transitive, direct and indirect edges are considered by default.
  40 # Direct edges (transitive-reduction) can also be considered independently.
  41 #
  42 # ~~~
  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
  46 #
  47 # assert pos.has_direct_edge("A", "B") == true  # direct
  48 # assert pos.has_direct_edge("A", "C") == false # indirect
  49 # ~~~
  50 #
  51 # POSet are dynamic.
  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.
  55 #
  56 # ~~~
  57 # pos.add_edge("A","D")
  58 # pos.add_edge("D","B")
  59 # pos.add_edge("A","E")
  60 # pos.add_edge("E","C")
  61 #
  62 # # A -> D -> B
  63 # # |         |
  64 # # v         v
  65 # # E ------> C
  66 #
  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
  70 # ~~~
  71 #
  72 # Thanks to the `[]` method, elements can be considered relatively to the poset.
  73 # SEE `POSetElement`
  74 class POSet[E]
  75         super Collection[E]
  76         super Comparator
  77         super Cloneable
  78
  79         redef type COMPARED: E is fixed
  80
  81         redef fun iterator do return elements.keys.iterator
  82
  83         # All the nodes
  84         private var elements = new HashMap[E, POSetElement[E]]
  85
  86         redef fun has(e) do return self.elements.keys.has(e)
  87
  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]
  93         do
  94                 if elements.keys.has(e) then return self.elements[e]
  95                 var poe = new POSetElement[E](self, e, elements.length)
  96                 poe.tos.add(e)
  97                 poe.froms.add(e)
  98                 self.elements[e] = poe
  99                 return poe
 100         end
 101
 102         # Return a view of `e` in the poset.
 103         # This allows to view the elements in their relation with others elements.
 104         #
 105         #     var poset = new POSet[String]
 106         #     poset.add_chain(["A", "B", "D"])
 107         #     poset.add_chain(["A", "C", "D"])
 108         #     var a = poset["A"]
 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
 112         #
 113         # REQUIRE: has(e)
 114         fun [](e: E): POSetElement[E]
 115         do
 116                 assert elements.keys.has(e)
 117                 return self.elements[e]
 118         end
 119
 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.
 123         #
 124         # ~~~
 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
 130         # ~~~
 131         #
 132         # If a reverse edge (from `t` to `f`) already exists, a loop is created.
 133         #
 134         # FIXME: Do something clever to manage loops.
 135         fun add_edge(f, t: E)
 136         do
 137                 var fe = add_node(f)
 138                 var te = add_node(t)
 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]
 144                         for tt in te.tos do
 145                                 var tte = self.elements[tt]
 146                                 tte.froms.add ff
 147                                 ffe.tos.add tt
 148                         end
 149                 end
 150                 # Update the transitive reduction
 151                 if te.tos.has(f) then return # Skip the reduction if there is a loop
 152
 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]
 163                                 to_remove.add x
 164                                 xe.dtos.remove(t)
 165                         end
 166                 end
 167                 if to_remove != null then
 168                         for x in to_remove do te.dfroms.remove(x)
 169                         to_remove.clear
 170                 end
 171
 172                 for x in fe.dtos do
 173                         var xe = self.elements[x]
 174                         if xe.froms.has(t) then
 175                                 xe.dfroms.remove(f)
 176                                 if to_remove == null then to_remove = new Array[E]
 177                                 to_remove.add x
 178                         end
 179                 end
 180                 if to_remove != null then
 181                         for x in to_remove do fe.dtos.remove(x)
 182                 end
 183
 184                 fe.dtos.add t
 185                 te.dfroms.add f
 186         end
 187
 188         # Add an edge between all elements of `es` in order.
 189         #
 190         # ~~~~
 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")
 196         # ~~~~
 197         fun add_chain(es: SequenceRead[E])
 198         do
 199                 if es.is_empty then return
 200                 var i = es.iterator
 201                 var e = i.item
 202                 i.next
 203                 for f in i do
 204                         add_edge(e, f)
 205                         e = f
 206                 end
 207         end
 208
 209         # Is there an edge (transitive or not) from `f` to `t`?
 210         #
 211         # SEE: `add_edge`
 212         #
 213         # Since the POSet is reflexive, true is returned if `f == t`.
 214         #
 215         # ~~~
 216         # var pos = new POSet[String]
 217         # pos.add_node("A")
 218         # assert pos.has_edge("A", "A") == true
 219         # ~~~
 220         fun has_edge(f,t: E): Bool
 221         do
 222                 if not elements.keys.has(f) then return false
 223                 var fe = self.elements[f]
 224                 return fe.tos.has(t)
 225         end
 226
 227         # Is there a direct edge from `f` to `t`?
 228         #
 229         # ~~~
 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
 235         # ~~~
 236         #
 237         # Note that because of loops, the result may not be the expected one.
 238         fun has_direct_edge(f,t: E): Bool
 239         do
 240                 if not elements.keys.has(f) then return false
 241                 var fe = self.elements[f]
 242                 return fe.dtos.has(t)
 243         end
 244
 245         # Write the POSet as a graphviz digraph.
 246         #
 247         # Nodes are labeled with their `to_s` so homonymous nodes may appear.
 248         # Edges are unlabeled.
 249         fun write_dot(f: Writer)
 250         do
 251                 f.write "digraph \{\n"
 252                 var ids = new HashMap[E, Int]
 253                 for x in elements.keys do
 254                         ids[x] = ids.length
 255                 end
 256                 for x in elements.keys do
 257                         var xstr = x.to_s.escape_to_dot
 258                         var nx = "n{ids[x]}"
 259                         f.write "{nx}[label=\"{xstr}\"];\n"
 260                         var xe = self.elements[x]
 261                         for y in xe.dtos do
 262                                 var ny = "n{ids[y]}"
 263                                 if self.has_edge(y,x) then
 264                                         f.write "{nx} -> {ny}[dir=both];\n"
 265                                 else
 266                                         f.write "{nx} -> {ny};\n"
 267                                 end
 268                         end
 269                 end
 270                 f.write "\}\n"
 271         end
 272
 273         # Display the POSet in a graphical windows.
 274         # Graphviz with a working -Txlib is expected.
 275         #
 276         # See `write_dot` for details.
 277         fun show_dot
 278         do
 279                 var f = new ProcessWriter("dot", "-Txlib")
 280                 write_dot(f)
 281                 f.close
 282                 f.wait
 283         end
 284
 285         # Compare two elements in an arbitrary total order.
 286         #
 287         # This function is mainly used to sort elements of the set in an coherent way.
 288         #
 289         # ~~~~
 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"]
 294         # pos.sort(a)
 295         # assert a == ["E", "D", "C", "X", "A"]
 296         # ~~~~
 297         #
 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.
 301         #
 302         # The abstract behavior of the method is thus the following:
 303         #
 304         # ~~~~nitish
 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.
 309         # ~~~~
 310         #
 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
 313         do
 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
 319         end
 320
 321         # Filter elements to return only the smallest ones
 322         #
 323         # ~~~
 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"]
 332         # ~~~
 333         fun select_smallest(elements: Collection[E]): Array[E]
 334         do
 335                 var res = new Array[E]
 336                 for e in elements do
 337                         for f in elements do
 338                                 if e == f then continue
 339                                 if has_edge(f, e) then continue label
 340                         end
 341                         res.add(e)
 342                 end label
 343                 return res
 344         end
 345
 346         # Filter elements to return only the greatest ones
 347         #
 348         # ~~~
 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"]
 357         # ~~~
 358         fun select_greatest(elements: Collection[E]): Array[E]
 359         do
 360                 var res = new Array[E]
 361                 for e in elements do
 362                         for f in elements do
 363                                 if e == f then continue
 364                                 if has_edge(e, f) then continue label
 365                         end
 366                         res.add(e)
 367                 end label
 368                 return res
 369         end
 370
 371         # Sort a sorted array of poset elements using linearization order
 372         # ~~~~
 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"]
 378         # ~~~~
 379         fun linearize(elements: Collection[E]): Array[E] do
 380                 var lin = elements.to_a
 381                 sort(lin)
 382                 return lin
 383         end
 384
 385         redef fun clone do return sub(self)
 386
 387         # Return an induced sub-poset
 388         #
 389         # The elements of the result are those given in argument.
 390         #
 391         # ~~~
 392         # var pos = new POSet[String]
 393         # pos.add_chain(["A", "B", "C", "D", "E"])
 394         # pos.add_chain(["A", "X", "C", "Y", "E"])
 395         #
 396         # var pos2 = pos.sub(["A", "B", "D", "Y", "E"])
 397         # assert pos2.has_exactly(["A", "B", "D", "Y", "E"])
 398         # ~~~
 399         #
 400         # The full relationship is preserved between the provided elements.
 401         #
 402         # ~~~
 403         # for e1 in pos2 do for e2 in pos2 do
 404         #    assert pos2.has_edge(e1, e2) == pos.has_edge(e1, e2)
 405         # end
 406         # ~~~
 407         #
 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.
 413         #
 414         # ~~~
 415         # assert pos.has_direct_edge("B", "D")  == false
 416         # assert pos2.has_direct_edge("B", "D") == true
 417         #
 418         # assert pos2["B"].direct_greaters.has_exactly(["D", "Y"])
 419         # ~~~
 420         #
 421         # If the `elements` contains all then the result is a clone of self.
 422         #
 423         # ~~~
 424         # var pos3 = pos.sub(pos)
 425         # assert pos3 == pos
 426         # assert pos3 == pos.clone
 427         # ~~~
 428         fun sub(elements: Collection[E]): POSet[E]
 429         do
 430                 var res = new POSet[E]
 431                 for e in self do
 432                         if not elements.has(e) then continue
 433                         res.add_node(e)
 434                 end
 435                 for e in res do
 436                         for f in self[e].greaters do
 437                                 if not elements.has(f) then continue
 438                                 res.add_edge(e, f)
 439                         end
 440                 end
 441                 return res
 442         end
 443
 444         # Two posets are equal if they contain the same elements and edges.
 445         #
 446         # ~~~
 447         # var pos1 = new POSet[String]
 448         # pos1.add_chain(["A", "B", "C", "D", "E"])
 449         # pos1.add_chain(["A", "X", "C", "Y", "E"])
 450         #
 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"])
 455         #
 456         # assert pos1 == pos2
 457         #
 458         # pos1.add_edge("D", "Y")
 459         # assert pos1 != pos2
 460         #
 461         # pos2.add_edge("D", "Y")
 462         # assert pos1 == pos2
 463         #
 464         # pos1.add_node("Z")
 465         # assert pos1 != pos2
 466         # ~~~
 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
 472                 end
 473                 assert hash == other.hash
 474                 return true
 475         end
 476
 477         redef fun hash
 478         do
 479                 var res = 0
 480                 for e, ee in elements do
 481                         if e == null then continue
 482                         res += e.hash
 483                         res += ee.direct_greaters.length
 484                 end
 485                 return res
 486         end
 487 end
 488
 489 # View of an objet in a poset
 490 # This class is a helper to handle specific queries on a same object
 491 #
 492 # For instance, one common usage is to add a specific attribute for each poset a class belong.
 493 #
 494 # ~~~nitish
 495 # class Thing
 496 #     var in_some_relation: POSetElement[Thing]
 497 #     var in_other_relation: POSetElement[Thing]
 498 # end
 499 # var t: Thing
 500 # # ...
 501 # t.in_some_relation.greaters
 502 # ~~~
 503 class POSetElement[E]
 504         # The poset self belong to
 505         var poset: POSet[E]
 506
 507         # The real object behind the view
 508         var element: E
 509
 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]
 514
 515         # The rank of the
 516         # This attribute is used to force a total order for POSet#compare
 517         private var count: Int
 518
 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.
 521         #
 522         # ~~~~
 523         # var pos = new POSet[String]
 524         # pos.add_chain(["A", "B", "C", "D"])
 525         # assert pos["B"].greaters.has_exactly(["B", "C", "D"])
 526         # ~~~~
 527         fun greaters: Collection[E]
 528         do
 529                 return self.tos
 530         end
 531
 532         # Return the set of all elements `t` that have a direct edge from `element` to `t`.
 533         #
 534         # ~~~~
 535         # var pos = new POSet[String]
 536         # pos.add_chain(["A", "B", "C", "D"])
 537         # assert pos["B"].direct_greaters.has_exactly(["C"])
 538         # ~~~~
 539         fun direct_greaters: Collection[E]
 540         do
 541                 return self.dtos
 542         end
 543
 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.
 546         #
 547         # ~~~~
 548         # var pos = new POSet[String]
 549         # pos.add_chain(["A", "B", "C", "D"])
 550         # assert pos["C"].smallers.has_exactly(["A", "B", "C"])
 551         # ~~~~
 552         fun smallers: Collection[E]
 553         do
 554                 return self.froms
 555         end
 556
 557         # Return the set of all elements `f` that have an edge from `f` to `element`.
 558         #
 559         # ~~~~
 560         # var pos = new POSet[String]
 561         # pos.add_chain(["A", "B", "C", "D"])
 562         # assert pos["C"].direct_smallers.has_exactly(["B"])
 563         # ~~~~
 564         fun direct_smallers: Collection[E]
 565         do
 566                 return self.dfroms
 567         end
 568
 569         # Is there an edge from `element` to `t`?
 570         #
 571         # ~~~~
 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"
 578         # ~~~~
 579         fun <=(t: E): Bool
 580         do
 581                 return self.tos.has(t)
 582         end
 583
 584         # Is `t != element` and is there an edge from `element` to `t`?
 585         #
 586         # ~~~~
 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"
 593         # ~~~~
 594         fun <(t: E): Bool
 595         do
 596                 return t != self.element and self.tos.has(t)
 597         end
 598
 599         # The length of the shortest path to the root of the poset hierarchy
 600         #
 601         # ~~~~
 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
 606         # ~~~~
 607         fun depth: Int do
 608                 if direct_greaters.is_empty then
 609                         return 0
 610                 end
 611                 var min = -1
 612                 for p in direct_greaters do
 613                         var d = poset[p].depth + 1
 614                         if min == -1 or d < min then
 615                                 min = d
 616                         end
 617                 end
 618                 return min
 619
 620         end
 621 end