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}