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 # Preorder set graph.
  21 # This class modelize an incremental preorder graph where new node and edges can be added (but no removal)
  22 # Preorder graph has two caracteristics:
  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 class POSet[E: Object]
  26         super Collection[E]
  27         super Comparator
  28
  29         redef type COMPARED: E is fixed
  30
  31         redef fun iterator do return elements.keys.iterator
  32
  33         # All the nodes
  34         private var elements = new HashMap[E, POSetElement[E]]
  35
  36         redef fun has(e) do return self.elements.keys.has(e)
  37
  38         # Add a node (an element) to the posed
  39         # The new element is added unconnected to any other nodes (it is both a new root and a new leaf).
  40         # Return the POSetElement associated to `e`.
  41         # If `e` is already present in the POSet then just return the POSetElement (usually you will prefer []) is this case.
  42         fun add_node(e: E): POSetElement[E]
  43         do
  44                 if elements.keys.has(e) then return self.elements[e]
  45                 var poe = new POSetElement[E](self, e, elements.length)
  46                 poe.tos.add(e)
  47                 poe.froms.add(e)
  48                 self.elements[e] = poe
  49                 return poe
  50         end
  51
  52         # Return a view of `e` in the poset.
  53         # This allows to asks manipulate elements in thier relation with others elements.
  54         #
  55         #     var poset: POSet[Something] # ...
  56         #     for x in poset do
  57         #         for y in poset[x].direct_greaters do
  58         #             print "{x} -> {y}"
  59         #         end
  60         #     end
  61         #
  62         # REQUIRE: has(e)
  63         fun [](e: E): POSetElement[E]
  64         do
  65                 assert elements.keys.has(e)
  66                 return self.elements[e]
  67         end
  68
  69         # Add an edge from `f` to `t`.
  70         # Because a POSet is transitive, all transitive edges are also added to the graph.
  71         # If the edge already exists, the this function does nothing.
  72         # If a reverse edge (from `t` to `f`) already exists, a loop is created.
  73         #
  74         # FIXME: Do somethind clever to manage loops.
  75         fun add_edge(f, t: E)
  76         do
  77                 var fe = add_node(f)
  78                 var te = add_node(t)
  79                 # Skip if edge already present
  80                 if fe.tos.has(t) then return
  81                 # Add the edge and close the transitivity
  82                 for ff in fe.froms do
  83                         var ffe = self.elements[ff]
  84                         for tt in te.tos do
  85                                 var tte = self.elements[tt]
  86                                 tte.froms.add ff
  87                                 ffe.tos.add tt
  88                         end
  89                 end
  90                 # Update the transitive reduction
  91                 if te.tos.has(f) then return # Skip the reduction if there is a loop
  92
  93                 for x in te.dfroms.to_a do
  94                         var xe = self.elements[x]
  95                         if xe.tos.has(f) then
  96                                 te.dfroms.remove(x)
  97                                 xe.dtos.remove(t)
  98                         end
  99                 end
 100                 for x in fe.dtos.to_a do
 101                         var xe = self.elements[x]
 102                         if xe.froms.has(t) then
 103                                 xe.dfroms.remove(f)
 104                                 fe.dtos.remove(x)
 105                         end
 106                 end
 107                 fe.dtos.add t
 108                 te.dfroms.add f
 109         end
 110
 111         # Add an edge between all elements of `es` in order.
 112         #
 113         # ~~~~
 114         # var pos = new POSet[String]
 115         # pos.add_chain(["A", "B", "C", "D"])
 116         # assert pos.has_direct_edge("A", "B")
 117         # assert pos.has_direct_edge("B", "C")
 118         # assert pos.has_direct_edge("C", "D")
 119         # ~~~~
 120         fun add_chain(es: SequenceRead[E])
 121         do
 122                 if es.is_empty then return
 123                 var i = es.iterator
 124                 var e = i.item
 125                 i.next
 126                 for f in i do
 127                         add_edge(e, f)
 128                         e = f
 129                 end
 130         end
 131
 132         # Is there an edge (transitive or not) from `f` to `t`?
 133         # Since the POSet is reflexive, true is returned if `f == t`.
 134         fun has_edge(f,t: E): Bool
 135         do
 136                 if not elements.keys.has(f) then return false
 137                 var fe = self.elements[f]
 138                 return fe.tos.has(t)
 139         end
 140
 141         # Is there a direct edge from `f` to `t`?
 142         # Note that because of loops, the result may not be the expected one.
 143         fun has_direct_edge(f,t: E): Bool
 144         do
 145                 if not elements.keys.has(f) then return false
 146                 var fe = self.elements[f]
 147                 return fe.dtos.has(t)
 148         end
 149
 150         # Write the POSet as a graphviz digraph.
 151         #
 152         # Nodes are identified with their `to_s`.
 153         # Edges are unlabeled.
 154         fun write_dot(f: OStream)
 155         do
 156                 f.write "digraph \{\n"
 157                 for x in elements.keys do
 158                         var xstr = x.to_s.escape_to_dot
 159                         f.write "\"{xstr}\";\n"
 160                         var xe = self.elements[x]
 161                         for y in xe.dtos do
 162                                 var ystr = y.to_s.escape_to_dot
 163                                 if self.has_edge(y,x) then
 164                                         f.write "\"{xstr}\" -> \"{ystr}\"[dir=both];\n"
 165                                 else
 166                                         f.write "\"{xstr}\" -> \"{ystr}\";\n"
 167                                 end
 168                         end
 169                 end
 170                 f.write "\}\n"
 171         end
 172
 173         # Display the POSet in a graphical windows.
 174         # Graphviz with a working -Txlib is expected.
 175         #
 176         # See `write_dot` for details.
 177         fun show_dot
 178         do
 179                 var f = new OProcess("dot", "-Txlib")
 180                 f.write "\}\n"
 181                 write_dot(f)
 182                 f.close
 183                 f.wait
 184         end
 185
 186         # Compare two elements in an arbitrary total order.
 187         # Tis function is mainly used to sort elements of the set in an arbitrary linear extension.
 188         # if a<b then return -1
 189         # if a>b then return 1
 190         # if a == b then return 0
 191         # else return -1 or 1
 192         # The total order is stable unless a new node or a new edge is added
 193         redef fun compare(a, b: E): Int
 194         do
 195                 var ae = self.elements[a]
 196                 var be = self.elements[b]
 197                 var res = ae.tos.length <=> be.tos.length
 198                 if res != 0 then return res
 199                 return elements[a].count <=> elements[b].count
 200         end
 201
 202         # Filter elements to return only the smallest ones
 203         #
 204         # ~~~
 205         # var s = new POSet[String]
 206         # s.add_edge("B", "A")
 207         # s.add_edge("C", "A")
 208         # s.add_edge("D", "B")
 209         # s.add_edge("D", "C")
 210         # assert s.select_smallest(["A", "B"]) == ["B"]
 211         # assert s.select_smallest(["A", "B", "C"]) == ["B", "C"]
 212         # assert s.select_smallest(["B", "C", "D"]) == ["D"]
 213         # ~~~
 214         fun select_smallest(elements: Collection[E]): Array[E]
 215         do
 216                 var res = new Array[E]
 217                 for e in elements do
 218                         for f in elements do
 219                                 if e == f then continue
 220                                 if has_edge(f, e) then continue label
 221                         end
 222                         res.add(e)
 223                 end label
 224                 return res
 225         end
 226
 227         # ~~~
 228         # var s = new POSet[String]
 229         # s.add_edge("B", "A")
 230         # s.add_edge("C", "A")
 231         # s.add_edge("D", "B")
 232         # s.add_edge("D", "C")
 233         # assert s.select_greatest(["A", "B"]) == ["A"]
 234         # assert s.select_greatest(["A", "B", "C"]) == ["A"]
 235         # assert s.select_greatest(["B", "C", "D"]) == ["B", "C"]
 236         # ~~~
 237         # Filter elements to return only the greatest ones
 238         fun select_greatest(elements: Collection[E]): Array[E]
 239         do
 240                 var res = new Array[E]
 241                 for e in elements do
 242                         for f in elements do
 243                                 if e == f then continue
 244                                 if has_edge(e, f) then continue label
 245                         end
 246                         res.add(e)
 247                 end label
 248                 return res
 249         end
 250
 251         # Sort a sorted array of poset elements using linearization order
 252         fun linearize(elements: Collection[E]): Array[E] do
 253                 var lin = elements.to_a
 254                 sort(lin)
 255                 return lin
 256         end
 257 end
 258
 259 # View of an objet in a poset
 260 # This class is a helper to handle specific queries on a same object
 261 #
 262 # For instance, one common usage is to add a specific attribute for each poset a class belong.
 263 #
 264 #     class Thing
 265 #         var in_some_relation: POSetElement[Thing]
 266 #         var in_other_relation: POSetElement[Thing]
 267 #     end
 268 #     var t: Thing # ...
 269 #     t.in_some_relation.greaters
 270 #
 271 class POSetElement[E: Object]
 272         # The poset self belong to
 273         var poset: POSet[E]
 274
 275         # The real object behind the view
 276         var element: E
 277
 278         private var tos = new HashSet[E]
 279         private var froms = new HashSet[E]
 280         private var dtos = new HashSet[E]
 281         private var dfroms = new HashSet[E]
 282
 283         # The rank of the
 284         # This attribute is used to force a total order for POSet#compare
 285         private var count: Int
 286
 287         # Return the set of all elements `t` that have an edge from `element` to `t`.
 288         # Since the POSet is reflexive, element is included in the set.
 289         fun greaters: Collection[E]
 290         do
 291                 return self.tos
 292         end
 293
 294         # Return the set of all elements `t` that have a direct edge from `element` to `t`.
 295         fun direct_greaters: Collection[E]
 296         do
 297                 return self.dtos
 298         end
 299
 300         # Return the set of all elements `f` that have an edge from `f` to `element`.
 301         # Since the POSet is reflexive, element is included in the set.
 302         fun smallers: Collection[E]
 303         do
 304                 return self.froms
 305         end
 306
 307         # Return the set of all elements `f` that have an edge from `f` to `element`.
 308         fun direct_smallers: Collection[E]
 309         do
 310                 return self.dfroms
 311         end
 312
 313         # Is there an edge from `element` to `t`?
 314         fun <=(t: E): Bool
 315         do
 316                 return self.tos.has(t)
 317         end
 318
 319         # Is `t != element` and is there an edge from `element` to `t`?
 320         fun <(t: E): Bool
 321         do
 322                 return t != self.element and self.tos.has(t)
 323         end
 324
 325         # The length of the shortest path to the root of the poset hierarchy
 326         fun depth: Int do
 327                 if direct_greaters.is_empty then
 328                         return 0
 329                 end
 330                 var min = -1
 331                 for p in direct_greaters do
 332                         var d = poset[p].depth + 1
 333                         if min == -1 or d < min then
 334                                 min = d
 335                         end
 336                 end
 337                 return min
 338
 339         end
 340 end