File D:\maven-qcr-plugin-testsunitaires\qcr4java\jenkins-master\target\site\qc\core\src\main\java\hudson\util\CyclicGraphDetector.java.html

1 package hudson.util;
2
3 import hudson.Util;
4
5 import java.util.ArrayList;
6 import java.util.Collection;
7 import java.util.HashSet;
8 import java.util.LinkedHashSet;
9 import java.util.List;
10 import java.util.Set;
11 import java.util.Stack;
12
13 /**
14 * Traverses a directed graph and if it contains any cycle, throw an exception.
15 *
16 * @author Kohsuke Kawaguchi
17 */
18 public abstract class CyclicGraphDetector<N> {
19 private final Set<N> visited = new HashSet<N>();
20 private final Set<N> visiting = new HashSet<N>();
21 private final Stack<N> path = new Stack<N>();
22
23 private final List<N> topologicalOrder = new ArrayList<N>();
24
25 public void run(Iterable<? extends N> allNodes) throws CycleDetectedException {
26 for (N n : allNodes){
27 visit(n);
28 }
29 }
30
31 /**
32 * Returns all the nodes in the topologically sorted order.
33 * That is, if there's an edge a->b, b always come earlier than a.
34 */
35 public List<N> getSorted() {
36 return topologicalOrder;
37 }
38
39 /**
40 * List up edges from the given node (by listing nodes that those edges point to.)
41 *
42 * @return
43 * Never null.
44 */
45 protected abstract Iterable<? extends N> getEdges(N n);
46
47 private void visit(N p) throws CycleDetectedException {
48 if (!visited.add(p)) return;
49
50 visiting.add(p);
51 path.push(p);
52 for (N q : getEdges(p)) {
53 if (q==null) continue; // ignore unresolved references
54 if (visiting.contains(q))
55 detectedCycle(q);
56 visit(q);
57 }
58 visiting.remove(p);
59 path.pop();
60 topologicalOrder.add(p);
61 }
62
63 private void detectedCycle(N q) throws CycleDetectedException {
64 int i = path.indexOf(q);
65 path.push(q);
66 reactOnCycle(q, path.subList(i, path.size()));
67 }
68
69 /**
70 * React on detected cycles - default implementation throws an exception.
71 * @param q
72 * @param cycle
73 * @throws CycleDetectedException
74 */
75 protected void reactOnCycle(N q, List<N> cycle) throws CycleDetectedException{
76 throw new CycleDetectedException(cycle);
77 }
78
79 public static final class CycleDetectedException extends Exception {
80 public final List cycle;
81
82 public CycleDetectedException(List cycle) {
83 super("Cycle detected: "+Util.join(cycle," -> "));
84 this.cycle = cycle;
85 }
86 }
87 }
88