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: HashMap[E, POSetElement[E]] = 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         # Is there an edge (transitive or not) from `f` to `t`?
 112         # Since the POSet is reflexive, true is returned if `f == t`.
 113         fun has_edge(f,t: E): Bool
 114         do
 115                 if not elements.keys.has(f) then return false
 116                 var fe = self.elements[f]
 117                 return fe.tos.has(t)
 118         end
 119
 120         # Is there a direct edge from `f` to `t`?
 121         # Note that because of loops, the result may not be the expected one.
 122         fun has_direct_edge(f,t: E): Bool
 123         do
 124                 if not elements.keys.has(f) then return false
 125                 var fe = self.elements[f]
 126                 return fe.dtos.has(t)
 127         end
 128
 129         # Display the POSet in a gaphical windows.
 130         # Graphviz with a working -Txlib is expected.
 131         # Used fo debugging.
 132         fun show_dot
 133         do
 134                 var f = new OProcess("dot", "-Txlib")
 135                 #var f = stdout
 136                 f.write "digraph \{\n"
 137                 for x in elements.keys do
 138                         f.write "\"{x}\";\n"
 139                         var xe = self.elements[x]
 140                         for y in xe.dtos do
 141                                 if self.has_edge(y,x) then
 142                                         f.write "\"{x}\" -> \"{y}\"[dir=both];\n"
 143                                 else
 144                                         f.write "\"{x}\" -> \"{y}\";\n"
 145                                 end
 146                         end
 147                 end
 148                 f.write "\}\n"
 149                 #f.close
 150                 #f.wait
 151         end
 152
 153         # Compare two elements in an arbitrary total order.
 154         # Tis function is mainly used to sort elements of the set in an arbitrary linear extension.
 155         # if a<b then return -1
 156         # if a>b then return 1
 157         # if a == b then return 0
 158         # else return -1 or 1
 159         # The total order is stable unless a new node or a new edge is added
 160         redef fun compare(a, b: E): Int
 161         do
 162                 var ae = self.elements[a]
 163                 var be = self.elements[b]
 164                 var res = ae.tos.length <=> be.tos.length
 165                 if res != 0 then return res
 166                 return elements[a].count <=> elements[b].count
 167         end
 168
 169         # Filter elements to return only the smallest ones
 170         #
 171         # ~~~
 172         # var s = new POSet[String]
 173         # s.add_edge("B", "A")
 174         # s.add_edge("C", "A")
 175         # s.add_edge("D", "B")
 176         # s.add_edge("D", "C")
 177         # assert s.select_smallest(["A", "B"]) == ["B"]
 178         # assert s.select_smallest(["A", "B", "C"]) == ["B", "C"]
 179         # assert s.select_smallest(["B", "C", "D"]) == ["D"]
 180         # ~~~
 181         fun select_smallest(elements: Collection[E]): Array[E]
 182         do
 183                 var res = new Array[E]
 184                 for e in elements do
 185                         for f in elements do
 186                                 if e == f then continue
 187                                 if has_edge(f, e) then continue label
 188                         end
 189                         res.add(e)
 190                 end label
 191                 return res
 192         end
 193
 194         # ~~~
 195         # var s = new POSet[String]
 196         # s.add_edge("B", "A")
 197         # s.add_edge("C", "A")
 198         # s.add_edge("D", "B")
 199         # s.add_edge("D", "C")
 200         # assert s.select_greatest(["A", "B"]) == ["A"]
 201         # assert s.select_greatest(["A", "B", "C"]) == ["A"]
 202         # assert s.select_greatest(["B", "C", "D"]) == ["B", "C"]
 203         # ~~~
 204         # Filter elements to return only the greatest ones
 205         fun select_greatest(elements: Collection[E]): Array[E]
 206         do
 207                 var res = new Array[E]
 208                 for e in elements do
 209                         for f in elements do
 210                                 if e == f then continue
 211                                 if has_edge(e, f) then continue label
 212                         end
 213                         res.add(e)
 214                 end label
 215                 return res
 216         end
 217
 218         # Sort a sorted array of poset elements using linearization order
 219         fun linearize(elements: Collection[E]): Array[E] do
 220                 var lin = elements.to_a
 221                 sort(lin)
 222                 return lin
 223         end
 224 end
 225
 226 # View of an objet in a poset
 227 # This class is a helper to handle specific queries on a same object
 228 #
 229 # For instance, one common usage is to add a specific attribute for each poset a class belong.
 230 #
 231 #     class Thing
 232 #         var in_some_relation: POSetElement[Thing]
 233 #         var in_other_relation: POSetElement[Thing]
 234 #     end
 235 #     var t: Thing # ...
 236 #     t.in_some_relation.greaters
 237 #
 238 class POSetElement[E: Object]
 239         # The poset self belong to
 240         var poset: POSet[E]
 241
 242         # The real object behind the view
 243         var element: E
 244
 245         private var tos = new HashSet[E]
 246         private var froms = new HashSet[E]
 247         private var dtos = new HashSet[E]
 248         private var dfroms = new HashSet[E]
 249
 250         # The rank of the
 251         # This attribute is used to force a total order for POSet#compare
 252         private var count: Int
 253
 254         # Return the set of all elements `t` that have an edge from `element` to `t`.
 255         # Since the POSet is reflexive, element is included in the set.
 256         fun greaters: Collection[E]
 257         do
 258                 return self.tos
 259         end
 260
 261         # Return the set of all elements `t` that have a direct edge from `element` to `t`.
 262         fun direct_greaters: Collection[E]
 263         do
 264                 return self.dtos
 265         end
 266
 267         # Return the set of all elements `f` that have an edge from `f` to `element`.
 268         # Since the POSet is reflexive, element is included in the set.
 269         fun smallers: Collection[E]
 270         do
 271                 return self.froms
 272         end
 273
 274         # Return the set of all elements `f` that have an edge from `f` to `element`.
 275         fun direct_smallers: Collection[E]
 276         do
 277                 return self.dfroms
 278         end
 279
 280         # Is there an edge from `element` to `t`?
 281         fun <=(t: E): Bool
 282         do
 283                 return self.tos.has(t)
 284         end
 285
 286         # Is `t != element` and is there an edge from `element` to `t`?
 287         fun <(t: E): Bool
 288         do
 289                 return t != self.element and self.tos.has(t)
 290         end
 291
 292         # The length of the shortest path to the root of the poset hierarchy
 293         fun depth: Int do
 294                 if direct_greaters.is_empty then
 295                         return 0
 296                 end
 297                 var min = -1
 298                 for p in direct_greaters do
 299                         var d = poset[p].depth + 1
 300                         if min == -1 or d < min then
 301                                 min = d
 302                         end
 303                 end
 304                 return min
 305
 306         end
 307 end