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 */
020package org.sonar.graph;
021
022import java.util.ArrayList;
023import java.util.Collection;
024import java.util.HashSet;
025import java.util.List;
026import java.util.Set;
027
028public 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
152class MaximumCyclesToFoundException extends RuntimeException {
153}