SONAR-236 remove deprecated code from checkstyle plugin + display default value of rule parameters in Q profile console

33 files changed, 2672 insertions, 0 deletions

diff --git a/sonar-graph/pom.xml b/sonar-graph/pom.xml
new file mode 100644
index 00000000000..62942050670
--- /dev/null
+++ b/sonar-graph/pom.xml
@@ -0,0 +1,35 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+  <modelVersion>4.0.0</modelVersion>
+  <parent>
+    <groupId>org.codehaus.sonar</groupId>
+    <artifactId>sonar</artifactId>
+    <version>2.3-SNAPSHOT</version>
+    <relativePath>..</relativePath>
+  </parent>
+  <groupId>org.codehaus.sonar</groupId>
+  <artifactId>sonar-graph</artifactId>
+  <packaging>jar</packaging>
+  <name>Sonar :: Graph</name>
+
+  <dependencies>
+    <dependency>
+      <groupId>commons-lang</groupId>
+      <artifactId>commons-lang</artifactId>
+    </dependency>
+    <dependency>
+      <groupId>com.google.collections</groupId>
+      <artifactId>google-collections</artifactId>
+    </dependency>
+    <dependency>
+      <groupId>junit</groupId>
+      <artifactId>junit</artifactId>
+      <scope>test</scope>
+    </dependency>
+    <dependency>
+      <groupId>org.hamcrest</groupId>
+      <artifactId>hamcrest-all</artifactId>
+      <scope>test</scope>
+    </dependency>
+  </dependencies>
+</project>
\ No newline at end of file
diff --git a/sonar-graph/src/main/java/org/sonar/graph/Cycle.java b/sonar-graph/src/main/java/org/sonar/graph/Cycle.java
new file mode 100644
index 00000000000..84353b485d7
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/Cycle.java
@@ -0,0 +1,85 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.util.List;
+
+public class Cycle {
+
+  private Edge[] edges;
+  private int hashcode = 0;
+
+  public Cycle(List<Edge> edges) {
+    this.edges = edges.toArray(new Edge[0]);
+    for(Edge edge : edges) {
+      hashcode += edge.hashCode();
+    }
+  }
+
+  public int size() {
+    return edges.length;
+  }
+
+  public boolean contains(Edge e) {
+    for (Edge edge : edges) {
+      if (edge.equals(e)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  public Edge[] getEdges() {
+    return edges;
+  }
+
+  @Override
+  public String toString() {
+    StringBuilder builder = new StringBuilder("Cycle with " + size() + " edges : ");
+    for (Edge edge : edges) {
+      builder.append(edge.getFrom()).append(" -> ");
+    }
+    return builder.toString();
+  }
+
+  @Override
+  public int hashCode() {
+    return hashcode;
+  }
+
+  @Override
+  public boolean equals(Object object) {
+    if (object instanceof Cycle) {
+      Cycle otherCycle = (Cycle) object;
+      if (otherCycle.hashcode == hashcode && otherCycle.edges.length == edges.length) {
+        mainLoop: for (Edge otherEdge : otherCycle.edges) {
+          for (Edge edge : edges) {
+            if (otherEdge.equals(edge)) {
+              continue mainLoop;
+            }
+          }
+          return false;
+        }
+        return true;
+      }
+    }
+    return false;
+  }
+}
\ No newline at end of file
diff --git a/sonar-graph/src/main/java/org/sonar/graph/CycleDetector.java b/sonar-graph/src/main/java/org/sonar/graph/CycleDetector.java
new file mode 100644
index 00000000000..df6062ab5ff
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/CycleDetector.java
@@ -0,0 +1,152 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+public class CycleDetector<V> {
+
+  private Set<V> vertices;
+  private DirectedGraphAccessor<V, ? extends Edge> graph;
+  private Set<V> analyzedVertices;
+  private Set<Cycle> cycles = new HashSet<Cycle>();
+  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 HashSet<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 HashSet<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 HashSet<V>(vertices);
+    this.analyzedVertices = new HashSet<V>();
+    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 HashSet<V>();
+          searchCycles(vertex, new ArrayList<V>(), tmpAnalyzedVertices);
+          analyzedVertices.addAll(tmpAnalyzedVertices);
+        }
+      }
+    } catch (MaximumCyclesToFoundException e) {
+    }
+  }
+
+  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<Edge>();
+    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
new file mode 100644
index 00000000000..816a01422bc
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/DirectedGraph.java
@@ -0,0 +1,144 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+public class DirectedGraph<V, E extends Edge<V>> implements DirectedGraphAccessor<V, E> {
+
+  private EdgeFactory<V, E> edgeFactory;
+  private Map<V, Map<V, E>> outgoingEdgesByVertex = new HashMap<V, Map<V, E>>();
+  private Map<V, Map<V, E>> incomingEdgesByVertex = new HashMap<V, Map<V, E>>();
+  private Set<V> vertices = new HashSet<V>();
+
+  public DirectedGraph() {
+  }
+
+  public DirectedGraph(EdgeFactory<V, E> edgeFactory) {
+    this.edgeFactory = edgeFactory;
+  }
+
+  public static DirectedGraph<String, StringEdge> createStringDirectedGraph() {
+    return new DirectedGraph<String, StringEdge>(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<V, E>();
+      edgesByVertex.put(vertexKey1, edges);
+    }
+    if (edges.containsKey(vertexKey2)) {
+      throw new IllegalStateException("The graph already contains the edge : " + edge);
+    }
+    edges.put(vertexKey2, edge);
+  }
+
+  public E getEdge(V from, V to) {
+    Map<V, E> outgoingEdgesFrom = outgoingEdgesByVertex.get(from);
+    if (outgoingEdgesFrom == null) {
+      return null;
+    } else {
+      return outgoingEdgesFrom.get(to);
+    }
+  }
+
+  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);
+    }
+  }
+
+  public Set<V> getVertices() {
+    return vertices;
+  }
+
+  public List<E> getEdges(Collection<V> vertices) {
+    List<E> result = new ArrayList<E>();
+    for (V vertice : vertices) {
+      Collection<E> outgoingEdges = getOutgoingEdges(vertice);
+      if (outgoingEdges != null) {
+        result.addAll(outgoingEdges);
+      }
+    }
+    return result;
+  }
+
+  public Collection<E> getOutgoingEdges(V from) {
+    Map<V, E> outgoingEdges = outgoingEdgesByVertex.get(from);
+    if (outgoingEdges == null) {
+      return new HashSet<E>();
+    }
+    return outgoingEdges.values();
+  }
+
+  public Collection<E> getIncomingEdges(V to) {
+    Map<V, E> incomingEdges = incomingEdgesByVertex.get(to);
+    if (incomingEdges == null) {
+      return new HashSet<E>();
+    }
+    return incomingEdges.values();
+  }
+}
diff --git a/sonar-graph/src/main/java/org/sonar/graph/DirectedGraphAccessor.java b/sonar-graph/src/main/java/org/sonar/graph/DirectedGraphAccessor.java
new file mode 100644
index 00000000000..219adf38222
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/DirectedGraphAccessor.java
@@ -0,0 +1,36 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.util.Collection;
+import java.util.Set;
+
+public interface DirectedGraphAccessor<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
new file mode 100644
index 00000000000..1c3527d37ca
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/Dsm.java
@@ -0,0 +1,159 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Set;
+
+public class Dsm<V> {
+
+  private V[] vertices;
+  private DsmCell[][] cells;
+  private int dimension;
+  private 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.cells = new DsmCell[dimension][dimension];
+    initVertices(vertices);
+    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 void initCells(Set<Edge> feedbackEdges) {
+    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);
+        boolean isFeedbackEdge = (edge != null && feedbackEdges.contains(edge));
+        DsmCell cell = new DsmCell(edge, isFeedbackEdge);
+        cells[x][y] = cell;
+      }
+    }
+  }
+
+  private void initVertices(Collection<V> verticesCol) {
+    this.vertices = (V[]) new Object[dimension];
+    int i = 0;
+    for (V vertex : verticesCol) {
+      vertices[i] = vertex;
+      i++;
+    }
+  }
+
+  public V getVertex(int rowIndex) {
+    return vertices[rowIndex];
+  }
+
+  public int getDimension() {
+    return dimension;
+  }
+
+  public void permute(int fromIndex, int toIndex) {
+    if (fromIndex != toIndex) {
+      checkIndicesBoudaries(fromIndex, toIndex);
+      permuteVertice(fromIndex, toIndex);
+      permuteColumns(fromIndex, toIndex);
+      permuteRows(fromIndex, toIndex);
+    }
+  }
+
+  private void checkIndicesBoudaries(int... indices) {
+    for (int index : indices) {
+      if (index < 0 || index >= dimension) {
+        StringBuilder builder = new StringBuilder("DSM contains the following vertices : ");
+        for (V vertex : vertices) {
+          builder.append(vertex.toString()).append(" | ");
+        }
+        builder.append(". Trying to reach index ").append(index);
+        throw new ArrayIndexOutOfBoundsException(builder.toString());
+      }
+    }
+  }
+
+  private void permuteVertice(int fromIndex, int toIndex) {
+    V fromVertex = vertices[fromIndex];
+    V toVertex = vertices[toIndex];
+    vertices[fromIndex] = toVertex;
+    vertices[toIndex] = fromVertex;
+  }
+
+  private void permuteRows(int fromYIndex, int toYIndex) {
+    for (int x = 0; x < dimension; x++) {
+      permuteCells(x, fromYIndex, x, toYIndex);
+    }
+  }
+
+  private void permuteColumns(int fromXIndex, int toXIndex) {
+    for (int y = 0; y < dimension; y++) {
+      permuteCells(fromXIndex, y, toXIndex, y);
+    }
+  }
+
+  private void permuteCells(int fromXIndex, int fromYIndex, int toXIndex, int toYIndex) {
+    DsmCell fromCell = cells[fromXIndex][fromYIndex];
+    DsmCell toCell = cells[toXIndex][toYIndex];
+    cells[toXIndex][toYIndex] = fromCell;
+    cells[fromXIndex][fromYIndex] = toCell;
+  }
+
+  public int getNumberOfIncomingEdges(int y, int from, int to) {
+    int incomingEdges = 0;
+    for (int x = from; x <= to; x++) {
+      DsmCell cell = cells[x][y];
+      if (cell.getWeight() != 0 && !cell.isFeedbackEdge()) {
+        incomingEdges++;
+      }
+    }
+    return incomingEdges;
+  }
+
+  public int getNumberOfOutgoingEdges(int x, int from, int to) {
+    int outgoingEdges = 0;
+    for (int y = from; y <= to; y++) {
+      DsmCell cell = cells[x][y];
+      if (cell.getWeight() != 0 && !cell.isFeedbackEdge()) {
+        outgoingEdges++;
+      }
+    }
+    return outgoingEdges;
+  }
+
+  public DsmCell getCell(int x, int y) {
+    return cells[x][y];
+  }
+
+  public V[] getVertices() {
+    V[] verticesCopy = (V[]) new Object[vertices.length];
+    System.arraycopy(vertices, 0, verticesCopy, 0, vertices.length);
+    return verticesCopy;
+  }
+}
diff --git a/sonar-graph/src/main/java/org/sonar/graph/DsmCell.java b/sonar-graph/src/main/java/org/sonar/graph/DsmCell.java
new file mode 100644
index 00000000000..0e992922c16
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/DsmCell.java
@@ -0,0 +1,46 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+public class DsmCell {
+
+  private final Edge edge;
+  private final boolean feedbackEdge;
+
+  public DsmCell(Edge edge, boolean isFeedbackEdge) {
+    this.feedbackEdge = isFeedbackEdge;
+    this.edge = edge;
+  }
+
+  public int getWeight() {
+    return (edge==null) ? 0 : edge.getWeight();
+  }
+
+  public boolean isFeedbackEdge() {
+    return feedbackEdge;
+  }
+
+  /**
+   * @return nullable edge
+   */
+  public Edge getEdge() {
+    return edge;
+  }
+}
diff --git a/sonar-graph/src/main/java/org/sonar/graph/DsmManualSorter.java b/sonar-graph/src/main/java/org/sonar/graph/DsmManualSorter.java
new file mode 100644
index 00000000000..26069308de8
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/DsmManualSorter.java
@@ -0,0 +1,61 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.util.Arrays;
+import java.util.List;
+
+
+public final class DsmManualSorter<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<V>(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
new file mode 100644
index 00000000000..df36cedb936
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/DsmPrinter.java
@@ -0,0 +1,104 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.io.IOException;
+import java.io.StringWriter;
+import java.io.Writer;
+
+public final class DsmPrinter {
+
+  private final Writer writer;
+  private final Dsm dsm;
+  private static final String CELL_SEPARATOR = "| ";
+  private static final String FEEDBACK_EDGE_FLAG = "*";
+  private final boolean displayColumnHeaders;
+
+  private DsmPrinter(Writer writer, Dsm dsm, boolean displayColumnHeaders) {
+    this.writer = writer;
+    this.dsm = dsm;
+    this.displayColumnHeaders = displayColumnHeaders;
+  }
+
+  private void print() {
+    try {
+      if (displayColumnHeaders) {
+        printColumnHeaders();
+      }
+      for (int y = 0; y < dsm.getDimension(); y++) {
+        printRow(y);
+      }
+      writer.flush();
+      
+    } catch (IOException e) {
+      throw new RuntimeException("Unable to print the desired DSM.", e); // NOSONAR
+    }
+  }
+
+  public static String print(Dsm dsm, boolean displayColumnHeaders) {
+    StringWriter writer = new StringWriter();
+    print(writer, dsm, displayColumnHeaders);
+    return writer.toString();
+  }
+
+  public static String print(Dsm dsm) {
+    return print(dsm, true);
+  }
+
+  public static void print(Writer writer, Dsm dsm, boolean displayColumnHeaders) {
+    DsmPrinter printer = new DsmPrinter(writer, dsm, displayColumnHeaders);
+    printer.print();
+  }
+
+  private void printRow(int y) throws IOException {
+    printRowHeader(y);
+    for (int x = 0; x < dsm.getDimension(); x++) {
+      printCell(y, x);
+    }
+    writer.append((char) Character.LINE_SEPARATOR);
+  }
+
+  private void printCell(int y, int x) throws IOException {
+    if (dsm.getCell(x, y).getWeight() == 0) {
+      writer.append(" ");
+    } else {
+      writer.append("").append(String.valueOf(dsm.getCell(x, y).getWeight()));
+    }
+    if (dsm.getCell(x, y).isFeedbackEdge()) {
+      writer.append(FEEDBACK_EDGE_FLAG);
+    } else {
+      writer.append(' ');
+    }
+    writer.append(CELL_SEPARATOR);
+  }
+
+  private void printRowHeader(int y) throws IOException {
+    writer.append(String.valueOf(dsm.getVertex(y))).append(" " + CELL_SEPARATOR);
+  }
+
+  private void printColumnHeaders() throws IOException {
+    writer.append("  " + CELL_SEPARATOR);
+    for (int i = 0; i < dsm.getDimension(); i++) {
+      printRowHeader(i);
+    }
+    writer.append((char) Character.LINE_SEPARATOR);
+  }
+
+}
diff --git a/sonar-graph/src/main/java/org/sonar/graph/DsmScanner.java b/sonar-graph/src/main/java/org/sonar/graph/DsmScanner.java
new file mode 100644
index 00000000000..997d5ce9e94
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/DsmScanner.java
@@ -0,0 +1,113 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.io.IOException;
+import java.io.LineNumberReader;
+import java.io.Reader;
+import java.io.StringReader;
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.Set;
+
+public final class DsmScanner {
+
+  private final LineNumberReader reader;
+  private static final String CELL_SEPARATOR = "|";
+  private static final char FEEDBACK_EDGE_FLAG = '*';
+  private final DirectedGraph<String, StringEdge> graph = DirectedGraph.createStringDirectedGraph();
+  private String[] vertices;
+  private Set<Edge> feedbackEdges = new HashSet<Edge>();
+
+  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<String>(graph, graph.getVertices(), feedbackEdges);
+    DsmManualSorter.sort(dsm, Arrays.asList(vertices));
+    return dsm;
+  }
+
+  private void readRow(int i) throws IOException {
+    String[] tokens = splitLine(reader.readLine());
+    if (tokens != null) {
+      for (int j = 1; j < tokens.length - 1; j++) {
+        int toVertexIndex = j - 1;
+        int weight = extractWeight(tokens[j]);
+        if (i != toVertexIndex) {
+          StringEdge edge = new StringEdge(vertices[toVertexIndex], vertices[i], weight);
+          if (isFeedbackEdge(tokens[j])) {
+            feedbackEdges.add(edge);
+          }
+          graph.addEdge(edge);
+        }
+      }
+    }
+  }
+
+  private boolean isFeedbackEdge(String cellContent) {
+    return cellContent.indexOf(FEEDBACK_EDGE_FLAG) != -1;
+  }
+
+  private int extractWeight(String stringContent) {
+    try {
+      return Integer.valueOf(stringContent.replace(FEEDBACK_EDGE_FLAG, ' ').trim());
+    } catch (NumberFormatException e) {
+      return 0;
+    }
+  }
+
+  private void readColumnHeadersAndcreateDsmBuilder() throws IOException {
+    String[] tokens = splitLine(reader.readLine());
+    if (tokens != null) {
+      vertices = new String[tokens.length - 2];
+      System.arraycopy(tokens, 1, vertices, 0, tokens.length - 2);
+      graph.addVertices(Arrays.asList(vertices));
+    }
+  }
+
+  private String[] splitLine(String line) {
+    String[] tokens = line.split("\\" + CELL_SEPARATOR);
+    String[] result = new String[tokens.length];
+    for (int i = 0; i < tokens.length; i++) {
+      result[i] = tokens[i].trim();
+    }
+    return result;
+  }
+
+  public static Dsm<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
new file mode 100644
index 00000000000..715bf8cba6c
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/DsmTopologicalSorter.java
@@ -0,0 +1,71 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+public final class DsmTopologicalSorter<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<V>(dsm);
+    boolean dsmCanBeSorted = true;
+    while (dsmCanBeSorted) {
+      boolean dsmCanBeSortedOnLeft = partitionner.pushToLeftVerticesWithoutIncomingEdges();
+      boolean dsmCanBeSortedOnRight = partitionner.pushToRightVerticesWithoutOutgointEdges();
+      dsmCanBeSorted = dsmCanBeSortedOnLeft || dsmCanBeSortedOnRight;
+    }
+    boolean isCyclicGraph = (partitionner.leftOrderedIndex < partitionner.rightOrderedIndex);
+    if (isCyclicGraph) {
+      throw new IllegalStateException("Can't sort a cyclic graph.");
+    }
+  }
+
+  private boolean pushToLeftVerticesWithoutIncomingEdges() {
+    boolean permutationsDone = false;
+    for (int i = leftOrderedIndex; i <= rightOrderedIndex; i++) {
+      if (dsm.getNumberOfIncomingEdges(i, leftOrderedIndex, rightOrderedIndex) == 0) {
+        dsm.permute(i, leftOrderedIndex);
+        leftOrderedIndex++;
+        permutationsDone = true;
+      }
+    }
+    return permutationsDone;
+  }
+
+  private boolean pushToRightVerticesWithoutOutgointEdges() {
+    boolean permutationsDone = false;
+    for (int i = leftOrderedIndex; i <= rightOrderedIndex; i++) {
+      if (dsm.getNumberOfOutgoingEdges(i, leftOrderedIndex, rightOrderedIndex) == 0) {
+        dsm.permute(i, rightOrderedIndex);
+        rightOrderedIndex--;
+        permutationsDone = true;
+      }
+    }
+    return permutationsDone;
+  }
+}
diff --git a/sonar-graph/src/main/java/org/sonar/graph/Edge.java b/sonar-graph/src/main/java/org/sonar/graph/Edge.java
new file mode 100644
index 00000000000..1e627b0cc9b
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/Edge.java
@@ -0,0 +1,30 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+public interface Edge<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
new file mode 100644
index 00000000000..935315bbd74
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/EdgeFactory.java
@@ -0,0 +1,27 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+public interface EdgeFactory<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
new file mode 100644
index 00000000000..618d07feb3e
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/FeedbackCycle.java
@@ -0,0 +1,107 @@
+/*

+ * Sonar, open source software quality management tool.

+ * Copyright (C) 2009 SonarSource SA

+ * mailto:contact AT sonarsource DOT com

+ *

+ * Sonar is free software; you can redistribute it and/or

+ * modify it under the terms of the GNU Lesser General Public

+ * License as published by the Free Software Foundation; either

+ * version 3 of the License, or (at your option) any later version.

+ *

+ * Sonar is distributed in the hope that it will be useful,

+ * but WITHOUT ANY WARRANTY; without even the implied warranty of

+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

+ * Lesser General Public License for more details.

+ *

+ * You should have received a copy of the GNU Lesser General Public

+ * License along with Sonar; if not, write to the Free Software

+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02

+ */

