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.*; 023 024 public class MinimumFeedbackEdgeSetSolver { 025 026 private final List<FeedbackCycle> feedbackCycles; 027 private Set<FeedbackEdge> feedbackEdges; 028 private int minimumFeedbackEdgesWeight = Integer.MAX_VALUE; 029 private final int cyclesNumber; 030 private final int maxNumberCyclesForSearchingMinimumFeedback; 031 private static final int DEFAULT_MAXIMUM_NUMBER_OF_LOOPS = 1000000; 032 private static final int MAXIMUM_NUMBER_OF_CYCLE_THAT_CAN_BE_HANDLED = 1500; 033 private final int maximumNumberOfLoops; 034 035 public int getNumberOfLoops() { 036 return numberOfLoops; 037 } 038 039 private int numberOfLoops = 0; 040 041 public MinimumFeedbackEdgeSetSolver(Set<Cycle> cycles, int maxCycles) { 042 this(cycles, DEFAULT_MAXIMUM_NUMBER_OF_LOOPS, maxCycles); 043 } 044 045 public MinimumFeedbackEdgeSetSolver(Set<Cycle> cycles) { 046 this(cycles, DEFAULT_MAXIMUM_NUMBER_OF_LOOPS, MAXIMUM_NUMBER_OF_CYCLE_THAT_CAN_BE_HANDLED); 047 } 048 049 public MinimumFeedbackEdgeSetSolver(Set<Cycle> cycles, int maximumNumberOfLoops, int maxNumberCyclesForSearchingMinimumFeedback) { 050 this.maximumNumberOfLoops = maximumNumberOfLoops; 051 this.feedbackCycles = FeedbackCycle.buildFeedbackCycles(cycles); 052 this.cyclesNumber = cycles.size(); 053 this.maxNumberCyclesForSearchingMinimumFeedback = maxNumberCyclesForSearchingMinimumFeedback; 054 this.run(); 055 } 056 057 public int getWeightOfFeedbackEdgeSet() { 058 return minimumFeedbackEdgesWeight; 059 } 060 061 /** 062 * Get edges tagged as feedback. 063 */ 064 public Set<Edge> getEdges() { 065 Set<Edge> edges = new HashSet<Edge>(); 066 for (FeedbackEdge fe : feedbackEdges) { 067 edges.add(fe.getEdge()); 068 } 069 return edges; 070 } 071 072 private void run() { 073 Set<FeedbackEdge> pendingFeedbackEdges = new HashSet<FeedbackEdge>(); 074 if (cyclesNumber < maxNumberCyclesForSearchingMinimumFeedback) { 075 searchFeedbackEdges(0, 0, pendingFeedbackEdges); 076 } 077 else { 078 lightResearchForFeedbackEdges(); 079 } 080 } 081 082 private void lightResearchForFeedbackEdges() { 083 feedbackEdges = new HashSet<FeedbackEdge>(); 084 for (FeedbackCycle cycle : feedbackCycles) { 085 for (FeedbackEdge edge : cycle) { 086 feedbackEdges.add(edge); 087 break; 088 } 089 } 090 minimumFeedbackEdgesWeight = 0; 091 for(FeedbackEdge edge : feedbackEdges) { 092 minimumFeedbackEdgesWeight += edge.getWeight(); 093 } 094 } 095 096 private void searchFeedbackEdges(int level, int pendingWeight, Set<FeedbackEdge> pendingFeedbackEdges) { 097 if (numberOfLoops++ > maximumNumberOfLoops) { 098 return; 099 } 100 101 if (pendingWeight >= minimumFeedbackEdgesWeight) { 102 return; 103 } 104 105 if (level == cyclesNumber) { 106 minimumFeedbackEdgesWeight = pendingWeight; 107 feedbackEdges = new HashSet<FeedbackEdge>(pendingFeedbackEdges); 108 return; 109 } 110 111 FeedbackCycle feedbackCycle = feedbackCycles.get(level); 112 113 if (doesFeedbackEdgesContainAnEdgeOfTheCycle(pendingFeedbackEdges, feedbackCycle)) { 114 searchFeedbackEdges(level + 1, pendingWeight, pendingFeedbackEdges); 115 } 116 else { 117 boolean hasAnEdgeWithOccurrenceOfOneBeenUsed = false; 118 for (FeedbackEdge feedbackEdge : feedbackCycle) { 119 if (feedbackEdge.getOccurences() == 1) { 120 if (hasAnEdgeWithOccurrenceOfOneBeenUsed) { 121 continue; 122 } 123 else { 124 hasAnEdgeWithOccurrenceOfOneBeenUsed = true; 125 } 126 } 127 int edgeWeight = addNewEdge(feedbackEdge, pendingFeedbackEdges); 128 pendingWeight += edgeWeight; 129 130 searchFeedbackEdges(level + 1, pendingWeight, pendingFeedbackEdges); 131 pendingWeight -= edgeWeight; 132 pendingFeedbackEdges.remove(feedbackEdge); 133 } 134 } 135 } 136 137 private boolean doesFeedbackEdgesContainAnEdgeOfTheCycle(Set<FeedbackEdge> pendingFeedbackEdges, FeedbackCycle cycle) { 138 boolean contains = false; 139 for (FeedbackEdge feedbackEdge : cycle) { 140 if (pendingFeedbackEdges.contains(feedbackEdge)) { 141 contains = true; 142 break; 143 } 144 } 145 return contains; 146 } 147 148 private int addNewEdge(FeedbackEdge feedbackEdge, Set<FeedbackEdge> pendingFeedbackEdges) { 149 pendingFeedbackEdges.add(feedbackEdge); 150 return feedbackEdge.getWeight(); 151 } 152 }