1 package org.thegalactic.dgraph;
2
3 /*
4 * ConcreteDGraph.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.AbstractSet;
15 import java.util.ArrayList;
16 import java.util.Collections;
17 import java.util.Comparator;
18 import java.util.Iterator;
19 import java.util.List;
20 import java.util.Map;
21 import java.util.NoSuchElementException;
22 import java.util.Set;
23 import java.util.SortedSet;
24 import java.util.TreeMap;
25 import java.util.TreeSet;
26
27 /**
28 * This class gives a standard representation for a directed graph by sets of
29 * successors and predecessors.
30 *
31 * A directed graph is composed of
32 *
33 * - a treeset of node, defined by class {@link Node}; - a treemap of successors
34 * that associates to each node a treeset of successors, defined by class
35 * {@link Edge}; - a treemap of predecessors that associates to each node a
36 * treeset of predecessors, defined by class {@link Edge}.
37 *
38 * This class provides methods implementing classical operation on a directed
39 * graph:
40 *
41 * - sinks - wells - subgraph - reflexive closure and reduction - transitive
42 * closure - strongly connected components - ...
43 *
44 * This class also provides a static method randomly generating a directed
45 * graph.
46 *
47 * 
48 *
49 * @param <N> Node content type
50 * @param <E> Edge content type
51 *
52 * @uml DGraph.png
53 * !include resources/org/thegalactic/dgraph/DGraph.iuml
54 * !include resources/org/thegalactic/dgraph/Edge.iuml
55 * !include resources/org/thegalactic/dgraph/Node.iuml
56 *
57 * hide members
58 * show DGraph members
59 * class DGraph #LightCyan
60 * title DGraph UML graph
61 */
62 public class ConcreteDGraph<N, E> extends AbstractDGraph<N, E> implements Cloneable {
63
64 /*
65 * ------------- FIELDS ------------------
66 */
67 /**
68 * A set of elements.
69 */
70 private TreeSet<Node<N>> nodes;
71
72 /**
73 * A map to associate a set of successors to each node.
74 *
75 * @todo use a TreeSet for edges with a specific comparator for predecessors
76 */
77 private TreeMap<Node<N>, TreeSet<Edge<N, E>>> successors;
78
79 /**
80 * A map to associate a set of predecessors to each node.
81 */
82 private TreeMap<Node<N>, TreeSet<Edge<N, E>>> predecessors;
83
84
85 /*
86 * ------------- CONSTRUCTORS ------------------
87 */
88 /**
89 * Constructs a new directed graph with an empty set of node.
90 */
91 public ConcreteDGraph() {
92 super();
93 this.nodes = new TreeSet<Node<N>>();
94 this.successors = new TreeMap<Node<N>, TreeSet<Edge<N, E>>>();
95 this.predecessors = new TreeMap<Node<N>, TreeSet<Edge<N, E>>>();
96 }
97
98 /**
99 * Constructs a new directed graph source the specified set of nodes.
100 *
101 * Successors and predecessors of each nodes are initialised by an empty
102 * set.
103 *
104 * @param set the set of nodes
105 */
106 public ConcreteDGraph(final SortedSet<Node<N>> set) {
107 this();
108 this.nodes.addAll(set);
109 for (final Node<N> node : this.nodes) {
110 this.successors.put(node, new TreeSet<Edge<N, E>>());
111 this.predecessors.put(node, new TreeSet<Edge<N, E>>());
112 }
113 }
114
115 /**
116 * Constructs this component as a copy of the specified directed graph.
117 *
118 * @param graph the directed graph to be copied
119 */
120 public ConcreteDGraph(final DGraph<N, E> graph) {
121 this(graph.getNodes());
122 for (final Edge<N, E> edge : graph.getEdges()) {
123 this.addEdge(edge);
124 }
125 }
126
127 /*
128 * --------------- ACCESSOR AND OVERLAPPING METHODS ------------
129 */
130 /**
131 * Returns a clone of this component composed of a clone of each node and
132 * each edge.
133 *
134 * @return the clone of this
135 *
136 * @throws java.lang.CloneNotSupportedException
137 */
138 @Override
139 public ConcreteDGraph<N, E> clone() throws CloneNotSupportedException {
140 final ConcreteDGraph<N, E> graph = (ConcreteDGraph<N, E>) super.clone();
141 graph.nodes = (TreeSet) this.nodes.clone();
142 graph.successors = new TreeMap<Node<N>, TreeSet<Edge<N, E>>>();
143 graph.predecessors = new TreeMap<Node<N>, TreeSet<Edge<N, E>>>();
144 for (final Map.Entry<Node<N>, TreeSet<Edge<N, E>>> entry : this.successors.entrySet()) {
145 graph.successors.put(entry.getKey(), (TreeSet<Edge<N, E>>) entry.getValue().clone());
146 }
147 for (final Map.Entry<Node<N>, TreeSet<Edge<N, E>>> entry : this.predecessors.entrySet()) {
148 graph.predecessors.put(entry.getKey(), (TreeSet<Edge<N, E>>) entry.getValue().clone());
149 }
150 return graph;
151 }
152
153 /**
154 * Returns the set of nodes of this component.
155 *
156 * @return the set of nodes
157 */
158 public final SortedSet<Node<N>> getNodes() {
159 return Collections.unmodifiableSortedSet(this.nodes);
160 }
161
162 /**
163 * Returns the set of edges of this component.
164 *
165 * @return the set of edges
166 */
167 public final SortedSet<Edge<N, E>> getEdges() {
168 return new Edges(this);
169 }
170
171 /**
172 * Returns the set of edges successors of the specified node.
173 *
174 * @param node the node to search for
175 *
176 * @return the set of edges
177 */
178 public final SortedSet<Edge<N, E>> getSuccessorEdges(final Node<N> node) {
179 return Collections.unmodifiableSortedSet(this.successors.get(node));
180 }
181
182 /**
183 * Returns the set of edges predecessors of the specified node.
184 *
185 * @param node the node to search for
186 *
187 * @return the set of edges
188 */
189 public final SortedSet<Edge<N, E>> getPredecessorEdges(final Node<N> node) {
190 return Collections.unmodifiableSortedSet(this.predecessors.get(node));
191 }
192
193 /**
194 * Returns the set of nodes successors of the specified node.
195 *
196 * @param node the node to search for
197 *
198 * @return the set of nodes
199 *
200 * @todo use iterator pattern (some changes in ArrowRelation.java and
201 * Lattice.java)
202 */
203 public final SortedSet<Node<N>> getSuccessorNodes(final Node<N> node) {
204 final SortedSet<Node<N>> successorsFromNode = new TreeSet<Node<N>>();
205 for (final Edge<N, E> edge : this.successors.get(node)) {
206 successorsFromNode.add(edge.getTarget());
207 }
208 return Collections.unmodifiableSortedSet(successorsFromNode);
209 }
210
211 /**
212 * Returns the set of nodes predecessors of the specified node.
213 *
214 * @param node the node to search for
215 *
216 * @return the set of nodes
217 *
218 * @todo use iterator pattern (some changes in ArrowRelation.java and
219 * Lattice.java)
220 */
221 public final SortedSet<Node<N>> getPredecessorNodes(final Node<N> node) {
222 final SortedSet<Node<N>> predecessorsFromNode = new TreeSet<Node<N>>();
223 for (final Edge<N, E> edge : this.predecessors.get(node)) {
224 predecessorsFromNode.add(edge.getSource());
225 }
226 return Collections.unmodifiableSortedSet(predecessorsFromNode);
227 }
228
229 /**
230 * Returns, if it exists, the edge between node source and node to.
231 *
232 * @param source The origin node
233 * @param target The destination node
234 *
235 * @return the found edge or null
236 *
237 * @todo see getNode
238 */
239 public final Edge<N, E> getEdge(final Node<N> source, final Node<N> target) {
240 Edge<N, E> edge = null;
241 if (source != null && target != null) {
242 try {
243 final Edge<N, E> search = new Edge<N, E>(source, target);
244 edge = this.successors.get(source).subSet(search, true, search, true).first();
245 } catch (NoSuchElementException ex) {
246 }
247 }
248 return edge;
249 }
250
251 /**
252 * Returns the node that is equal to the specified one.
253 *
254 * @param search The node to search for
255 *
256 * @return the found node or null
257 *
258 * @todo maybe use try { return this.nodes.subSet(search, true, search,
259 * true).first(); } catch (NoSuchElementException e) { return null; }
260 *
261 */
262 public final Node<N> getNode(final Node<N> search) {
263 for (final Node<N> node : this.nodes) {
264 if (node.equals(search)) {
265 return node;
266 }
267 }
268 return null;
269 }
270
271 /**
272 * Returns the node whose content is equal to the specified one.
273 *
274 * @param content The content to search for
275 *
276 * @return the found node or null
277 *
278 * @todo this method is not efficient. Do we remove it or add an index on
279 * DGraph using content field? Verify where it is called for migrating it if
280 * necessary.
281 */
282 public final Node<N> getNodeByContent(final Object content) {
283 for (final Node<N> node : this.nodes) {
284 if (node.getContent().equals(content)) {
285 return node;
286 }
287 }
288 return null;
289 }
290
291 /**
292 * Returns the node whose ident is equal to the specified one.
293 *
294 * @param identifier node identifier
295 *
296 * @return the found node or null
297 */
298 public final Node<N> getNodeByIdentifier(int identifier) {
299 for (final Node<N> node : this.nodes) {
300 if (node.getIdentifier() == identifier) {
301 return node;
302 }
303 }
304 return null;
305 }
306
307 /**
308 * Returns the number of nodes of this component.
309 *
310 * @return the number of nodes
311 */
312 public final int sizeNodes() {
313 return this.nodes.size();
314 }
315
316 /**
317 * Returns the number of edges of this component.
318 *
319 * @return the number of edges
320 */
321 public final int sizeEdges() {
322 int size = 0;
323 for (final Node<N> node : this.nodes) {
324 size += this.successors.get(node).size();
325 }
326 return size;
327 }
328
329
330 /*
331 * --------------- NODES AND EDGES MODIFICATION METHODS ------------
332 */
333 /**
334 * Checks if the specified node belong to this component.
335 *
336 * @param node the node to insert
337 *
338 * @return true if the node has been successfully inserted
339 */
340 public final boolean containsNode(final Node<N> node) {
341 return this.nodes.contains(node);
342 }
343
344 /**
345 * Adds the specified node to the set of node of this component.
346 *
347 * @param node the node to insert
348 *
349 * @return true if the node has been successfully inserted
350 */
351 public final boolean addNode(final Node<N> node) {
352 if (!this.containsNode(node)) {
353 this.nodes.add(node);
354 this.successors.put(node, new TreeSet<Edge<N, E>>());
355 this.predecessors.put(node, new TreeSet<Edge<N, E>>());
356 return true;
357 }
358 return false;
359 }
360
361 /**
362 * Removes the specified node from this component.
363 *
364 * @param node the node to remove
365 *
366 * @return true if the node was successfully removed
367 */
368 public final boolean removeNode(final Node<N> node) {
369 if (this.containsNode(node)) {
370 // Remove the edges (node,target) with key node in successors, and key target in predecessors
371 for (final Edge<N, E> successor : this.successors.get(node)) {
372 if (successor.getTarget().compareTo(node) != 0) {
373 for (final Edge<N, E> predecessor : this.predecessors.get(successor.getTarget())) {
374 if (predecessor.getSource().compareTo(node) == 0) {
375 this.predecessors.get(successor.getTarget()).remove(predecessor);
376 }
377 }
378 }
379 this.successors.remove(node);
380 }
381 // Remove the edges (source,node) with key node in predecessors, and key source in successors
382 for (final Edge<N, E> predecessor : this.predecessors.get(node)) {
383 if (predecessor.getSource().compareTo(node) != 0) {
384 for (final Edge<N, E> successor : this.successors.get(predecessor.getSource())) {
385 if (successor.getTarget().compareTo(node) == 0) {
386 this.successors.get(predecessor.getSource()).remove(successor);
387 }
388 }
389 }
390 this.predecessors.remove(node);
391 }
392 // Remove node
393 this.nodes.remove(node);
394 return true;
395 }
396 return false;
397 }
398
399 /**
400 * Removes the specified set of nodes from this component.
401 *
402 * @param nodes set of nodes
403 *
404 * @return true if all nodes were removed
405 */
406 public final boolean removeNodes(final Set<Node<N>> nodes) {
407 boolean all = true;
408 for (final Node<N> node : nodes) {
409 if (!this.removeNode(node)) {
410 all = false;
411 }
412 }
413 return all;
414 }
415
416 /**
417 * Checks if there exists an edge between the two specified nodes.
418 *
419 * @param source the node origine of the edge
420 * @param target the node destination of the edge
421 *
422 * @return true if the edge is contained by this component
423 */
424 public final boolean containsEdge(final Node<N> source, final Node<N> target) {
425 return this.containsNode(source)
426 && this.containsNode(target)
427 && this.getSuccessorNodes(source).contains(target)
428 && this.getPredecessorNodes(target).contains(source);
429 }
430
431 /**
432 * Checks if the specified edge belong to this component.
433 *
434 * @param edge the edge to be checked
435 *
436 * @return true if the edge is contained by this component
437 */
438 public final boolean containsEdge(final Edge<N, E> edge) {
439 return this.containsEdge(edge.getSource(), edge.getTarget());
440 }
441
442 /**
443 * Adds an edge between the specified nodes to this component: `to` is added
444 * as a successor of `source`.
445 *
446 * If the case where specified nodes don't belongs to the node set, then the
447 * edge will not be added.
448 *
449 * @param source the node origin of the edge
450 * @param target the node destination of the edge
451 * @param content the edge content
452 *
453 * @return true if the edge was successfully added
454 */
455 public final boolean addEdge(final Node<N> source, final Node<N> target, final Object content) {
456 if (this.containsNode(source) && this.containsNode(target)) {
457 final Edge<N, E> edge = new Edge(source, target, content);
458 this.successors.get(source).add(edge);
459 this.predecessors.get(target).add(edge);
460 return true;
461 }
462 return false;
463 }
464
465 /**
466 * Adds an edge between the specified nodes to this component: `to` is added
467 * as a successor of `source`.
468 *
469 * If the case where specified nodes don't belongs to the node set, then the
470 * edge will not be added.
471 *
472 * @param source the node origin of the edge
473 * @param target the node destination of the edge
474 *
475 * @return true if the edge was successfully added
476 */
477 public final boolean addEdge(final Node<N> source, final Node<N> target) {
478 return this.addEdge(source, target, null);
479 }
480
481 /**
482 * Adds the specified edge to this component in the successors of
483 * edge.getSource() and in the predecessors of edge.getTarget().
484 *
485 * If the case where nodes to and source of this edges don't belongs to the
486 * node set, then the edge will not be added.
487 *
488 * @param edge the edge to be added
489 *
490 * @return true if the edge was added
491 */
492 public final boolean addEdge(final Edge<N, E> edge) {
493 if (this.containsNode(edge.getSource()) && this.containsNode(edge.getTarget())) {
494 this.successors.get(edge.getSource()).add(edge);
495 this.predecessors.get(edge.getTarget()).add(edge);
496 return true;
497 }
498 return false;
499 }
500
501 /**
502 * Removes source this component the edge between the specified node.
503 *
504 * `to` is removed source the successors of `source` and `to` is removed
505 * source
506 * the predecessors of `source`.
507 *
508 * @param source the node origine of the edge
509 * @param target the node destination of the edge
510 *
511 * @return true if the edge was removed
512 */
513 public final boolean removeEdge(final Node<N> source, final Node<N> target) {
514 if (this.containsEdge(source, target)) {
515 final Edge<N, E> edge = new Edge(source, target);
516 this.successors.get(source).remove(edge);
517 this.predecessors.get(target).remove(edge);
518 return true;
519 }
520 return false;
521 }
522
523 /**
524 * Removes source this component the specified edge source the successors of
525 * edge.getSource() and source the predecessors of edge.getTarget().
526 *
527 * @param edge the edge to be removed.
528 *
529 * @return true if the edge was removed
530 */
531 public final boolean removeEdge(final Edge<N, E> edge) {
532 if (this.containsEdge(edge)) {
533 this.successors.get(edge.getSource()).remove(edge);
534 this.predecessors.get(edge.getTarget()).remove(edge);
535 return true;
536 }
537 return false;
538 }
539
540 /*
541 * --------------- ACYCLIC CHECKING METHODS ------------
542 */
543 /**
544 * Returns the subgraph of this component induced by the specified set of
545 * nodes.
546 *
547 * The subgraph only contains nodes of the specified set that also are in
548 * this component.
549 *
550 * @param nodes The set of nodes
551 *
552 * @return The subgraph
553 *
554 * @todo implement a SubGraph class?
555 */
556 public ConcreteDGraph<N, E> getSubgraphByNodes(final Set<Node<N>> nodes) {
557 ConcreteDGraph<N, E> graph = new ConcreteDGraph<N, E>();
558 // addition of nodes in the subgraph
559 for (Node<N> node : nodes) {
560 if (this.containsNode(node)) {
561 graph.addNode(node);
562 }
563 }
564 // addition of edges in the subgraph
565 for (Edge<N, E> edge : this.getEdges()) {
566 if (graph.containsNode(edge.getTarget())) {
567 graph.addEdge(edge);
568 }
569 }
570 return graph;
571 }
572
573 /**
574 * Returns the subgraph of this component induced by the specified set of
575 * edges.
576 *
577 * The subgraph contains all nodes of this components, and only edges of the
578 * specified set that also are in this component.
579 *
580 * @param edges The set of edges
581 *
582 * @return The subgraph
583 *
584 * @todo implement a SubGraph class?
585 */
586 public ConcreteDGraph<N, E> getSubgraphByEdges(final Set<Edge<N, E>> edges) {
587 ConcreteDGraph<N, E> graph = new ConcreteDGraph<N, E>();
588 // addition of all nodes in the subgraph
589 for (Node<N> node : this.nodes) {
590 graph.addNode(node);
591 }
592 // addition of specified edges in the subgraph
593 for (Edge<N, E> edge : edges) {
594 if (this.containsEdge(edge)) {
595 graph.addEdge(edge);
596 }
597 }
598 return graph;
599 }
600
601 /**
602 * Replaces this component by its complementary graph.
603 *
604 * There is an edge between to nodes in the complementary graph when there
605 * is no edges between the nodes in this component.
606 */
607 public void complementary() {
608 for (Node<N> source : this.nodes) {
609 TreeSet<Node<N>> newSuccessors = new TreeSet<Node<N>>(this.nodes);
610 newSuccessors.removeAll(this.getSuccessorNodes(source));
611 TreeSet<Node<N>> oldSuccessors = new TreeSet<Node<N>>(this.getSuccessorNodes(source));
612 for (Node<N> target : oldSuccessors) {
613 this.removeEdge(source, target);
614 }
615 for (Node<N> target : newSuccessors) {
616 this.addEdge(source, target);
617 }
618 }
619 }
620
621 /*
622 * --------------- GRAPH TREATMENT METHODS ------------
623 */
624 /**
625 * Computes the reflexive reduction of this component.
626 *
627 * @return the number of removed edges
628 */
629 public final int reflexiveReduction() {
630 int size = 0;
631 for (final Node<N> node : this.nodes) {
632 if (this.containsEdge(node, node)) {
633 size++;
634 this.removeEdge(node, node);
635 }
636 }
637 return size;
638 }
639
640 /**
641 * Computes the reflexive closure of this component.
642 *
643 * @return the number of added edges
644 */
645 public final int reflexiveClosure() {
646 int size = 0;
647 for (final Node<N> node : this.nodes) {
648 if (!this.containsEdge(node, node)) {
649 size++;
650 this.addEdge(node, node);
651 }
652 }
653 return size;
654 }
655
656 /**
657 * Computes the transitive closure of this component.
658 *
659 * This treatment is performed in $O(nm+m_c)$, where $n$ corresponds to the
660 * number of nodes, $m$ to the number of edges, and $m_c$ to the number of edges
661 * in the closure. This treatment improves the Roy-Warshall algorithm that
662 * directly implements the definition in $O(log(m) n^3)$.
663 *
664 * This treatment is overridden in class {@link DAGraph} with a more
665 * efficient algorithm dedicated to directed acyclic graph.
666 *
667 * @return the number of added edges
668 */
669 public int transitiveClosure() {
670 int size = 0;
671 // mark each node to false
672 final TreeMap<Node<N>, Boolean> mark = new TreeMap<Node<N>, Boolean>();
673 for (final Node<N> node : this.nodes) {
674 mark.put(node, Boolean.FALSE);
675 }
676 // treatment of nodes
677 final List<Node<N>> list = new ArrayList<Node<N>>();
678 for (final Node<N> source : this.nodes) {
679 list.clear();
680 list.add(source);
681 while (!list.isEmpty()) {
682 // Remove the first node
683 final Node<N> source2 = list.remove(0);
684 for (final Node<N> target : this.getSuccessorNodes(source2)) {
685 // treatment of target when not marked
686 if (!mark.get(target)) {
687 mark.put(target, Boolean.TRUE);
688 this.addEdge(source, target);
689 list.add(target);
690 size++;
691 }
692 }
693 }
694 for (final Node<N> target : this.getSuccessorNodes(source)) {
695 mark.put(target, Boolean.FALSE);
696 }
697 }
698 return size;
699 }
700
701 /**
702 * Transposes this component by replacing for each node its successor set by
703 * its predecessor set, and its predecessor set by its successor set.
704 */
705 public final void transpose() {
706 ConcreteDGraph<N, E> tmp = new ConcreteDGraph<N, E>(this);
707 for (Edge<N, E> edge : tmp.getEdges()) {
708 this.removeEdge(edge);
709 this.addEdge(new Edge(edge.getTarget(), edge.getSource(), edge.getContent()));
710 }
711 }
712
713 /**
714 * Returns the directed acyclic graph where each node corresponds to a
715 * strongly connected component (SCC) of this component stored in a TreeSet
716 * of nodes.
717 *
718 * When two nodes in two different SCC are in relation, the same is for the
719 * SCC they belongs to.
720 *
721 * @return The directed acyclic graph
722 */
723 public DAGraph<SortedSet<Node<N>>, Object> getStronglyConnectedComponent() {
724 DAGraph<SortedSet<Node<N>>, Object> cc = new DAGraph<SortedSet<Node<N>>, Object>();
725 // first depth first search
726 ConcreteDGraph<N, E> tmp = new ConcreteDGraph<N, E>(this);
727 tmp.transitiveClosure();
728 ArrayList<Node<N>> last = tmp.depthFirstSearch()[1];
729 // transposition of the graph
730 ConcreteDGraph<N, E> transposedGraph = new ConcreteDGraph<N, E>(this);
731 transposedGraph.transpose();
732 // sort nodes according to the reverse last sort
733 ArrayList<Node<N>> sort = new ArrayList<Node<N>>();
734 Object[] array = last.toArray();
735 for (int i = array.length - 1; i >= 0; i--) {
736 sort.add((Node<N>) array[i]);
737 }
738 // second depth first search according to sort
739 TreeSet<Node<N>> visited = new TreeSet<Node<N>>();
740 for (Node<N> node : sort) {
741 if (!visited.contains(node)) {
742 last = transposedGraph.depthFirstSearch(node, visited, sort)[1];
743 visited.addAll(last);
744 TreeSet<Node<N>> sCC = new TreeSet<Node<N>>(last);
745 // a strongly connected component is generated
746 cc.addNode(new Node<SortedSet<Node<N>>>(sCC)); // addition of
747 }
748 }
749 // edges between strongly connected component
750 for (Node<SortedSet<Node<N>>> ccSource : cc.getNodes()) {
751 for (Node<SortedSet<Node<N>>> ccTarget : cc.getNodes()) {
752 for (Node<N> source : ccSource.getContent()) {
753 for (Node<N> target : ccTarget.getContent()) {
754 if (tmp.getSuccessorNodes(source).contains(target)) {
755 cc.addEdge(ccSource, ccTarget);
756 }
757 }
758 }
759 }
760 }
761 cc.reflexiveReduction();
762 return cc;
763 }
764
765 /**
766 * Set the set of nodes of this component.
767 *
768 * @param nodes The nodes
769 *
770 * @return this for chaining
771 */
772 protected ConcreteDGraph<N, E> setNodes(final TreeSet<Node<N>> nodes) {
773 this.nodes = nodes;
774 return this;
775 }
776
777 /**
778 * Returns the successors of this component.
779 *
780 * @return the map
781 */
782 protected TreeMap<Node<N>, TreeSet<Edge<N, E>>> getSuccessors() {
783 return this.successors;
784 }
785
786 /**
787 * Set the successors of this component.
788 *
789 * @param successors The successors
790 *
791 * @return this for chaining
792 */
793 protected ConcreteDGraph<N, E> setSuccessors(final TreeMap<Node<N>, TreeSet<Edge<N, E>>> successors) {
794 this.successors = successors;
795 return this;
796 }
797
798 /**
799 * Returns the predecessors of this component.
800 *
801 * @return the map
802 */
803 protected TreeMap<Node<N>, TreeSet<Edge<N, E>>> getPredecessors() {
804 return this.predecessors;
805 }
806
807 /**
808 * Set the predecessors of this component.
809 *
810 * @param predecessors The predecessors
811 *
812 * @return this for chaining
813 */
814 protected ConcreteDGraph<N, E> setPredecessors(final TreeMap<Node<N>, TreeSet<Edge<N, E>>> predecessors) {
815 this.predecessors = predecessors;
816 return this;
817 }
818
819 /**
820 * Returns a two cells array containing the first visited sort on the nodes,
821 * and the last visited sort on the nodes, by a depth first traverse issued
822 * source the specified node.
823 *
824 * @param source The source node
825 * @param visited The visited nodes
826 * @param sort The sort parameter
827 *
828 * @return The array
829 *
830 * @todo Do we change that to iterators? Change to private and add a method
831 * that return an iterator
832 */
833 private ArrayList<Node<N>>[] depthFirstSearch(Node<N> source, TreeSet<Node<N>> visited, ArrayList<Node<N>> sort) {
834 ArrayList<Node<N>> first = new ArrayList<Node<N>>();
835 ArrayList<Node<N>> last = new ArrayList<Node<N>>();
836 first.add(source);
837 visited.add(source);
838 ArrayList<Node<N>>[] arrayVisited = new ArrayList[2];
839 if (sort != null) {
840 // search according to a sort
841 for (Node<N> node : sort) {
842 if (this.getSuccessorNodes(source).contains(node) && !visited.contains(node)) {
843 arrayVisited = this.depthFirstSearch(node, visited, sort);
844 visited.addAll(arrayVisited[0]);
845 first.addAll(arrayVisited[0]);
846 last.addAll(arrayVisited[1]);
847 }
848 }
849 } else {
850 // classical search
851 for (Node<N> node : this.getSuccessorNodes(source)) {
852 if (!visited.contains(node)) {
853 arrayVisited = this.depthFirstSearch(node, visited, sort);
854 visited.addAll(arrayVisited[0]);
855 first.addAll(arrayVisited[0]);
856 last.addAll(arrayVisited[1]);
857 }
858 }
859 }
860 last.add(source);
861 arrayVisited[0] = first;
862 arrayVisited[1] = last;
863 return arrayVisited;
864 }
865
866 /**
867 * Returns a two cells array containing the first visited sort on the nodes,
868 * and the last visited sort on the nodes, by a depth first search.
869 *
870 * @return The array
871 */
872 private ArrayList<Node<N>>[] depthFirstSearch() {
873 TreeSet<Node<N>> visited = new TreeSet<Node<N>>();
874 ArrayList<Node<N>>[] arrayVisited = new ArrayList[2];
875 ArrayList<Node<N>> first = new ArrayList<Node<N>>();
876 ArrayList<Node<N>> last = new ArrayList<Node<N>>();
877 for (Node<N> node : this.nodes) {
878 if (!visited.contains(node)) {
879 arrayVisited = this.depthFirstSearch(node, visited, null);
880 visited.addAll(arrayVisited[0]);
881 first.addAll(arrayVisited[0]);
882 last.addAll(arrayVisited[1]);
883 }
884 }
885 arrayVisited[0] = first;
886 arrayVisited[1] = last;
887 return arrayVisited;
888 }
889
890 /**
891 * This class implements a sorted set of the edges.
892 *
893 * @param <N> Node content type
894 * @param <E> Edge content type
895 */
896 private class Edges<N, E> extends AbstractSet<Edge<N, E>> implements SortedSet<Edge<N, E>> {
897
898 /**
899 * The underlying graph.
900 */
901 private final ConcreteDGraph<N, E> graph;
902
903 /**
904 * Constructs a sorted set of the edges source a graph.
905 *
906 * @param graph A ConcreteDGraph
907 */
908 Edges(final ConcreteDGraph<N, E> graph) {
909 this.graph = graph;
910 }
911
912 /**
913 * Get the underlying graph.
914 *
915 * @return the graph
916 */
917 protected final ConcreteDGraph<N, E> getGraph() {
918 return this.graph;
919 }
920
921 /**
922 * Implements the SortedSet interface.
923 *
924 * @return the first edge
925 */
926 public final Edge<N, E> first() {
927 throw new UnsupportedOperationException();
928 }
929
930 /**
931 * Implements the SortedSet interface.
932 *
933 * @return the last edge
934 */
935 public final Edge<N, E> last() {
936 throw new UnsupportedOperationException();
937 }
938
939 /**
940 * Implements the SortedSet interface.
941 *
942 * @param edge the to edge
943 *
944 * @return The head set
945 *
946 * @throws UnsupportedOperationException
947 */
948 public final SortedSet<Edge<N, E>> headSet(final Edge<N, E> edge) {
949 throw new UnsupportedOperationException();
950 }
951
952 /**
953 * Implements the SortedSet interface.
954 *
955 * @param edge the source edge
956 *
957 * @return The tail set
958 *
959 * @throws UnsupportedOperationException
960 */
961 public final SortedSet<Edge<N, E>> tailSet(final Edge<N, E> edge) {
962 throw new UnsupportedOperationException();
963 }
964
965 /**
966 * Implements the SortedSet interface.
967 *
968 * @param fromEdge the source edge
969 * @param toEdge the to edge
970 *
971 * @return The sub set
972 *
973 * @throws UnsupportedOperationException
974 */
975 public final SortedSet<Edge<N, E>> subSet(final Edge<N, E> fromEdge, final Edge<N, E> toEdge) {
976 throw new UnsupportedOperationException();
977 }
978
979 /**
980 * Implements the SortedSet interface.
981 *
982 * @return null
983 */
984 public final Comparator<? super Edge<N, E>> comparator() {
985 return null;
986 }
987
988 /**
989 * Implements the AbstractCollection class.
990 *
991 * @return the size of the collection
992 */
993 public final int size() {
994 return this.graph.sizeEdges();
995 }
996
997 /**
998 * Implements the AbstractCollection class.
999 *
1000 * @return a new edges iterator
1001 */
1002 public final EdgesIterator iterator() {
1003 return new EdgesIterator(this);
1004 }
1005
1006 /**
1007 * This class implements an iterator over the edges of a graph.
1008 */
1009 private class EdgesIterator implements Iterator<Edge<N, E>> {
1010
1011 /**
1012 * The nodes iterator.
1013 */
1014 private final Iterator<Node<N>> nodesIterator;
1015
1016 /**
1017 * The edges iterator for the current node.
1018 */
1019 private Iterator<Edge<N, E>> edgesIterator;
1020
1021 /**
1022 * The edges object.
1023 */
1024 private final Edges<N, E> edges;
1025
1026 /**
1027 * The hasNext flag.
1028 */
1029 private boolean hasNext;
1030
1031 /**
1032 * Constructs the iterator source a set of edges.
1033 *
1034 * @param edges The edges.
1035 */
1036 EdgesIterator(final Edges<N, E> edges) {
1037 this.edges = edges;
1038 this.nodesIterator = edges.graph.nodes.iterator();
1039 this.prepareNext();
1040 }
1041
1042 /**
1043 * Prepare the next edge and the hasNext flag.
1044 */
1045 private void prepareNext() {
1046 this.hasNext = false;
1047 while (!this.hasNext && this.nodesIterator.hasNext()) {
1048 this.edgesIterator = this.edges.getGraph().successors.get(this.nodesIterator.next()).iterator();
1049 this.hasNext = this.edgesIterator.hasNext();
1050 }
1051 }
1052
1053 /**
1054 * The remove operation is not supported.
1055 *
1056 * @throws UnsupportedOperationException
1057 */
1058 @Override
1059 public void remove() {
1060 throw new UnsupportedOperationException();
1061 }
1062
1063 /**
1064 * The next method returns the next edge.
1065 *
1066 * @return The next edge
1067 */
1068 public Edge<N, E> next() {
1069 Edge<N, E> edge = this.edgesIterator.next();
1070 if (!this.edgesIterator.hasNext()) {
1071 this.prepareNext();
1072 }
1073 return edge;
1074 }
1075
1076 /**
1077 * The hasNext method return true if the iterator has a next edge.
1078 *
1079 * @return true if the iterator has a next edge
1080 */
1081 public boolean hasNext() {
1082 return this.hasNext;
1083 }
1084 }
1085 }
1086 }