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.Collection;
023    import java.util.HashSet;
024    import java.util.Set;
025    
026    public class IncrementalCyclesAndFESSolver<V> {
027    
028      private Set<Cycle> cycles = new HashSet<Cycle>();
029      private Set<Edge> edgesToExclude = new HashSet<Edge>();
030      private long searchCyclesCalls = 0;
031      private static final int DEFAULT_MAX_SEARCH_DEPTH_AT_FIRST = 3;
032      private static final int DEFAULT_MAX_CYCLES_TO_FOUND_BY_ITERATION = 100;
033      private MinimumFeedbackEdgeSetSolver solver;
034      private int iterations = 0;
035    
036      public IncrementalCyclesAndFESSolver(DirectedGraphAccessor<V, ? extends Edge> graph, Collection<V> vertices) {
037        this(graph, vertices, DEFAULT_MAX_SEARCH_DEPTH_AT_FIRST, DEFAULT_MAX_CYCLES_TO_FOUND_BY_ITERATION);
038      }
039    
040      public IncrementalCyclesAndFESSolver(DirectedGraphAccessor<V, ? extends Edge> graph, Collection<V> vertices, int maxSearchDepthAtFirst,
041          int maxCyclesToFoundByIteration) {
042    
043        iterations++;
044        CycleDetector<V> cycleDetector = new CycleDetector<V>(graph, vertices);
045        cycleDetector.detectCyclesWithMaxSearchDepth(maxSearchDepthAtFirst);
046        searchCyclesCalls += cycleDetector.getSearchCyclesCalls();
047        cycles.addAll(cycleDetector.getCycles());
048        solver = new MinimumFeedbackEdgeSetSolver(cycles);
049        edgesToExclude = solver.getEdges();
050    
051        do {
052          iterations++;
053          cycleDetector = new CycleDetector<V>(graph, vertices, edgesToExclude);
054          cycleDetector.detectCyclesWithUpperLimit(maxCyclesToFoundByIteration);
055          searchCyclesCalls += cycleDetector.getSearchCyclesCalls();
056          cycles.addAll(cycleDetector.getCycles());
057          solver = new MinimumFeedbackEdgeSetSolver(cycles);
058          edgesToExclude = solver.getEdges();
059        } while (cycleDetector.getCycles().size() != 0);
060      }
061    
062      public int getWeightOfFeedbackEdgeSet() {
063        return solver.getWeightOfFeedbackEdgeSet();
064      }
065    
066      public int getNumberOfLoops() {
067        return solver.getNumberOfLoops();
068      }
069    
070      public Set<Edge> getFeedbackEdgeSet() {
071        return solver.getEdges();
072      }
073    
074      public Set<Cycle> getCycles() {
075        return cycles;
076      }
077    
078      public boolean isAcyclicGraph() {
079        return cycles.isEmpty();
080      }
081    
082      public long getSearchCyclesCalls() {
083        return searchCyclesCalls;
084      }
085    
086      public int getIterations() {
087        return iterations;
088      }
089    }