+

+package org.sonar.graph;

+

+import java.util.ArrayList;

+import java.util.Collections;

+import java.util.Iterator;

+import java.util.List;

+import java.util.Set;

+

+import com.google.common.collect.HashMultiset;

+import com.google.common.collect.Multiset;

+

+public final class FeedbackCycle implements Iterable<FeedbackEdge>, Comparable<FeedbackCycle> {

+

+  private List<FeedbackEdge> orderedFeedbackEdges;

+  private int totalOccurrencesOfEdgesInCycle;

+  private final Cycle cycle;

+

+  private FeedbackCycle(Cycle cycle) {

+    orderedFeedbackEdges = new ArrayList<FeedbackEdge>();

+    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<FeedbackCycle>();

+    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 = HashMultiset.create();

+    for (Cycle cycle : cycles) {

+      for (Edge edge : cycle.getEdges()) {

+        edgesBag.add(edge);

+      }

+    }

+    return edgesBag;

+  }

+

+  private void setTotalOccurrencesOfEdgesInCycle(int totalOccurrencesOfEdgesInCycle) {

+    this.totalOccurrencesOfEdgesInCycle = totalOccurrencesOfEdgesInCycle;

+  }

+

+  public int getTotalOccurrencesOfEdgesInCycle() {

+    return totalOccurrencesOfEdgesInCycle;

+  }

+

+  public Iterator<FeedbackEdge> iterator() {

+    return orderedFeedbackEdges.iterator();

+  }

+

+  public int compareTo(FeedbackCycle feedbackCycle) {

+    if (getTotalOccurrencesOfEdgesInCycle() < feedbackCycle.getTotalOccurrencesOfEdgesInCycle()) {

+      return -1;

+    }

+    if (getTotalOccurrencesOfEdgesInCycle() == feedbackCycle.getTotalOccurrencesOfEdgesInCycle()) {

+      if (cycle.size() == feedbackCycle.cycle.size()) {

+        return orderedFeedbackEdges.get(0).compareTo(feedbackCycle.orderedFeedbackEdges.get(0));

+      }

+      return cycle.size() - feedbackCycle.cycle.size();

+    }

+    return 1;

+  }

+

+  public Cycle getCycle() {

+    return cycle;

+  }

+}

