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: Object]
  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                 for x in te.dfroms.to_a do
 153                         var xe = self.elements[x]
 154                         if xe.tos.has(f) then
 155                                 te.dfroms.remove(x)
 156                                 xe.dtos.remove(t)
 157                         end
 158                 end
 159                 for x in fe.dtos.to_a do
 160                         var xe = self.elements[x]
 161                         if xe.froms.has(t) then
 162                                 xe.dfroms.remove(f)
 163                                 fe.dtos.remove(x)
 164                         end
 165                 end
 166                 fe.dtos.add t
 167                 te.dfroms.add f
 168         end
 169
 170         # Add an edge between all elements of `es` in order.
 171         #
 172         # ~~~~
 173         # var pos = new POSet[String]
 174         # pos.add_chain(["A", "B", "C", "D"])
 175         # assert pos.has_direct_edge("A", "B")
 176         # assert pos.has_direct_edge("B", "C")
 177         # assert pos.has_direct_edge("C", "D")
 178         # ~~~~
 179         fun add_chain(es: SequenceRead[E])
 180         do
 181                 if es.is_empty then return
 182                 var i = es.iterator
 183                 var e = i.item
 184                 i.next
 185                 for f in i do
 186                         add_edge(e, f)
 187                         e = f
 188                 end
 189         end
 190
 191         # Is there an edge (transitive or not) from `f` to `t`?
 192         #
 193         # SEE: `add_edge`
 194         #
 195         # Since the POSet is reflexive, true is returned if `f == t`.
 196         #
 197         # ~~~
 198         # var pos = new POSet[String]
 199         # pos.add_node("A")
 200         # assert pos.has_edge("A", "A") == true
 201         # ~~~
 202         fun has_edge(f,t: E): Bool
 203         do
 204                 if not elements.keys.has(f) then return false
 205                 var fe = self.elements[f]
 206                 return fe.tos.has(t)
 207         end
 208
 209         # Is there a direct edge from `f` to `t`?
 210         #
 211         # ~~~
 212         # var pos = new POSet[String]
 213         # pos.add_chain(["A", "B", "C"]) # add A->B->C
 214         # assert pos.has_direct_edge("A", "B") == true
 215         # assert pos.has_direct_edge("A", "C") == false
 216         # assert pos.has_edge("A", "C")        == true
 217         # ~~~
 218         #
 219         # Note that because of loops, the result may not be the expected one.
 220         fun has_direct_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.dtos.has(t)
 225         end
 226
 227         # Write the POSet as a graphviz digraph.
 228         #
 229         # Nodes are identified with their `to_s`.
 230         # Edges are unlabeled.
 231         fun write_dot(f: OStream)
 232         do
 233                 f.write "digraph \{\n"
 234                 for x in elements.keys do
 235                         var xstr = x.to_s.escape_to_dot
 236                         f.write "\"{xstr}\";\n"
 237                         var xe = self.elements[x]
 238                         for y in xe.dtos do
 239                                 var ystr = y.to_s.escape_to_dot
 240                                 if self.has_edge(y,x) then
 241                                         f.write "\"{xstr}\" -> \"{ystr}\"[dir=both];\n"
 242                                 else
 243                                         f.write "\"{xstr}\" -> \"{ystr}\";\n"
 244                                 end
 245                         end
 246                 end
 247                 f.write "\}\n"
 248         end
 249
 250         # Display the POSet in a graphical windows.
 251         # Graphviz with a working -Txlib is expected.
 252         #
 253         # See `write_dot` for details.
 254         fun show_dot
 255         do
 256                 var f = new OProcess("dot", "-Txlib")
 257                 f.write "\}\n"
 258                 write_dot(f)
 259                 f.close
 260                 f.wait
 261         end
 262
 263         # Compare two elements in an arbitrary total order.
 264         #
 265         # This function is mainly used to sort elements of the set in an coherent way.
 266         #
 267         # ~~~~
 268         # var pos = new POSet[String]
 269         # pos.add_chain(["A", "B", "C", "D", "E"])
 270         # pos.add_chain(["A", "X", "C", "Y", "E"])
 271         # var a = ["X", "C", "E", "A", "D"]
 272         # pos.sort(a)
 273         # assert a == ["E", "D", "C", "X", "A"]
 274         # ~~~~
 275         #
 276         # POSet are not necessarily total orders because some distinct elements may be incomparable (neither greater or smaller).
 277         # Therefore this method relies on arbitrary linear extension.
 278         # This linear extension is a lawful total order (transitive, anti-symmetric, reflexive, and total), so can be used to compare the elements.
 279         #
 280         # The abstract behavior of the method is thus the following:
 281         #
 282         # ~~~~nitish
 283         # if a == b then return 0
 284         # if has_edge(b, a) then return -1
 285         # if has_edge(a, b) then return 1
 286         # return -1 or 1 # according to the linear extension.
 287         # ~~~~
 288         #
 289         # Note that the linear extension is stable, unless a new node or a new edge is added.
 290         redef fun compare(a, b: E): Int
 291         do
 292                 var ae = self.elements[a]
 293                 var be = self.elements[b]
 294                 var res = ae.tos.length <=> be.tos.length
 295                 if res != 0 then return res
 296                 return elements[a].count <=> elements[b].count
 297         end
 298
 299         # Filter elements to return only the smallest ones
 300         #
 301         # ~~~
 302         # var s = new POSet[String]
 303         # s.add_edge("B", "A")
 304         # s.add_edge("C", "A")
 305         # s.add_edge("D", "B")
 306         # s.add_edge("D", "C")
 307         # assert s.select_smallest(["A", "B"]) == ["B"]
 308         # assert s.select_smallest(["A", "B", "C"]) == ["B", "C"]
 309         # assert s.select_smallest(["B", "C", "D"]) == ["D"]
 310         # ~~~
 311         fun select_smallest(elements: Collection[E]): Array[E]
 312         do
 313                 var res = new Array[E]
 314                 for e in elements do
 315                         for f in elements do
 316                                 if e == f then continue
 317                                 if has_edge(f, e) then continue label
 318                         end
 319                         res.add(e)
 320                 end label
 321                 return res
 322         end
 323
 324         # Filter elements to return only the greatest ones
 325         #
 326         # ~~~
 327         # var s = new POSet[String]
 328         # s.add_edge("B", "A")
 329         # s.add_edge("C", "A")
 330         # s.add_edge("D", "B")
 331         # s.add_edge("D", "C")
 332         # assert s.select_greatest(["A", "B"]) == ["A"]
 333         # assert s.select_greatest(["A", "B", "C"]) == ["A"]
 334         # assert s.select_greatest(["B", "C", "D"]) == ["B", "C"]
 335         # ~~~
 336         fun select_greatest(elements: Collection[E]): Array[E]
 337         do
 338                 var res = new Array[E]
 339                 for e in elements do
 340                         for f in elements do
 341                                 if e == f then continue
 342                                 if has_edge(e, f) then continue label
 343                         end
 344                         res.add(e)
 345                 end label
 346                 return res
 347         end
 348
 349         # Sort a sorted array of poset elements using linearization order
 350         # ~~~~
 351         # var pos = new POSet[String]
 352         # pos.add_chain(["A", "B", "C", "D", "E"])
 353         # pos.add_chain(["A", "X", "C", "Y", "E"])
 354         # var a = pos.linearize(["X", "C", "E", "A", "D"])
 355         # assert a == ["E", "D", "C", "X", "A"]
 356         # ~~~~
 357         fun linearize(elements: Collection[E]): Array[E] do
 358                 var lin = elements.to_a
 359                 sort(lin)
 360                 return lin
 361         end
 362 end
 363
 364 # View of an objet in a poset
 365 # This class is a helper to handle specific queries on a same object
 366 #
 367 # For instance, one common usage is to add a specific attribute for each poset a class belong.
 368 #
 369 #     class Thing
 370 #         var in_some_relation: POSetElement[Thing]
 371 #         var in_other_relation: POSetElement[Thing]
 372 #     end
 373 #     var t: Thing # ...
 374 #     t.in_some_relation.greaters
 375 #
 376 class POSetElement[E: Object]
 377         # The poset self belong to
 378         var poset: POSet[E]
 379
 380         # The real object behind the view
 381         var element: E
 382
 383         private var tos = new HashSet[E]
 384         private var froms = new HashSet[E]
 385         private var dtos = new HashSet[E]
 386         private var dfroms = new HashSet[E]
 387
 388         # The rank of the
 389         # This attribute is used to force a total order for POSet#compare
 390         private var count: Int
 391
 392         # Return the set of all elements `t` that have an edge from `element` to `t`.
 393         # Since the POSet is reflexive, element is included in the set.
 394         #
 395         # ~~~~
 396         # var pos = new POSet[String]
 397         # pos.add_chain(["A", "B", "C", "D"])
 398         # assert pos["B"].greaters.has_exactly(["B", "C", "D"])
 399         # ~~~~
 400         fun greaters: Collection[E]
 401         do
 402                 return self.tos
 403         end
 404
 405         # Return the set of all elements `t` that have a direct edge from `element` to `t`.
 406         #
 407         # ~~~~
 408         # var pos = new POSet[String]
 409         # pos.add_chain(["A", "B", "C", "D"])
 410         # assert pos["B"].direct_greaters.has_exactly(["C"])
 411         # ~~~~
 412         fun direct_greaters: Collection[E]
 413         do
 414                 return self.dtos
 415         end
 416
 417         # Return the set of all elements `f` that have an edge from `f` to `element`.
 418         # Since the POSet is reflexive, element is included in the set.
 419         #
 420         # ~~~~
 421         # var pos = new POSet[String]
 422         # pos.add_chain(["A", "B", "C", "D"])
 423         # assert pos["C"].smallers.has_exactly(["A", "B", "C"])
 424         # ~~~~
 425         fun smallers: Collection[E]
 426         do
 427                 return self.froms
 428         end
 429
 430         # Return the set of all elements `f` that have an edge from `f` to `element`.
 431         #
 432         # ~~~~
 433         # var pos = new POSet[String]
 434         # pos.add_chain(["A", "B", "C", "D"])
 435         # assert pos["C"].direct_smallers.has_exactly(["B"])
 436         # ~~~~
 437         fun direct_smallers: Collection[E]
 438         do
 439                 return self.dfroms
 440         end
 441
 442         # Is there an edge from `element` to `t`?
 443         #
 444         # ~~~~
 445         # var pos = new POSet[String]
 446         # pos.add_chain(["A", "B", "C", "D"])
 447         # assert     pos["B"] <= "D"
 448         # assert     pos["B"] <= "C"
 449         # assert     pos["B"] <= "B"
 450         # assert not pos["B"] <= "A"
 451         # ~~~~
 452         fun <=(t: E): Bool
 453         do
 454                 return self.tos.has(t)
 455         end
 456
 457         # Is `t != element` and is there an edge from `element` to `t`?
 458         #
 459         # ~~~~
 460         # var pos = new POSet[String]
 461         # pos.add_chain(["A", "B", "C", "D"])
 462         # assert     pos["B"] < "D"
 463         # assert     pos["B"] < "C"
 464         # assert not pos["B"] < "B"
 465         # assert not pos["B"] < "A"
 466         # ~~~~
 467         fun <(t: E): Bool
 468         do
 469                 return t != self.element and self.tos.has(t)
 470         end
 471
 472         # The length of the shortest path to the root of the poset hierarchy
 473         #
 474         # ~~~~
 475         # var pos = new POSet[String]
 476         # pos.add_chain(["A", "B", "C", "D"])
 477         # assert pos["A"].depth == 3
 478         # assert pos["D"].depth == 0
 479         # ~~~~
 480         fun depth: Int do
 481                 if direct_greaters.is_empty then
 482                         return 0
 483                 end
 484                 var min = -1
 485                 for p in direct_greaters do
 486                         var d = poset[p].depth + 1
 487                         if min == -1 or d < min then
 488                                 min = d
 489                         end
 490                 end
 491                 return min
 492
 493         end
 494 end