001 /* 002 * Sonar, open source software quality management tool. 003 * Copyright (C) 2009 SonarSource SA 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 } 097 } 098 099 private void searchCycles(V fromVertex, List<V> path, Set<V> tmpAnalyzedVertices) { 100 searchCyclesCalls++; 101 path.add(fromVertex); 102 tmpAnalyzedVertices.add(fromVertex); 103 for (Edge<V> edge : graph.getOutgoingEdges(fromVertex)) { 104 V toVertex = edge.getTo(); 105 if (!edgesToExclude.contains(edge) && vertices.contains(toVertex) 106 && (maxSearchDepthActivated || !analyzedVertices.contains(toVertex))) { 107 if (path.contains(toVertex)) { 108 path.add(toVertex); 109 List<V> cyclePath = path.subList(path.indexOf(toVertex), path.size()); 110 Cycle cycle = convertListOfVerticesToCycle(cyclePath); 111 cycles.add(cycle); 112 113 if (cycles.size() >= maxCyclesToFound) { 114 throw new MaximumCyclesToFoundException(); 115 } 116 path.remove(path.size() - 1); 117 } else if (!maxSearchDepthActivated || (maxSearchDepthActivated && path.size() < maxSearchDepth)) { 118 searchCycles(toVertex, path, tmpAnalyzedVertices); 119 } 120 } 121 } 122 path.remove(path.size() - 1); 123 } 124 125 private Cycle convertListOfVerticesToCycle(List<V> vertices) { 126 List<Edge> edges = new ArrayList<Edge>(); 127 V firstVertex = vertices.get(0); 128 V from = firstVertex; 129 for (int index = 1; index < vertices.size(); index++) { 130 V to = vertices.get(index); 131 edges.add(graph.getEdge(from, to)); 132 from = to; 133 } 134 return new Cycle(edges); 135 } 136 137 public Set<Cycle> getCycles() { 138 return cycles; 139 } 140 141 public boolean isAcyclicGraph() { 142 return cycles.isEmpty(); 143 } 144 145 public long getSearchCyclesCalls() { 146 return searchCyclesCalls; 147 } 148 149 } 150 151 class MaximumCyclesToFoundException extends RuntimeException { 152 }