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 nodes.iterator
  30
  31         # All the nodes
  32         private var nodes: Set[E] = new HashSet[E]
  33         private var tos: HashMap[E, Set[E]] = new HashMap[E, Set[E]]
  34         private var froms: HashMap[E, Set[E]] = new HashMap[E, Set[E]]
  35         private var dtos: HashMap[E, Set[E]] = new HashMap[E, Set[E]]
  36         private var dfroms: HashMap[E, Set[E]] = new HashMap[E, Set[E]]
  37         private var elements: HashMap[E, POSetElement[E]] = new HashMap[E, POSetElement[E]]
  38
  39         redef fun has(e) do return self.nodes.has(e)
  40
  41         # Add a node (an element) to the posed
  42         # The new element is added unconnected to any other nodes (it is both a new root and a new leaf).
  43         # Return the POSetElement associated to `e'.
  44         # If `e' is already present in the POSet then just return the POSetElement (usually you will prefer []) is this case.
  45         fun add_node(e: E): POSetElement[E]
  46         do
  47                 if nodes.has(e) then return self.elements[e]
  48                 nodes.add(e)
  49                 tos[e] = new HashSet[E]
  50                 tos[e].add(e)
  51                 froms[e] = new HashSet[E]
  52                 froms[e].add(e)
  53                 dtos[e] = new HashSet[E]
  54                 dfroms[e] = new HashSet[E]
  55                 var poe = new POSetElement[E](self, e, nodes.length)
  56                 self.elements[e] = poe
  57                 return poe
  58         end
  59
  60         # Return a view of `e' in the poset.
  61         # This allows to asks manipulate elements in thier relation with others elements.
  62         #
  63         #     var poset = POSet[Something] = ...
  64         #     for x in poset do
  65         #         for y in poset[x].direct_greaters do
  66         #             print "{x} -> {y}"
  67         #         end
  68         #     end
  69         #
  70         # REQUIRE: has(e)
  71         fun [](e: E): POSetElement[E]
  72         do
  73                 assert nodes.has(e)
  74                 return self.elements[e]
  75         end
  76
  77         # Add an edge from `f' to `t'.
  78         # Because a POSet is transitive, all transitive edges are also added to the graph.
  79         # If the edge already exists, the this function does nothing.
  80         # If a reverse edge (from `t' to 'f') already exists, a loop is created.
  81         #
  82         # FIXME: Do somethind clever to manage loops.
  83         fun add_edge(f, t: E)
  84         do
  85                 add_node(f)
  86                 add_node(t)
  87                 # Skip if edge already present
  88                 if tos[f].has(t) then return
  89                 # Add the edge and close the transitivity
  90                 for ff in froms[f] do
  91                         for tt in tos[t] do
  92                                 froms[tt].add ff
  93                                 tos[ff].add tt
  94                         end
  95                 end
  96                 # Update the transitive reduction
  97                 if tos[t].has(f) then return # Skip the reduction if there is a loop
  98
  99                 for x in dfroms[t].to_a do
 100                         if tos[x].has(f) then
 101                                 dfroms[t].remove(x)
 102                                 dtos[x].remove(t)
 103                         end
 104                 end
 105                 for x in dtos[f].to_a do
 106                         if froms[x].has(t) then
 107                                 dfroms[x].remove(f)
 108                                 dtos[f].remove(x)
 109                         end
 110                 end
 111                 dtos[f].add t
 112                 dfroms[t].add f
 113         end
 114
 115         # Is there an edge (transitive or not) from `f' to `t'?
 116         # Since the POSet is reflexive, true is returned if `f == t'.
 117         fun has_edge(f,t: E): Bool
 118         do
 119                 return nodes.has(f) and tos[f].has(t)
 120         end
 121
 122         # Is there a direct edge from `f' to `t'?
 123         # Note that because of loops, the result may not be the expected one.
 124         fun has_direct_edge(f,t: E): Bool
 125         do
 126                 return nodes.has(f) and dtos[f].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 nodes do
 138                         for y in dtos[x] 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 res = tos[a].length <=> tos[b].length
 161                 if res != 0 then return res
 162                 return elements[a].count <=> elements[b].count
 163         end
 164 end
 165
 166 # View of an objet in a poset
 167 # This class is a helper to handle specific queries on a same object
 168 #
 169 # For instance, one common usage is to add a specific attribute for each poset a class belong.
 170 #
 171 #     class Thing
 172 #         var in_some_relation: POSetElement[Thing]
 173 #         var in_other_relation: POSetElement[Thing]
 174 #     end
 175 #     var t: Thing ...
 176 #     t.in_some_relation.greaters
 177 #
 178 class POSetElement[E: Object]
 179         # The poset self belong to
 180         var poset: POSet[E]
 181
 182         # The real object behind the view
 183         var element: E
 184
 185         # The rank of the
 186         # This attribute is used to force a total order for POSet#compare
 187         private var count: Int
 188
 189         # Return the set of all elements `t' that have an edge from `element' to `t'.
 190         # Since the POSet is reflexive, element is included in the set.
 191         fun greaters: Collection[E]
 192         do
 193                 return self.poset.tos[self.element]
 194         end
 195
 196         # Return the set of all elements `t' that have a direct edge from `element' to `t'.
 197         fun direct_greaters: Collection[E]
 198         do
 199                 return self.poset.dtos[self.element]
 200         end
 201
 202         # Return the set of all elements `f' that have an edge from `f' to `element'.
 203         # Since the POSet is reflexive, element is included in the set.
 204         fun smallers: Collection[E]
 205         do
 206                 return self.poset.froms[self.element]
 207         end
 208
 209         # Return the set of all elements `f' that have an edge from `f' to `element'.
 210         fun direct_smallers: Collection[E]
 211         do
 212                 return self.poset.dfroms[self.element]
 213         end
 214
 215         # Is there an edge from `object' to `t'?
 216         fun <=(t: E): Bool
 217         do
 218                 return self.poset.tos[self.element].has(t)
 219         end
 220
 221         # Is `t != element' and is there an edge from `object' to `t'?
 222         fun <(t: E): Bool
 223         do
 224                 return t != self.element and self.poset.tos[self.element].has(t)
 225         end
 226 end