1 package org.thegalactic.dgraph;
2
3 /*
4 * DAGraph.java
5 *
6 * Copyright: 2010-2015 Karell Bertet, France
7 * Copyright: 2015-2016 The Galactic Organization, France
8 *
9 * License: http://www.cecill.info/licences/Licence_CeCILL-B_V1-en.html CeCILL-B license
10 *
11 * This file is part of java-lattices.
12 * You can redistribute it and/or modify it under the terms of the CeCILL-B license.
13 */
14 import java.util.List;
15 import java.util.Set;
16 import java.util.SortedSet;
17 import java.util.TreeMap;
18 import java.util.TreeSet;
19
20 /**
21 * This class extends the representation of a directed graph given by class
22 * {@link ConcreteDGraph} for directed acyclic graph (DAG).
23 *
24 * The main property of a directed acyclic graph is to be a partially ordered
25 * set (poset) when transitively closed, and a Hasse diagram when transitively
26 * reduced.
27 *
28 * This property is not ensured for components of this class because it would
29 * require a checking treatment over the graph whenever a new edge or node is
30 * added. However, this property can be explicitely ckecked using method
31 * {@link #isAcyclic}.
32 *
33 * This class provides methods implementing classical operation on a directed
34 * acyclic graph: minorants and majorants, filter and ideal, transitive
35 * reduction, ideal lattice, ...
36 *
37 * This class also provides a static method randomly generating a directed
38 * acyclic graph, and a static method generating the graph of divisors.
39 *
40 * 
41 *
42 * @param <N> Node content type
43 * @param <E> Edge content type
44 *
45 * @todo Do we forbid to add an edge that breaks acyclic property by verifying
46 * that the destination node has no successors? May be a DAGraph could contain a
47 * ConcreteDGraph and export only interesting method by proxy
48 *
49 * @uml DAGraph.png
50 * !include resources/org/thegalactic/dgraph/DAGraph.iuml
51 * !include resources/org/thegalactic/dgraph/DGraph.iuml
52 * !include resources/org/thegalactic/dgraph/Edge.iuml
53 * !include resources/org/thegalactic/dgraph/Node.iuml
54 *
55 * hide members
56 * show DAGraph members
57 * class DAGraph #LightCyan
58 * title DAGraph UML graph
59 */
60 public class DAGraph<N, E> extends ConcreteDGraph<N, E> {
61
62 /**
63 * Constructs a new DAG with an empty set of node.
64 */
65 public DAGraph() {
66 super();
67 }
68
69 /**
70 * Constructs this component with the specified set of nodes, and empty
71 * treemap of successors and predecessors.
72 *
73 * @param set the set of nodes
74 */
75 public DAGraph(final SortedSet<Node<N>> set) {
76 super(set);
77 }
78
79 /**
80 * Constructs this component as a copy of the specified directed graph.
81 *
82 * Acyclic property is checked for the specified DAG. When not verified,
83 * this component is construct with the same set of nodes but with no edges.
84 *
85 * @param graph the ConcreteDGraph to be copied
86 */
87 public DAGraph(final ConcreteDGraph<N, E> graph) {
88 super(graph);
89 if (this.isAcyclic()) {
90 this.reflexiveReduction();
91 } else {
92 TreeMap<Node<N>, TreeSet<Edge<N, E>>> successors = new TreeMap<Node<N>, TreeSet<Edge<N, E>>>();
93 TreeMap<Node<N>, TreeSet<Edge<N, E>>> predecessors = new TreeMap<Node<N>, TreeSet<Edge<N, E>>>();
94 for (Node<N> node : this.getNodes()) {
95 successors.put(node, new TreeSet<Edge<N, E>>());
96 predecessors.put(node, new TreeSet<Edge<N, E>>());
97 }
98 this.setSuccessors(successors);
99 this.setPredecessors(predecessors);
100 }
101 }
102
103 /*
104 * --------------- DAG HANDLING METHODS ------------
105 */
106 /**
107 * Returns the minimal elements of this component.
108 *
109 * @return the minimal elements
110 */
111 public final SortedSet<Node<N>> min() {
112 return this.getSinks();
113 }
114
115 /**
116 * Returns the maximal elements of this component.
117 *
118 * @return the maximal elements
119 */
120 public final SortedSet<Node<N>> max() {
121 return this.getWells();
122 }
123
124 /**
125 * Returns the set of majorants of the specified node.
126 *
127 * Majorants of a node are its successors in the transitive closure
128 *
129 * @param node the specified node
130 *
131 * @return the set of majorants
132 */
133 public final SortedSet<Node<N>> majorants(final Node<N> node) {
134 final DAGraph graph = new DAGraph(this);
135 graph.transitiveClosure();
136 return graph.getSuccessorNodes(node);
137 }
138
139 /**
140 * Returns the set of minorants of the specified node.
141 *
142 * Minorants of a node are its predecessors in the transitive closure
143 *
144 * @param node the specified node
145 *
146 * @return the set of minorants
147 */
148 public final SortedSet<Node<N>> minorants(final Node<N> node) {
149 final DAGraph graph = new DAGraph(this);
150 graph.transitiveClosure();
151 return graph.getPredecessorNodes(node);
152 }
153
154 /**
155 * Returns the subgraph induced by the specified node and its successors in
156 * the transitive closure.
157 *
158 * @param node the specified node
159 *
160 * @return the subgraph
161 */
162 public final DAGraph<N, E> filter(final Node<N> node) {
163 final TreeSet<Node<N>> set = new TreeSet<Node<N>>(this.majorants(node));
164 set.add(node);
165 return this.getSubgraphByNodes(set);
166 }
167
168 /**
169 * Returns the subgraph induced by the specified node and its predecessors
170 * in the transitive closure.
171 *
172 * @param node the specified node
173 *
174 * @return the subgraph
175 */
176 public final DAGraph<N, E> ideal(final Node<N> node) {
177 final TreeSet<Node<N>> set = new TreeSet<Node<N>>(this.minorants(node));
178 set.add(node);
179 return this.getSubgraphByNodes(set);
180 }
181
182 /**
183 * Returns the subgraph of this component induced by the specified set of
184 * nodes.
185 *
186 * The subgraph only contains nodes of the specified set that also are in
187 * this component.
188 *
189 * @param nodes The set of nodes
190 *
191 * @return The subgraph
192 */
193 @Override
194 public DAGraph<N, E> getSubgraphByNodes(final Set<Node<N>> nodes) {
195 ConcreteDGraph tmp = new ConcreteDGraph(this);
196 tmp.transitiveClosure();
197 ConcreteDGraph sub = tmp.getSubgraphByNodes(nodes);
198 DAGraph sub2 = new DAGraph(sub);
199 sub2.transitiveReduction();
200 return sub2;
201 }
202
203 /*
204 * --------------- DAG TREATMENT METHODS ------------
205 */
206 /**
207 * Computes the transitive reduction of this component.
208 *
209 * The transitive reduction is not uniquely defined only when the acyclic
210 * property is verified. In this case, it corresponds to the Hasse diagram
211 * of the DAG.
212 *
213 * This method is an implementation of the Goralcikova-Koubeck algorithm
214 * that can also compute the transitive closure. This tratment is performed
215 * in O(n+nm_r+nm_c), where n corresponds to the number of nodes, m_r to the
216 * numer of edges in the transitive closure, and m_r the number of edges in
217 * the transitive reduction.
218 *
219 * @return the number of added edges
220 */
221 public int transitiveReduction() {
222
223 // copy this component in a new DAG graph
224 DAGraph<N, E> graph = new DAGraph<N, E>(this);
225 graph.reflexiveReduction();
226 // initalize this component with no edges
227 this.setSuccessors(new TreeMap<Node<N>, TreeSet<Edge<N, E>>>());
228 for (Node<N> node : this.getNodes()) {
229 this.getSuccessors().put(node, new TreeSet<Edge<N, E>>());
230 }
231 this.setPredecessors(new TreeMap<Node<N>, TreeSet<Edge<N, E>>>());
232 for (Node<N> node : this.getNodes()) {
233 this.getPredecessors().put(node, new TreeSet<Edge<N, E>>());
234 }
235 int number = 0;
236 // mark each node to false
237 TreeMap<Node<N>, Boolean> mark = new TreeMap<Node<N>, Boolean>();
238 for (Node<N> node : graph.getNodes()) {
239 mark.put(node, Boolean.FALSE);
240 }
241 // treatment of nodes according to a topological sort
242 List<Node<N>> sort = graph.topologicalSort();
243 for (Node<N> x : sort) {
244 TreeSet<Node<N>> set = new TreeSet<Node<N>>(graph.getSuccessorNodes(x));
245 while (!set.isEmpty()) {
246 // compute the smallest successor y of x according to the topological sort
247 int i = 0;
248 while (!set.contains(sort.get(i))) {
249 i++;
250 }
251 Node<N> y = sort.get(i);
252 // when y is not not marked, x->y is a reduced edge
253 if (y != null && !mark.get(y)) {
254 this.addEdge(x, y);
255 graph.addEdge(x, y);
256 }
257 for (Node<N> z : graph.getSuccessorNodes(y)) {
258 // treatment of z when not marked
259 if (!mark.get(z)) {
260 mark.put(z, Boolean.TRUE);
261 graph.addEdge(x, z);
262 number++;
263 set.add(z);
264 }
265 }
266 set.remove(y);
267 }
268 for (Node<N> y : graph.getSuccessorNodes(x)) {
269 mark.put(y, Boolean.FALSE);
270 }
271 }
272 return number;
273 }
274
275 /**
276 * Computes the transitive closure of this component.
277 *
278 * This method overlaps the computation of the transitive closure for
279 * directed graph in class {@link ConcreteDGraph} with an implementation of the
280 * Goralcikova-Koubeck algorithm dedicated to acyclic directed graph. This
281 * algorithm can also compute the transitive reduction of a directed acyclic
282 * graph.
283 *
284 * This treatment is performed in O(n+nm_r+nm_c), where n corresponds to the
285 * number of nodes, m_r to the numer of edges in the transitive closure, and
286 * m_r the number of edges in the transitive reduction.
287 *
288 * @return the number of added edges
289 */
290 public int transitiveClosure() {
291 int number = 0;
292 // mark each node to false
293 TreeMap<Node<N>, Boolean> mark = new TreeMap<Node<N>, Boolean>();
294 for (Node<N> node : this.getNodes()) {
295 mark.put(node, Boolean.FALSE);
296 }
297 // treatment of nodes according to a topological sort
298 List<Node<N>> sort = this.topologicalSort();
299 for (Node<N> x : sort) {
300 TreeSet<Node<N>> set = new TreeSet<Node<N>>(this.getSuccessorNodes(x));
301 while (!set.isEmpty()) {
302 // compute the smallest successor y of x according to the topological sort
303 int i = 0;
304 do {
305 i++;
306 } while (!set.contains(sort.get(i)));
307 Node<N> y = sort.get(i);
308 for (Node<N> z : this.getSuccessorNodes(y)) {
309 // treatment of z when not marked
310 if (!mark.get(z)) {
311 mark.put(z, Boolean.TRUE);
312 this.addEdge(x, z);
313 number++;
314 set.add(z);
315 }
316 }
317 set.remove(y);
318 }
319 for (Node<N> y : this.getSuccessorNodes(x)) {
320 mark.put(y, Boolean.FALSE);
321 }
322 }
323 return number;
324 }
325 }