1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2012 Jean Privat <jean@pryen.org>
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
9 # http://www.apache.org/licenses/LICENSE-2.0
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.
17 # Pre order sets and partial order set (ie hierarchies)
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]
29 redef type COMPARED: E
is fixed
31 redef fun iterator
do return elements
.keys
.iterator
34 private var elements
: HashMap[E
, POSetElement[E
]] = new HashMap[E
, POSetElement[E
]]
36 redef fun has
(e
) do return self.elements
.keys
.has
(e
)
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
]
44 if elements
.keys
.has
(e
) then return self.elements
[e
]
45 var poe
= new POSetElement[E
](self, e
, elements
.length
)
48 self.elements
[e
] = poe
52 # Return a view of `e` in the poset.
53 # This allows to asks manipulate elements in thier relation with others elements.
55 # var poset: POSet[Something] # ...
57 # for y in poset[x].direct_greaters do
63 fun [](e
: E
): POSetElement[E
]
65 assert elements
.keys
.has
(e
)
66 return self.elements
[e
]
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.
74 # FIXME: Do somethind clever to manage loops.
79 # Skip if edge already present
80 if fe
.tos
.has
(t
) then return
81 # Add the edge and close the transitivity
83 var ffe
= self.elements
[ff
]
85 var tte
= self.elements
[tt
]
90 # Update the transitive reduction
91 if te
.tos
.has
(f
) then return # Skip the reduction if there is a loop
93 for x
in te
.dfroms
.to_a
do
94 var xe
= self.elements
[x
]
100 for x
in fe
.dtos
.to_a
do
101 var xe
= self.elements
[x
]
102 if xe
.froms
.has
(t
) then
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
115 if not elements
.keys
.has
(f
) then return false
116 var fe
= self.elements
[f
]
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
124 if not elements
.keys
.has
(f
) then return false
125 var fe
= self.elements
[f
]
126 return fe
.dtos
.has
(t
)
129 # Display the POSet in a gaphical windows.
130 # Graphviz with a working -Txlib is expected.
134 var f
= new OProcess("dot", "-Txlib")
136 f
.write
"digraph \{\n"
137 for x
in elements
.keys
do
139 var xe
= self.elements
[x
]
141 if self.has_edge
(y
,x
) then
142 f
.write
"\"{x}\
" -> \"{y}\
"[dir=both];\n"
144 f
.write
"\"{x}\
" -> \"{y}\
";\n"
153 # Compare two elements in an arbitrary total order.
154 # Tis function is mainly used to sort elements of the set in an arbitrary linear extension.
155 # if a<b then return -1
156 # if a>b then return 1
157 # if a == b then return 0
158 # else return -1 or 1
159 # The total order is stable unless a new node or a new edge is added
160 redef fun compare
(a
, b
: E
): Int
162 var ae
= self.elements
[a
]
163 var be
= self.elements
[b
]
164 var res
= ae
.tos
.length
<=> be
.tos
.length
165 if res
!= 0 then return res
166 return elements
[a
].count
<=> elements
[b
].count
169 # Filter elements to return only the smallest ones
172 # var s = new POSet[String]
173 # s.add_edge("B", "A")
174 # s.add_edge("C", "A")
175 # s.add_edge("D", "B")
176 # s.add_edge("D", "C")
177 # assert s.select_smallest(["A", "B"]) == ["B"]
178 # assert s.select_smallest(["A", "B", "C"]) == ["B", "C"]
179 # assert s.select_smallest(["B", "C", "D"]) == ["D"]
181 fun select_smallest
(elements
: Collection[E
]): Array[E
]
183 var res
= new Array[E
]
186 if e
== f
then continue
187 if has_edge
(f
, e
) then continue label
195 # var s = new POSet[String]
196 # s.add_edge("B", "A")
197 # s.add_edge("C", "A")
198 # s.add_edge("D", "B")
199 # s.add_edge("D", "C")
200 # assert s.select_greatest(["A", "B"]) == ["A"]
201 # assert s.select_greatest(["A", "B", "C"]) == ["A"]
202 # assert s.select_greatest(["B", "C", "D"]) == ["B", "C"]
204 # Filter elements to return only the greatest ones
205 fun select_greatest
(elements
: Collection[E
]): Array[E
]
207 var res
= new Array[E
]
210 if e
== f
then continue
211 if has_edge
(e
, f
) then continue label
218 # Sort a sorted array of poset elements using linearization order
219 fun linearize
(elements
: Collection[E
]): Array[E
] do
220 var lin
= elements
.to_a
226 # View of an objet in a poset
227 # This class is a helper to handle specific queries on a same object
229 # For instance, one common usage is to add a specific attribute for each poset a class belong.
232 # var in_some_relation: POSetElement[Thing]
233 # var in_other_relation: POSetElement[Thing]
236 # t.in_some_relation.greaters
238 class POSetElement[E
: Object]
239 # The poset self belong to
242 # The real object behind the view
245 private var tos
= new HashSet[E
]
246 private var froms
= new HashSet[E
]
247 private var dtos
= new HashSet[E
]
248 private var dfroms
= new HashSet[E
]
251 # This attribute is used to force a total order for POSet#compare
252 private var count
: Int
254 # Return the set of all elements `t` that have an edge from `element` to `t`.
255 # Since the POSet is reflexive, element is included in the set.
256 fun greaters
: Collection[E
]
261 # Return the set of all elements `t` that have a direct edge from `element` to `t`.
262 fun direct_greaters
: Collection[E
]
267 # Return the set of all elements `f` that have an edge from `f` to `element`.
268 # Since the POSet is reflexive, element is included in the set.
269 fun smallers
: Collection[E
]
274 # Return the set of all elements `f` that have an edge from `f` to `element`.
275 fun direct_smallers
: Collection[E
]
280 # Is there an edge from `element` to `t`?
283 return self.tos
.has
(t
)
286 # Is `t != element` and is there an edge from `element` to `t`?
289 return t
!= self.element
and self.tos
.has
(t
)
292 # The length of the shortest path to the root of the poset hierarchy
294 if direct_greaters
.is_empty
then
298 for p
in direct_greaters
do
299 var d
= poset
[p
].depth
+ 1
300 if min
== -1 or d
< min
then