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