diff --git a/sonar-graph/src/main/java/org/sonar/graph/FeedbackEdge.java b/sonar-graph/src/main/java/org/sonar/graph/FeedbackEdge.java
new file mode 100644
index 00000000000..53fe8918583
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/FeedbackEdge.java
@@ -0,0 +1,75 @@
+/*

+ * Sonar, open source software quality management tool.

+ * Copyright (C) 2009 SonarSource SA

+ * mailto:contact AT sonarsource DOT com

+ *

+ * Sonar is free software; you can redistribute it and/or

+ * modify it under the terms of the GNU Lesser General Public

+ * License as published by the Free Software Foundation; either

+ * version 3 of the License, or (at your option) any later version.

+ *

+ * Sonar is distributed in the hope that it will be useful,

+ * but WITHOUT ANY WARRANTY; without even the implied warranty of

+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

+ * Lesser General Public License for more details.

+ *

+ * You should have received a copy of the GNU Lesser General Public

+ * License along with Sonar; if not, write to the Free Software

+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02

+ */

+package org.sonar.graph;

+

+public class FeedbackEdge implements Comparable<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;

+  }

+

+  public int compareTo(FeedbackEdge feedbackEdge) {

+    if (this.getRelativeWeight() < feedbackEdge.getRelativeWeight()) {

+      return -1;

+    }

+    if (this.getRelativeWeight() == feedbackEdge.getRelativeWeight()) {

+      return this.getEdge().getFrom().toString().compareTo(feedbackEdge.getEdge().getFrom().toString());

+    }

+    return 1;

+  }

