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