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.*;
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 //System.out.println("Weight : " + minimumFeedbackEdgesWeight + " in " + numberOfLoops + " loops");
109 return;
110 }
111
112 FeedbackCycle feedbackCycle = feedbackCycles.get(level);
113
114 if (doesFeedbackEdgesContainAnEdgeOfTheCycle(pendingFeedbackEdges, feedbackCycle)) {
115 searchFeedbackEdges(level + 1, pendingWeight, pendingFeedbackEdges);
116 }
117 else {
118 boolean hasAnEdgeWithOccurrenceOfOneBeenUsed = false;
119 for (FeedbackEdge feedbackEdge : feedbackCycle) {
120 if (feedbackEdge.getOccurences() == 1) {
121 if (hasAnEdgeWithOccurrenceOfOneBeenUsed) {
122 continue;
123 }
124 else {
125 hasAnEdgeWithOccurrenceOfOneBeenUsed = true;
126 }
127 }
128 int edgeWeight = addNewEdge(feedbackEdge, pendingFeedbackEdges);
129 pendingWeight += edgeWeight;
130
131 searchFeedbackEdges(level + 1, pendingWeight, pendingFeedbackEdges);
132 pendingWeight -= edgeWeight;
133 pendingFeedbackEdges.remove(feedbackEdge);
134 }
135 }
136 }
137
138 private boolean doesFeedbackEdgesContainAnEdgeOfTheCycle(Set<FeedbackEdge> pendingFeedbackEdges, FeedbackCycle cycle) {
139 boolean contains = false;
140 for (FeedbackEdge feedbackEdge : cycle) {
141 if (pendingFeedbackEdges.contains(feedbackEdge)) {
142 contains = true;
143 break;
144 }
145 }
146 return contains;
147 }
148
149 private int addNewEdge(FeedbackEdge feedbackEdge, Set<FeedbackEdge> pendingFeedbackEdges) {
150 pendingFeedbackEdges.add(feedbackEdge);
151 return feedbackEdge.getWeight();
152 }
153 }