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 }