001 /*
002 * Sonar, open source software quality management tool.
003 * Copyright (C) 2008-2012 SonarSource
004 * mailto:contact AT sonarsource DOT com
005 *
006 * Sonar is free software; you can redistribute it and/or
007 * modify it under the terms of the GNU Lesser General Public
008 * License as published by the Free Software Foundation; either
009 * version 3 of the License, or (at your option) any later version.
010 *
011 * Sonar is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014 * Lesser General Public License for more details.
015 *
016 * You should have received a copy of the GNU Lesser General Public
017 * License along with Sonar; if not, write to the Free Software
018 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02
019 */
020 package org.sonar.graph;
021
022 import java.util.ArrayList;
023 import java.util.Collection;
024 import java.util.HashSet;
025 import java.util.List;
026 import java.util.Set;
027
028 public class CycleDetector<V> {
029
030 private Set<V> vertices;
031 private DirectedGraphAccessor<V, ? extends Edge> graph;
032 private Set<V> analyzedVertices;
033 private Set<Cycle> cycles = new HashSet<Cycle>();
034 private Set<Edge> edgesToExclude;
035 private long searchCyclesCalls = 0;
036 private int maxSearchDepth = -1;
037 private boolean maxSearchDepthActivated = false;
038 private int maxCyclesToFound = Integer.MAX_VALUE;
039
040 public CycleDetector(DirectedGraphAccessor<V, ? extends Edge> graph, Collection<V> vertices) {
041 init(graph, vertices, new HashSet<Edge>());
042 }
043
044 public CycleDetector(DirectedGraphAccessor<V, ? extends Edge> graph, Collection<V> vertices, Set<Edge> edgesToExclude) {
045 init(graph, vertices, edgesToExclude);
046 }
047
048 public CycleDetector(DirectedGraphAccessor<V, ? extends Edge> graph) {
049 init(graph, graph.getVertices(), new HashSet<Edge>());
050 }
051
052 public CycleDetector(DirectedGraphAccessor<V, ? extends Edge> graph, Set<Edge> edgesToExclude) {
053 init(graph, graph.getVertices(), edgesToExclude);
054 }
055
056 private void init(DirectedGraphAccessor<V, ? extends Edge> graph, Collection<V> vertices, Set<Edge> edgesToExclude) {
057 this.graph = graph;
058 this.vertices = new HashSet<V>(vertices);
059 this.analyzedVertices = new HashSet<V>();
060 this.edgesToExclude = edgesToExclude;
061 }
062
063 public Set<Cycle> detectCycles() {
064 run();
065 return getCycles();
066 }
067
068 public Set<Cycle> detectCyclesWithUpperLimit(int maxCyclesToFound) {
069 this.maxCyclesToFound = maxCyclesToFound;
070 run();
071 return getCycles();
072 }
073
074 public Set<Cycle> detectCyclesWithMaxSearchDepth(int maxSearchDepth) {
075 if (maxSearchDepth > 1) {
076 maxSearchDepthActivated = true;
077 this.maxSearchDepth = maxSearchDepth;
078 }
079 run();
080 return getCycles();
081 }
082
083 private void run() {
084 if (!cycles.isEmpty()) {
085 throw new IllegalStateException("Cycle detection can't be executed twice on the same CycleDetector object.");
086 }
087 try {
088 for (V vertex : vertices) {
089 if (maxSearchDepthActivated || !analyzedVertices.contains(vertex)) {
090 Set<V> tmpAnalyzedVertices = new HashSet<V>();
091 searchCycles(vertex, new ArrayList<V>(), tmpAnalyzedVertices);
092 analyzedVertices.addAll(tmpAnalyzedVertices);
093 }
094 }
095 } catch (MaximumCyclesToFoundException e) {
096 // ignore
097 }
098 }
099
100 private void searchCycles(V fromVertex, List<V> path, Set<V> tmpAnalyzedVertices) {
101 searchCyclesCalls++;
102 path.add(fromVertex);
103 tmpAnalyzedVertices.add(fromVertex);
104 for (Edge<V> edge : graph.getOutgoingEdges(fromVertex)) {
105 V toVertex = edge.getTo();
106 if (!edgesToExclude.contains(edge) && vertices.contains(toVertex)
107 && (maxSearchDepthActivated || !analyzedVertices.contains(toVertex))) {
108 if (path.contains(toVertex)) {
109 path.add(toVertex);
110 List<V> cyclePath = path.subList(path.indexOf(toVertex), path.size());
111 Cycle cycle = convertListOfVerticesToCycle(cyclePath);
112 cycles.add(cycle);
113
114 if (cycles.size() >= maxCyclesToFound) {
115 throw new MaximumCyclesToFoundException();
116 }
117 path.remove(path.size() - 1);
118 } else if (!maxSearchDepthActivated || (maxSearchDepthActivated && path.size() < maxSearchDepth)) {
119 searchCycles(toVertex, path, tmpAnalyzedVertices);
120 }
121 }
122 }
123 path.remove(path.size() - 1);
124 }
125
126 private Cycle convertListOfVerticesToCycle(List<V> vertices) {
127 List<Edge> edges = new ArrayList<Edge>();
128 V firstVertex = vertices.get(0);
129 V from = firstVertex;
130 for (int index = 1; index < vertices.size(); index++) {
131 V to = vertices.get(index);
132 edges.add(graph.getEdge(from, to));
133 from = to;
134 }
135 return new Cycle(edges);
136 }
137
138 public Set<Cycle> getCycles() {
139 return cycles;
140 }
141
142 public boolean isAcyclicGraph() {
143 return cycles.isEmpty();
144 }
145
146 public long getSearchCyclesCalls() {
147 return searchCyclesCalls;
148 }
149
150 }
151
152 class MaximumCyclesToFoundException extends RuntimeException {
153 }