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
  78         redef type COMPARED: E is fixed
  79
  80         redef fun iterator do return elements.keys.iterator
  81
  82         # All the nodes
  83         private var elements = new HashMap[E, POSetElement[E]]
  84
  85         redef fun has(e) do return self.elements.keys.has(e)
  86
  87         # Add a node (an element) to the posed
  88         # The new element is added unconnected to any other nodes (it is both a new root and a new leaf).
  89         # Return the POSetElement associated to `e`.
  90         # If `e` is already present in the POSet then just return the POSetElement (usually you will prefer []) is this case.
  91         fun add_node(e: E): POSetElement[E]
  92         do
  93                 if elements.keys.has(e) then return self.elements[e]
  94                 var poe = new POSetElement[E](self, e, elements.length)
  95                 poe.tos.add(e)
  96                 poe.froms.add(e)
  97                 self.elements[e] = poe
  98                 return poe
  99         end
 100
 101         # Return a view of `e` in the poset.
 102         # This allows to view the elements in their relation with others elements.
 103         #
 104         #     var poset = new POSet[String]
 105         #     poset.add_chain(["A", "B", "D"])
 106         #     poset.add_chain(["A", "C", "D"])
 107         #     var a = poset["A"]
 108         #     assert a.direct_greaters.has_exactly(["B", "C"])
 109         #     assert a.greaters.has_exactly(["A", "B", "C", "D"])
 110         #     assert a.direct_smallers.is_empty
 111         #
 112         # REQUIRE: has(e)
 113         fun [](e: E): POSetElement[E]
 114         do
 115                 assert elements.keys.has(e)
 116                 return self.elements[e]
 117         end
 118
 119         # Add an edge from `f` to `t`.
 120         # Because a POSet is transitive, all transitive edges are also added to the graph.
 121         # If the edge already exists, the this function does nothing.
 122         #
 123         # ~~~
 124         # var pos = new POSet[String]
 125         # pos.add_edge("A", "B") # add A->B
 126         # assert pos.has_edge("A", "C") == false
 127         # pos.add_edge("B", "C") # add B->C
 128         # assert pos.has_edge("A", "C") == true
 129         # ~~~
 130         #
 131         # If a reverse edge (from `t` to `f`) already exists, a loop is created.
 132         #
 133         # FIXME: Do something clever to manage loops.
 134         fun add_edge(f, t: E)
 135         do
 136                 var fe = add_node(f)
 137                 var te = add_node(t)
 138                 # Skip if edge already present
 139                 if fe.tos.has(t) then return
 140                 # Add the edge and close the transitivity
 141                 for ff in fe.froms do
 142                         var ffe = self.elements[ff]
 143                         for tt in te.tos do
 144                                 var tte = self.elements[tt]
 145                                 tte.froms.add ff
 146                                 ffe.tos.add tt
 147                         end
 148                 end
 149                 # Update the transitive reduction
 150                 if te.tos.has(f) then return # Skip the reduction if there is a loop
 151
 152                 # Remove transitive edges.
 153                 # Because the sets of direct is iterated, the list of edges to remove
 154                 # is stored and is applied after the iteration.
 155                 # The usual case is that no direct edges need to be removed,
 156                 # so start with a `null` list of edges.
 157                 var to_remove: nullable Array[E] = null
 158                 for x in te.dfroms do
 159                         var xe = self.elements[x]
 160                         if xe.tos.has(f) then
 161                                 if to_remove == null then to_remove = new Array[E]
 162                                 to_remove.add x
 163                                 xe.dtos.remove(t)
 164                         end
 165                 end
 166                 if to_remove != null then
 167                         for x in to_remove do te.dfroms.remove(x)
 168                         to_remove.clear
 169                 end
 170
 171                 for x in fe.dtos do
 172                         var xe = self.elements[x]
 173                         if xe.froms.has(t) then
 174                                 xe.dfroms.remove(f)
 175                                 if to_remove == null then to_remove = new Array[E]
 176                                 to_remove.add x
 177                         end
 178                 end
 179                 if to_remove != null then
 180                         for x in to_remove do fe.dtos.remove(x)
 181                 end
 182
 183                 fe.dtos.add t
 184                 te.dfroms.add f
 185         end
 186
 187         # Add an edge between all elements of `es` in order.
 188         #
 189         # ~~~~
 190         # var pos = new POSet[String]
 191         # pos.add_chain(["A", "B", "C", "D"])
 192         # assert pos.has_direct_edge("A", "B")
 193         # assert pos.has_direct_edge("B", "C")
 194         # assert pos.has_direct_edge("C", "D")
 195         # ~~~~
 196         fun add_chain(es: SequenceRead[E])
 197         do
 198                 if es.is_empty then return
 199                 var i = es.iterator
 200                 var e = i.item
 201                 i.next
 202                 for f in i do
 203                         add_edge(e, f)
 204                         e = f
 205                 end
 206         end
 207
 208         # Is there an edge (transitive or not) from `f` to `t`?
 209         #
 210         # SEE: `add_edge`
 211         #
 212         # Since the POSet is reflexive, true is returned if `f == t`.
 213         #
 214         # ~~~
 215         # var pos = new POSet[String]
 216         # pos.add_node("A")
 217         # assert pos.has_edge("A", "A") == true
 218         # ~~~
 219         fun has_edge(f,t: E): Bool
 220         do
 221                 if not elements.keys.has(f) then return false
 222                 var fe = self.elements[f]
 223                 return fe.tos.has(t)
 224         end
 225
 226         # Is there a direct edge from `f` to `t`?
 227         #
 228         # ~~~
 229         # var pos = new POSet[String]
 230         # pos.add_chain(["A", "B", "C"]) # add A->B->C
 231         # assert pos.has_direct_edge("A", "B") == true
 232         # assert pos.has_direct_edge("A", "C") == false
 233         # assert pos.has_edge("A", "C")        == true
 234         # ~~~
 235         #
 236         # Note that because of loops, the result may not be the expected one.
 237         fun has_direct_edge(f,t: E): Bool
 238         do
 239                 if not elements.keys.has(f) then return false
 240                 var fe = self.elements[f]
 241                 return fe.dtos.has(t)
 242         end
 243
 244         # Write the POSet as a graphviz digraph.
 245         #
 246         # Nodes are labeled with their `to_s` so homonymous nodes may appear.
 247         # Edges are unlabeled.
 248         fun write_dot(f: Writer)
 249         do
 250                 f.write "digraph \{\n"
 251                 var ids = new HashMap[E, Int]
 252                 for x in elements.keys do
 253                         ids[x] = ids.length
 254                 end
 255                 for x in elements.keys do
 256                         var xstr = x.to_s.escape_to_dot
 257                         var nx = "n{ids[x]}"
 258                         f.write "{nx}[label=\"{xstr}\"];\n"
 259                         var xe = self.elements[x]
 260                         for y in xe.dtos do
 261                                 var ny = "n{ids[y]}"
 262                                 if self.has_edge(y,x) then
 263                                         f.write "{nx} -> {ny}[dir=both];\n"
 264                                 else
 265                                         f.write "{nx} -> {ny};\n"
 266                                 end
 267                         end
 268                 end
 269                 f.write "\}\n"
 270         end
 271
 272         # Display the POSet in a graphical windows.
 273         # Graphviz with a working -Txlib is expected.
 274         #
 275         # See `write_dot` for details.
 276         fun show_dot
 277         do
 278                 var f = new ProcessWriter("dot", "-Txlib")
 279                 write_dot(f)
 280                 f.close
 281                 f.wait
 282         end
 283
 284         # Compare two elements in an arbitrary total order.
 285         #
 286         # This function is mainly used to sort elements of the set in an coherent way.
 287         #
 288         # ~~~~
 289         # var pos = new POSet[String]
 290         # pos.add_chain(["A", "B", "C", "D", "E"])
 291         # pos.add_chain(["A", "X", "C", "Y", "E"])
 292         # var a = ["X", "C", "E", "A", "D"]
 293         # pos.sort(a)
 294         # assert a == ["E", "D", "C", "X", "A"]
 295         # ~~~~
 296         #
 297         # POSet are not necessarily total orders because some distinct elements may be incomparable (neither greater or smaller).
 298         # Therefore this method relies on arbitrary linear extension.
 299         # This linear extension is a lawful total order (transitive, anti-symmetric, reflexive, and total), so can be used to compare the elements.
 300         #
 301         # The abstract behavior of the method is thus the following:
 302         #
 303         # ~~~~nitish
 304         # if a == b then return 0
 305         # if has_edge(b, a) then return -1
 306         # if has_edge(a, b) then return 1
 307         # return -1 or 1 # according to the linear extension.
 308         # ~~~~
 309         #
 310         # Note that the linear extension is stable, unless a new node or a new edge is added.
 311         redef fun compare(a, b: E): Int
 312         do
 313                 var ae = self.elements[a]
 314                 var be = self.elements[b]
 315                 var res = ae.tos.length <=> be.tos.length
 316                 if res != 0 then return res
 317                 return elements[a].count <=> elements[b].count
 318         end
 319
 320         # Filter elements to return only the smallest ones
 321         #
 322         # ~~~
 323         # var s = new POSet[String]
 324         # s.add_edge("B", "A")
 325         # s.add_edge("C", "A")
 326         # s.add_edge("D", "B")
 327         # s.add_edge("D", "C")
 328         # assert s.select_smallest(["A", "B"]) == ["B"]
 329         # assert s.select_smallest(["A", "B", "C"]) == ["B", "C"]
 330         # assert s.select_smallest(["B", "C", "D"]) == ["D"]
 331         # ~~~
 332         fun select_smallest(elements: Collection[E]): Array[E]
 333         do
 334                 var res = new Array[E]
 335                 for e in elements do
 336                         for f in elements do
 337                                 if e == f then continue
 338                                 if has_edge(f, e) then continue label
 339                         end
 340                         res.add(e)
 341                 end label
 342                 return res
 343         end
 344
 345         # Filter elements to return only the greatest ones
 346         #
 347         # ~~~
 348         # var s = new POSet[String]
 349         # s.add_edge("B", "A")
 350         # s.add_edge("C", "A")
 351         # s.add_edge("D", "B")
 352         # s.add_edge("D", "C")
 353         # assert s.select_greatest(["A", "B"]) == ["A"]
 354         # assert s.select_greatest(["A", "B", "C"]) == ["A"]
 355         # assert s.select_greatest(["B", "C", "D"]) == ["B", "C"]
 356         # ~~~
 357         fun select_greatest(elements: Collection[E]): Array[E]
 358         do
 359                 var res = new Array[E]
 360                 for e in elements do
 361                         for f in elements do
 362                                 if e == f then continue
 363                                 if has_edge(e, f) then continue label
 364                         end
 365                         res.add(e)
 366                 end label
 367                 return res
 368         end
 369
 370         # Sort a sorted array of poset elements using linearization order
 371         # ~~~~
 372         # var pos = new POSet[String]
 373         # pos.add_chain(["A", "B", "C", "D", "E"])
 374         # pos.add_chain(["A", "X", "C", "Y", "E"])
 375         # var a = pos.linearize(["X", "C", "E", "A", "D"])
 376         # assert a == ["E", "D", "C", "X", "A"]
 377         # ~~~~
 378         fun linearize(elements: Collection[E]): Array[E] do
 379                 var lin = elements.to_a
 380                 sort(lin)
 381                 return lin
 382         end
 383 end
 384
 385 # View of an objet in a poset
 386 # This class is a helper to handle specific queries on a same object
 387 #
 388 # For instance, one common usage is to add a specific attribute for each poset a class belong.
 389 #
 390 # ~~~nitish
 391 # class Thing
 392 #     var in_some_relation: POSetElement[Thing]
 393 #     var in_other_relation: POSetElement[Thing]
 394 # end
 395 # var t: Thing
 396 # # ...
 397 # t.in_some_relation.greaters
 398 # ~~~
 399 class POSetElement[E]
 400         # The poset self belong to
 401         var poset: POSet[E]
 402
 403         # The real object behind the view
 404         var element: E
 405
 406         private var tos = new HashSet[E]
 407         private var froms = new HashSet[E]
 408         private var dtos = new HashSet[E]
 409         private var dfroms = new HashSet[E]
 410
 411         # The rank of the
 412         # This attribute is used to force a total order for POSet#compare
 413         private var count: Int
 414
 415         # Return the set of all elements `t` that have an edge from `element` to `t`.
 416         # Since the POSet is reflexive, element is included in the set.
 417         #
 418         # ~~~~
 419         # var pos = new POSet[String]
 420         # pos.add_chain(["A", "B", "C", "D"])
 421         # assert pos["B"].greaters.has_exactly(["B", "C", "D"])
 422         # ~~~~
 423         fun greaters: Collection[E]
 424         do
 425                 return self.tos
 426         end
 427
 428         # Return the set of all elements `t` that have a direct edge from `element` to `t`.
 429         #
 430         # ~~~~
 431         # var pos = new POSet[String]
 432         # pos.add_chain(["A", "B", "C", "D"])
 433         # assert pos["B"].direct_greaters.has_exactly(["C"])
 434         # ~~~~
 435         fun direct_greaters: Collection[E]
 436         do
 437                 return self.dtos
 438         end
 439
 440         # Return the set of all elements `f` that have an edge from `f` to `element`.
 441         # Since the POSet is reflexive, element is included in the set.
 442         #
 443         # ~~~~
 444         # var pos = new POSet[String]
 445         # pos.add_chain(["A", "B", "C", "D"])
 446         # assert pos["C"].smallers.has_exactly(["A", "B", "C"])
 447         # ~~~~
 448         fun smallers: Collection[E]
 449         do
 450                 return self.froms
 451         end
 452
 453         # Return the set of all elements `f` that have an edge from `f` to `element`.
 454         #
 455         # ~~~~
 456         # var pos = new POSet[String]
 457         # pos.add_chain(["A", "B", "C", "D"])
 458         # assert pos["C"].direct_smallers.has_exactly(["B"])
 459         # ~~~~
 460         fun direct_smallers: Collection[E]
 461         do
 462                 return self.dfroms
 463         end
 464
 465         # Is there an edge from `element` to `t`?
 466         #
 467         # ~~~~
 468         # var pos = new POSet[String]
 469         # pos.add_chain(["A", "B", "C", "D"])
 470         # assert     pos["B"] <= "D"
 471         # assert     pos["B"] <= "C"
 472         # assert     pos["B"] <= "B"
 473         # assert not pos["B"] <= "A"
 474         # ~~~~
 475         fun <=(t: E): Bool
 476         do
 477                 return self.tos.has(t)
 478         end
 479
 480         # Is `t != element` and is there an edge from `element` to `t`?
 481         #
 482         # ~~~~
 483         # var pos = new POSet[String]
 484         # pos.add_chain(["A", "B", "C", "D"])
 485         # assert     pos["B"] < "D"
 486         # assert     pos["B"] < "C"
 487         # assert not pos["B"] < "B"
 488         # assert not pos["B"] < "A"
 489         # ~~~~
 490         fun <(t: E): Bool
 491         do
 492                 return t != self.element and self.tos.has(t)
 493         end
 494
 495         # The length of the shortest path to the root of the poset hierarchy
 496         #
 497         # ~~~~
 498         # var pos = new POSet[String]
 499         # pos.add_chain(["A", "B", "C", "D"])
 500         # assert pos["A"].depth == 3
 501         # assert pos["D"].depth == 0
 502         # ~~~~
 503         fun depth: Int do
 504                 if direct_greaters.is_empty then
 505                         return 0
 506                 end
 507                 var min = -1
 508                 for p in direct_greaters do
 509                         var d = poset[p].depth + 1
 510                         if min == -1 or d < min then
 511                                 min = d
 512                         end
 513                 end
 514                 return min
 515
 516         end
 517 end