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