From aeadc1f9129274949daaa57738c7c4550bdfbc7b Mon Sep 17 00:00:00 2001 From: simonbrandhof Date: Mon, 6 Sep 2010 14:08:06 +0000 Subject: SONAR-236 remove deprecated code from checkstyle plugin + display default value of rule parameters in Q profile console --- .../java/org/sonar/graph/CycleDetectorTest.java | 156 +++++++++++++++++++++ .../src/test/java/org/sonar/graph/CycleTest.java | 58 ++++++++ .../java/org/sonar/graph/DirectedGraphTest.java | 106 ++++++++++++++ .../src/test/java/org/sonar/graph/DsmCellTest.java | 45 ++++++ .../java/org/sonar/graph/DsmManualSorterTest.java | 46 ++++++ .../test/java/org/sonar/graph/DsmPrinterTest.java | 64 +++++++++ .../test/java/org/sonar/graph/DsmScannerTest.java | 55 ++++++++ .../src/test/java/org/sonar/graph/DsmTest.java | 77 ++++++++++ .../org/sonar/graph/DsmTopologicalSorterTest.java | 112 +++++++++++++++ .../java/org/sonar/graph/FeedbackCycleTest.java | 66 +++++++++ .../java/org/sonar/graph/FeedbackEdgeTest.java | 81 +++++++++++ .../graph/IncrementalCyclesAndFESSolverTest.java | 73 ++++++++++ .../graph/MinimumFeedbackEdgeSetSolverTest.java | 110 +++++++++++++++ .../java/org/sonar/graph/StringPrintWriter.java | 34 +++++ 14 files changed, 1083 insertions(+) create mode 100644 sonar-graph/src/test/java/org/sonar/graph/CycleDetectorTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/CycleTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/DirectedGraphTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/DsmCellTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/DsmManualSorterTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/DsmPrinterTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/DsmScannerTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/DsmTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/DsmTopologicalSorterTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/FeedbackCycleTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/FeedbackEdgeTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/IncrementalCyclesAndFESSolverTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/MinimumFeedbackEdgeSetSolverTest.java create mode 100644 sonar-graph/src/test/java/org/sonar/graph/StringPrintWriter.java (limited to 'sonar-graph/src/test/java/org/sonar') diff --git a/sonar-graph/src/test/java/org/sonar/graph/CycleDetectorTest.java b/sonar-graph/src/test/java/org/sonar/graph/CycleDetectorTest.java new file mode 100644 index 00000000000..dd010d64d4b --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/CycleDetectorTest.java @@ -0,0 +1,156 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.Arrays; +import java.util.HashSet; +import java.util.Set; + +import org.junit.Test; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertThat; +import static org.junit.Assert.assertTrue; + +public class CycleDetectorTest { + + @Test + public void testIsAcyclicGraph() { + DirectedGraph dag = DirectedGraph.createStringDirectedGraph(); + dag.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D"); + dag.addEdge("B", "D"); + dag.addEdge("A", "D"); + + CycleDetector cycleDetector = new CycleDetector(dag); + cycleDetector.detectCycles(); + assertTrue(cycleDetector.isAcyclicGraph()); + } + + @Test + public void testIsNotAcyclicGraph() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "A"); + + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + assertFalse(cycleDetector.isAcyclicGraph()); + } + + @Test + public void testGetCyclesWithMultipleCycles() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); + dcg.addEdge("C", "A"); + dcg.addEdge("B", "A"); + dcg.addEdge("A", "E").addEdge("E", "C"); + dcg.addEdge("E", "D"); + dcg.addEdge("E", "F"); + dcg.addEdge("F", "C"); + + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + assertThat(cycleDetector.getCycles().size(), is(8)); + assertThat(cycleDetector.getSearchCyclesCalls(), is(8L)); + } + + @Test + public void testMaxSearchDepthOption() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); + dcg.addEdge("C", "A"); + dcg.addEdge("B", "A"); + + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCyclesWithMaxSearchDepth(3); + assertThat(cycleDetector.getCycles().size(), is(2)); + + cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCyclesWithMaxSearchDepth(2); + assertThat(cycleDetector.getCycles().size(), is(1)); + } + + @Test + public void testExcludeEdgesFromSearch() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); + dcg.addEdge("C", "A"); + dcg.addEdge("B", "A"); + + Set excludedEdges = new HashSet(); + excludedEdges.add(dcg.getEdge("C", "A")); + excludedEdges.add(dcg.getEdge("B", "A")); + + CycleDetector cycleDetector = new CycleDetector(dcg, excludedEdges); + cycleDetector.detectCycles(); + assertThat(cycleDetector.getCycles().size(), is(1)); + } + + @Test + public void testGetCyclesWithOneCycle() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "E"); + dcg.addEdge("B", "A"); + + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + assertThat(cycleDetector.getCycles().size(), is(1)); + Cycle cycle = cycleDetector.getCycles().iterator().next(); + assertThat(cycle.size(), is(2)); + assertTrue(cycle.contains(new StringEdge("A", "B"))); + assertTrue(cycle.contains(new StringEdge("B", "A"))); + } + + @Test + public void getCyclesInLimitedSetOfVertices() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "A"); + + // C must not be used to find cycles + CycleDetector cycleDetector = new CycleDetector(dcg, Arrays.asList("A", "B")); + cycleDetector.detectCycles(); + assertThat(cycleDetector.getCycles().size(), is(0)); + + // C is used to find cycles + cycleDetector = new CycleDetector(dcg, Arrays.asList("A", "B", "C")); + cycleDetector.detectCycles(); + assertThat(cycleDetector.getCycles().size(), is(1)); + } + + @Test(expected = IllegalStateException.class) + public void testExecutingTwoCycleDetectionsOnSameObject() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "A"); + + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + cycleDetector.detectCycles(); + } + + @Test + public void testDetectCyclesWithUpperLimit() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); + dcg.addEdge("B", "A"); + + CycleDetector cycleDetector = new CycleDetector(dcg); + assertThat(cycleDetector.detectCyclesWithUpperLimit(1).size(), is(1)); + } +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/CycleTest.java b/sonar-graph/src/test/java/org/sonar/graph/CycleTest.java new file mode 100644 index 00000000000..a42366abbab --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/CycleTest.java @@ -0,0 +1,58 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.Arrays; + +import org.junit.Test; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertTrue; + +public class CycleTest { + + private Edge[] AB_Cycle = { new StringEdge("A", "B"), new StringEdge("B", "A") }; + private Edge[] BA_Cycle = { new StringEdge("B", "A"), new StringEdge("A", "B") }; + private Edge[] ABC_Cycle = { new StringEdge("A", "B"), new StringEdge("B", "C"), new StringEdge("C", "A") }; + private Edge[] HIJ_Cycle = { new StringEdge("H", "I"), new StringEdge("I", "J"), new StringEdge("J", "H") }; + private Edge[] ABCD_Cycle = { new StringEdge("A", "B"), new StringEdge("B", "C"), new StringEdge("C", "D"), new StringEdge("D", "A") }; + private Edge[] BCDA_Cycle = { new StringEdge("B", "C"), new StringEdge("C", "D"), new StringEdge("D", "A"), new StringEdge("A", "B"), }; + + @Test + public void testHashCode() { + assertTrue(new Cycle(Arrays.asList(AB_Cycle)).hashCode() == new Cycle(Arrays.asList(BA_Cycle)).hashCode()); + assertTrue(new Cycle(Arrays.asList(BCDA_Cycle)).hashCode() == new Cycle(Arrays.asList(ABCD_Cycle)).hashCode()); + assertFalse(new Cycle(Arrays.asList(AB_Cycle)).hashCode() == new Cycle(Arrays.asList(ABC_Cycle)).hashCode()); + } + + @Test + public void testContains() { + assertTrue(new Cycle(Arrays.asList(ABCD_Cycle)).contains(new StringEdge("B", "C"))); + } + + @Test + public void testEqualsObject() { + assertEquals(new Cycle(Arrays.asList(AB_Cycle)), new Cycle(Arrays.asList(BA_Cycle))); + assertEquals(new Cycle(Arrays.asList(BCDA_Cycle)), new Cycle(Arrays.asList(ABCD_Cycle))); + assertFalse(new Cycle(Arrays.asList(BCDA_Cycle)).equals(new Cycle(Arrays.asList(AB_Cycle)))); + assertFalse(new Cycle(Arrays.asList(ABC_Cycle)).equals(new Cycle(Arrays.asList(HIJ_Cycle)))); + } +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DirectedGraphTest.java b/sonar-graph/src/test/java/org/sonar/graph/DirectedGraphTest.java new file mode 100644 index 00000000000..0abcb4c9af2 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/DirectedGraphTest.java @@ -0,0 +1,106 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.junit.Before; +import org.junit.Test; +import org.sonar.graph.DirectedGraph; +import org.sonar.graph.StringEdge; + +import java.util.Arrays; + +import static org.hamcrest.Matchers.*; +import static org.junit.Assert.*; + +public class DirectedGraphTest { + + private DirectedGraph graph; + + @Before + public void init() { + graph = DirectedGraph.createStringDirectedGraph(); + graph.addEdge("A", "B"); + graph.addEdge("A", "C"); + graph.addEdge("B", "C"); + } + + @Test + public void testGetVertices() { + assertThat(graph.getVertices(), hasItems("A", "B")); + assertThat(graph.getVertices().size(), is(3)); + } + + @Test + public void testGetEdge() { + assertNull(graph.getEdge("A", "T")); + graph.addEdge("A", "T", 5); + assertThat(graph.getEdge("A", "T").getWeight(), is(5)); + } + + @Test(expected = IllegalStateException.class) + public void testAddEdgeThrowsException() { + graph.addEdge("B", "C"); + } + + @Test + public void testAddEdgeWithWeight() { + graph.addEdge("D", "B", 4); + assertThat(graph.getOutgoingEdges("D").iterator().next().getWeight(), is(4)); + } + + @Test + public void testGetOutgoingEdges() { + assertThat(graph.getOutgoingEdges("A"), hasItem(new StringEdge("A", "B"))); + assertThat(graph.getOutgoingEdges("A").size(), is(2)); + assertThat(graph.getOutgoingEdges("B"), hasItem(new StringEdge("B", "C"))); + } + + @Test + public void testGetIncomingEdges() { + assertThat(graph.getIncomingEdges("C"), hasItem(new StringEdge("A", "C"))); + assertThat(graph.getIncomingEdges("A").size(), is(0)); + } + + @Test + public void testGetEdges() { + assertTrue(graph.getEdges(Arrays.asList("A")).containsAll(Arrays.asList(new StringEdge("A", "B"), new StringEdge("A", "C")))); + assertTrue(graph.getEdges(Arrays.asList("A", "B")).containsAll(Arrays.asList(new StringEdge("A", "B"), new StringEdge("A", "C"), new StringEdge("B", "C")))); + } + + @Test + public void testHasEdge() { + assertTrue(graph.hasEdge("A", "B")); + assertFalse(graph.hasEdge("C", "A")); + } + + @Test + public void testAddVertex() { + graph.addVertex("X"); + assertThat(graph.getVertices(), hasItem("X")); + assertThat(graph.getOutgoingEdges("X").size(), is(0)); + } + + @Test + public void testAddVertices() { + String[] vertices = { "X", "Y", "Z" }; + graph.addVertices(Arrays.asList(vertices)); + assertThat(graph.getVertices(), hasItems("X", "Y", "Z")); + } +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmCellTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmCellTest.java new file mode 100644 index 00000000000..12069d2dc88 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/DsmCellTest.java @@ -0,0 +1,45 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.junit.Ignore; +import org.junit.Test; +import org.sonar.graph.DsmCell; +import org.sonar.graph.StringEdge; + +import static org.hamcrest.Matchers.equalTo; +import static org.hamcrest.Matchers.not; +import static org.junit.Assert.assertThat; + +public class DsmCellTest { + + @Test + @Ignore + public void testEquals() { + DsmCell cell1 = new DsmCell(new StringEdge("A", "B", 1), true); + DsmCell cell1bis = new DsmCell(new StringEdge("A", "B", 1), false); + DsmCell cell4 = new DsmCell(new StringEdge("B", "A", 4), true); + + assertThat(cell1, equalTo(cell1)); + assertThat(cell1, equalTo(cell1bis)); + assertThat(cell1, not(equalTo(cell4))); + } + +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmManualSorterTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmManualSorterTest.java new file mode 100644 index 00000000000..617abe383f6 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/DsmManualSorterTest.java @@ -0,0 +1,46 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.junit.Test; + +import static org.junit.Assert.assertEquals; + +public class DsmManualSorterTest { + + @Test + public void testSort() { + DirectedGraph graph = DirectedGraph.createStringDirectedGraph(); + graph.addEdge("A", "B", 2); + graph.addEdge("A", "C", 3); + graph.addEdge("C", "B", 1); + Dsm dsm = new Dsm(graph); + DsmManualSorter.sort(dsm, "B", "A", "C"); + + StringPrintWriter expectedDsm = new StringPrintWriter(); + expectedDsm.println(" | B | A | C |"); + expectedDsm.println("B | | 2 | 1 |"); + expectedDsm.println("A | | | |"); + expectedDsm.println("C | | 3 | |"); + + assertEquals(expectedDsm.toString(), DsmPrinter.print(dsm)); + } + +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmPrinterTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmPrinterTest.java new file mode 100644 index 00000000000..55e8de64de6 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/DsmPrinterTest.java @@ -0,0 +1,64 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import com.google.common.collect.Sets; +import org.junit.Before; +import org.junit.Test; + +import java.util.HashSet; + +import static org.junit.Assert.assertEquals; + +public class DsmPrinterTest { + + private Dsm dsm; + + @Before + public void init() { + DirectedGraph graph = DirectedGraph.createStringDirectedGraph(); + graph.addEdge("A", "B", 3).addEdge("A", "C", 2); + graph.addEdge("C", "B", 4).addEdge("C", "A", 1); + HashSet feedbackEdges = Sets.newHashSet(graph.getEdge("C", "A")); + dsm = new Dsm(graph, feedbackEdges); + DsmManualSorter.sort(dsm, "A", "C", "B"); + } + + @Test + public void testPrintDsm() { + StringPrintWriter expectedResult = new StringPrintWriter(); + expectedResult.println(" | A | C | B |"); + expectedResult.println("A | | 1*| |"); + expectedResult.println("C | 2 | | |"); + expectedResult.println("B | 3 | 4 | |"); + + assertEquals(expectedResult.toString(), DsmPrinter.print(dsm)); + } + + @Test + public void testPrintDsmWithoutColumnHeaders() { + StringPrintWriter expectedResult = new StringPrintWriter(); + expectedResult.println("A | | 1*| |"); + expectedResult.println("C | 2 | | |"); + expectedResult.println("B | 3 | 4 | |"); + + assertEquals(expectedResult.toString(), DsmPrinter.print(dsm, false)); + } +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmScannerTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmScannerTest.java new file mode 100644 index 00000000000..1d9df9239d4 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/DsmScannerTest.java @@ -0,0 +1,55 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.junit.Test; +import org.sonar.graph.Dsm; +import org.sonar.graph.DsmCell; +import org.sonar.graph.DsmScanner; + +import static org.junit.Assert.*; + +public class DsmScannerTest { + + @Test + public void testScanString() { + StringPrintWriter builder = new StringPrintWriter(); + builder.println(" | A | B |"); + builder.println("A | | 1*|"); + builder.println("B | 3 | |"); + Dsm dsm = DsmScanner.scan(builder.toString()); + + assertEquals("A", dsm.getVertex(0).toString()); + assertEquals("B", dsm.getVertex(1).toString()); + + assertEquals(2, dsm.getDimension()); + + DsmCell ba = dsm.getCell(1, 0); + assertEquals(1, ba.getWeight()); + assertTrue(ba.isFeedbackEdge()); + + DsmCell ab = dsm.getCell(0, 1); + assertEquals(3, ab.getWeight()); + assertFalse(ab.isFeedbackEdge()); + + assertEquals(0, dsm.getCell(1, 1).getWeight()); + } + +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmTest.java new file mode 100644 index 00000000000..06fbcba4160 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/DsmTest.java @@ -0,0 +1,77 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.junit.Before; +import org.junit.Test; +import org.sonar.graph.Dsm; +import org.sonar.graph.DsmScanner; + +import static org.hamcrest.Matchers.equalTo; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertThat; + +public class DsmTest { + + private Dsm dsm; + + @Before + public void init() { + StringPrintWriter textDsm = new StringPrintWriter(); + textDsm.println(" | A | B | C | D | E |"); + textDsm.println("A | | 1 | | | |"); + textDsm.println("B | 2 | | | | |"); + textDsm.println("C | 4 | | | | |"); + textDsm.println("D | | 7 | | | 5 |"); + textDsm.println("E | | | | | |"); + dsm = DsmScanner.scan(textDsm.toString()); + } + + @Test + public void testGetVertex() { + assertEquals("A", dsm.getVertex(0)); + assertEquals("B", dsm.getVertex(1)); + assertEquals("C", dsm.getVertex(2)); + assertEquals("D", dsm.getVertex(3)); + assertEquals("E", dsm.getVertex(4)); + } + + @Test + public void testPermute() { + assertEquals(2, dsm.getCell(0, 1).getWeight()); + assertEquals(4, dsm.getCell(0, 2).getWeight()); + + dsm.permute(0, 1); + assertEquals(1, dsm.getCell(0, 1).getWeight()); + assertEquals(0, dsm.getCell(0, 2).getWeight()); + } + + @Test + public void testGetNumberOfOutgoingEdges() { + assertEquals(0, dsm.getNumberOfOutgoingEdges(3, 0, 4)); + assertEquals(2, dsm.getNumberOfOutgoingEdges(0, 0, 4)); + } + + @Test + public void testGetNumberOfIncomingEdges() { + assertThat(dsm.getNumberOfIncomingEdges(0, 0, 4), equalTo(1)); + assertThat(dsm.getNumberOfIncomingEdges(4, 0, 4), equalTo(0)); + } +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/DsmTopologicalSorterTest.java b/sonar-graph/src/test/java/org/sonar/graph/DsmTopologicalSorterTest.java new file mode 100644 index 00000000000..f017d32dc23 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/DsmTopologicalSorterTest.java @@ -0,0 +1,112 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.io.IOException; + +import org.junit.Test; + +import static org.junit.Assert.assertEquals; + +public class DsmTopologicalSorterTest { + + @Test + public void sortAcyclicGraph() { + StringPrintWriter textDsm = new StringPrintWriter(); + textDsm.println(" | A | B | C | D | E |"); + textDsm.println("A | | | | | |"); + textDsm.println("B | 3 | | 4 | | |"); + textDsm.println("C | 1 | | | | |"); + textDsm.println("D | | 2 | | | 1 |"); + textDsm.println("E | | 5 | | | |"); + + Dsm dsm = DsmScanner.scan(textDsm.toString()); + DsmTopologicalSorter.sort(dsm); + + StringPrintWriter expectedTextDsm = new StringPrintWriter(); + expectedTextDsm.println(" | A | C | B | E | D |"); + expectedTextDsm.println("A | | | | | |"); + expectedTextDsm.println("C | 1 | | | | |"); + expectedTextDsm.println("B | 3 | 4 | | | |"); + expectedTextDsm.println("E | | | 5 | | |"); + expectedTextDsm.println("D | | | 2 | 1 | |"); + + Dsm expectedDsm = DsmScanner.scan(expectedTextDsm.toString()); + DsmTopologicalSorter.sort(expectedDsm); + + assertEquals(DsmPrinter.print(dsm), DsmPrinter.print(expectedDsm)); + } + + @Test(expected = IllegalStateException.class) + public void sortCyclicGraph() throws IOException { + StringPrintWriter textDsm = new StringPrintWriter(); + textDsm.println(" | A | B | C | D |"); + textDsm.println("A | | | | |"); + textDsm.println("B | 3 | | 4 | |"); + textDsm.println("C | 1 | 1 | | |"); + textDsm.println("D | | 2 | | |"); + + Dsm dsm = DsmScanner.scan(textDsm.toString()); + DsmTopologicalSorter.sort(dsm); + } + + @Test + public void sortCyclicGraphWithManuallyFlaggedFeedbackEdges() throws IOException { + StringPrintWriter textDsm = new StringPrintWriter(); + textDsm.println(" | A | B | C | D |"); + textDsm.println("A | | | | |"); + textDsm.println("B | 3 | | 4 | |"); + textDsm.println("C | 1 | 1*| | |"); + textDsm.println("D | | 2 | | |"); + + Dsm dsm = DsmScanner.scan(textDsm.toString()); + DsmTopologicalSorter.sort(dsm); + + StringPrintWriter expectedDsm = new StringPrintWriter(); + expectedDsm.println(" | A | C | B | D |"); + expectedDsm.println("A | | | | |"); + expectedDsm.println("C | 1 | | 1*| |"); + expectedDsm.println("B | 3 | 4 | | |"); + expectedDsm.println("D | | | 2 | |"); + + assertEquals(expectedDsm.toString(), DsmPrinter.print(dsm)); + } + + @Test + public void sortCyclicGraphWithFlaggedFeedbackEdges() throws IOException { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B", 3).addEdge("B", "A", 1); + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + + MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); + + Dsm dsm = new Dsm(dcg, solver.getEdges()); + DsmTopologicalSorter.sort(dsm); + + StringPrintWriter expectedDsm = new StringPrintWriter(); + expectedDsm.println(" | A | B |"); + expectedDsm.println("A | | 1*|"); + expectedDsm.println("B | 3 | |"); + + assertEquals(expectedDsm.toString(), DsmPrinter.print(dsm)); + } + +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/FeedbackCycleTest.java b/sonar-graph/src/test/java/org/sonar/graph/FeedbackCycleTest.java new file mode 100644 index 00000000000..b132d6c8e60 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/FeedbackCycleTest.java @@ -0,0 +1,66 @@ +/* +w * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.Arrays; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import org.junit.Test; + +import static org.junit.Assert.assertEquals; + +public class FeedbackCycleTest { + + private Edge[] AB_Edges = { new StringEdge("A", "B"), new StringEdge("B", "A") }; + private Edge[] ABC_Edges = { new StringEdge("A", "B"), new StringEdge("B", "C"), new StringEdge("C", "A") }; + private Edge[] BCDA_Edges = { new StringEdge("B", "C"), new StringEdge("C", "D"), new StringEdge("D", "A"), new StringEdge("A", "B"), }; + private Edge[] EF_Edges = { new StringEdge("E", "F"), new StringEdge("F", "E") }; + private Edge[] GHIJ_Edges = { new StringEdge("G", "H"), new StringEdge("H", "I"), new StringEdge("I", "J"), new StringEdge("J", "G") }; + private Edge[] XYZW_Edges = { new StringEdge("X", "Y"), new StringEdge("Y", "Z"), new StringEdge("Z", "W"), new StringEdge("W", "X") }; + + private Cycle AB_Cycle = new Cycle(Arrays.asList(AB_Edges)); + private Cycle ABC_Cycle = new Cycle(Arrays.asList(ABC_Edges)); + private Cycle BCDA_Cycle = new Cycle(Arrays.asList(BCDA_Edges)); + private Cycle EF_Cycle = new Cycle(Arrays.asList(EF_Edges)); + private Cycle GHIJ_Cycle = new Cycle(Arrays.asList(GHIJ_Edges)); + private Cycle XYZW_Cycle = new Cycle(Arrays.asList(XYZW_Edges)); + + @Test + public void testBuildFeedbackCycles() { + Set cycles = new HashSet(); + cycles.add(AB_Cycle); + cycles.add(ABC_Cycle); + cycles.add(BCDA_Cycle); + cycles.add(EF_Cycle); + cycles.add(GHIJ_Cycle); + cycles.add(XYZW_Cycle); + + List feedbackCycles = FeedbackCycle.buildFeedbackCycles(cycles); + assertEquals(6, feedbackCycles.size()); + assertEquals(EF_Cycle, feedbackCycles.get(0).getCycle()); + assertEquals(AB_Cycle, feedbackCycles.get(1).getCycle()); + assertEquals(GHIJ_Cycle, feedbackCycles.get(2).getCycle()); + assertEquals(XYZW_Cycle, feedbackCycles.get(3).getCycle()); + assertEquals(ABC_Cycle, feedbackCycles.get(4).getCycle()); + assertEquals(BCDA_Cycle, feedbackCycles.get(5).getCycle()); + } +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/FeedbackEdgeTest.java b/sonar-graph/src/test/java/org/sonar/graph/FeedbackEdgeTest.java new file mode 100644 index 00000000000..67ba883635b --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/FeedbackEdgeTest.java @@ -0,0 +1,81 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.junit.Test; + +import static org.hamcrest.MatcherAssert.assertThat; +import static org.hamcrest.Matchers.greaterThan; +import static org.hamcrest.Matchers.is; + +public class FeedbackEdgeTest { + + @Test + public void testWeights() { + FeedbackEdge fEdge = mockFeedbackEdge(14, 2); + assertThat(fEdge.getWeight(), is(14)); + assertThat(fEdge.getRelativeWeight(), is(7.0)); + assertThat(fEdge.getOccurences(), is(2)); + } + + @Test + public void testCompareTo() { + FeedbackEdge feedbackEdge1; + FeedbackEdge feedbackEdge2; + FeedbackEdge feedbackEdge3; + + feedbackEdge1 = mockFeedbackEdge(14, 2); + feedbackEdge2 = mockFeedbackEdge(10, 2); + assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(1)); + + feedbackEdge1 = mockFeedbackEdge(10, 2); + feedbackEdge2 = mockFeedbackEdge(14, 2); + assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(-1)); + + feedbackEdge1 = mockFeedbackEdge(14, 2); + feedbackEdge2 = mockFeedbackEdge(14, 2); + assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(0)); + + feedbackEdge1 = mockFeedbackEdge(14, 2); + feedbackEdge2 = mockFeedbackEdge(13, 2); + assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(1)); + + feedbackEdge1 = mockFeedbackEdge(13, 2); + feedbackEdge2 = mockFeedbackEdge(14, 2); + assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(-1)); + + feedbackEdge1 = mockFeedbackEdge("A", "B", 14, 2); + feedbackEdge2 = mockFeedbackEdge("B", "C", 14, 2); + feedbackEdge3 = mockFeedbackEdge("C", "A", 14, 2); + assertThat(feedbackEdge1.compareTo(feedbackEdge2), is(-1)); + assertThat(feedbackEdge2.compareTo(feedbackEdge3), is(-1)); + assertThat(feedbackEdge3.compareTo(feedbackEdge1), greaterThan(1)); + } + + private FeedbackEdge mockFeedbackEdge(int weight, int occurrences) { + return mockFeedbackEdge("from", "to", weight, occurrences); + } + + private FeedbackEdge mockFeedbackEdge(String from, String to, int weight, int occurrences) { + Edge edge = new StringEdge(from, to, weight); + return new FeedbackEdge(edge, occurrences); + } + +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/IncrementalCyclesAndFESSolverTest.java b/sonar-graph/src/test/java/org/sonar/graph/IncrementalCyclesAndFESSolverTest.java new file mode 100644 index 00000000000..3b11829819c --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/IncrementalCyclesAndFESSolverTest.java @@ -0,0 +1,73 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import org.junit.Test; + +import static org.hamcrest.Matchers.containsString; +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; + +public class IncrementalCyclesAndFESSolverTest { + + @Test + public void testSimpleCase() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); + dcg.addEdge("C", "A"); + dcg.addEdge("B", "A"); + dcg.addEdge("A", "E").addEdge("E", "C"); + dcg.addEdge("E", "D"); + dcg.addEdge("E", "F"); + dcg.addEdge("F", "C"); + + IncrementalCyclesAndFESSolver cyclesAndFESSolver = new IncrementalCyclesAndFESSolver(dcg, dcg.getVertices(), 3, + Integer.MAX_VALUE); + assertThat(cyclesAndFESSolver.getCycles().size(), is(4)); + assertThat(cyclesAndFESSolver.getFeedbackEdgeSet().size(), is(2)); + assertThat(cyclesAndFESSolver.getWeightOfFeedbackEdgeSet(), is(2)); + } + + @Test + public void testWithNoCycleUnderTheThreshold() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); + + IncrementalCyclesAndFESSolver cyclesAndFESSolver = new IncrementalCyclesAndFESSolver(dcg, dcg.getVertices(), 2, + Integer.MAX_VALUE); + assertThat(cyclesAndFESSolver.getCycles().size(), is(1)); + assertThat(cyclesAndFESSolver.getFeedbackEdgeSet().size(), is(1)); + assertThat(cyclesAndFESSolver.getWeightOfFeedbackEdgeSet(), is(1)); + } + + @Test + public void testBothMaxSearchDepthAtFirstAndMaxCyclesToFoundByIteration() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B").addEdge("B", "C").addEdge("C", "D").addEdge("D", "A"); + dcg.addEdge("E", "F").addEdge("F", "G").addEdge("G", "E"); + dcg.addEdge("H", "I").addEdge("I", "H"); + + IncrementalCyclesAndFESSolver cyclesAndFESSolver = new IncrementalCyclesAndFESSolver(dcg, dcg.getVertices(), 2, 1); + assertThat(cyclesAndFESSolver.getCycles().size(), is(3)); + assertThat(cyclesAndFESSolver.getIterations(), is(4)); + cyclesAndFESSolver.getFeedbackEdgeSet(); + } + +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/MinimumFeedbackEdgeSetSolverTest.java b/sonar-graph/src/test/java/org/sonar/graph/MinimumFeedbackEdgeSetSolverTest.java new file mode 100644 index 00000000000..704b8f83402 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/MinimumFeedbackEdgeSetSolverTest.java @@ -0,0 +1,110 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +import java.util.Set; + +import org.junit.Test; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; +import static org.junit.Assert.assertTrue; + +public class MinimumFeedbackEdgeSetSolverTest { + + @Test + public void testGetFeedbackEdgesOnSimpleLoop() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B", 3).addEdge("B", "A", 1); + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + + MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); + Set feedbackEdges = solver.getEdges(); + assertThat(feedbackEdges.size(), is(1)); + } + + @Test + public void testFlagFeedbackEdgesOnSimpleLoop() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B", 3).addEdge("B", "A", 1); + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + + MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); + Set feedbackEdges = solver.getEdges(); + assertTrue(feedbackEdges.contains(dcg.getEdge("B", "A"))); + } + + @Test + public void testGetFeedbackEdgesOnComplexGraph() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B", 7).addEdge("B", "C", 3).addEdge("C", "D", 1).addEdge("D", "A", 3); + dcg.addEdge("B", "A", 12); + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + + MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); + Set feedbackEdges = solver.getEdges(); + assertThat(feedbackEdges.size(), is(1)); + + assertTrue(feedbackEdges.contains(dcg.getEdge("A", "B"))); + } + + @Test + public void testFlagFeedbackEdgesOnUnrelatedCycles() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B", 7).addEdge("B", "C", 3).addEdge("C", "A", 2); + dcg.addEdge("D", "E", 3).addEdge("E", "D", 5); + dcg.addEdge("F", "G", 1).addEdge("G", "H", 4).addEdge("H", "F", 7); + + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + + MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); + Set feedbackEdges = solver.getEdges(); + + assertThat(feedbackEdges.size(), is(3)); + + assertTrue(feedbackEdges.contains(dcg.getEdge("C", "A"))); + assertTrue(feedbackEdges.contains(dcg.getEdge("D", "E"))); + assertTrue(feedbackEdges.contains(dcg.getEdge("F", "G"))); + } + + @Test + public void testApproximateMinimumFeedbackEdges() { + DirectedGraph dcg = DirectedGraph.createStringDirectedGraph(); + dcg.addEdge("A", "B", 5).addEdge("B", "C", 9).addEdge("C", "A", 1); + dcg.addEdge("D", "B", 5).addEdge("C", "D", 7); + dcg.addEdge("F", "B", 5).addEdge("C", "F", 4); + CycleDetector cycleDetector = new CycleDetector(dcg); + cycleDetector.detectCycles(); + + MinimumFeedbackEdgeSetSolver minimumSolver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles()); + assertThat(minimumSolver.getEdges().size(), is(1)); + assertTrue(minimumSolver.getEdges().contains(dcg.getEdge("B", "C"))); + + MinimumFeedbackEdgeSetSolver approximateSolver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles(), 2); + assertThat(approximateSolver.getEdges().size(), is(2)); + assertTrue(approximateSolver.getEdges().contains(dcg.getEdge("B", "C"))); + assertTrue(approximateSolver.getEdges().contains(dcg.getEdge("C", "A"))); + } + +} diff --git a/sonar-graph/src/test/java/org/sonar/graph/StringPrintWriter.java b/sonar-graph/src/test/java/org/sonar/graph/StringPrintWriter.java new file mode 100644 index 00000000000..3beddf48215 --- /dev/null +++ b/sonar-graph/src/test/java/org/sonar/graph/StringPrintWriter.java @@ -0,0 +1,34 @@ +/* + * Sonar, open source software quality management tool. + * Copyright (C) 2009 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * Sonar is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * Sonar is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with Sonar; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 + */ +package org.sonar.graph; + +public class StringPrintWriter { + + private StringBuilder builder = new StringBuilder(); + + public void println(String line) { + builder.append(line + " \r"); + } + + public String toString() { + return builder.toString(); + } + +} -- cgit v1.2.3