src/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 NaiveCollection[E]
  27         super AbstractSorter[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 end
 167
 168 # View of an objet in a poset
 169 # This class is a helper to handle specific queries on a same object
 170 #
 171 # For instance, one common usage is to add a specific attribute for each poset a class belong.
 172 #
 173 #     class Thing
 174 #         var in_some_relation: POSetElement[Thing]
 175 #         var in_other_relation: POSetElement[Thing]
 176 #     end
 177 #     var t: Thing ...
 178 #     t.in_some_relation.greaters
 179 #
 180 class POSetElement[E: Object]
 181         # The poset self belong to
 182         var poset: POSet[E]
 183
 184         # The real object behind the view
 185         var element: E
 186
 187         private var tos = new HashSet[E]
 188         private var froms = new HashSet[E]
 189         private var dtos = new HashSet[E]
 190         private var dfroms = new HashSet[E]
 191
 192         # The rank of the
 193         # This attribute is used to force a total order for POSet#compare
 194         private var count: Int
 195
 196         # Return the set of all elements `t' that have an edge from `element' to `t'.
 197         # Since the POSet is reflexive, element is included in the set.
 198         fun greaters: Collection[E]
 199         do
 200                 return self.tos
 201         end
 202
 203         # Return the set of all elements `t' that have a direct edge from `element' to `t'.
 204         fun direct_greaters: Collection[E]
 205         do
 206                 return self.dtos
 207         end
 208
 209         # Return the set of all elements `f' that have an edge from `f' to `element'.
 210         # Since the POSet is reflexive, element is included in the set.
 211         fun smallers: Collection[E]
 212         do
 213                 return self.froms
 214         end
 215
 216         # Return the set of all elements `f' that have an edge from `f' to `element'.
 217         fun direct_smallers: Collection[E]
 218         do
 219                 return self.dfroms
 220         end
 221
 222         # Is there an edge from `object' to `t'?
 223         fun <=(t: E): Bool
 224         do
 225                 return self.tos.has(t)
 226         end
 227
 228         # Is `t != element' and is there an edge from `object' to `t'?
 229         fun <(t: E): Bool
 230         do
 231                 return t != self.element and self.tos.has(t)
 232         end
 233 end