+

+  @Override

+  public boolean equals(Object obj) {

+    if (!(obj instanceof FeedbackEdge) || this.hashCode() != obj.hashCode()) {

+      return false;

+    }

+    FeedbackEdge otherEdge = (FeedbackEdge) obj;

+    return edge.equals(otherEdge.edge);

+  }

+

+  @Override

+  public int hashCode() {

+    return hashcode;

+  }

+}

diff --git a/sonar-graph/src/main/java/org/sonar/graph/IncrementalCyclesAndFESSolver.java b/sonar-graph/src/main/java/org/sonar/graph/IncrementalCyclesAndFESSolver.java
new file mode 100644
index 00000000000..3fde2eaa2e8
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/IncrementalCyclesAndFESSolver.java
@@ -0,0 +1,89 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.Set;
+
+public class IncrementalCyclesAndFESSolver<V> {
+
+  private Set<Cycle> cycles = new HashSet<Cycle>();
+  private Set<Edge> edgesToExclude = new HashSet<Edge>();
+  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<V>(graph, vertices);
+    cycleDetector.detectCyclesWithMaxSearchDepth(maxSearchDepthAtFirst);
+    searchCyclesCalls += cycleDetector.getSearchCyclesCalls();
+    cycles.addAll(cycleDetector.getCycles());
+    solver = new MinimumFeedbackEdgeSetSolver(cycles);
+    edgesToExclude = solver.getEdges();
+
+    do {
+      iterations++;
+      cycleDetector = new CycleDetector<V>(graph, vertices, edgesToExclude);
+      cycleDetector.detectCyclesWithUpperLimit(maxCyclesToFoundByIteration);
+      searchCyclesCalls += cycleDetector.getSearchCyclesCalls();
+      cycles.addAll(cycleDetector.getCycles());
+      solver = new MinimumFeedbackEdgeSetSolver(cycles);
+      edgesToExclude = solver.getEdges();
+    } while (cycleDetector.getCycles().size() != 0);
+  }
+
+  public int getWeightOfFeedbackEdgeSet() {
+    return solver.getWeightOfFeedbackEdgeSet();
+  }
+
+  public int getNumberOfLoops() {
+    return solver.getNumberOfLoops();
+  }
+
+  public Set<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
new file mode 100644
index 00000000000..2c27caad174
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/MinimumFeedbackEdgeSetSolver.java
@@ -0,0 +1,153 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.util.*;
+
+public class MinimumFeedbackEdgeSetSolver {
+
+  private final List<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 HashSet<Edge>();
+    for (FeedbackEdge fe : feedbackEdges) {
+      edges.add(fe.getEdge());
+    }
+    return edges;
+  }
+
+  private void run() {
+    Set<FeedbackEdge> pendingFeedbackEdges = new HashSet<FeedbackEdge>();
+    if (cyclesNumber < maxNumberCyclesForSearchingMinimumFeedback) {
+      searchFeedbackEdges(0, 0, pendingFeedbackEdges);
+    }
+    else {
+      lightResearchForFeedbackEdges();
+    }
+  }
+
+  private void lightResearchForFeedbackEdges() {
+    feedbackEdges = new HashSet<FeedbackEdge>();
+    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 HashSet<FeedbackEdge>(pendingFeedbackEdges);
+      //System.out.println("Weight : " + minimumFeedbackEdgesWeight + " in " + numberOfLoops + " loops");
+      return;
+    }
+
+    FeedbackCycle feedbackCycle = feedbackCycles.get(level);
+
+    if (doesFeedbackEdgesContainAnEdgeOfTheCycle(pendingFeedbackEdges, feedbackCycle)) {
+      searchFeedbackEdges(level + 1, pendingWeight, pendingFeedbackEdges);
+    }
+    else {
+      boolean hasAnEdgeWithOccurrenceOfOneBeenUsed = false;
+      for (FeedbackEdge feedbackEdge : feedbackCycle) {
+        if (feedbackEdge.getOccurences() == 1) {
+          if (hasAnEdgeWithOccurrenceOfOneBeenUsed) {
+            continue;
+          }
+          else {
+            hasAnEdgeWithOccurrenceOfOneBeenUsed = true;
+          }
+        }
+        int edgeWeight = addNewEdge(feedbackEdge, pendingFeedbackEdges);
+        pendingWeight += edgeWeight;
+
+        searchFeedbackEdges(level + 1, pendingWeight, pendingFeedbackEdges);
+        pendingWeight -= edgeWeight;
+        pendingFeedbackEdges.remove(feedbackEdge);
+      }
+    }
+  }
+
+  private boolean doesFeedbackEdgesContainAnEdgeOfTheCycle(Set<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
new file mode 100644
index 00000000000..bd11d99adfd
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/StringEdge.java
@@ -0,0 +1,71 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import org.apache.commons.lang.builder.ToStringBuilder;
+
+public class StringEdge implements Edge<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;
+  }
+
+  public String getFrom() {
+    return from;
+  }
+
+  public String getTo() {
+    return to;
+  }
+
+  public int getWeight() {
+    return weight;
+  }
+
+  @Override
+  public boolean equals(Object obj) {
+    if (!(obj instanceof StringEdge)) {
+      return false;
+    }
+    StringEdge edge = (StringEdge) obj;
+    return from.equals(edge.from) && to.equals(edge.to);
+  }
+
+  @Override
+  public int hashCode() {
+    return 3*from.hashCode() + to.hashCode(); //NOSONAR Magic number 3 is suitable here
+  }
+
+  @Override
+  public String toString() {
+    return new ToStringBuilder(this).append("from", from).append("to", to).toString();
+  }
+}
diff --git a/sonar-graph/src/main/java/org/sonar/graph/StringEdgeFactory.java b/sonar-graph/src/main/java/org/sonar/graph/StringEdgeFactory.java
new file mode 100644
index 00000000000..c576b5a47ef
--- /dev/null
+++ b/sonar-graph/src/main/java/org/sonar/graph/StringEdgeFactory.java
@@ -0,0 +1,31 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+public class StringEdgeFactory implements EdgeFactory<String, StringEdge> {
+
+  public StringEdge createEdge(String from, String to) {
+    return new StringEdge(from, to);
+  }
+
+  public StringEdge createEdge(String from, String to, int weight) {
+    return new StringEdge(from, to, weight);
+  }
+}
diff --git a/sonar-graph/src/test/java/org/sonar/graph/CycleDetectorTest.java b/sonar-graph/src/test/java/org/sonar/graph/CycleDetectorTest.java
new file mode 100644
index 00000000000..dd010d64d4b
--- /dev/null
+++ b/sonar-graph/src/test/java/org/sonar/graph/CycleDetectorTest.java
@@ -0,0 +1,156 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.Set;
+
+import org.junit.Test;
+
+import static org.hamcrest.Matchers.is;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertThat;
+import static org.junit.Assert.assertTrue;
+
+public class CycleDetectorTest {
+
+  @Test
+  public void testIsAcyclicGraph() {
+    DirectedGraph<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<String>(dag);
+    cycleDetector.detectCycles();
+    assertTrue(cycleDetector.isAcyclicGraph());
+  }
+
+  @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<String>(dcg);
+    cycleDetector.detectCycles();
+    assertFalse(cycleDetector.isAcyclicGraph());
+  }
+
+  @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<String>(dcg);
+    cycleDetector.detectCycles();
+    assertThat(cycleDetector.getCycles().size(), is(8));
+    assertThat(cycleDetector.getSearchCyclesCalls(), is(8L));
+  }
+
+  @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<String>(dcg);
+    cycleDetector.detectCyclesWithMaxSearchDepth(3);
+    assertThat(cycleDetector.getCycles().size(), is(2));
+
+    cycleDetector = new CycleDetector<String>(dcg);
+    cycleDetector.detectCyclesWithMaxSearchDepth(2);
+    assertThat(cycleDetector.getCycles().size(), is(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<Edge>();
+    excludedEdges.add(dcg.getEdge("C", "A"));
+    excludedEdges.add(dcg.getEdge("B", "A"));
+
+    CycleDetector<String> cycleDetector = new CycleDetector<String>(dcg, excludedEdges);
+    cycleDetector.detectCycles();
+    assertThat(cycleDetector.getCycles().size(), is(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<String>(dcg);
+    cycleDetector.detectCycles();
+    assertThat(cycleDetector.getCycles().size(), is(1));
+    Cycle cycle = cycleDetector.getCycles().iterator().next();
+    assertThat(cycle.size(), is(2));
+    assertTrue(cycle.contains(new StringEdge("A", "B")));
+    assertTrue(cycle.contains(new StringEdge("B", "A")));
+  }
+
+  @Test
+  public void getCyclesInLimitedSetOfVertices() {
+    DirectedGraph<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<String>(dcg, Arrays.asList("A", "B"));
+    cycleDetector.detectCycles();
+    assertThat(cycleDetector.getCycles().size(), is(0));
+
+    // C is used to find cycles
+    cycleDetector = new CycleDetector<String>(dcg, Arrays.asList("A", "B", "C"));
+    cycleDetector.detectCycles();
+    assertThat(cycleDetector.getCycles().size(), is(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<String>(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<String>(dcg);
+    assertThat(cycleDetector.detectCyclesWithUpperLimit(1).size(), is(1));
+  }
+}
diff --git a/sonar-graph/src/test/java/org/sonar/graph/CycleTest.java b/sonar-graph/src/test/java/org/sonar/graph/CycleTest.java
new file mode 100644
index 00000000000..a42366abbab
--- /dev/null
+++ b/sonar-graph/src/test/java/org/sonar/graph/CycleTest.java
@@ -0,0 +1,58 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.util.Arrays;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+public class CycleTest {
+
+  private Edge[] AB_Cycle = { new StringEdge("A", "B"), new StringEdge("B", "A") };
+  private Edge[] BA_Cycle = { new StringEdge("B", "A"), new StringEdge("A", "B") };
+  private Edge[] ABC_Cycle = { new StringEdge("A", "B"), new StringEdge("B", "C"), new StringEdge("C", "A") };
+  private Edge[] HIJ_Cycle = { new StringEdge("H", "I"), new StringEdge("I", "J"), new StringEdge("J", "H") };
+  private Edge[] ABCD_Cycle = { new StringEdge("A", "B"), new StringEdge("B", "C"), new StringEdge("C", "D"), new StringEdge("D", "A") };
+  private Edge[] BCDA_Cycle = { new StringEdge("B", "C"), new StringEdge("C", "D"), new StringEdge("D", "A"), new StringEdge("A", "B"), };
+
+  @Test
+  public void testHashCode() {
+    assertTrue(new Cycle(Arrays.asList(AB_Cycle)).hashCode() == new Cycle(Arrays.asList(BA_Cycle)).hashCode());
+    assertTrue(new Cycle(Arrays.asList(BCDA_Cycle)).hashCode() == new Cycle(Arrays.asList(ABCD_Cycle)).hashCode());
+    assertFalse(new Cycle(Arrays.asList(AB_Cycle)).hashCode() == new Cycle(Arrays.asList(ABC_Cycle)).hashCode());
+  }
+
+  @Test
+  public void testContains() {
+    assertTrue(new Cycle(Arrays.asList(ABCD_Cycle)).contains(new StringEdge("B", "C")));
+  }
+
+  @Test
+  public void testEqualsObject() {
+    assertEquals(new Cycle(Arrays.asList(AB_Cycle)), new Cycle(Arrays.asList(BA_Cycle)));
+    assertEquals(new Cycle(Arrays.asList(BCDA_Cycle)), new Cycle(Arrays.asList(ABCD_Cycle)));
+    assertFalse(new Cycle(Arrays.asList(BCDA_Cycle)).equals(new Cycle(Arrays.asList(AB_Cycle))));
+    assertFalse(new Cycle(Arrays.asList(ABC_Cycle)).equals(new Cycle(Arrays.asList(HIJ_Cycle))));
+  }
+}
diff --git a/sonar-graph/src/test/java/org/sonar/graph/DirectedGraphTest.java b/sonar-graph/src/test/java/org/sonar/graph/DirectedGraphTest.java
new file mode 100644
index 00000000000..0abcb4c9af2
--- /dev/null
+++ b/sonar-graph/src/test/java/org/sonar/graph/DirectedGraphTest.java
@@ -0,0 +1,106 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.sonar.graph.DirectedGraph;
+import org.sonar.graph.StringEdge;
+
+import java.util.Arrays;
+
+import static org.hamcrest.Matchers.*;
+import static org.junit.Assert.*;
+
+public class DirectedGraphTest {
+
+  private DirectedGraph<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/DsmCellTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmCellTest.java
new file mode 100644
index 00000000000..12069d2dc88
--- /dev/null
+++ b/sonar-graph/src/test/java/org/sonar/graph/DsmCellTest.java
@@ -0,0 +1,45 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import org.junit.Ignore;
+import org.junit.Test;
+import org.sonar.graph.DsmCell;
+import org.sonar.graph.StringEdge;
+
+import static org.hamcrest.Matchers.equalTo;
+import static org.hamcrest.Matchers.not;
+import static org.junit.Assert.assertThat;
+
+public class DsmCellTest {
+
+  @Test
+  @Ignore
+  public void testEquals() {
+    DsmCell cell1 = new DsmCell(new StringEdge("A", "B", 1), true);
+    DsmCell cell1bis = new DsmCell(new StringEdge("A", "B", 1), false);
+    DsmCell cell4 = new DsmCell(new StringEdge("B", "A", 4), true);
+
+    assertThat(cell1, equalTo(cell1));
+    assertThat(cell1, equalTo(cell1bis));
+    assertThat(cell1, not(equalTo(cell4)));
+  }
+
+}
diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmManualSorterTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmManualSorterTest.java
new file mode 100644
index 00000000000..617abe383f6
--- /dev/null
+++ b/sonar-graph/src/test/java/org/sonar/graph/DsmManualSorterTest.java
@@ -0,0 +1,46 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class DsmManualSorterTest {
+
+  @Test
+  public void testSort() {
+    DirectedGraph<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<String>(graph);
+    DsmManualSorter.sort(dsm, "B", "A", "C");
+
+    StringPrintWriter expectedDsm = new StringPrintWriter();
+    expectedDsm.println("  | B | A | C |");
+    expectedDsm.println("B |   | 2 | 1 |");
+    expectedDsm.println("A |   |   |   |");
+    expectedDsm.println("C |   | 3 |   |");
+
+    assertEquals(expectedDsm.toString(), DsmPrinter.print(dsm));
+  }
+
+}
diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmPrinterTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmPrinterTest.java
new file mode 100644
index 00000000000..55e8de64de6
--- /dev/null
+++ b/sonar-graph/src/test/java/org/sonar/graph/DsmPrinterTest.java
@@ -0,0 +1,64 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import com.google.common.collect.Sets;
+import org.junit.Before;
+import org.junit.Test;
+
+import java.util.HashSet;
+
+import static org.junit.Assert.assertEquals;
+
+public class DsmPrinterTest {
+
+  private Dsm<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<String>(graph, feedbackEdges);
+    DsmManualSorter.sort(dsm, "A", "C", "B");
+  }
+
+  @Test
+  public void testPrintDsm() {
+    StringPrintWriter expectedResult = new StringPrintWriter();
+    expectedResult.println("  | A | C | B |");
+    expectedResult.println("A |   | 1*|   |");
+    expectedResult.println("C | 2 |   |   |");
+    expectedResult.println("B | 3 | 4 |   |");
+
+    assertEquals(expectedResult.toString(), DsmPrinter.print(dsm));
+  }
+
+  @Test
+  public void testPrintDsmWithoutColumnHeaders() {
+    StringPrintWriter expectedResult = new StringPrintWriter();
+    expectedResult.println("A |   | 1*|   |");
+    expectedResult.println("C | 2 |   |   |");
+    expectedResult.println("B | 3 | 4 |   |");
+
+    assertEquals(expectedResult.toString(), DsmPrinter.print(dsm, false));
+  }
+}
diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmScannerTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmScannerTest.java
new file mode 100644
index 00000000000..1d9df9239d4
--- /dev/null
+++ b/sonar-graph/src/test/java/org/sonar/graph/DsmScannerTest.java
@@ -0,0 +1,55 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import org.junit.Test;
+import org.sonar.graph.Dsm;
+import org.sonar.graph.DsmCell;
+import org.sonar.graph.DsmScanner;
+
+import static org.junit.Assert.*;
+
+public class DsmScannerTest {
+
+  @Test
+  public void testScanString() {
+    StringPrintWriter builder = new StringPrintWriter();
+    builder.println("  | A | B |");
+    builder.println("A |   | 1*|");
+    builder.println("B | 3 |   |");
+    Dsm dsm = DsmScanner.scan(builder.toString());
+
+    assertEquals("A", dsm.getVertex(0).toString());
+    assertEquals("B", dsm.getVertex(1).toString());
+
+    assertEquals(2, dsm.getDimension());
+
+    DsmCell ba = dsm.getCell(1, 0);
+    assertEquals(1, ba.getWeight());
+    assertTrue(ba.isFeedbackEdge());
+
+    DsmCell ab = dsm.getCell(0, 1);
+    assertEquals(3, ab.getWeight());
+    assertFalse(ab.isFeedbackEdge());
+
+    assertEquals(0, dsm.getCell(1, 1).getWeight());
+  }
+
+}
diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmTest.java
new file mode 100644
index 00000000000..06fbcba4160
--- /dev/null
+++ b/sonar-graph/src/test/java/org/sonar/graph/DsmTest.java
@@ -0,0 +1,77 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.sonar.graph.Dsm;
+import org.sonar.graph.DsmScanner;
+
+import static org.hamcrest.Matchers.equalTo;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertThat;
+
+public class DsmTest {
+
+  private Dsm<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
new file mode 100644
index 00000000000..f017d32dc23
--- /dev/null
+++ b/sonar-graph/src/test/java/org/sonar/graph/DsmTopologicalSorterTest.java
@@ -0,0 +1,112 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.io.IOException;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class DsmTopologicalSorterTest {
+
+  @Test
+  public void sortAcyclicGraph() {
+    StringPrintWriter textDsm = new StringPrintWriter();
+    textDsm.println("  | A | B | C | D | E |");
+    textDsm.println("A |   |   |   |   |   |");
+    textDsm.println("B | 3 |   | 4 |   |   |");
+    textDsm.println("C | 1 |   |   |   |   |");
+    textDsm.println("D |   | 2 |   |   | 1 |");
+    textDsm.println("E |   | 5 |   |   |   |");
+
+    Dsm<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() throws IOException {
+    StringPrintWriter textDsm = new StringPrintWriter();
+    textDsm.println("  | A | B | C | D |");
+    textDsm.println("A |   |   |   |   |");
+    textDsm.println("B | 3 |   | 4 |   |");
+    textDsm.println("C | 1 | 1 |   |   |");
+    textDsm.println("D |   | 2 |   |   |");
+
+    Dsm<String> dsm = DsmScanner.scan(textDsm.toString());
+    DsmTopologicalSorter.sort(dsm);
+  }
+
+  @Test
+  public void sortCyclicGraphWithManuallyFlaggedFeedbackEdges() throws IOException {
+    StringPrintWriter textDsm = new StringPrintWriter();
+    textDsm.println("  | A | B | C | D |");
+    textDsm.println("A |   |   |   |   |");
+    textDsm.println("B | 3 |   | 4 |   |");
+    textDsm.println("C | 1 | 1*|   |   |");
+    textDsm.println("D |   | 2 |   |   |");
+
+    Dsm<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() throws IOException {
+    DirectedGraph<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph();
+    dcg.addEdge("A", "B", 3).addEdge("B", "A", 1);
+    CycleDetector<String> cycleDetector = new CycleDetector<String>(dcg);
+    cycleDetector.detectCycles();
+
+    MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles());
+
+    Dsm<String> dsm = new Dsm<String>(dcg, solver.getEdges());
+    DsmTopologicalSorter.sort(dsm);
+
+    StringPrintWriter expectedDsm = new StringPrintWriter();
+    expectedDsm.println("  | A | B |");
+    expectedDsm.println("A |   | 1*|");
+    expectedDsm.println("B | 3 |   |");
+
+    assertEquals(expectedDsm.toString(), DsmPrinter.print(dsm));
+  }
+
+}
diff --git a/sonar-graph/src/test/java/org/sonar/graph/FeedbackCycleTest.java b/sonar-graph/src/test/java/org/sonar/graph/FeedbackCycleTest.java
new file mode 100644
index 00000000000..b132d6c8e60
--- /dev/null
+++ b/sonar-graph/src/test/java/org/sonar/graph/FeedbackCycleTest.java
@@ -0,0 +1,66 @@
+/*
+w * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class FeedbackCycleTest {
+
+  private Edge[] AB_Edges = { new StringEdge("A", "B"), new StringEdge("B", "A") };
+  private Edge[] ABC_Edges = { new StringEdge("A", "B"), new StringEdge("B", "C"), new StringEdge("C", "A") };
+  private Edge[] BCDA_Edges = { new StringEdge("B", "C"), new StringEdge("C", "D"), new StringEdge("D", "A"), new StringEdge("A", "B"), };
+  private Edge[] EF_Edges = { new StringEdge("E", "F"), new StringEdge("F", "E") };
+  private Edge[] GHIJ_Edges = { new StringEdge("G", "H"), new StringEdge("H", "I"), new StringEdge("I", "J"), new StringEdge("J", "G") };
+  private Edge[] XYZW_Edges = { new StringEdge("X", "Y"), new StringEdge("Y", "Z"), new StringEdge("Z", "W"), new StringEdge("W", "X") };
+
+  private Cycle AB_Cycle = new Cycle(Arrays.asList(AB_Edges));
+  private Cycle ABC_Cycle = new Cycle(Arrays.asList(ABC_Edges));
+  private Cycle BCDA_Cycle = new Cycle(Arrays.asList(BCDA_Edges));
+  private Cycle EF_Cycle = new Cycle(Arrays.asList(EF_Edges));
+  private Cycle GHIJ_Cycle = new Cycle(Arrays.asList(GHIJ_Edges));
+  private Cycle XYZW_Cycle = new Cycle(Arrays.asList(XYZW_Edges));
+
+  @Test
+  public void testBuildFeedbackCycles() {
+    Set<Cycle> cycles = new HashSet<Cycle>();
+    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
new file mode 100644
index 00000000000..67ba883635b
--- /dev/null
+++ b/sonar-graph/src/test/java/org/sonar/graph/FeedbackEdgeTest.java
@@ -0,0 +1,81 @@
+/*

+ * Sonar, open source software quality management tool.

+ * Copyright (C) 2009 SonarSource SA

+ * mailto:contact AT sonarsource DOT com

+ *

+ * Sonar is free software; you can redistribute it and/or

+ * modify it under the terms of the GNU Lesser General Public

+ * License as published by the Free Software Foundation; either

+ * version 3 of the License, or (at your option) any later version.

+ *

+ * Sonar is distributed in the hope that it will be useful,

+ * but WITHOUT ANY WARRANTY; without even the implied warranty of

+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

+ * Lesser General Public License for more details.

+ *

+ * You should have received a copy of the GNU Lesser General Public

+ * License along with Sonar; if not, write to the Free Software

+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02

+ */

+package org.sonar.graph;

+

+import org.junit.Test;

+

+import static org.hamcrest.MatcherAssert.assertThat;

+import static org.hamcrest.Matchers.greaterThan;

+import static org.hamcrest.Matchers.is;

+

+public class FeedbackEdgeTest {

+

+  @Test

+  public void testWeights() {

+    FeedbackEdge fEdge = mockFeedbackEdge(14, 2);

+    assertThat(fEdge.getWeight(), is(14));

+    assertThat(fEdge.getRelativeWeight(), is(7.0));

+    assertThat(fEdge.getOccurences(), is(2));

+  }

+

+  @Test

+  public void testCompareTo() {

+    FeedbackEdge feedbackEdge1;

+    FeedbackEdge feedbackEdge2;

+    FeedbackEdge feedbackEdge3;

+

+    feedbackEdge1 = mockFeedbackEdge(14, 2);

+    feedbackEdge2 = mockFeedbackEdge(10, 2);

+    assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(1));

+

+    feedbackEdge1 = mockFeedbackEdge(10, 2);

+    feedbackEdge2 = mockFeedbackEdge(14, 2);

+    assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(-1));

+

+    feedbackEdge1 = mockFeedbackEdge(14, 2);

+    feedbackEdge2 = mockFeedbackEdge(14, 2);

+    assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(0));

+

+    feedbackEdge1 = mockFeedbackEdge(14, 2);

+    feedbackEdge2 = mockFeedbackEdge(13, 2);

+    assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(1));

+

+    feedbackEdge1 = mockFeedbackEdge(13, 2);

+    feedbackEdge2 = mockFeedbackEdge(14, 2);

+    assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(-1));

+

+    feedbackEdge1 = mockFeedbackEdge("A", "B", 14, 2);

+    feedbackEdge2 = mockFeedbackEdge("B", "C", 14, 2);

+    feedbackEdge3 = mockFeedbackEdge("C", "A", 14, 2);

+    assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(-1));

+    assertThat(feedbackEdge2.compareTo(feedbackEdge3), is(-1));

+    assertThat(feedbackEdge3.compareTo(feedbackEdge1), greaterThan(1));

+  }

+

+  private FeedbackEdge mockFeedbackEdge(int weight, int occurrences) {

+    return mockFeedbackEdge("from", "to", weight, occurrences);

+  }

+

+  private FeedbackEdge mockFeedbackEdge(String from, String to, int weight, int occurrences) {

+    Edge edge = new StringEdge(from, to, weight);

+    return new FeedbackEdge(edge, occurrences);

+  }

+

+}

diff --git a/sonar-graph/src/test/java/org/sonar/graph/IncrementalCyclesAndFESSolverTest.java b/sonar-graph/src/test/java/org/sonar/graph/IncrementalCyclesAndFESSolverTest.java
new file mode 100644
index 00000000000..3b11829819c
--- /dev/null
+++ b/sonar-graph/src/test/java/org/sonar/graph/IncrementalCyclesAndFESSolverTest.java
@@ -0,0 +1,73 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import org.junit.Test;
+
+import static org.hamcrest.Matchers.containsString;
+import static org.hamcrest.Matchers.is;
+import static org.junit.Assert.assertThat;
+
+public class IncrementalCyclesAndFESSolverTest {
+
+  @Test
+  public void testSimpleCase() {
+    DirectedGraph<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<String>(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<String>(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<String>(dcg, dcg.getVertices(), 2, 1);
+    assertThat(cyclesAndFESSolver.getCycles().size(), is(3));
+    assertThat(cyclesAndFESSolver.getIterations(), is(4));
+    cyclesAndFESSolver.getFeedbackEdgeSet();
+  }
+
+}
diff --git a/sonar-graph/src/test/java/org/sonar/graph/MinimumFeedbackEdgeSetSolverTest.java b/sonar-graph/src/test/java/org/sonar/graph/MinimumFeedbackEdgeSetSolverTest.java
new file mode 100644
index 00000000000..704b8f83402
--- /dev/null
+++ b/sonar-graph/src/test/java/org/sonar/graph/MinimumFeedbackEdgeSetSolverTest.java
@@ -0,0 +1,110 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+import java.util.Set;
+
+import org.junit.Test;
+
+import static org.hamcrest.Matchers.is;
+import static org.junit.Assert.assertThat;
+import static org.junit.Assert.assertTrue;
+
+public class MinimumFeedbackEdgeSetSolverTest {
+
+  @Test
+  public void testGetFeedbackEdgesOnSimpleLoop() {
+    DirectedGraph<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph();
+    dcg.addEdge("A", "B", 3).addEdge("B", "A", 1);
+    CycleDetector<String> cycleDetector = new CycleDetector<String>(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<String>(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<String>(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<String>(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<String>(dcg);
+    cycleDetector.detectCycles();
+
+    MinimumFeedbackEdgeSetSolver minimumSolver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles());
+    assertThat(minimumSolver.getEdges().size(), is(1));
+    assertTrue(minimumSolver.getEdges().contains(dcg.getEdge("B", "C")));
+
+    MinimumFeedbackEdgeSetSolver approximateSolver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles(), 2);
+    assertThat(approximateSolver.getEdges().size(), is(2));
+    assertTrue(approximateSolver.getEdges().contains(dcg.getEdge("B", "C")));
+    assertTrue(approximateSolver.getEdges().contains(dcg.getEdge("C", "A")));
+  }
+
+}
diff --git a/sonar-graph/src/test/java/org/sonar/graph/StringPrintWriter.java b/sonar-graph/src/test/java/org/sonar/graph/StringPrintWriter.java
new file mode 100644
index 00000000000..3beddf48215
--- /dev/null
+++ b/sonar-graph/src/test/java/org/sonar/graph/StringPrintWriter.java
@@ -0,0 +1,34 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2009 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.graph;
+
+public class StringPrintWriter {
+
+  private StringBuilder builder = new StringBuilder();
+
+  public void println(String line) {
+    builder.append(line + " \r");
+  }
+
+  public String toString() {
+    return builder.toString();
+  }
+
+}