From aeadc1f9129274949daaa57738c7c4550bdfbc7b Mon Sep 17 00:00:00 2001 From: simonbrandhof Date: Mon, 6 Sep 2010 14:08:06 +0000 Subject: SONAR-236 remove deprecated code from checkstyle plugin + display default value of rule parameters in Q profile console --- sonar-graph/pom.xml | 35 +++++ .../src/main/java/org/sonar/graph/Cycle.java | 85 +++++++++++ .../main/java/org/sonar/graph/CycleDetector.java | 152 ++++++++++++++++++++ .../main/java/org/sonar/graph/DirectedGraph.java | 144 +++++++++++++++++++ .../org/sonar/graph/DirectedGraphAccessor.java | 36 +++++ sonar-graph/src/main/java/org/sonar/graph/Dsm.java | 159 +++++++++++++++++++++ .../src/main/java/org/sonar/graph/DsmCell.java | 46 ++++++ .../main/java/org/sonar/graph/DsmManualSorter.java | 61 ++++++++ .../src/main/java/org/sonar/graph/DsmPrinter.java | 104 ++++++++++++++ .../src/main/java/org/sonar/graph/DsmScanner.java | 113 +++++++++++++++ .../java/org/sonar/graph/DsmTopologicalSorter.java | 71 +++++++++ .../src/main/java/org/sonar/graph/Edge.java | 30 ++++ .../src/main/java/org/sonar/graph/EdgeFactory.java | 27 ++++ .../main/java/org/sonar/graph/FeedbackCycle.java | 107 ++++++++++++++ .../main/java/org/sonar/graph/FeedbackEdge.java | 75 ++++++++++ .../sonar/graph/IncrementalCyclesAndFESSolver.java | 89 ++++++++++++ .../sonar/graph/MinimumFeedbackEdgeSetSolver.java | 153 ++++++++++++++++++++ .../src/main/java/org/sonar/graph/StringEdge.java | 71 +++++++++ .../java/org/sonar/graph/StringEdgeFactory.java | 31 ++++ .../java/org/sonar/graph/CycleDetectorTest.java | 156 ++++++++++++++++++++ .../src/test/java/org/sonar/graph/CycleTest.java | 58 ++++++++ .../java/org/sonar/graph/DirectedGraphTest.java | 106 ++++++++++++++ .../src/test/java/org/sonar/graph/DsmCellTest.java | 45 ++++++ .../java/org/sonar/graph/DsmManualSorterTest.java | 46 ++++++ .../test/java/org/sonar/graph/DsmPrinterTest.java | 64 +++++++++ .../test/java/org/sonar/graph/DsmScannerTest.java | 55 +++++++ .../src/test/java/org/sonar/graph/DsmTest.java | 77 ++++++++++ .../org/sonar/graph/DsmTopologicalSorterTest.java | 112 +++++++++++++++ .../java/org/sonar/graph/FeedbackCycleTest.java | 66 +++++++++ .../java/org/sonar/graph/FeedbackEdgeTest.java | 81 +++++++++++ .../graph/IncrementalCyclesAndFESSolverTest.java | 73 ++++++++++ .../graph/MinimumFeedbackEdgeSetSolverTest.java | 110 ++++++++++++++ .../java/org/sonar/graph/StringPrintWriter.java | 34 +++++ 33 files changed, 2672 insertions(+) create mode 100644 sonar-graph/pom.xml create mode 100644 sonar-graph/src/main/java/org/sonar/graph/Cycle.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/CycleDetector.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/DirectedGraph.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/DirectedGraphAccessor.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/Dsm.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/DsmCell.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/DsmManualSorter.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/DsmPrinter.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/DsmScanner.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/DsmTopologicalSorter.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/Edge.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/EdgeFactory.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/FeedbackCycle.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/FeedbackEdge.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/IncrementalCyclesAndFESSolver.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/MinimumFeedbackEdgeSetSolver.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/StringEdge.java create mode 100644 sonar-graph/src/main/java/org/sonar/graph/StringEdgeFactory.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/CycleDetectorTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/CycleTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/DirectedGraphTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/DsmCellTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/DsmManualSorterTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/DsmPrinterTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/DsmScannerTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/DsmTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/DsmTopologicalSorterTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/FeedbackCycleTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/FeedbackEdgeTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/IncrementalCyclesAndFESSolverTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/MinimumFeedbackEdgeSetSolverTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/StringPrintWriter.java (limited to 'sonar-graph') diff --git a/sonar-graph/pom.xml b/sonar-graph/pom.xml new file mode 100644 index 00000000000..62942050670 --- /dev/null +++ b/sonar-graph/pom.xml @@ -0,0 +1,35 @@ + + + 4.0.0 + + org.codehaus.sonar + sonar + 2.3-SNAPSHOT + .. + + org.codehaus.sonar + sonar-graph + jar + Sonar :: Graph + + + + commons-lang + commons-lang + + + com.google.collections + google-collections + + + junit + junit + test + + + org.hamcrest + hamcrest-all + test + + + \ No newline at end of file diff --git a/sonar-graph/src/main/java/org/sonar/graph/Cycle.java b/sonar-graph/src/main/java/org/sonar/graph/Cycle.java new file mode 100644 index 00000000000..84353b485d7 --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/Cycle.java @@ -0,0 +1,85 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.List; + +public class Cycle { + + private Edge[] edges; + private int hashcode = 0; + + public Cycle(List edges) { + this.edges = edges.toArray(new Edge[0]); + for(Edge edge : edges) { + hashcode += edge.hashCode(); + } + } + + public int size() { + return edges.length; + } + + public boolean contains(Edge e) { + for (Edge edge : edges) { + if (edge.equals(e)) { + return true; + } + } + return false; + } + + public Edge[] getEdges() { + return edges; + } + + @Override + public String toString() { + StringBuilder builder = new StringBuilder("Cycle with " + size() + " edges : "); + for (Edge edge : edges) { + builder.append(edge.getFrom()).append(" -> "); + } + return builder.toString(); + } + + @Override + public int hashCode() { + return hashcode; + } + + @Override + public boolean equals(Object object) { + if (object instanceof Cycle) { + Cycle otherCycle = (Cycle) object; + if (otherCycle.hashcode == hashcode && otherCycle.edges.length == edges.length) { + mainLoop: for (Edge otherEdge : otherCycle.edges) { + for (Edge edge : edges) { + if (otherEdge.equals(edge)) { + continue mainLoop; + } + } + return false; + } + return true; + } + } + return false; + } +} \ No newline at end of file diff --git a/sonar-graph/src/main/java/org/sonar/graph/CycleDetector.java b/sonar-graph/src/main/java/org/sonar/graph/CycleDetector.java new file mode 100644 index 00000000000..df6062ab5ff --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/CycleDetector.java @@ -0,0 +1,152 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +public class CycleDetector { + + private Set vertices; + private DirectedGraphAccessor graph; + private Set analyzedVertices; + private Set cycles = new HashSet(); + private Set edgesToExclude; + private long searchCyclesCalls = 0; + private int maxSearchDepth = -1; + private boolean maxSearchDepthActivated = false; + private int maxCyclesToFound = Integer.MAX_VALUE; + + public CycleDetector(DirectedGraphAccessor graph, Collection vertices) { + init(graph, vertices, new HashSet()); + } + + public CycleDetector(DirectedGraphAccessor graph, Collection vertices, Set edgesToExclude) { + init(graph, vertices, edgesToExclude); + } + + public CycleDetector(DirectedGraphAccessor graph) { + init(graph, graph.getVertices(), new HashSet()); + } + + public CycleDetector(DirectedGraphAccessor graph, Set edgesToExclude) { + init(graph, graph.getVertices(), edgesToExclude); + } + + private void init(DirectedGraphAccessor graph, Collection vertices, Set edgesToExclude) { + this.graph = graph; + this.vertices = new HashSet(vertices); + this.analyzedVertices = new HashSet(); + this.edgesToExclude = edgesToExclude; + } + + public Set detectCycles() { + run(); + return getCycles(); + } + + public Set detectCyclesWithUpperLimit(int maxCyclesToFound) { + this.maxCyclesToFound = maxCyclesToFound; + run(); + return getCycles(); + } + + public Set detectCyclesWithMaxSearchDepth(int maxSearchDepth) { + if (maxSearchDepth > 1) { + maxSearchDepthActivated = true; + this.maxSearchDepth = maxSearchDepth; + } + run(); + return getCycles(); + } + + private void run() { + if (!cycles.isEmpty()) { + throw new IllegalStateException("Cycle detection can't be executed twice on the same CycleDetector object."); + } + try { + for (V vertex : vertices) { + if (maxSearchDepthActivated || !analyzedVertices.contains(vertex)) { + Set tmpAnalyzedVertices = new HashSet(); + searchCycles(vertex, new ArrayList(), tmpAnalyzedVertices); + analyzedVertices.addAll(tmpAnalyzedVertices); + } + } + } catch (MaximumCyclesToFoundException e) { + } + } + + private void searchCycles(V fromVertex, List path, Set tmpAnalyzedVertices) { + searchCyclesCalls++; + path.add(fromVertex); + tmpAnalyzedVertices.add(fromVertex); + for (Edge edge : graph.getOutgoingEdges(fromVertex)) { + V toVertex = edge.getTo(); + if (!edgesToExclude.contains(edge) && vertices.contains(toVertex) + && (maxSearchDepthActivated || !analyzedVertices.contains(toVertex))) { + if (path.contains(toVertex)) { + path.add(toVertex); + List cyclePath = path.subList(path.indexOf(toVertex), path.size()); + Cycle cycle = convertListOfVerticesToCycle(cyclePath); + cycles.add(cycle); + + if (cycles.size() >= maxCyclesToFound) { + throw new MaximumCyclesToFoundException(); + } + path.remove(path.size() - 1); + } else if (!maxSearchDepthActivated || (maxSearchDepthActivated && path.size() < maxSearchDepth)) { + searchCycles(toVertex, path, tmpAnalyzedVertices); + } + } + } + path.remove(path.size() - 1); + } + + private Cycle convertListOfVerticesToCycle(List vertices) { + List edges = new ArrayList(); + V firstVertex = vertices.get(0); + V from = firstVertex; + for (int index = 1; index < vertices.size(); index++) { + V to = vertices.get(index); + edges.add(graph.getEdge(from, to)); + from = to; + } + return new Cycle(edges); + } + + public Set getCycles() { + return cycles; + } + + public boolean isAcyclicGraph() { + return cycles.isEmpty(); + } + + public long getSearchCyclesCalls() { + return searchCyclesCalls; + } + +} + +class MaximumCyclesToFoundException extends RuntimeException { +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/DirectedGraph.java b/sonar-graph/src/main/java/org/sonar/graph/DirectedGraph.java new file mode 100644 index 00000000000..816a01422bc --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/DirectedGraph.java @@ -0,0 +1,144 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Set; + +public class DirectedGraph> implements DirectedGraphAccessor { + + private EdgeFactory edgeFactory; + private Map> outgoingEdgesByVertex = new HashMap>(); + private Map> incomingEdgesByVertex = new HashMap>(); + private Set vertices = new HashSet(); + + public DirectedGraph() { + } + + public DirectedGraph(EdgeFactory edgeFactory) { + this.edgeFactory = edgeFactory; + } + + public static DirectedGraph createStringDirectedGraph() { + return new DirectedGraph(new StringEdgeFactory()); + } + + public DirectedGraph addEdge(V from, V to) { + checkEdgeFacory(); + E edge = edgeFactory.createEdge(from, to); + return addEdge(edge); + } + + public DirectedGraph addEdge(V from, V to, int weight) { + checkEdgeFacory(); + E edge = edgeFactory.createEdge(from, to, weight); + return addEdge(edge); + } + + private void checkEdgeFacory() { + if (edgeFactory == null) { + throw new IllegalStateException( + "EdgeFactory has not been defined. Please use the 'public E addEdge(V from, V to, E edge)' method."); + } + } + + public DirectedGraph addEdge(E edge) { + addEdgeToMap(edge.getFrom(), edge.getTo(), edge, outgoingEdgesByVertex); + addEdgeToMap(edge.getTo(), edge.getFrom(), edge, incomingEdgesByVertex); + vertices.add(edge.getFrom()); + vertices.add(edge.getTo()); + return this; + } + + private void addEdgeToMap(V vertexKey1, V vertexKey2, E edge, Map> edgesByVertex) { + Map edges = edgesByVertex.get(vertexKey1); + if (edges == null) { + edges = new HashMap(); + edgesByVertex.put(vertexKey1, edges); + } + if (edges.containsKey(vertexKey2)) { + throw new IllegalStateException("The graph already contains the edge : " + edge); + } + edges.put(vertexKey2, edge); + } + + public E getEdge(V from, V to) { + Map outgoingEdgesFrom = outgoingEdgesByVertex.get(from); + if (outgoingEdgesFrom == null) { + return null; + } else { + return outgoingEdgesFrom.get(to); + } + } + + public boolean hasEdge(V from, V to) { + Map outgoingEdges = outgoingEdgesByVertex.get(from); + if (outgoingEdges == null) { + return false; + } + return outgoingEdges.containsKey(to); + } + + public void addVertex(V vertex) { + vertices.add(vertex); + } + + public void addVertices(Collection vertices) { + for (V vertex : vertices) { + addVertex(vertex); + } + } + + public Set getVertices() { + return vertices; + } + + public List getEdges(Collection vertices) { + List result = new ArrayList(); + for (V vertice : vertices) { + Collection outgoingEdges = getOutgoingEdges(vertice); + if (outgoingEdges != null) { + result.addAll(outgoingEdges); + } + } + return result; + } + + public Collection getOutgoingEdges(V from) { + Map outgoingEdges = outgoingEdgesByVertex.get(from); + if (outgoingEdges == null) { + return new HashSet(); + } + return outgoingEdges.values(); + } + + public Collection getIncomingEdges(V to) { + Map incomingEdges = incomingEdgesByVertex.get(to); + if (incomingEdges == null) { + return new HashSet(); + } + return incomingEdges.values(); + } +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/DirectedGraphAccessor.java b/sonar-graph/src/main/java/org/sonar/graph/DirectedGraphAccessor.java new file mode 100644 index 00000000000..219adf38222 --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/DirectedGraphAccessor.java @@ -0,0 +1,36 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.Collection; +import java.util.Set; + +public interface DirectedGraphAccessor> { + + E getEdge(V from, V to); + + boolean hasEdge(V from, V to); + + Set getVertices(); + + Collection getOutgoingEdges(V from); + + Collection getIncomingEdges(V to); +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/Dsm.java b/sonar-graph/src/main/java/org/sonar/graph/Dsm.java new file mode 100644 index 00000000000..1c3527d37ca --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/Dsm.java @@ -0,0 +1,159 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.Collection; +import java.util.Collections; +import java.util.Set; + +public class Dsm { + + private V[] vertices; + private DsmCell[][] cells; + private int dimension; + private DirectedGraphAccessor> graph; + + public Dsm(DirectedGraphAccessor> graph, Collection vertices, Set feedbackEdges) { + this.graph = graph; + this.dimension = vertices.size(); + this.cells = new DsmCell[dimension][dimension]; + initVertices(vertices); + initCells(feedbackEdges); + } + + public Dsm(DirectedGraphAccessor> acyclicGraph, Set feedbackEdges) { + this(acyclicGraph, acyclicGraph.getVertices(), feedbackEdges); + } + + public Dsm(DirectedGraphAccessor> acyclicGraph) { + this(acyclicGraph, acyclicGraph.getVertices(), Collections.emptySet()); + } + + private void initCells(Set feedbackEdges) { + for (int x = 0; x < dimension; x++) { + for (int y = 0; y < dimension; y++) { + V from = vertices[x]; + V to = vertices[y]; + + Edge edge = graph.getEdge(from, to); + boolean isFeedbackEdge = (edge != null && feedbackEdges.contains(edge)); + DsmCell cell = new DsmCell(edge, isFeedbackEdge); + cells[x][y] = cell; + } + } + } + + private void initVertices(Collection verticesCol) { + this.vertices = (V[]) new Object[dimension]; + int i = 0; + for (V vertex : verticesCol) { + vertices[i] = vertex; + i++; + } + } + + public V getVertex(int rowIndex) { + return vertices[rowIndex]; + } + + public int getDimension() { + return dimension; + } + + public void permute(int fromIndex, int toIndex) { + if (fromIndex != toIndex) { + checkIndicesBoudaries(fromIndex, toIndex); + permuteVertice(fromIndex, toIndex); + permuteColumns(fromIndex, toIndex); + permuteRows(fromIndex, toIndex); + } + } + + private void checkIndicesBoudaries(int... indices) { + for (int index : indices) { + if (index < 0 || index >= dimension) { + StringBuilder builder = new StringBuilder("DSM contains the following vertices : "); + for (V vertex : vertices) { + builder.append(vertex.toString()).append(" | "); + } + builder.append(". Trying to reach index ").append(index); + throw new ArrayIndexOutOfBoundsException(builder.toString()); + } + } + } + + private void permuteVertice(int fromIndex, int toIndex) { + V fromVertex = vertices[fromIndex]; + V toVertex = vertices[toIndex]; + vertices[fromIndex] = toVertex; + vertices[toIndex] = fromVertex; + } + + private void permuteRows(int fromYIndex, int toYIndex) { + for (int x = 0; x < dimension; x++) { + permuteCells(x, fromYIndex, x, toYIndex); + } + } + + private void permuteColumns(int fromXIndex, int toXIndex) { + for (int y = 0; y < dimension; y++) { + permuteCells(fromXIndex, y, toXIndex, y); + } + } + + private void permuteCells(int fromXIndex, int fromYIndex, int toXIndex, int toYIndex) { + DsmCell fromCell = cells[fromXIndex][fromYIndex]; + DsmCell toCell = cells[toXIndex][toYIndex]; + cells[toXIndex][toYIndex] = fromCell; + cells[fromXIndex][fromYIndex] = toCell; + } + + public int getNumberOfIncomingEdges(int y, int from, int to) { + int incomingEdges = 0; + for (int x = from; x <= to; x++) { + DsmCell cell = cells[x][y]; + if (cell.getWeight() != 0 && !cell.isFeedbackEdge()) { + incomingEdges++; + } + } + return incomingEdges; + } + + public int getNumberOfOutgoingEdges(int x, int from, int to) { + int outgoingEdges = 0; + for (int y = from; y <= to; y++) { + DsmCell cell = cells[x][y]; + if (cell.getWeight() != 0 && !cell.isFeedbackEdge()) { + outgoingEdges++; + } + } + return outgoingEdges; + } + + public DsmCell getCell(int x, int y) { + return cells[x][y]; + } + + public V[] getVertices() { + V[] verticesCopy = (V[]) new Object[vertices.length]; + System.arraycopy(vertices, 0, verticesCopy, 0, vertices.length); + return verticesCopy; + } +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/DsmCell.java b/sonar-graph/src/main/java/org/sonar/graph/DsmCell.java new file mode 100644 index 00000000000..0e992922c16 --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/DsmCell.java @@ -0,0 +1,46 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +public class DsmCell { + + private final Edge edge; + private final boolean feedbackEdge; + + public DsmCell(Edge edge, boolean isFeedbackEdge) { + this.feedbackEdge = isFeedbackEdge; + this.edge = edge; + } + + public int getWeight() { + return (edge==null) ? 0 : edge.getWeight(); + } + + public boolean isFeedbackEdge() { + return feedbackEdge; + } + + /** + * @return nullable edge + */ + public Edge getEdge() { + return edge; + } +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/DsmManualSorter.java b/sonar-graph/src/main/java/org/sonar/graph/DsmManualSorter.java new file mode 100644 index 00000000000..26069308de8 --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/DsmManualSorter.java @@ -0,0 +1,61 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.Arrays; +import java.util.List; + + +public final class DsmManualSorter { + + private final Dsm dsm; + private final List verticesInDesiredOrder; + + private DsmManualSorter(Dsm dsm, List verticesInDesiredOrder) { + this.dsm = dsm; + this.verticesInDesiredOrder = verticesInDesiredOrder; + } + + public static void sort(Dsm dsm, List vertices) { + DsmManualSorter sorter = new DsmManualSorter(dsm, vertices); + sorter.sort(); + } + + public static void sort(Dsm dsm, V... vertices) { + sort(dsm, Arrays.asList(vertices)); + } + + private void sort() { + for (int desiredIndex = 0; desiredIndex < verticesInDesiredOrder.size(); desiredIndex++) { + int currentIndex = getCurrentIndex(verticesInDesiredOrder.get(desiredIndex)); + dsm.permute(currentIndex, desiredIndex); + } + } + + private int getCurrentIndex(V v) { + for (int currentIndex = 0; currentIndex < dsm.getVertices().length; currentIndex++) { + if (dsm.getVertices()[currentIndex].equals(v)) { + return currentIndex; + } + } + throw new IllegalStateException("Vertex " + v + " is not contained in the DSM."); + } + +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/DsmPrinter.java b/sonar-graph/src/main/java/org/sonar/graph/DsmPrinter.java new file mode 100644 index 00000000000..df36cedb936 --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/DsmPrinter.java @@ -0,0 +1,104 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.io.IOException; +import java.io.StringWriter; +import java.io.Writer; + +public final class DsmPrinter { + + private final Writer writer; + private final Dsm dsm; + private static final String CELL_SEPARATOR = "| "; + private static final String FEEDBACK_EDGE_FLAG = "*"; + private final boolean displayColumnHeaders; + + private DsmPrinter(Writer writer, Dsm dsm, boolean displayColumnHeaders) { + this.writer = writer; + this.dsm = dsm; + this.displayColumnHeaders = displayColumnHeaders; + } + + private void print() { + try { + if (displayColumnHeaders) { + printColumnHeaders(); + } + for (int y = 0; y < dsm.getDimension(); y++) { + printRow(y); + } + writer.flush(); + + } catch (IOException e) { + throw new RuntimeException("Unable to print the desired DSM.", e); // NOSONAR + } + } + + public static String print(Dsm dsm, boolean displayColumnHeaders) { + StringWriter writer = new StringWriter(); + print(writer, dsm, displayColumnHeaders); + return writer.toString(); + } + + public static String print(Dsm dsm) { + return print(dsm, true); + } + + public static void print(Writer writer, Dsm dsm, boolean displayColumnHeaders) { + DsmPrinter printer = new DsmPrinter(writer, dsm, displayColumnHeaders); + printer.print(); + } + + private void printRow(int y) throws IOException { + printRowHeader(y); + for (int x = 0; x < dsm.getDimension(); x++) { + printCell(y, x); + } + writer.append((char) Character.LINE_SEPARATOR); + } + + private void printCell(int y, int x) throws IOException { + if (dsm.getCell(x, y).getWeight() == 0) { + writer.append(" "); + } else { + writer.append("").append(String.valueOf(dsm.getCell(x, y).getWeight())); + } + if (dsm.getCell(x, y).isFeedbackEdge()) { + writer.append(FEEDBACK_EDGE_FLAG); + } else { + writer.append(' '); + } + writer.append(CELL_SEPARATOR); + } + + private void printRowHeader(int y) throws IOException { + writer.append(String.valueOf(dsm.getVertex(y))).append(" " + CELL_SEPARATOR); + } + + private void printColumnHeaders() throws IOException { + writer.append(" " + CELL_SEPARATOR); + for (int i = 0; i < dsm.getDimension(); i++) { + printRowHeader(i); + } + writer.append((char) Character.LINE_SEPARATOR); + } + +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/DsmScanner.java b/sonar-graph/src/main/java/org/sonar/graph/DsmScanner.java new file mode 100644 index 00000000000..997d5ce9e94 --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/DsmScanner.java @@ -0,0 +1,113 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.io.IOException; +import java.io.LineNumberReader; +import java.io.Reader; +import java.io.StringReader; +import java.util.Arrays; +import java.util.HashSet; +import java.util.Set; + +public final class DsmScanner { + + private final LineNumberReader reader; + private static final String CELL_SEPARATOR = "|"; + private static final char FEEDBACK_EDGE_FLAG = '*'; + private final DirectedGraph graph = DirectedGraph.createStringDirectedGraph(); + private String[] vertices; + private Set feedbackEdges = new HashSet(); + + private DsmScanner(Reader reader) { + this.reader = new LineNumberReader(reader); + } + + private Dsm scan() { + try { + readColumnHeadersAndcreateDsmBuilder(); + for (int i = 0; i < vertices.length; i++) { + readRow(i); + } + } catch (IOException e) { + throw new RuntimeException("Unable to read DSM content.", e); //NOSONAR + } + Dsm dsm = new Dsm(graph, graph.getVertices(), feedbackEdges); + DsmManualSorter.sort(dsm, Arrays.asList(vertices)); + return dsm; + } + + private void readRow(int i) throws IOException { + String[] tokens = splitLine(reader.readLine()); + if (tokens != null) { + for (int j = 1; j < tokens.length - 1; j++) { + int toVertexIndex = j - 1; + int weight = extractWeight(tokens[j]); + if (i != toVertexIndex) { + StringEdge edge = new StringEdge(vertices[toVertexIndex], vertices[i], weight); + if (isFeedbackEdge(tokens[j])) { + feedbackEdges.add(edge); + } + graph.addEdge(edge); + } + } + } + } + + private boolean isFeedbackEdge(String cellContent) { + return cellContent.indexOf(FEEDBACK_EDGE_FLAG) != -1; + } + + private int extractWeight(String stringContent) { + try { + return Integer.valueOf(stringContent.replace(FEEDBACK_EDGE_FLAG, ' ').trim()); + } catch (NumberFormatException e) { + return 0; + } + } + + private void readColumnHeadersAndcreateDsmBuilder() throws IOException { + String[] tokens = splitLine(reader.readLine()); + if (tokens != null) { + vertices = new String[tokens.length - 2]; + System.arraycopy(tokens, 1, vertices, 0, tokens.length - 2); + graph.addVertices(Arrays.asList(vertices)); + } + } + + private String[] splitLine(String line) { + String[] tokens = line.split("\\" + CELL_SEPARATOR); + String[] result = new String[tokens.length]; + for (int i = 0; i < tokens.length; i++) { + result[i] = tokens[i].trim(); + } + return result; + } + + public static Dsm scan(String textDsm) { + StringReader reader = new StringReader(textDsm); + return scan(reader); + } + + public static Dsm scan(Reader dsmReader) { + DsmScanner scanner = new DsmScanner(dsmReader); + return scanner.scan(); + } +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/DsmTopologicalSorter.java b/sonar-graph/src/main/java/org/sonar/graph/DsmTopologicalSorter.java new file mode 100644 index 00000000000..715bf8cba6c --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/DsmTopologicalSorter.java @@ -0,0 +1,71 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +public final class DsmTopologicalSorter { + + private final Dsm dsm; + private int leftOrderedIndex; + private int rightOrderedIndex; + + private DsmTopologicalSorter(Dsm dsm) { + this.dsm = dsm; + leftOrderedIndex = 0; + rightOrderedIndex = dsm.getDimension() - 1; + } + + public static void sort(Dsm dsm) { + DsmTopologicalSorter partitionner = new DsmTopologicalSorter(dsm); + boolean dsmCanBeSorted = true; + while (dsmCanBeSorted) { + boolean dsmCanBeSortedOnLeft = partitionner.pushToLeftVerticesWithoutIncomingEdges(); + boolean dsmCanBeSortedOnRight = partitionner.pushToRightVerticesWithoutOutgointEdges(); + dsmCanBeSorted = dsmCanBeSortedOnLeft || dsmCanBeSortedOnRight; + } + boolean isCyclicGraph = (partitionner.leftOrderedIndex < partitionner.rightOrderedIndex); + if (isCyclicGraph) { + throw new IllegalStateException("Can't sort a cyclic graph."); + } + } + + private boolean pushToLeftVerticesWithoutIncomingEdges() { + boolean permutationsDone = false; + for (int i = leftOrderedIndex; i <= rightOrderedIndex; i++) { + if (dsm.getNumberOfIncomingEdges(i, leftOrderedIndex, rightOrderedIndex) == 0) { + dsm.permute(i, leftOrderedIndex); + leftOrderedIndex++; + permutationsDone = true; + } + } + return permutationsDone; + } + + private boolean pushToRightVerticesWithoutOutgointEdges() { + boolean permutationsDone = false; + for (int i = leftOrderedIndex; i <= rightOrderedIndex; i++) { + if (dsm.getNumberOfOutgoingEdges(i, leftOrderedIndex, rightOrderedIndex) == 0) { + dsm.permute(i, rightOrderedIndex); + rightOrderedIndex--; + permutationsDone = true; + } + } + return permutationsDone; + } +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/Edge.java b/sonar-graph/src/main/java/org/sonar/graph/Edge.java new file mode 100644 index 00000000000..1e627b0cc9b --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/Edge.java @@ -0,0 +1,30 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +public interface Edge { + + int getWeight(); + + V getFrom(); + + V getTo(); + +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/EdgeFactory.java b/sonar-graph/src/main/java/org/sonar/graph/EdgeFactory.java new file mode 100644 index 00000000000..935315bbd74 --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/EdgeFactory.java @@ -0,0 +1,27 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +public interface EdgeFactory { + + E createEdge(V from, V to); + + E createEdge(V from, V to, int weigth); +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/FeedbackCycle.java b/sonar-graph/src/main/java/org/sonar/graph/FeedbackCycle.java new file mode 100644 index 00000000000..618d07feb3e --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/FeedbackCycle.java @@ -0,0 +1,107 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ + +package org.sonar.graph; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; +import java.util.Set; + +import com.google.common.collect.HashMultiset; +import com.google.common.collect.Multiset; + +public final class FeedbackCycle implements Iterable, Comparable { + + private List orderedFeedbackEdges; + private int totalOccurrencesOfEdgesInCycle; + private final Cycle cycle; + + private FeedbackCycle(Cycle cycle) { + orderedFeedbackEdges = new ArrayList(); + totalOccurrencesOfEdgesInCycle = 0; + this.cycle = cycle; + } + + private void add(FeedbackEdge feedbackEdge) { + orderedFeedbackEdges.add(feedbackEdge); + } + + public static List buildFeedbackCycles(Set cycles) { + Multiset edgesBag = createBagWithAllEdgesOfCycles(cycles); + + List feedbackCycles = new ArrayList(); + for (Cycle cycle : cycles) { + FeedbackCycle feedbackCycle = new FeedbackCycle(cycle); + int totalOccurrences = 0; + for (Edge edge : cycle.getEdges()) { + FeedbackEdge feedbackEdge = new FeedbackEdge(edge, edgesBag.count(edge)); + feedbackCycle.add(feedbackEdge); + totalOccurrences += feedbackEdge.getOccurences(); + } + feedbackCycle.setTotalOccurrencesOfEdgesInCycle(totalOccurrences); + Collections.sort(feedbackCycle.orderedFeedbackEdges); + feedbackCycles.add(feedbackCycle); + } + Collections.sort(feedbackCycles); + + return feedbackCycles; + } + + private static Multiset createBagWithAllEdgesOfCycles(Set cycles) { + Multiset edgesBag = HashMultiset.create(); + for (Cycle cycle : cycles) { + for (Edge edge : cycle.getEdges()) { + edgesBag.add(edge); + } + } + return edgesBag; + } + + private void setTotalOccurrencesOfEdgesInCycle(int totalOccurrencesOfEdgesInCycle) { + this.totalOccurrencesOfEdgesInCycle = totalOccurrencesOfEdgesInCycle; + } + + public int getTotalOccurrencesOfEdgesInCycle() { + return totalOccurrencesOfEdgesInCycle; + } + + public Iterator iterator() { + return orderedFeedbackEdges.iterator(); + } + + public int compareTo(FeedbackCycle feedbackCycle) { + if (getTotalOccurrencesOfEdgesInCycle() < feedbackCycle.getTotalOccurrencesOfEdgesInCycle()) { + return -1; + } + if (getTotalOccurrencesOfEdgesInCycle() == feedbackCycle.getTotalOccurrencesOfEdgesInCycle()) { + if (cycle.size() == feedbackCycle.cycle.size()) { + return orderedFeedbackEdges.get(0).compareTo(feedbackCycle.orderedFeedbackEdges.get(0)); + } + return cycle.size() - feedbackCycle.cycle.size(); + } + return 1; + } + + public Cycle getCycle() { + return cycle; + } +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/FeedbackEdge.java b/sonar-graph/src/main/java/org/sonar/graph/FeedbackEdge.java new file mode 100644 index 00000000000..53fe8918583 --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/FeedbackEdge.java @@ -0,0 +1,75 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +public class FeedbackEdge implements Comparable { + + private Edge edge; + private double relativeWeight; + private int occurences; + private final int hashcode; + + public FeedbackEdge(Edge edge, int occurences) { + this.edge = edge; + this.hashcode = edge.hashCode(); + this.occurences = occurences; + this.relativeWeight = (double) edge.getWeight() / occurences; + } + + protected Edge getEdge() { + return edge; + } + + protected int getWeight() { + return edge.getWeight(); + } + + protected double getRelativeWeight() { + return relativeWeight; + } + + protected int getOccurences() { + return occurences; + } + + public int compareTo(FeedbackEdge feedbackEdge) { + if (this.getRelativeWeight() < feedbackEdge.getRelativeWeight()) { + return -1; + } + if (this.getRelativeWeight() == feedbackEdge.getRelativeWeight()) { + return this.getEdge().getFrom().toString().compareTo(feedbackEdge.getEdge().getFrom().toString()); + } + return 1; + } + + @Override + public boolean equals(Object obj) { + if (!(obj instanceof FeedbackEdge) || this.hashCode() != obj.hashCode()) { + return false; + } + FeedbackEdge otherEdge = (FeedbackEdge) obj; + return edge.equals(otherEdge.edge); + } + + @Override + public int hashCode() { + return hashcode; + } +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/IncrementalCyclesAndFESSolver.java b/sonar-graph/src/main/java/org/sonar/graph/IncrementalCyclesAndFESSolver.java new file mode 100644 index 00000000000..3fde2eaa2e8 --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/IncrementalCyclesAndFESSolver.java @@ -0,0 +1,89 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.Collection; +import java.util.HashSet; +import java.util.Set; + +public class IncrementalCyclesAndFESSolver { + + private Set cycles = new HashSet(); + private Set edgesToExclude = new HashSet(); + private long searchCyclesCalls = 0; + private static final int DEFAULT_MAX_SEARCH_DEPTH_AT_FIRST = 3; + private static final int DEFAULT_MAX_CYCLES_TO_FOUND_BY_ITERATION = 100; + private MinimumFeedbackEdgeSetSolver solver; + private int iterations = 0; + + public IncrementalCyclesAndFESSolver(DirectedGraphAccessor graph, Collection vertices) { + this(graph, vertices, DEFAULT_MAX_SEARCH_DEPTH_AT_FIRST, DEFAULT_MAX_CYCLES_TO_FOUND_BY_ITERATION); + } + + public IncrementalCyclesAndFESSolver(DirectedGraphAccessor graph, Collection vertices, int maxSearchDepthAtFirst, + int maxCyclesToFoundByIteration) { + + iterations++; + CycleDetector cycleDetector = new CycleDetector(graph, vertices); + cycleDetector.detectCyclesWithMaxSearchDepth(maxSearchDepthAtFirst); + searchCyclesCalls += cycleDetector.getSearchCyclesCalls(); + cycles.addAll(cycleDetector.getCycles()); + solver = new MinimumFeedbackEdgeSetSolver(cycles); + edgesToExclude = solver.getEdges(); + + do { + iterations++; + cycleDetector = new CycleDetector(graph, vertices, edgesToExclude); + cycleDetector.detectCyclesWithUpperLimit(maxCyclesToFoundByIteration); + searchCyclesCalls += cycleDetector.getSearchCyclesCalls(); + cycles.addAll(cycleDetector.getCycles()); + solver = new MinimumFeedbackEdgeSetSolver(cycles); + edgesToExclude = solver.getEdges(); + } while (cycleDetector.getCycles().size() != 0); + } + + public int getWeightOfFeedbackEdgeSet() { + return solver.getWeightOfFeedbackEdgeSet(); + } + + public int getNumberOfLoops() { + return solver.getNumberOfLoops(); + } + + public Set getFeedbackEdgeSet() { + return solver.getEdges(); + } + + public Set getCycles() { + return cycles; + } + + public boolean isAcyclicGraph() { + return cycles.isEmpty(); + } + + public long getSearchCyclesCalls() { + return searchCyclesCalls; + } + + public int getIterations() { + return iterations; + } +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/MinimumFeedbackEdgeSetSolver.java b/sonar-graph/src/main/java/org/sonar/graph/MinimumFeedbackEdgeSetSolver.java new file mode 100644 index 00000000000..2c27caad174 --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/MinimumFeedbackEdgeSetSolver.java @@ -0,0 +1,153 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.*; + +public class MinimumFeedbackEdgeSetSolver { + + private final List feedbackCycles; + private Set feedbackEdges; + private int minimumFeedbackEdgesWeight = Integer.MAX_VALUE; + private final int cyclesNumber; + private final int maxNumberCyclesForSearchingMinimumFeedback; + private static final int DEFAULT_MAXIMUM_NUMBER_OF_LOOPS = 1000000; + private static final int MAXIMUM_NUMBER_OF_CYCLE_THAT_CAN_BE_HANDLED = 1500; + private final int maximumNumberOfLoops; + + public int getNumberOfLoops() { + return numberOfLoops; + } + + private int numberOfLoops = 0; + + public MinimumFeedbackEdgeSetSolver(Set cycles, int maxCycles) { + this(cycles, DEFAULT_MAXIMUM_NUMBER_OF_LOOPS, maxCycles); + } + + public MinimumFeedbackEdgeSetSolver(Set cycles) { + this(cycles, DEFAULT_MAXIMUM_NUMBER_OF_LOOPS, MAXIMUM_NUMBER_OF_CYCLE_THAT_CAN_BE_HANDLED); + } + + public MinimumFeedbackEdgeSetSolver(Set cycles, int maximumNumberOfLoops, int maxNumberCyclesForSearchingMinimumFeedback) { + this.maximumNumberOfLoops = maximumNumberOfLoops; + this.feedbackCycles = FeedbackCycle.buildFeedbackCycles(cycles); + this.cyclesNumber = cycles.size(); + this.maxNumberCyclesForSearchingMinimumFeedback = maxNumberCyclesForSearchingMinimumFeedback; + this.run(); + } + + public int getWeightOfFeedbackEdgeSet() { + return minimumFeedbackEdgesWeight; + } + + /** + * Get edges tagged as feedback. + */ + public Set getEdges() { + Set edges = new HashSet(); + for (FeedbackEdge fe : feedbackEdges) { + edges.add(fe.getEdge()); + } + return edges; + } + + private void run() { + Set pendingFeedbackEdges = new HashSet(); + if (cyclesNumber < maxNumberCyclesForSearchingMinimumFeedback) { + searchFeedbackEdges(0, 0, pendingFeedbackEdges); + } + else { + lightResearchForFeedbackEdges(); + } + } + + private void lightResearchForFeedbackEdges() { + feedbackEdges = new HashSet(); + for (FeedbackCycle cycle : feedbackCycles) { + for (FeedbackEdge edge : cycle) { + feedbackEdges.add(edge); + break; + } + } + minimumFeedbackEdgesWeight = 0; + for(FeedbackEdge edge : feedbackEdges) { + minimumFeedbackEdgesWeight += edge.getWeight(); + } + } + + private void searchFeedbackEdges(int level, int pendingWeight, Set pendingFeedbackEdges) { + if (numberOfLoops++ > maximumNumberOfLoops) { + return; + } + + if (pendingWeight >= minimumFeedbackEdgesWeight) { + return; + } + + if (level == cyclesNumber) { + minimumFeedbackEdgesWeight = pendingWeight; + feedbackEdges = new HashSet(pendingFeedbackEdges); + //System.out.println("Weight : " + minimumFeedbackEdgesWeight + " in " + numberOfLoops + " loops"); + return; + } + + FeedbackCycle feedbackCycle = feedbackCycles.get(level); + + if (doesFeedbackEdgesContainAnEdgeOfTheCycle(pendingFeedbackEdges, feedbackCycle)) { + searchFeedbackEdges(level + 1, pendingWeight, pendingFeedbackEdges); + } + else { + boolean hasAnEdgeWithOccurrenceOfOneBeenUsed = false; + for (FeedbackEdge feedbackEdge : feedbackCycle) { + if (feedbackEdge.getOccurences() == 1) { + if (hasAnEdgeWithOccurrenceOfOneBeenUsed) { + continue; + } + else { + hasAnEdgeWithOccurrenceOfOneBeenUsed = true; + } + } + int edgeWeight = addNewEdge(feedbackEdge, pendingFeedbackEdges); + pendingWeight += edgeWeight; + + searchFeedbackEdges(level + 1, pendingWeight, pendingFeedbackEdges); + pendingWeight -= edgeWeight; + pendingFeedbackEdges.remove(feedbackEdge); + } + } + } + + private boolean doesFeedbackEdgesContainAnEdgeOfTheCycle(Set pendingFeedbackEdges, FeedbackCycle cycle) { + boolean contains = false; + for (FeedbackEdge feedbackEdge : cycle) { + if (pendingFeedbackEdges.contains(feedbackEdge)) { + contains = true; + break; + } + } + return contains; + } + + private int addNewEdge(FeedbackEdge feedbackEdge, Set pendingFeedbackEdges) { + pendingFeedbackEdges.add(feedbackEdge); + return feedbackEdge.getWeight(); + } +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/StringEdge.java b/sonar-graph/src/main/java/org/sonar/graph/StringEdge.java new file mode 100644 index 00000000000..bd11d99adfd --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/StringEdge.java @@ -0,0 +1,71 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.apache.commons.lang.builder.ToStringBuilder; + +public class StringEdge implements Edge { + + private final String from; + private final String to; + private int weight; + + public StringEdge(String from, String to) { + this.from = from; + this.to = to; + this.weight = 1; + } + + public StringEdge(String from, String to, int weight) { + this(from, to); + this.weight = weight; + } + + public String getFrom() { + return from; + } + + public String getTo() { + return to; + } + + public int getWeight() { + return weight; + } + + @Override + public boolean equals(Object obj) { + if (!(obj instanceof StringEdge)) { + return false; + } + StringEdge edge = (StringEdge) obj; + return from.equals(edge.from) && to.equals(edge.to); + } + + @Override + public int hashCode() { + return 3*from.hashCode() + to.hashCode(); //NOSONAR Magic number 3 is suitable here + } + + @Override + public String toString() { + return new ToStringBuilder(this).append("from", from).append("to", to).toString(); + } +} diff --git a/sonar-graph/src/main/java/org/sonar/graph/StringEdgeFactory.java b/sonar-graph/src/main/java/org/sonar/graph/StringEdgeFactory.java new file mode 100644 index 00000000000..c576b5a47ef --- /dev/null +++ b/sonar-graph/src/main/java/org/sonar/graph/StringEdgeFactory.java @@ -0,0 +1,31 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +public class StringEdgeFactory implements EdgeFactory { + + public StringEdge createEdge(String from, String to) { + return new StringEdge(from, to); + } + + public StringEdge createEdge(String from, String to, int weight) { + return new StringEdge(from, to, weight); + } +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/CycleDetectorTest.java b/sonar-graph/src/test/java/org/sonar/graph/CycleDetectorTest.java new file mode 100644 index 00000000000..dd010d64d4b --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/CycleDetectorTest.java @@ -0,0 +1,156 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.Arrays; +import java.util.HashSet; +import java.util.Set; + +import org.junit.Test; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertThat; +import static org.junit.Assert.assertTrue; + +public class CycleDetectorTest { + + @Test + public void testIsAcyclicGraph() { + DirectedGraph dag = DirectedGraph.createStringDirectedGraph(); + dag.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D"); + dag.addEdge("B", "D"); + dag.addEdge("A", "D"); + + CycleDetector cycleDetector = new CycleDetector(dag); + cycleDetector.detectCycles(); + assertTrue(cycleDetector.isAcyclicGraph()); + } + + @Test + public void testIsNotAcyclicGraph() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "A"); + + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + assertFalse(cycleDetector.isAcyclicGraph()); + } + + @Test + public void testGetCyclesWithMultipleCycles() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); + dcg.addEdge("C", "A"); + dcg.addEdge("B", "A"); + dcg.addEdge("A", "E").addEdge("E", "C"); + dcg.addEdge("E", "D"); + dcg.addEdge("E", "F"); + dcg.addEdge("F", "C"); + + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + assertThat(cycleDetector.getCycles().size(), is(8)); + assertThat(cycleDetector.getSearchCyclesCalls(), is(8L)); + } + + @Test + public void testMaxSearchDepthOption() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); + dcg.addEdge("C", "A"); + dcg.addEdge("B", "A"); + + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCyclesWithMaxSearchDepth(3); + assertThat(cycleDetector.getCycles().size(), is(2)); + + cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCyclesWithMaxSearchDepth(2); + assertThat(cycleDetector.getCycles().size(), is(1)); + } + + @Test + public void testExcludeEdgesFromSearch() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); + dcg.addEdge("C", "A"); + dcg.addEdge("B", "A"); + + Set excludedEdges = new HashSet(); + excludedEdges.add(dcg.getEdge("C", "A")); + excludedEdges.add(dcg.getEdge("B", "A")); + + CycleDetector cycleDetector = new CycleDetector(dcg, excludedEdges); + cycleDetector.detectCycles(); + assertThat(cycleDetector.getCycles().size(), is(1)); + } + + @Test + public void testGetCyclesWithOneCycle() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "E"); + dcg.addEdge("B", "A"); + + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + assertThat(cycleDetector.getCycles().size(), is(1)); + Cycle cycle = cycleDetector.getCycles().iterator().next(); + assertThat(cycle.size(), is(2)); + assertTrue(cycle.contains(new StringEdge("A", "B"))); + assertTrue(cycle.contains(new StringEdge("B", "A"))); + } + + @Test + public void getCyclesInLimitedSetOfVertices() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "A"); + + // C must not be used to find cycles + CycleDetector cycleDetector = new CycleDetector(dcg, Arrays.asList("A", "B")); + cycleDetector.detectCycles(); + assertThat(cycleDetector.getCycles().size(), is(0)); + + // C is used to find cycles + cycleDetector = new CycleDetector(dcg, Arrays.asList("A", "B", "C")); + cycleDetector.detectCycles(); + assertThat(cycleDetector.getCycles().size(), is(1)); + } + + @Test(expected = IllegalStateException.class) + public void testExecutingTwoCycleDetectionsOnSameObject() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "A"); + + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + cycleDetector.detectCycles(); + } + + @Test + public void testDetectCyclesWithUpperLimit() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); + dcg.addEdge("B", "A"); + + CycleDetector cycleDetector = new CycleDetector(dcg); + assertThat(cycleDetector.detectCyclesWithUpperLimit(1).size(), is(1)); + } +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/CycleTest.java b/sonar-graph/src/test/java/org/sonar/graph/CycleTest.java new file mode 100644 index 00000000000..a42366abbab --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/CycleTest.java @@ -0,0 +1,58 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.Arrays; + +import org.junit.Test; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertTrue; + +public class CycleTest { + + private Edge[] AB_Cycle = { new StringEdge("A", "B"), new StringEdge("B", "A") }; + private Edge[] BA_Cycle = { new StringEdge("B", "A"), new StringEdge("A", "B") }; + private Edge[] ABC_Cycle = { new StringEdge("A", "B"), new StringEdge("B", "C"), new StringEdge("C", "A") }; + private Edge[] HIJ_Cycle = { new StringEdge("H", "I"), new StringEdge("I", "J"), new StringEdge("J", "H") }; + private Edge[] ABCD_Cycle = { new StringEdge("A", "B"), new StringEdge("B", "C"), new StringEdge("C", "D"), new StringEdge("D", "A") }; + private Edge[] BCDA_Cycle = { new StringEdge("B", "C"), new StringEdge("C", "D"), new StringEdge("D", "A"), new StringEdge("A", "B"), }; + + @Test + public void testHashCode() { + assertTrue(new Cycle(Arrays.asList(AB_Cycle)).hashCode() == new Cycle(Arrays.asList(BA_Cycle)).hashCode()); + assertTrue(new Cycle(Arrays.asList(BCDA_Cycle)).hashCode() == new Cycle(Arrays.asList(ABCD_Cycle)).hashCode()); + assertFalse(new Cycle(Arrays.asList(AB_Cycle)).hashCode() == new Cycle(Arrays.asList(ABC_Cycle)).hashCode()); + } + + @Test + public void testContains() { + assertTrue(new Cycle(Arrays.asList(ABCD_Cycle)).contains(new StringEdge("B", "C"))); + } + + @Test + public void testEqualsObject() { + assertEquals(new Cycle(Arrays.asList(AB_Cycle)), new Cycle(Arrays.asList(BA_Cycle))); + assertEquals(new Cycle(Arrays.asList(BCDA_Cycle)), new Cycle(Arrays.asList(ABCD_Cycle))); + assertFalse(new Cycle(Arrays.asList(BCDA_Cycle)).equals(new Cycle(Arrays.asList(AB_Cycle)))); + assertFalse(new Cycle(Arrays.asList(ABC_Cycle)).equals(new Cycle(Arrays.asList(HIJ_Cycle)))); + } +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DirectedGraphTest.java b/sonar-graph/src/test/java/org/sonar/graph/DirectedGraphTest.java new file mode 100644 index 00000000000..0abcb4c9af2 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/DirectedGraphTest.java @@ -0,0 +1,106 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.junit.Before; +import org.junit.Test; +import org.sonar.graph.DirectedGraph; +import org.sonar.graph.StringEdge; + +import java.util.Arrays; + +import static org.hamcrest.Matchers.*; +import static org.junit.Assert.*; + +public class DirectedGraphTest { + + private DirectedGraph graph; + + @Before + public void init() { + graph = DirectedGraph.createStringDirectedGraph(); + graph.addEdge("A", "B"); + graph.addEdge("A", "C"); + graph.addEdge("B", "C"); + } + + @Test + public void testGetVertices() { + assertThat(graph.getVertices(), hasItems("A", "B")); + assertThat(graph.getVertices().size(), is(3)); + } + + @Test + public void testGetEdge() { + assertNull(graph.getEdge("A", "T")); + graph.addEdge("A", "T", 5); + assertThat(graph.getEdge("A", "T").getWeight(), is(5)); + } + + @Test(expected = IllegalStateException.class) + public void testAddEdgeThrowsException() { + graph.addEdge("B", "C"); + } + + @Test + public void testAddEdgeWithWeight() { + graph.addEdge("D", "B", 4); + assertThat(graph.getOutgoingEdges("D").iterator().next().getWeight(), is(4)); + } + + @Test + public void testGetOutgoingEdges() { + assertThat(graph.getOutgoingEdges("A"), hasItem(new StringEdge("A", "B"))); + assertThat(graph.getOutgoingEdges("A").size(), is(2)); + assertThat(graph.getOutgoingEdges("B"), hasItem(new StringEdge("B", "C"))); + } + + @Test + public void testGetIncomingEdges() { + assertThat(graph.getIncomingEdges("C"), hasItem(new StringEdge("A", "C"))); + assertThat(graph.getIncomingEdges("A").size(), is(0)); + } + + @Test + public void testGetEdges() { + assertTrue(graph.getEdges(Arrays.asList("A")).containsAll(Arrays.asList(new StringEdge("A", "B"), new StringEdge("A", "C")))); + assertTrue(graph.getEdges(Arrays.asList("A", "B")).containsAll(Arrays.asList(new StringEdge("A", "B"), new StringEdge("A", "C"), new StringEdge("B", "C")))); + } + + @Test + public void testHasEdge() { + assertTrue(graph.hasEdge("A", "B")); + assertFalse(graph.hasEdge("C", "A")); + } + + @Test + public void testAddVertex() { + graph.addVertex("X"); + assertThat(graph.getVertices(), hasItem("X")); + assertThat(graph.getOutgoingEdges("X").size(), is(0)); + } + + @Test + public void testAddVertices() { + String[] vertices = { "X", "Y", "Z" }; + graph.addVertices(Arrays.asList(vertices)); + assertThat(graph.getVertices(), hasItems("X", "Y", "Z")); + } +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmCellTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmCellTest.java new file mode 100644 index 00000000000..12069d2dc88 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/DsmCellTest.java @@ -0,0 +1,45 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.junit.Ignore; +import org.junit.Test; +import org.sonar.graph.DsmCell; +import org.sonar.graph.StringEdge; + +import static org.hamcrest.Matchers.equalTo; +import static org.hamcrest.Matchers.not; +import static org.junit.Assert.assertThat; + +public class DsmCellTest { + + @Test + @Ignore + public void testEquals() { + DsmCell cell1 = new DsmCell(new StringEdge("A", "B", 1), true); + DsmCell cell1bis = new DsmCell(new StringEdge("A", "B", 1), false); + DsmCell cell4 = new DsmCell(new StringEdge("B", "A", 4), true); + + assertThat(cell1, equalTo(cell1)); + assertThat(cell1, equalTo(cell1bis)); + assertThat(cell1, not(equalTo(cell4))); + } + +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmManualSorterTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmManualSorterTest.java new file mode 100644 index 00000000000..617abe383f6 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/DsmManualSorterTest.java @@ -0,0 +1,46 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.junit.Test; + +import static org.junit.Assert.assertEquals; + +public class DsmManualSorterTest { + + @Test + public void testSort() { + DirectedGraph graph = DirectedGraph.createStringDirectedGraph(); + graph.addEdge("A", "B", 2); + graph.addEdge("A", "C", 3); + graph.addEdge("C", "B", 1); + Dsm dsm = new Dsm(graph); + DsmManualSorter.sort(dsm, "B", "A", "C"); + + StringPrintWriter expectedDsm = new StringPrintWriter(); + expectedDsm.println(" | B | A | C |"); + expectedDsm.println("B | | 2 | 1 |"); + expectedDsm.println("A | | | |"); + expectedDsm.println("C | | 3 | |"); + + assertEquals(expectedDsm.toString(), DsmPrinter.print(dsm)); + } + +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmPrinterTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmPrinterTest.java new file mode 100644 index 00000000000..55e8de64de6 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/DsmPrinterTest.java @@ -0,0 +1,64 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import com.google.common.collect.Sets; +import org.junit.Before; +import org.junit.Test; + +import java.util.HashSet; + +import static org.junit.Assert.assertEquals; + +public class DsmPrinterTest { + + private Dsm dsm; + + @Before + public void init() { + DirectedGraph graph = DirectedGraph.createStringDirectedGraph(); + graph.addEdge("A", "B", 3).addEdge("A", "C", 2); + graph.addEdge("C", "B", 4).addEdge("C", "A", 1); + HashSet feedbackEdges = Sets.newHashSet(graph.getEdge("C", "A")); + dsm = new Dsm(graph, feedbackEdges); + DsmManualSorter.sort(dsm, "A", "C", "B"); + } + + @Test + public void testPrintDsm() { + StringPrintWriter expectedResult = new StringPrintWriter(); + expectedResult.println(" | A | C | B |"); + expectedResult.println("A | | 1*| |"); + expectedResult.println("C | 2 | | |"); + expectedResult.println("B | 3 | 4 | |"); + + assertEquals(expectedResult.toString(), DsmPrinter.print(dsm)); + } + + @Test + public void testPrintDsmWithoutColumnHeaders() { + StringPrintWriter expectedResult = new StringPrintWriter(); + expectedResult.println("A | | 1*| |"); + expectedResult.println("C | 2 | | |"); + expectedResult.println("B | 3 | 4 | |"); + + assertEquals(expectedResult.toString(), DsmPrinter.print(dsm, false)); + } +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmScannerTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmScannerTest.java new file mode 100644 index 00000000000..1d9df9239d4 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/DsmScannerTest.java @@ -0,0 +1,55 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.junit.Test; +import org.sonar.graph.Dsm; +import org.sonar.graph.DsmCell; +import org.sonar.graph.DsmScanner; + +import static org.junit.Assert.*; + +public class DsmScannerTest { + + @Test + public void testScanString() { + StringPrintWriter builder = new StringPrintWriter(); + builder.println(" | A | B |"); + builder.println("A | | 1*|"); + builder.println("B | 3 | |"); + Dsm dsm = DsmScanner.scan(builder.toString()); + + assertEquals("A", dsm.getVertex(0).toString()); + assertEquals("B", dsm.getVertex(1).toString()); + + assertEquals(2, dsm.getDimension()); + + DsmCell ba = dsm.getCell(1, 0); + assertEquals(1, ba.getWeight()); + assertTrue(ba.isFeedbackEdge()); + + DsmCell ab = dsm.getCell(0, 1); + assertEquals(3, ab.getWeight()); + assertFalse(ab.isFeedbackEdge()); + + assertEquals(0, dsm.getCell(1, 1).getWeight()); + } + +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmTest.java new file mode 100644 index 00000000000..06fbcba4160 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/DsmTest.java @@ -0,0 +1,77 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.junit.Before; +import org.junit.Test; +import org.sonar.graph.Dsm; +import org.sonar.graph.DsmScanner; + +import static org.hamcrest.Matchers.equalTo; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertThat; + +public class DsmTest { + + private Dsm dsm; + + @Before + public void init() { + StringPrintWriter textDsm = new StringPrintWriter(); + textDsm.println(" | A | B | C | D | E |"); + textDsm.println("A | | 1 | | | |"); + textDsm.println("B | 2 | | | | |"); + textDsm.println("C | 4 | | | | |"); + textDsm.println("D | | 7 | | | 5 |"); + textDsm.println("E | | | | | |"); + dsm = DsmScanner.scan(textDsm.toString()); + } + + @Test + public void testGetVertex() { + assertEquals("A", dsm.getVertex(0)); + assertEquals("B", dsm.getVertex(1)); + assertEquals("C", dsm.getVertex(2)); + assertEquals("D", dsm.getVertex(3)); + assertEquals("E", dsm.getVertex(4)); + } + + @Test + public void testPermute() { + assertEquals(2, dsm.getCell(0, 1).getWeight()); + assertEquals(4, dsm.getCell(0, 2).getWeight()); + + dsm.permute(0, 1); + assertEquals(1, dsm.getCell(0, 1).getWeight()); + assertEquals(0, dsm.getCell(0, 2).getWeight()); + } + + @Test + public void testGetNumberOfOutgoingEdges() { + assertEquals(0, dsm.getNumberOfOutgoingEdges(3, 0, 4)); + assertEquals(2, dsm.getNumberOfOutgoingEdges(0, 0, 4)); + } + + @Test + public void testGetNumberOfIncomingEdges() { + assertThat(dsm.getNumberOfIncomingEdges(0, 0, 4), equalTo(1)); + assertThat(dsm.getNumberOfIncomingEdges(4, 0, 4), equalTo(0)); + } +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmTopologicalSorterTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmTopologicalSorterTest.java new file mode 100644 index 00000000000..f017d32dc23 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/DsmTopologicalSorterTest.java @@ -0,0 +1,112 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.io.IOException; + +import org.junit.Test; + +import static org.junit.Assert.assertEquals; + +public class DsmTopologicalSorterTest { + + @Test + public void sortAcyclicGraph() { + StringPrintWriter textDsm = new StringPrintWriter(); + textDsm.println(" | A | B | C | D | E |"); + textDsm.println("A | | | | | |"); + textDsm.println("B | 3 | | 4 | | |"); + textDsm.println("C | 1 | | | | |"); + textDsm.println("D | | 2 | | | 1 |"); + textDsm.println("E | | 5 | | | |"); + + Dsm dsm = DsmScanner.scan(textDsm.toString()); + DsmTopologicalSorter.sort(dsm); + + StringPrintWriter expectedTextDsm = new StringPrintWriter(); + expectedTextDsm.println(" | A | C | B | E | D |"); + expectedTextDsm.println("A | | | | | |"); + expectedTextDsm.println("C | 1 | | | | |"); + expectedTextDsm.println("B | 3 | 4 | | | |"); + expectedTextDsm.println("E | | | 5 | | |"); + expectedTextDsm.println("D | | | 2 | 1 | |"); + + Dsm expectedDsm = DsmScanner.scan(expectedTextDsm.toString()); + DsmTopologicalSorter.sort(expectedDsm); + + assertEquals(DsmPrinter.print(dsm), DsmPrinter.print(expectedDsm)); + } + + @Test(expected = IllegalStateException.class) + public void sortCyclicGraph() throws IOException { + StringPrintWriter textDsm = new StringPrintWriter(); + textDsm.println(" | A | B | C | D |"); + textDsm.println("A | | | | |"); + textDsm.println("B | 3 | | 4 | |"); + textDsm.println("C | 1 | 1 | | |"); + textDsm.println("D | | 2 | | |"); + + Dsm dsm = DsmScanner.scan(textDsm.toString()); + DsmTopologicalSorter.sort(dsm); + } + + @Test + public void sortCyclicGraphWithManuallyFlaggedFeedbackEdges() throws IOException { + StringPrintWriter textDsm = new StringPrintWriter(); + textDsm.println(" | A | B | C | D |"); + textDsm.println("A | | | | |"); + textDsm.println("B | 3 | | 4 | |"); + textDsm.println("C | 1 | 1*| | |"); + textDsm.println("D | | 2 | | |"); + + Dsm dsm = DsmScanner.scan(textDsm.toString()); + DsmTopologicalSorter.sort(dsm); + + StringPrintWriter expectedDsm = new StringPrintWriter(); + expectedDsm.println(" | A | C | B | D |"); + expectedDsm.println("A | | | | |"); + expectedDsm.println("C | 1 | | 1*| |"); + expectedDsm.println("B | 3 | 4 | | |"); + expectedDsm.println("D | | | 2 | |"); + + assertEquals(expectedDsm.toString(), DsmPrinter.print(dsm)); + } + + @Test + public void sortCyclicGraphWithFlaggedFeedbackEdges() throws IOException { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B", 3).addEdge("B", "A", 1); + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + + MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); + + Dsm dsm = new Dsm(dcg, solver.getEdges()); + DsmTopologicalSorter.sort(dsm); + + StringPrintWriter expectedDsm = new StringPrintWriter(); + expectedDsm.println(" | A | B |"); + expectedDsm.println("A | | 1*|"); + expectedDsm.println("B | 3 | |"); + + assertEquals(expectedDsm.toString(), DsmPrinter.print(dsm)); + } + +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/FeedbackCycleTest.java b/sonar-graph/src/test/java/org/sonar/graph/FeedbackCycleTest.java new file mode 100644 index 00000000000..b132d6c8e60 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/FeedbackCycleTest.java @@ -0,0 +1,66 @@ +/* +w * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.Arrays; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import org.junit.Test; + +import static org.junit.Assert.assertEquals; + +public class FeedbackCycleTest { + + private Edge[] AB_Edges = { new StringEdge("A", "B"), new StringEdge("B", "A") }; + private Edge[] ABC_Edges = { new StringEdge("A", "B"), new StringEdge("B", "C"), new StringEdge("C", "A") }; + private Edge[] BCDA_Edges = { new StringEdge("B", "C"), new StringEdge("C", "D"), new StringEdge("D", "A"), new StringEdge("A", "B"), }; + private Edge[] EF_Edges = { new StringEdge("E", "F"), new StringEdge("F", "E") }; + private Edge[] GHIJ_Edges = { new StringEdge("G", "H"), new StringEdge("H", "I"), new StringEdge("I", "J"), new StringEdge("J", "G") }; + private Edge[] XYZW_Edges = { new StringEdge("X", "Y"), new StringEdge("Y", "Z"), new StringEdge("Z", "W"), new StringEdge("W", "X") }; + + private Cycle AB_Cycle = new Cycle(Arrays.asList(AB_Edges)); + private Cycle ABC_Cycle = new Cycle(Arrays.asList(ABC_Edges)); + private Cycle BCDA_Cycle = new Cycle(Arrays.asList(BCDA_Edges)); + private Cycle EF_Cycle = new Cycle(Arrays.asList(EF_Edges)); + private Cycle GHIJ_Cycle = new Cycle(Arrays.asList(GHIJ_Edges)); + private Cycle XYZW_Cycle = new Cycle(Arrays.asList(XYZW_Edges)); + + @Test + public void testBuildFeedbackCycles() { + Set cycles = new HashSet(); + cycles.add(AB_Cycle); + cycles.add(ABC_Cycle); + cycles.add(BCDA_Cycle); + cycles.add(EF_Cycle); + cycles.add(GHIJ_Cycle); + cycles.add(XYZW_Cycle); + + List feedbackCycles = FeedbackCycle.buildFeedbackCycles(cycles); + assertEquals(6, feedbackCycles.size()); + assertEquals(EF_Cycle, feedbackCycles.get(0).getCycle()); + assertEquals(AB_Cycle, feedbackCycles.get(1).getCycle()); + assertEquals(GHIJ_Cycle, feedbackCycles.get(2).getCycle()); + assertEquals(XYZW_Cycle, feedbackCycles.get(3).getCycle()); + assertEquals(ABC_Cycle, feedbackCycles.get(4).getCycle()); + assertEquals(BCDA_Cycle, feedbackCycles.get(5).getCycle()); + } +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/FeedbackEdgeTest.java b/sonar-graph/src/test/java/org/sonar/graph/FeedbackEdgeTest.java new file mode 100644 index 00000000000..67ba883635b --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/FeedbackEdgeTest.java @@ -0,0 +1,81 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.junit.Test; + +import static org.hamcrest.MatcherAssert.assertThat; +import static org.hamcrest.Matchers.greaterThan; +import static org.hamcrest.Matchers.is; + +public class FeedbackEdgeTest { + + @Test + public void testWeights() { + FeedbackEdge fEdge = mockFeedbackEdge(14, 2); + assertThat(fEdge.getWeight(), is(14)); + assertThat(fEdge.getRelativeWeight(), is(7.0)); + assertThat(fEdge.getOccurences(), is(2)); + } + + @Test + public void testCompareTo() { + FeedbackEdge feedbackEdge1; + FeedbackEdge feedbackEdge2; + FeedbackEdge feedbackEdge3; + + feedbackEdge1 = mockFeedbackEdge(14, 2); + feedbackEdge2 = mockFeedbackEdge(10, 2); + assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(1)); + + feedbackEdge1 = mockFeedbackEdge(10, 2); + feedbackEdge2 = mockFeedbackEdge(14, 2); + assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(-1)); + + feedbackEdge1 = mockFeedbackEdge(14, 2); + feedbackEdge2 = mockFeedbackEdge(14, 2); + assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(0)); + + feedbackEdge1 = mockFeedbackEdge(14, 2); + feedbackEdge2 = mockFeedbackEdge(13, 2); + assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(1)); + + feedbackEdge1 = mockFeedbackEdge(13, 2); + feedbackEdge2 = mockFeedbackEdge(14, 2); + assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(-1)); + + feedbackEdge1 = mockFeedbackEdge("A", "B", 14, 2); + feedbackEdge2 = mockFeedbackEdge("B", "C", 14, 2); + feedbackEdge3 = mockFeedbackEdge("C", "A", 14, 2); + assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(-1)); + assertThat(feedbackEdge2.compareTo(feedbackEdge3), is(-1)); + assertThat(feedbackEdge3.compareTo(feedbackEdge1), greaterThan(1)); + } + + private FeedbackEdge mockFeedbackEdge(int weight, int occurrences) { + return mockFeedbackEdge("from", "to", weight, occurrences); + } + + private FeedbackEdge mockFeedbackEdge(String from, String to, int weight, int occurrences) { + Edge edge = new StringEdge(from, to, weight); + return new FeedbackEdge(edge, occurrences); + } + +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/IncrementalCyclesAndFESSolverTest.java b/sonar-graph/src/test/java/org/sonar/graph/IncrementalCyclesAndFESSolverTest.java new file mode 100644 index 00000000000..3b11829819c --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/IncrementalCyclesAndFESSolverTest.java @@ -0,0 +1,73 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.junit.Test; + +import static org.hamcrest.Matchers.containsString; +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; + +public class IncrementalCyclesAndFESSolverTest { + + @Test + public void testSimpleCase() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); + dcg.addEdge("C", "A"); + dcg.addEdge("B", "A"); + dcg.addEdge("A", "E").addEdge("E", "C"); + dcg.addEdge("E", "D"); + dcg.addEdge("E", "F"); + dcg.addEdge("F", "C"); + + IncrementalCyclesAndFESSolver cyclesAndFESSolver = new IncrementalCyclesAndFESSolver(dcg, dcg.getVertices(), 3, + Integer.MAX_VALUE); + assertThat(cyclesAndFESSolver.getCycles().size(), is(4)); + assertThat(cyclesAndFESSolver.getFeedbackEdgeSet().size(), is(2)); + assertThat(cyclesAndFESSolver.getWeightOfFeedbackEdgeSet(), is(2)); + } + + @Test + public void testWithNoCycleUnderTheThreshold() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); + + IncrementalCyclesAndFESSolver cyclesAndFESSolver = new IncrementalCyclesAndFESSolver(dcg, dcg.getVertices(), 2, + Integer.MAX_VALUE); + assertThat(cyclesAndFESSolver.getCycles().size(), is(1)); + assertThat(cyclesAndFESSolver.getFeedbackEdgeSet().size(), is(1)); + assertThat(cyclesAndFESSolver.getWeightOfFeedbackEdgeSet(), is(1)); + } + + @Test + public void testBothMaxSearchDepthAtFirstAndMaxCyclesToFoundByIteration() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); + dcg.addEdge("E", "F").addEdge("F", "G").addEdge("G", "E"); + dcg.addEdge("H", "I").addEdge("I", "H"); + + IncrementalCyclesAndFESSolver cyclesAndFESSolver = new IncrementalCyclesAndFESSolver(dcg, dcg.getVertices(), 2, 1); + assertThat(cyclesAndFESSolver.getCycles().size(), is(3)); + assertThat(cyclesAndFESSolver.getIterations(), is(4)); + cyclesAndFESSolver.getFeedbackEdgeSet(); + } + +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/MinimumFeedbackEdgeSetSolverTest.java b/sonar-graph/src/test/java/org/sonar/graph/MinimumFeedbackEdgeSetSolverTest.java new file mode 100644 index 00000000000..704b8f83402 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/MinimumFeedbackEdgeSetSolverTest.java @@ -0,0 +1,110 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.Set; + +import org.junit.Test; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; +import static org.junit.Assert.assertTrue; + +public class MinimumFeedbackEdgeSetSolverTest { + + @Test + public void testGetFeedbackEdgesOnSimpleLoop() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B", 3).addEdge("B", "A", 1); + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + + MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); + Set feedbackEdges = solver.getEdges(); + assertThat(feedbackEdges.size(), is(1)); + } + + @Test + public void testFlagFeedbackEdgesOnSimpleLoop() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B", 3).addEdge("B", "A", 1); + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + + MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); + Set feedbackEdges = solver.getEdges(); + assertTrue(feedbackEdges.contains(dcg.getEdge("B", "A"))); + } + + @Test + public void testGetFeedbackEdgesOnComplexGraph() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B", 7).addEdge("B", "C", 3).addEdge("C", "D", 1).addEdge("D", "A", 3); + dcg.addEdge("B", "A", 12); + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + + MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); + Set feedbackEdges = solver.getEdges(); + assertThat(feedbackEdges.size(), is(1)); + + assertTrue(feedbackEdges.contains(dcg.getEdge("A", "B"))); + } + + @Test + public void testFlagFeedbackEdgesOnUnrelatedCycles() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B", 7).addEdge("B", "C", 3).addEdge("C", "A", 2); + dcg.addEdge("D", "E", 3).addEdge("E", "D", 5); + dcg.addEdge("F", "G", 1).addEdge("G", "H", 4).addEdge("H", "F", 7); + + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + + MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); + Set feedbackEdges = solver.getEdges(); + + assertThat(feedbackEdges.size(), is(3)); + + assertTrue(feedbackEdges.contains(dcg.getEdge("C", "A"))); + assertTrue(feedbackEdges.contains(dcg.getEdge("D", "E"))); + assertTrue(feedbackEdges.contains(dcg.getEdge("F", "G"))); + } + + @Test + public void testApproximateMinimumFeedbackEdges() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B", 5).addEdge("B", "C", 9).addEdge("C", "A", 1); + dcg.addEdge("D", "B", 5).addEdge("C", "D", 7); + dcg.addEdge("F", "B", 5).addEdge("C", "F", 4); + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + + MinimumFeedbackEdgeSetSolver minimumSolver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); + assertThat(minimumSolver.getEdges().size(), is(1)); + assertTrue(minimumSolver.getEdges().contains(dcg.getEdge("B", "C"))); + + MinimumFeedbackEdgeSetSolver approximateSolver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles(), 2); + assertThat(approximateSolver.getEdges().size(), is(2)); + assertTrue(approximateSolver.getEdges().contains(dcg.getEdge("B", "C"))); + assertTrue(approximateSolver.getEdges().contains(dcg.getEdge("C", "A"))); + } + +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/StringPrintWriter.java b/sonar-graph/src/test/java/org/sonar/graph/StringPrintWriter.java new file mode 100644 index 00000000000..3beddf48215 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/StringPrintWriter.java @@ -0,0 +1,34 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +public class StringPrintWriter { + + private StringBuilder builder = new StringBuilder(); + + public void println(String line) { + builder.append(line + " \r"); + } + + public String toString() { + return builder.toString(); + } + +} -- cgit v1.2.3