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