diff options
Diffstat (limited to 'sonar-graph/src')
32 files changed, 0 insertions, 2660 deletions
diff --git a/sonar-graph/src/main/java/org/sonar/graph/Cycle.java b/sonar-graph/src/main/java/org/sonar/graph/Cycle.java deleted file mode 100644 index d0134492f67..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/Cycle.java +++ /dev/null @@ -1,85 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import java.util.List; - -public class Cycle { - - private Edge[] edges; - private int hashcode = 0; - - public Cycle(List<Edge> edges) { - this.edges = edges.toArray(new Edge[edges.size()]); - 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; - } -} diff --git a/sonar-graph/src/main/java/org/sonar/graph/CycleDetector.java b/sonar-graph/src/main/java/org/sonar/graph/CycleDetector.java deleted file mode 100644 index 49a9b4c9f60..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/CycleDetector.java +++ /dev/null @@ -1,153 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import java.util.ArrayList; -import java.util.Collection; -import java.util.LinkedHashSet; -import java.util.List; -import java.util.Set; - -public class CycleDetector<V> { - - private Set<V> vertices; - private DirectedGraphAccessor<V, ? extends Edge> graph; - private Set<V> analyzedVertices; - private Set<Cycle> cycles = new LinkedHashSet<>(); - private Set<Edge> edgesToExclude; - private long searchCyclesCalls = 0; - private int maxSearchDepth = -1; - private boolean maxSearchDepthActivated = false; - private int maxCyclesToFound = Integer.MAX_VALUE; - - public CycleDetector(DirectedGraphAccessor<V, ? extends Edge> graph, Collection<V> vertices) { - init(graph, vertices, new LinkedHashSet<Edge>()); - } - - public CycleDetector(DirectedGraphAccessor<V, ? extends Edge> graph, Collection<V> vertices, Set<Edge> edgesToExclude) { - init(graph, vertices, edgesToExclude); - } - - public CycleDetector(DirectedGraphAccessor<V, ? extends Edge> graph) { - init(graph, graph.getVertices(), new LinkedHashSet<Edge>()); - } - - public CycleDetector(DirectedGraphAccessor<V, ? extends Edge> graph, Set<Edge> edgesToExclude) { - init(graph, graph.getVertices(), edgesToExclude); - } - - private void init(DirectedGraphAccessor<V, ? extends Edge> graph, Collection<V> vertices, Set<Edge> edgesToExclude) { - this.graph = graph; - this.vertices = new LinkedHashSet<>(vertices); - this.analyzedVertices = new LinkedHashSet<>(); - this.edgesToExclude = edgesToExclude; - } - - public Set<Cycle> detectCycles() { - run(); - return getCycles(); - } - - public Set<Cycle> detectCyclesWithUpperLimit(int maxCyclesToFound) { - this.maxCyclesToFound = maxCyclesToFound; - run(); - return getCycles(); - } - - public Set<Cycle> 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<V> tmpAnalyzedVertices = new LinkedHashSet<>(); - searchCycles(vertex, new ArrayList<V>(), tmpAnalyzedVertices); - analyzedVertices.addAll(tmpAnalyzedVertices); - } - } - } catch (MaximumCyclesToFoundException e) { - // ignore - } - } - - private void searchCycles(V fromVertex, List<V> path, Set<V> tmpAnalyzedVertices) { - searchCyclesCalls++; - path.add(fromVertex); - tmpAnalyzedVertices.add(fromVertex); - for (Edge<V> 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<V> 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<V> vertices) { - List<Edge> 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<Cycle> 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 deleted file mode 100644 index 9dab7d83b5f..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/DirectedGraph.java +++ /dev/null @@ -1,149 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import java.util.ArrayList; -import java.util.Collection; -import java.util.HashMap; -import java.util.LinkedHashSet; -import java.util.List; -import java.util.Map; -import java.util.Set; - -public class DirectedGraph<V, E extends Edge<V>> implements DirectedGraphAccessor<V, E> { - - private EdgeFactory<V, E> edgeFactory; - private Map<V, Map<V, E>> outgoingEdgesByVertex = new HashMap<>(); - private Map<V, Map<V, E>> incomingEdgesByVertex = new HashMap<>(); - private Set<V> vertices = new LinkedHashSet<>(); - - public DirectedGraph() { - } - - public DirectedGraph(EdgeFactory<V, E> edgeFactory) { - this.edgeFactory = edgeFactory; - } - - public static DirectedGraph<String, StringEdge> createStringDirectedGraph() { - return new DirectedGraph<>(new StringEdgeFactory()); - } - - public DirectedGraph<V, E> addEdge(V from, V to) { - checkEdgeFacory(); - E edge = edgeFactory.createEdge(from, to); - return addEdge(edge); - } - - public DirectedGraph<V, E> 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<V, E> has not been defined. Please use the 'public E addEdge(V from, V to, E edge)' method."); - } - } - - public DirectedGraph<V, E> 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<V, Map<V, E>> edgesByVertex) { - Map<V, E> 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); - } - - @Override - public E getEdge(V from, V to) { - Map<V, E> outgoingEdgesFrom = outgoingEdgesByVertex.get(from); - if (outgoingEdgesFrom == null) { - return null; - } else { - return outgoingEdgesFrom.get(to); - } - } - - @Override - public boolean hasEdge(V from, V to) { - Map<V, E> 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<V> vertices) { - for (V vertex : vertices) { - addVertex(vertex); - } - } - - @Override - public Set<V> getVertices() { - return vertices; - } - - public List<E> getEdges(Collection<V> vertices) { - List<E> result = new ArrayList<>(); - for (V vertice : vertices) { - Collection<E> outgoingEdges = getOutgoingEdges(vertice); - if (outgoingEdges != null) { - result.addAll(outgoingEdges); - } - } - return result; - } - - @Override - public Collection<E> getOutgoingEdges(V from) { - Map<V, E> outgoingEdges = outgoingEdgesByVertex.get(from); - if (outgoingEdges == null) { - return new LinkedHashSet<>(); - } - return outgoingEdges.values(); - } - - @Override - public Collection<E> getIncomingEdges(V to) { - Map<V, E> incomingEdges = incomingEdgesByVertex.get(to); - if (incomingEdges == null) { - return new LinkedHashSet<>(); - } - 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 deleted file mode 100644 index 4e4c453db85..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/DirectedGraphAccessor.java +++ /dev/null @@ -1,36 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import java.util.Collection; -import java.util.Set; - -public interface DirectedGraphAccessor<V, E extends Edge<V>> { - - E getEdge(V from, V to); - - boolean hasEdge(V from, V to); - - Set<V> getVertices(); - - Collection<E> getOutgoingEdges(V from); - - Collection<E> 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 deleted file mode 100644 index 811cad56e3e..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/Dsm.java +++ /dev/null @@ -1,177 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import javax.annotation.CheckForNull; - -import java.util.Collection; -import java.util.Collections; -import java.util.Set; - -public class Dsm<V> { - - private final V[] vertices; - private final DsmCell[][] cells; - private final int dimension; - private final DirectedGraphAccessor<V, ? extends Edge<V>> graph; - - public Dsm(DirectedGraphAccessor<V, ? extends Edge<V>> graph, Collection<V> vertices, Set<Edge> feedbackEdges) { - this.graph = graph; - this.dimension = vertices.size(); - this.vertices = initVertices(vertices); - this.cells = initCells(feedbackEdges); - } - - public Dsm(DirectedGraphAccessor<V, ? extends Edge<V>> acyclicGraph, Set<Edge> feedbackEdges) { - this(acyclicGraph, acyclicGraph.getVertices(), feedbackEdges); - } - - public Dsm(DirectedGraphAccessor<V, ? extends Edge<V>> acyclicGraph) { - this(acyclicGraph, acyclicGraph.getVertices(), Collections.<Edge>emptySet()); - } - - private DsmCell[][] initCells(Set<Edge> feedbackEdges) { - DsmCell[][] result = new DsmCell[dimension][dimension]; - for (int x = 0; x < dimension; x++) { - for (int y = 0; y < dimension; y++) { - V from = vertices[x]; - V to = vertices[y]; - - Edge<V> edge = graph.getEdge(from, to); - if (edge != null) { - boolean isFeedbackEdge = feedbackEdges.contains(edge); - result[x][y] = new DsmCell(edge, isFeedbackEdge); - } - } - } - return result; - } - - private V[] initVertices(Collection<V> verticesCol) { - V[] result = (V[]) new Object[dimension]; - int i = 0; - for (V vertex : verticesCol) { - result[i] = vertex; - i++; - } - return result; - } - - 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 != null && 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 != null && cell.getWeight() != 0 && !cell.isFeedbackEdge()) { - outgoingEdges++; - } - } - return outgoingEdges; - } - - /** - * @deprecated since 5.0 use {@link #cell(int, int)} - */ - @Deprecated - public DsmCell getCell(int x, int y) { - DsmCell cell = cells[x][y]; - return cell != null ? cell : new DsmCell(null, false); - } - - /** - * @since 5.0 - */ - @CheckForNull - public DsmCell cell(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 deleted file mode 100644 index 88729bff2bc..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/DsmCell.java +++ /dev/null @@ -1,48 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import javax.annotation.Nullable; - -public class DsmCell { - - private final Edge edge; - private final boolean feedbackEdge; - - public DsmCell(@Nullable 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 deleted file mode 100644 index 685dfbe348e..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/DsmManualSorter.java +++ /dev/null @@ -1,61 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import java.util.Arrays; -import java.util.List; - - -public final class DsmManualSorter<V> { - - private final Dsm<V> dsm; - private final List<V> verticesInDesiredOrder; - - private DsmManualSorter(Dsm<V> dsm, List<V> verticesInDesiredOrder) { - this.dsm = dsm; - this.verticesInDesiredOrder = verticesInDesiredOrder; - } - - public static <V> void sort(Dsm<V> dsm, List<V> vertices) { - DsmManualSorter<V> sorter = new DsmManualSorter<>(dsm, vertices); - sorter.sort(); - } - - public static <V> void sort(Dsm<V> 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 deleted file mode 100644 index 5cdbd694829..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/DsmPrinter.java +++ /dev/null @@ -1,105 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -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 { - DsmCell cell = dsm.cell(x, y); - if (cell == null || cell.getWeight() == 0) { - writer.append(" "); - } else { - writer.append("").append(String.valueOf(cell.getWeight())); - } - if (cell != null && cell.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 deleted file mode 100644 index 268edcc1b84..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/DsmScanner.java +++ /dev/null @@ -1,116 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import org.apache.commons.lang.ArrayUtils; - -import java.io.IOException; -import java.io.LineNumberReader; -import java.io.Reader; -import java.io.StringReader; -import java.util.Arrays; -import java.util.LinkedHashSet; -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<String, StringEdge> graph = DirectedGraph.createStringDirectedGraph(); - private String[] vertices; - private Set<Edge> feedbackEdges = new LinkedHashSet<>(); - - private DsmScanner(Reader reader) { - this.reader = new LineNumberReader(reader); - } - - private Dsm<String> 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<String> 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()); - 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) { - if (line == null) { - return ArrayUtils.EMPTY_STRING_ARRAY; - } - 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<String> scan(String textDsm) { - StringReader reader = new StringReader(textDsm); - return scan(reader); - } - - public static Dsm<String> 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 deleted file mode 100644 index a55ec749fd8..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/DsmTopologicalSorter.java +++ /dev/null @@ -1,71 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -public final class DsmTopologicalSorter<V> { - - private final Dsm<V> dsm; - private int leftOrderedIndex; - private int rightOrderedIndex; - - private DsmTopologicalSorter(Dsm<V> dsm) { - this.dsm = dsm; - leftOrderedIndex = 0; - rightOrderedIndex = dsm.getDimension() - 1; - } - - public static <V> void sort(Dsm<V> dsm) { - DsmTopologicalSorter<V> 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 deleted file mode 100644 index 93ea29cb55b..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/Edge.java +++ /dev/null @@ -1,30 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -public interface Edge<V> { - - 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 deleted file mode 100644 index 93a4229ed8e..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/EdgeFactory.java +++ /dev/null @@ -1,27 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -public interface EdgeFactory<V, E> { - - 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 deleted file mode 100644 index 30822911df2..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/FeedbackCycle.java +++ /dev/null @@ -1,114 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ - -package org.sonar.graph; - -import com.google.common.collect.LinkedHashMultiset; -import com.google.common.collect.Multiset; - -import java.util.ArrayList; -import java.util.Collections; -import java.util.Iterator; -import java.util.List; -import java.util.Set; - -/** - * Note: this class has a natural ordering that is inconsistent with equals - */ -public final class FeedbackCycle implements Iterable<FeedbackEdge>, Comparable<FeedbackCycle> { - - private List<FeedbackEdge> 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<FeedbackCycle> buildFeedbackCycles(Set<Cycle> cycles) { - Multiset<Edge> edgesBag = createBagWithAllEdgesOfCycles(cycles); - - List<FeedbackCycle> 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<Edge> createBagWithAllEdgesOfCycles(Set<Cycle> cycles) { - Multiset<Edge> edgesBag = LinkedHashMultiset.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; - } - - @Override - public Iterator<FeedbackEdge> iterator() { - return orderedFeedbackEdges.iterator(); - } - - @Override - public int compareTo(FeedbackCycle feedbackCycle) { - if (getTotalOccurrencesOfEdgesInCycle() < feedbackCycle.getTotalOccurrencesOfEdgesInCycle()) {// NOSONAR this class has a natural - // ordering that is inconsistent with - // equals - 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 deleted file mode 100644 index 6e24a466058..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/FeedbackEdge.java +++ /dev/null @@ -1,78 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import org.apache.commons.lang.math.NumberUtils; - -public class FeedbackEdge implements Comparable<FeedbackEdge> { - - 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; - } - - @Override - public int compareTo(FeedbackEdge feedbackEdge) { - if (this.getRelativeWeight() < feedbackEdge.getRelativeWeight()) { - return -1; - } - if (NumberUtils.compare(this.getRelativeWeight(), feedbackEdge.getRelativeWeight())==0) { - 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 deleted file mode 100644 index 4e8bda55c77..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/IncrementalCyclesAndFESSolver.java +++ /dev/null @@ -1,88 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import java.util.Collection; -import java.util.LinkedHashSet; -import java.util.Set; - -public class IncrementalCyclesAndFESSolver<V> { - - private Set<Cycle> cycles = new LinkedHashSet<>(); - 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<V, ? extends Edge> graph, Collection<V> vertices) { - this(graph, vertices, DEFAULT_MAX_SEARCH_DEPTH_AT_FIRST, DEFAULT_MAX_CYCLES_TO_FOUND_BY_ITERATION); - } - - public IncrementalCyclesAndFESSolver(DirectedGraphAccessor<V, ? extends Edge> graph, Collection<V> vertices, int maxSearchDepthAtFirst, - int maxCyclesToFoundByIteration) { - - iterations++; - CycleDetector<V> cycleDetector = new CycleDetector<>(graph, vertices); - cycleDetector.detectCyclesWithMaxSearchDepth(maxSearchDepthAtFirst); - searchCyclesCalls += cycleDetector.getSearchCyclesCalls(); - cycles.addAll(cycleDetector.getCycles()); - solver = new MinimumFeedbackEdgeSetSolver(cycles); - Set<Edge> 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().isEmpty()); - } - - public int getWeightOfFeedbackEdgeSet() { - return solver.getWeightOfFeedbackEdgeSet(); - } - - public int getNumberOfLoops() { - return solver.getNumberOfLoops(); - } - - public Set<Edge> getFeedbackEdgeSet() { - return solver.getEdges(); - } - - public Set<Cycle> 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 deleted file mode 100644 index 6f9ec3b1ce1..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/MinimumFeedbackEdgeSetSolver.java +++ /dev/null @@ -1,151 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import java.util.LinkedHashSet; -import java.util.List; -import java.util.Set; - -public class MinimumFeedbackEdgeSetSolver { - - private final List<FeedbackCycle> feedbackCycles; - private Set<FeedbackEdge> 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<Cycle> cycles, int maxCycles) { - this(cycles, DEFAULT_MAXIMUM_NUMBER_OF_LOOPS, maxCycles); - } - - public MinimumFeedbackEdgeSetSolver(Set<Cycle> cycles) { - this(cycles, DEFAULT_MAXIMUM_NUMBER_OF_LOOPS, MAXIMUM_NUMBER_OF_CYCLE_THAT_CAN_BE_HANDLED); - } - - public MinimumFeedbackEdgeSetSolver(Set<Cycle> 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<Edge> getEdges() { - Set<Edge> edges = new LinkedHashSet<>(); - for (FeedbackEdge fe : feedbackEdges) { - edges.add(fe.getEdge()); - } - return edges; - } - - private void run() { - Set<FeedbackEdge> pendingFeedbackEdges = new LinkedHashSet<>(); - if (cyclesNumber < maxNumberCyclesForSearchingMinimumFeedback) { - searchFeedbackEdges(0, 0, pendingFeedbackEdges); - } else { - lightResearchForFeedbackEdges(); - } - } - - private void lightResearchForFeedbackEdges() { - feedbackEdges = new LinkedHashSet<>(); - 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<FeedbackEdge> pendingFeedbackEdges) { - if (numberOfLoops++ > maximumNumberOfLoops) { - return; - } - - if (pendingWeight >= minimumFeedbackEdgesWeight) { - return; - } - - if (level == cyclesNumber) { - minimumFeedbackEdgesWeight = pendingWeight; - feedbackEdges = new LinkedHashSet<>(pendingFeedbackEdges); - 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<FeedbackEdge> 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<FeedbackEdge> 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 deleted file mode 100644 index c5aa7bb1844..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/StringEdge.java +++ /dev/null @@ -1,74 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import org.apache.commons.lang.builder.ToStringBuilder; - -public class StringEdge implements Edge<String> { - - 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; - } - - @Override - public String getFrom() { - return from; - } - - @Override - public String getTo() { - return to; - } - - @Override - 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 deleted file mode 100644 index a7dd4dee50c..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/StringEdgeFactory.java +++ /dev/null @@ -1,33 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -public class StringEdgeFactory implements EdgeFactory<String, StringEdge> { - - @Override - public StringEdge createEdge(String from, String to) { - return new StringEdge(from, to); - } - - @Override - public StringEdge createEdge(String from, String to, int weight) { - return new StringEdge(from, to, weight); - } -} diff --git a/sonar-graph/src/main/java/org/sonar/graph/package-info.java b/sonar-graph/src/main/java/org/sonar/graph/package-info.java deleted file mode 100644 index e1f395aea51..00000000000 --- a/sonar-graph/src/main/java/org/sonar/graph/package-info.java +++ /dev/null @@ -1,25 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ - -@ParametersAreNonnullByDefault -package org.sonar.graph; - -import javax.annotation.ParametersAreNonnullByDefault; - diff --git a/sonar-graph/src/test/java/org/sonar/graph/CycleDetectorTest.java b/sonar-graph/src/test/java/org/sonar/graph/CycleDetectorTest.java deleted file mode 100644 index 244ae9f6ada..00000000000 --- a/sonar-graph/src/test/java/org/sonar/graph/CycleDetectorTest.java +++ /dev/null @@ -1,153 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import org.junit.Test; - -import java.util.Arrays; -import java.util.HashSet; -import java.util.Set; - -import static org.assertj.core.api.Assertions.assertThat; - -public class CycleDetectorTest { - - @Test - public void testIsAcyclicGraph() { - DirectedGraph<String, StringEdge> dag = DirectedGraph.createStringDirectedGraph(); - dag.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D"); - dag.addEdge("B", "D"); - dag.addEdge("A", "D"); - - CycleDetector<String> cycleDetector = new CycleDetector<>(dag); - cycleDetector.detectCycles(); - assertThat(cycleDetector.isAcyclicGraph()).isTrue(); - } - - @Test - public void testIsNotAcyclicGraph() { - DirectedGraph<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph(); - dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "A"); - - CycleDetector<String> cycleDetector = new CycleDetector<>(dcg); - cycleDetector.detectCycles(); - assertThat(cycleDetector.isAcyclicGraph()).isFalse(); - } - - @Test - public void testGetCyclesWithMultipleCycles() { - DirectedGraph<String, StringEdge> 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<String> cycleDetector = new CycleDetector<>(dcg); - cycleDetector.detectCycles(); - assertThat(cycleDetector.getCycles()).hasSize(8); - assertThat(cycleDetector.getSearchCyclesCalls()).isEqualTo(11); - } - - @Test - public void testMaxSearchDepthOption() { - DirectedGraph<String, StringEdge> 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<String> cycleDetector = new CycleDetector<>(dcg); - cycleDetector.detectCyclesWithMaxSearchDepth(3); - assertThat(cycleDetector.getCycles()).hasSize(2); - - cycleDetector = new CycleDetector<>(dcg); - cycleDetector.detectCyclesWithMaxSearchDepth(2); - assertThat(cycleDetector.getCycles()).hasSize(1); - } - - @Test - public void testExcludeEdgesFromSearch() { - DirectedGraph<String, StringEdge> 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<Edge> excludedEdges = new HashSet<>(); - excludedEdges.add(dcg.getEdge("C", "A")); - excludedEdges.add(dcg.getEdge("B", "A")); - - CycleDetector<String> cycleDetector = new CycleDetector<>(dcg, excludedEdges); - cycleDetector.detectCycles(); - assertThat(cycleDetector.getCycles()).hasSize(1); - } - - @Test - public void testGetCyclesWithOneCycle() { - DirectedGraph<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph(); - dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "E"); - dcg.addEdge("B", "A"); - - CycleDetector<String> cycleDetector = new CycleDetector<>(dcg); - cycleDetector.detectCycles(); - assertThat(cycleDetector.getCycles()).hasSize(1); - Cycle cycle = cycleDetector.getCycles().iterator().next(); - assertThat(cycle.size()).isEqualTo(2); - assertThat(cycle.contains(new StringEdge("A", "B"))).isTrue(); - assertThat(cycle.contains(new StringEdge("B", "A"))).isTrue(); - } - - @Test - public void getCyclesInLimitedSetOfVertices() { - DirectedGraph<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph(); - dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "A"); - - // C must not be used to find cycles - CycleDetector<String> cycleDetector = new CycleDetector<>(dcg, Arrays.asList("A", "B")); - cycleDetector.detectCycles(); - assertThat(cycleDetector.getCycles()).isEmpty(); - - // C is used to find cycles - cycleDetector = new CycleDetector<>(dcg, Arrays.asList("A", "B", "C")); - cycleDetector.detectCycles(); - assertThat(cycleDetector.getCycles().size()).isEqualTo(1); - } - - @Test(expected = IllegalStateException.class) - public void testExecutingTwoCycleDetectionsOnSameObject() { - DirectedGraph<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph(); - dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "A"); - - CycleDetector<String> cycleDetector = new CycleDetector<>(dcg); - cycleDetector.detectCycles(); - cycleDetector.detectCycles(); - } - - @Test - public void testDetectCyclesWithUpperLimit() { - DirectedGraph<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph(); - dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); - dcg.addEdge("B", "A"); - - CycleDetector<String> cycleDetector = new CycleDetector<>(dcg); - assertThat(cycleDetector.detectCyclesWithUpperLimit(1)).hasSize(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 deleted file mode 100644 index b90e0cc32e0..00000000000 --- a/sonar-graph/src/test/java/org/sonar/graph/CycleTest.java +++ /dev/null @@ -1,64 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import org.junit.Test; - -import java.util.Arrays; -import java.util.List; - -import static org.assertj.core.api.Assertions.assertThat; - -public class CycleTest { - static List<Edge> AB_BA = list(new StringEdge("A", "B"), new StringEdge("B", "A")); - static List<Edge> BA_AB = list(new StringEdge("B", "A"), new StringEdge("A", "B")); - static List<Edge> AB_BC_CA = list(new StringEdge("A", "B"), new StringEdge("B", "C"), new StringEdge("C", "A")); - static List<Edge> HI_IJ_JH = list(new StringEdge("H", "I"), new StringEdge("I", "J"), new StringEdge("J", "H")); - static List<Edge> AB_BC_CD_DA = list(new StringEdge("A", "B"), new StringEdge("B", "C"), new StringEdge("C", "D"), new StringEdge("D", "A")); - static List<Edge> BC_CD_DA_AB = list(new StringEdge("B", "C"), new StringEdge("C", "D"), new StringEdge("D", "A"), new StringEdge("A", "B")); - - @Test - public void testHashCode() { - assertThat(new Cycle(AB_BA).hashCode()).isEqualTo(new Cycle(BA_AB).hashCode()); - assertThat(new Cycle(BC_CD_DA_AB).hashCode()).isEqualTo(new Cycle(AB_BC_CD_DA).hashCode()); - assertThat(new Cycle(AB_BA).hashCode()).isNotEqualTo(new Cycle(AB_BC_CA).hashCode()); - } - - @Test - public void testContains() { - assertThat(new Cycle(AB_BC_CD_DA).contains(new StringEdge("B", "C"))).isTrue(); - } - - @Test - public void testEqualsObject() { - assertThat(new Cycle(AB_BA)).isEqualTo(new Cycle(BA_AB)); - assertThat(new Cycle(BC_CD_DA_AB)).isEqualTo(new Cycle(AB_BC_CD_DA)); - } - - @Test - public void testNotEqualsObject() { - assertThat(new Cycle(BC_CD_DA_AB)).isNotEqualTo(new Cycle(AB_BA)); - assertThat(new Cycle(AB_BC_CA)).isNotEqualTo(new Cycle(HI_IJ_JH)); - } - - static List<Edge> list(StringEdge... edges) { - return Arrays.<Edge> asList(edges); - } -} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DirectedGraphTest.java b/sonar-graph/src/test/java/org/sonar/graph/DirectedGraphTest.java deleted file mode 100644 index fac53692e1a..00000000000 --- a/sonar-graph/src/test/java/org/sonar/graph/DirectedGraphTest.java +++ /dev/null @@ -1,106 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -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<String, StringEdge> 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/DsmManualSorterTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmManualSorterTest.java deleted file mode 100644 index 7735dd510c5..00000000000 --- a/sonar-graph/src/test/java/org/sonar/graph/DsmManualSorterTest.java +++ /dev/null @@ -1,46 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import org.junit.Test; - -import static org.junit.Assert.assertEquals; - -public class DsmManualSorterTest { - - @Test - public void testSort() { - DirectedGraph<String, StringEdge> graph = DirectedGraph.createStringDirectedGraph(); - graph.addEdge("A", "B", 2); - graph.addEdge("A", "C", 3); - graph.addEdge("C", "B", 1); - Dsm<String> 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 deleted file mode 100644 index 063e1955b89..00000000000 --- a/sonar-graph/src/test/java/org/sonar/graph/DsmPrinterTest.java +++ /dev/null @@ -1,64 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -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<String> dsm; - - @Before - public void init() { - DirectedGraph<String, StringEdge> graph = DirectedGraph.createStringDirectedGraph(); - graph.addEdge("A", "B", 3).addEdge("A", "C", 2); - graph.addEdge("C", "B", 4).addEdge("C", "A", 1); - HashSet<Edge> feedbackEdges = Sets.<Edge>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 deleted file mode 100644 index 676a812796e..00000000000 --- a/sonar-graph/src/test/java/org/sonar/graph/DsmScannerTest.java +++ /dev/null @@ -1,55 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -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 deleted file mode 100644 index 9d01eaf1467..00000000000 --- a/sonar-graph/src/test/java/org/sonar/graph/DsmTest.java +++ /dev/null @@ -1,77 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -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<String> 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 deleted file mode 100644 index 9a22ea4555b..00000000000 --- a/sonar-graph/src/test/java/org/sonar/graph/DsmTopologicalSorterTest.java +++ /dev/null @@ -1,110 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -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<String> 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<String> expectedDsm = DsmScanner.scan(expectedTextDsm.toString()); - DsmTopologicalSorter.sort(expectedDsm); - - assertEquals(DsmPrinter.print(dsm), DsmPrinter.print(expectedDsm)); - } - - @Test(expected = IllegalStateException.class) - public void sortCyclicGraph() { - 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<String> dsm = DsmScanner.scan(textDsm.toString()); - DsmTopologicalSorter.sort(dsm); - } - - @Test - public void sortCyclicGraphWithManuallyFlaggedFeedbackEdges() { - 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<String> 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() { - DirectedGraph<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph(); - dcg.addEdge("A", "B", 3).addEdge("B", "A", 1); - CycleDetector<String> cycleDetector = new CycleDetector<>(dcg); - cycleDetector.detectCycles(); - - MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); - - Dsm<String> 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 deleted file mode 100644 index e14a97e691a..00000000000 --- a/sonar-graph/src/test/java/org/sonar/graph/FeedbackCycleTest.java +++ /dev/null @@ -1,66 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -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<Cycle> 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<FeedbackCycle> 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 deleted file mode 100644 index 366b5d2a231..00000000000 --- a/sonar-graph/src/test/java/org/sonar/graph/FeedbackEdgeTest.java +++ /dev/null @@ -1,81 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -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 deleted file mode 100644 index 104c11044a9..00000000000 --- a/sonar-graph/src/test/java/org/sonar/graph/IncrementalCyclesAndFESSolverTest.java +++ /dev/null @@ -1,72 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -import org.junit.Test; - -import static org.hamcrest.Matchers.is; -import static org.junit.Assert.assertThat; - -public class IncrementalCyclesAndFESSolverTest { - - @Test - public void testSimpleCase() { - DirectedGraph<String, StringEdge> 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<String> 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<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph(); - dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); - - IncrementalCyclesAndFESSolver<String> 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<String, StringEdge> 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<String> 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 deleted file mode 100644 index 580cc64f37f..00000000000 --- a/sonar-graph/src/test/java/org/sonar/graph/MinimumFeedbackEdgeSetSolverTest.java +++ /dev/null @@ -1,110 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -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<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph(); - dcg.addEdge("A", "B", 3).addEdge("B", "A", 1); - CycleDetector<String> cycleDetector = new CycleDetector<>(dcg); - cycleDetector.detectCycles(); - - MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); - Set<Edge> feedbackEdges = solver.getEdges(); - assertThat(feedbackEdges.size(), is(1)); - } - - @Test - public void testFlagFeedbackEdgesOnSimpleLoop() { - DirectedGraph<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph(); - dcg.addEdge("A", "B", 3).addEdge("B", "A", 1); - CycleDetector<String> cycleDetector = new CycleDetector<>(dcg); - cycleDetector.detectCycles(); - - MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); - Set<Edge> feedbackEdges = solver.getEdges(); - assertTrue(feedbackEdges.contains(dcg.getEdge("B", "A"))); - } - - @Test - public void testGetFeedbackEdgesOnComplexGraph() { - DirectedGraph<String, StringEdge> 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<String> cycleDetector = new CycleDetector<>(dcg); - cycleDetector.detectCycles(); - - MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); - Set<Edge> feedbackEdges = solver.getEdges(); - assertThat(feedbackEdges.size(), is(1)); - - assertTrue(feedbackEdges.contains(dcg.getEdge("A", "B"))); - } - - @Test - public void testFlagFeedbackEdgesOnUnrelatedCycles() { - DirectedGraph<String, StringEdge> 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<String> cycleDetector = new CycleDetector<>(dcg); - cycleDetector.detectCycles(); - - MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); - Set<Edge> 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<String, StringEdge> 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<String> 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 deleted file mode 100644 index 4ac77c0675d..00000000000 --- a/sonar-graph/src/test/java/org/sonar/graph/StringPrintWriter.java +++ /dev/null @@ -1,35 +0,0 @@ -/* - * SonarQube, open source software quality management tool. - * Copyright (C) 2008-2014 SonarSource - * mailto:contact AT sonarsource DOT com - * - * SonarQube 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. - * - * SonarQube 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 this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ -package org.sonar.graph; - -public class StringPrintWriter { - - private StringBuilder builder = new StringBuilder(); - - public void println(String line) { - builder.append(line + " \r"); - } - - @Override - public String toString() { - return builder.toString(); - } - -} |