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