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