This is an automated email from the ASF dual-hosted git repository.
gnodet pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/maven.git
The following commit(s) were added to refs/heads/master by this push:
new e91cee9a2d [MNG-7820] Get rid of plexus-utils DAG class (#1250)
e91cee9a2d is described below
commit e91cee9a2d704f4b5f5429a67ccccd5675e4df6a
Author: Guillaume Nodet <gno...@gmail.com>
AuthorDate: Fri Sep 22 08:02:04 2023 +0200
[MNG-7820] Get rid of plexus-utils DAG class (#1250)
---
maven-core/pom.xml | 2 +
.../org/apache/maven/ProjectCycleException.java | 2 +-
.../org/apache/maven/execution/ReactorManager.java | 2 +-
.../apache/maven/graph/DefaultGraphBuilder.java | 2 +-
.../maven/graph/DefaultProjectDependencyGraph.java | 2 +-
.../CycleDetectedException.java} | 22 +-
.../main/java/org/apache/maven/project/Graph.java | 125 +++++++++++
.../org/apache/maven/project/ProjectSorter.java | 27 +--
.../graph/DefaultProjectDependencyGraphTest.java | 2 +-
.../PluginParameterExpressionEvaluatorTest.java | 2 +-
.../PluginParameterExpressionEvaluatorV4Test.java | 2 +-
.../java/org/apache/maven/project/GraphTest.java | 233 +++++++++++++++++++++
12 files changed, 391 insertions(+), 32 deletions(-)
diff --git a/maven-core/pom.xml b/maven-core/pom.xml
index 50c87aaf77..f62bb41bc3 100644
--- a/maven-core/pom.xml
+++ b/maven-core/pom.xml
@@ -327,6 +327,8 @@ under the License.
<exclude>org.apache.maven.toolchain.DefaultToolchain#DefaultToolchain(org.apache.maven.toolchain.model.ToolchainModel,org.codehaus.plexus.logging.Logger):CONSTRUCTOR_REMOVED</exclude>
<exclude>org.apache.maven.toolchain.DefaultToolchain#DefaultToolchain(org.apache.maven.toolchain.model.ToolchainModel,java.lang.String,org.codehaus.plexus.logging.Logger):CONSTRUCTOR_REMOVED</exclude>
<exclude>org.apache.maven.toolchain.DefaultToolchainManager#logger</exclude>
+ <!-- Remove plexus utils -->
+
<exclude>org.apache.maven.project.ProjectSorter#getDAG():METHOD_REMOVED</exclude>
<!-- classes moved to maven-compat -->
<exclude>org.apache.maven.plugin.PluginManager</exclude>
<exclude>org.apache.maven.repository.ArtifactDoesNotExistException</exclude>
diff --git
a/maven-core/src/main/java/org/apache/maven/ProjectCycleException.java
b/maven-core/src/main/java/org/apache/maven/ProjectCycleException.java
index 0157f2ebd3..ad004a7a76 100644
--- a/maven-core/src/main/java/org/apache/maven/ProjectCycleException.java
+++ b/maven-core/src/main/java/org/apache/maven/ProjectCycleException.java
@@ -18,7 +18,7 @@
*/
package org.apache.maven;
-import org.codehaus.plexus.util.dag.CycleDetectedException;
+import org.apache.maven.project.CycleDetectedException;
/**
*/
diff --git
a/maven-core/src/main/java/org/apache/maven/execution/ReactorManager.java
b/maven-core/src/main/java/org/apache/maven/execution/ReactorManager.java
index e1f21c3066..2ac0643135 100644
--- a/maven-core/src/main/java/org/apache/maven/execution/ReactorManager.java
+++ b/maven-core/src/main/java/org/apache/maven/execution/ReactorManager.java
@@ -25,10 +25,10 @@ import java.util.Map;
import org.apache.maven.artifact.ArtifactUtils;
import org.apache.maven.plugin.descriptor.PluginDescriptor;
+import org.apache.maven.project.CycleDetectedException;
import org.apache.maven.project.DuplicateProjectException;
import org.apache.maven.project.MavenProject;
import org.apache.maven.project.ProjectSorter;
-import org.codehaus.plexus.util.dag.CycleDetectedException;
/**
* ReactorManager - unused
diff --git
a/maven-core/src/main/java/org/apache/maven/graph/DefaultGraphBuilder.java
b/maven-core/src/main/java/org/apache/maven/graph/DefaultGraphBuilder.java
index 6e617eace8..ca2334e894 100644
--- a/maven-core/src/main/java/org/apache/maven/graph/DefaultGraphBuilder.java
+++ b/maven-core/src/main/java/org/apache/maven/graph/DefaultGraphBuilder.java
@@ -43,13 +43,13 @@ import org.apache.maven.execution.ProjectDependencyGraph;
import org.apache.maven.model.Plugin;
import org.apache.maven.model.building.DefaultModelProblem;
import org.apache.maven.model.building.Result;
+import org.apache.maven.project.CycleDetectedException;
import org.apache.maven.project.DuplicateProjectException;
import org.apache.maven.project.MavenProject;
import org.apache.maven.project.ProjectBuildingException;
import org.apache.maven.project.collector.MultiModuleCollectionStrategy;
import org.apache.maven.project.collector.PomlessCollectionStrategy;
import org.apache.maven.project.collector.RequestPomCollectionStrategy;
-import org.codehaus.plexus.util.dag.CycleDetectedException;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
diff --git
a/maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
b/maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
index fed6eb62a6..d49670b438 100644
---
a/maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
+++
b/maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
@@ -31,10 +31,10 @@ import java.util.Set;
import java.util.stream.Collectors;
import org.apache.maven.execution.ProjectDependencyGraph;
+import org.apache.maven.project.CycleDetectedException;
import org.apache.maven.project.DuplicateProjectException;
import org.apache.maven.project.MavenProject;
import org.apache.maven.project.ProjectSorter;
-import org.codehaus.plexus.util.dag.CycleDetectedException;
/**
* Describes the interdependencies between projects in the reactor.
diff --git
a/maven-core/src/main/java/org/apache/maven/ProjectCycleException.java
b/maven-core/src/main/java/org/apache/maven/project/CycleDetectedException.java
similarity index 66%
copy from maven-core/src/main/java/org/apache/maven/ProjectCycleException.java
copy to
maven-core/src/main/java/org/apache/maven/project/CycleDetectedException.java
index 0157f2ebd3..334034228d 100644
--- a/maven-core/src/main/java/org/apache/maven/ProjectCycleException.java
+++
b/maven-core/src/main/java/org/apache/maven/project/CycleDetectedException.java
@@ -16,18 +16,24 @@
* specific language governing permissions and limitations
* under the License.
*/
-package org.apache.maven;
+package org.apache.maven.project;
-import org.codehaus.plexus.util.dag.CycleDetectedException;
+import java.util.List;
-/**
- */
-public class ProjectCycleException extends BuildFailureException {
- public ProjectCycleException(String message) {
+public class CycleDetectedException extends Exception {
+ private final List<String> cycle;
+
+ public CycleDetectedException(String message, List<String> cycle) {
super(message);
+ this.cycle = cycle;
+ }
+
+ public List<String> getCycle() {
+ return cycle;
}
- public ProjectCycleException(String message, CycleDetectedException cause)
{
- super(message, cause);
+ @Override
+ public String getMessage() {
+ return super.getMessage() + " " + String.join(" --> ", cycle);
}
}
diff --git a/maven-core/src/main/java/org/apache/maven/project/Graph.java
b/maven-core/src/main/java/org/apache/maven/project/Graph.java
new file mode 100644
index 0000000000..a0c75cb1b2
--- /dev/null
+++ b/maven-core/src/main/java/org/apache/maven/project/Graph.java
@@ -0,0 +1,125 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.maven.project;
+
+import java.util.*;
+
+class Graph {
+ private enum DfsState {
+ VISITING,
+ VISITED
+ }
+
+ final Map<String, Vertex> vertices = new LinkedHashMap<>();
+
+ public Vertex getVertex(String id) {
+ return vertices.get(id);
+ }
+
+ public Collection<Vertex> getVertices() {
+ return vertices.values();
+ }
+
+ Vertex addVertex(String label) {
+ return vertices.computeIfAbsent(label, Vertex::new);
+ }
+
+ void addEdge(Vertex from, Vertex to) throws CycleDetectedException {
+ from.children.add(to);
+ to.parents.add(from);
+ List<String> cycle = findCycle(to);
+ if (cycle != null) {
+ // remove edge which introduced cycle
+ removeEdge(from, to);
+ throw new CycleDetectedException(
+ "Edge between '" + from.label + "' and '" + to.label + "'
introduces to cycle in the graph", cycle);
+ }
+ }
+
+ void removeEdge(Vertex from, Vertex to) {
+ from.children.remove(to);
+ to.parents.remove(from);
+ }
+
+ List<String> visitAll() {
+ return visitAll(vertices.values(), new HashMap<>(), new ArrayList<>());
+ }
+
+ List<String> findCycle(Vertex vertex) {
+ return visitCycle(Collections.singleton(vertex), new HashMap<>(), new
LinkedList<>());
+ }
+
+ private static List<String> visitAll(
+ Collection<Vertex> children, Map<Vertex, DfsState> stateMap,
List<String> list) {
+ for (Vertex v : children) {
+ DfsState state = stateMap.putIfAbsent(v, DfsState.VISITING);
+ if (state == null) {
+ visitAll(v.children, stateMap, list);
+ stateMap.put(v, DfsState.VISITED);
+ list.add(v.label);
+ }
+ }
+ return list;
+ }
+
+ private static List<String> visitCycle(
+ Collection<Vertex> children, Map<Vertex, DfsState> stateMap,
LinkedList<String> cycle) {
+ for (Vertex v : children) {
+ DfsState state = stateMap.putIfAbsent(v, DfsState.VISITING);
+ if (state == null) {
+ cycle.addLast(v.label);
+ List<String> ret = visitCycle(v.children, stateMap, cycle);
+ if (ret != null) {
+ return ret;
+ }
+ cycle.removeLast();
+ stateMap.put(v, DfsState.VISITED);
+ } else if (state == DfsState.VISITING) {
+ // we are already visiting this vertex, this mean we have a
cycle
+ int pos = cycle.lastIndexOf(v.label);
+ List<String> ret = cycle.subList(pos, cycle.size());
+ ret.add(v.label);
+ return ret;
+ }
+ }
+ return null;
+ }
+
+ static class Vertex {
+ final String label;
+ final List<Vertex> children = new ArrayList<>();
+ final List<Vertex> parents = new ArrayList<>();
+
+ Vertex(String label) {
+ this.label = label;
+ }
+
+ String getLabel() {
+ return label;
+ }
+
+ List<Vertex> getChildren() {
+ return children;
+ }
+
+ List<Vertex> getParents() {
+ return parents;
+ }
+ }
+}
diff --git
a/maven-core/src/main/java/org/apache/maven/project/ProjectSorter.java
b/maven-core/src/main/java/org/apache/maven/project/ProjectSorter.java
index 560c94eae5..32be1fee59 100644
--- a/maven-core/src/main/java/org/apache/maven/project/ProjectSorter.java
+++ b/maven-core/src/main/java/org/apache/maven/project/ProjectSorter.java
@@ -31,16 +31,13 @@ import org.apache.maven.api.model.Extension;
import org.apache.maven.api.model.Parent;
import org.apache.maven.api.model.Plugin;
import org.apache.maven.artifact.ArtifactUtils;
-import org.codehaus.plexus.util.dag.CycleDetectedException;
-import org.codehaus.plexus.util.dag.DAG;
-import org.codehaus.plexus.util.dag.TopologicalSorter;
-import org.codehaus.plexus.util.dag.Vertex;
+import org.apache.maven.project.Graph.Vertex;
/**
* ProjectSorter
*/
public class ProjectSorter {
- private DAG dag;
+ private Graph graph;
private List<MavenProject> sortedProjects;
@@ -70,7 +67,7 @@ public class ProjectSorter {
// in a different lifecycle. Though the compiler-plugin has a valid use
case, although
// that seems to work fine. We need to take versions and lifecycle into
account.
public ProjectSorter(Collection<MavenProject> projects) throws
CycleDetectedException, DuplicateProjectException {
- dag = new DAG();
+ graph = new Graph();
// groupId:artifactId:version -> project
projectMap = new HashMap<>(projects.size() * 2);
@@ -95,10 +92,10 @@ public class ProjectSorter {
Map<String, Vertex> vertices =
vertexMap.computeIfAbsent(projectKey, k -> new HashMap<>(2, 1));
- vertices.put(project.getVersion(), dag.addVertex(projectId));
+ vertices.put(project.getVersion(), graph.addVertex(projectId));
}
- for (Vertex projectVertex : dag.getVertices()) {
+ for (Vertex projectVertex : graph.getVertices()) {
String projectId = projectVertex.getLabel();
MavenProject project = projectMap.get(projectId);
@@ -176,7 +173,7 @@ public class ProjectSorter {
}
}
- List<String> sortedProjectLabels = TopologicalSorter.sort(dag);
+ List<String> sortedProjectLabels = graph.visitAll();
this.sortedProjects = sortedProjectLabels.stream()
.map(id -> projectMap.get(id))
@@ -231,11 +228,11 @@ public class ProjectSorter {
}
if (force && toVertex.getChildren().contains(fromVertex)) {
- dag.removeEdge(toVertex, fromVertex);
+ graph.removeEdge(toVertex, fromVertex);
}
try {
- dag.addEdge(fromVertex, toVertex);
+ graph.addEdge(fromVertex, toVertex);
} catch (CycleDetectedException e) {
if (!safe) {
throw e;
@@ -265,21 +262,17 @@ public class ProjectSorter {
}
public List<String> getDependents(String id) {
- return dag.getParentLabels(id);
+ return
graph.getVertex(id).getParents().stream().map(Vertex::getLabel).collect(Collectors.toList());
}
public List<String> getDependencies(String id) {
- return dag.getChildLabels(id);
+ return
graph.getVertex(id).getChildren().stream().map(Vertex::getLabel).collect(Collectors.toList());
}
public static String getId(MavenProject project) {
return ArtifactUtils.key(project.getGroupId(),
project.getArtifactId(), project.getVersion());
}
- public DAG getDAG() {
- return dag;
- }
-
public Map<String, MavenProject> getProjectMap() {
return projectMap;
}
diff --git
a/maven-core/src/test/java/org/apache/maven/graph/DefaultProjectDependencyGraphTest.java
b/maven-core/src/test/java/org/apache/maven/graph/DefaultProjectDependencyGraphTest.java
index 67a722a53a..9d68de0190 100644
---
a/maven-core/src/test/java/org/apache/maven/graph/DefaultProjectDependencyGraphTest.java
+++
b/maven-core/src/test/java/org/apache/maven/graph/DefaultProjectDependencyGraphTest.java
@@ -23,9 +23,9 @@ import java.util.List;
import org.apache.maven.execution.ProjectDependencyGraph;
import org.apache.maven.model.Dependency;
+import org.apache.maven.project.CycleDetectedException;
import org.apache.maven.project.DuplicateProjectException;
import org.apache.maven.project.MavenProject;
-import org.codehaus.plexus.util.dag.CycleDetectedException;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
diff --git
a/maven-core/src/test/java/org/apache/maven/plugin/PluginParameterExpressionEvaluatorTest.java
b/maven-core/src/test/java/org/apache/maven/plugin/PluginParameterExpressionEvaluatorTest.java
index 3e3ba0a1a6..4090be80bf 100644
---
a/maven-core/src/test/java/org/apache/maven/plugin/PluginParameterExpressionEvaluatorTest.java
+++
b/maven-core/src/test/java/org/apache/maven/plugin/PluginParameterExpressionEvaluatorTest.java
@@ -45,12 +45,12 @@ import org.apache.maven.model.Model;
import org.apache.maven.model.root.RootLocator;
import org.apache.maven.plugin.descriptor.MojoDescriptor;
import org.apache.maven.plugin.descriptor.PluginDescriptor;
+import org.apache.maven.project.CycleDetectedException;
import org.apache.maven.project.DuplicateProjectException;
import org.apache.maven.project.MavenProject;
import org.codehaus.plexus.MutablePlexusContainer;
import org.codehaus.plexus.PlexusContainer;
import
org.codehaus.plexus.component.configurator.expression.ExpressionEvaluator;
-import org.codehaus.plexus.util.dag.CycleDetectedException;
import org.junit.jupiter.api.Test;
import static org.codehaus.plexus.testing.PlexusExtension.getTestFile;
diff --git
a/maven-core/src/test/java/org/apache/maven/plugin/PluginParameterExpressionEvaluatorV4Test.java
b/maven-core/src/test/java/org/apache/maven/plugin/PluginParameterExpressionEvaluatorV4Test.java
index dc03adf8b9..bcb247dade 100644
---
a/maven-core/src/test/java/org/apache/maven/plugin/PluginParameterExpressionEvaluatorV4Test.java
+++
b/maven-core/src/test/java/org/apache/maven/plugin/PluginParameterExpressionEvaluatorV4Test.java
@@ -48,12 +48,12 @@ import org.apache.maven.model.Model;
import org.apache.maven.model.root.RootLocator;
import org.apache.maven.plugin.descriptor.MojoDescriptor;
import org.apache.maven.plugin.descriptor.PluginDescriptor;
+import org.apache.maven.project.CycleDetectedException;
import org.apache.maven.project.DuplicateProjectException;
import org.apache.maven.project.MavenProject;
import org.codehaus.plexus.MutablePlexusContainer;
import org.codehaus.plexus.PlexusContainer;
import
org.codehaus.plexus.component.configurator.expression.ExpressionEvaluator;
-import org.codehaus.plexus.util.dag.CycleDetectedException;
import org.eclipse.aether.DefaultRepositorySystemSession;
import org.eclipse.aether.internal.impl.DefaultRepositorySystem;
import org.eclipse.aether.internal.impl.SimpleLocalRepositoryManagerFactory;
diff --git a/maven-core/src/test/java/org/apache/maven/project/GraphTest.java
b/maven-core/src/test/java/org/apache/maven/project/GraphTest.java
new file mode 100644
index 0000000000..ef2b83278d
--- /dev/null
+++ b/maven-core/src/test/java/org/apache/maven/project/GraphTest.java
@@ -0,0 +1,233 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.maven.project;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import org.apache.maven.project.Graph.Vertex;
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+public class GraphTest {
+
+ @Test
+ public void testGraph() throws CycleDetectedException {
+ Graph graph = new Graph();
+ graph.addVertex("a");
+ assertEquals(1, graph.getVertices().size());
+ assertEquals("a", graph.getVertex("a").getLabel());
+ graph.addVertex("a");
+ assertEquals(1, graph.getVertices().size());
+ assertEquals("a", graph.getVertex("a").getLabel());
+
+ graph.addVertex("b");
+ assertEquals(2, graph.getVertices().size());
+ assertFalse(hasEdge(graph, "a", "b"));
+ assertFalse(hasEdge(graph, "b", "a"));
+
+ Vertex a = graph.getVertex("a");
+ Vertex b = graph.getVertex("b");
+ assertEquals("a", a.getLabel());
+ assertEquals("b", b.getLabel());
+
+ addEdge(graph, "a", "b");
+ assertTrue(a.getChildren().contains(b));
+ assertTrue(b.getParents().contains(a));
+ assertTrue(hasEdge(graph, "a", "b"));
+ assertFalse(hasEdge(graph, "b", "a"));
+
+ addEdge(graph, "c", "d");
+ assertEquals(4, graph.getVertices().size());
+
+ Vertex c = graph.getVertex("c");
+ Vertex d = graph.getVertex("d");
+ assertEquals("a", a.getLabel());
+ assertEquals("b", b.getLabel());
+ assertEquals("c", c.getLabel());
+ assertEquals("d", d.getLabel());
+ assertFalse(hasEdge(graph, "b", "a"));
+ assertFalse(hasEdge(graph, "a", "c"));
+ assertFalse(hasEdge(graph, "a", "d"));
+ assertTrue(hasEdge(graph, "c", "d"));
+ assertFalse(hasEdge(graph, "d", "c"));
+
+ Set<String> labels =
graph.getVertices().stream().map(Vertex::getLabel).collect(Collectors.toSet());
+ assertEquals(4, labels.size());
+ assertTrue(labels.contains("a"));
+ assertTrue(labels.contains("b"));
+ assertTrue(labels.contains("c"));
+ assertTrue(labels.contains("d"));
+
+ addEdge(graph, "a", "d");
+ assertEquals(2, a.getChildren().size());
+ assertTrue(a.getChildren().contains(b));
+ assertTrue(a.getChildren().contains(d));
+ assertEquals(2, d.getParents().size());
+ assertTrue(d.getParents().contains(a));
+ assertTrue(d.getParents().contains(c));
+ }
+
+ @Test
+ public void testCycleDetection() throws Exception {
+ Graph graph1 = new Graph();
+ addEdge(graph1, "a", "b");
+ addEdge(graph1, "b", "c");
+
+ Graph graph2 = new Graph();
+ addEdge(graph2, "a", "b");
+ addEdge(graph2, "b", "c");
+ CycleDetectedException cde =
assertThrows(CycleDetectedException.class, () -> addEdge(graph2, "c", "a"));
+ List<String> cycle = cde.getCycle();
+ assertNotNull(cycle, "Cycle should be not null");
+ assertTrue(cycle.contains("a"), "Cycle contains 'a'");
+ assertTrue(cycle.contains("b"), "Cycle contains 'b'");
+ assertTrue(cycle.contains("c"), "Cycle contains 'c'");
+
+ Graph graph3 = new Graph();
+ addEdge(graph3, "a", "b");
+ addEdge(graph3, "b", "c");
+ addEdge(graph3, "b", "d");
+ addEdge(graph3, "a", "d");
+
+ Graph graph4 = new Graph();
+ addEdge(graph4, "a", "b");
+ addEdge(graph4, "b", "c");
+ addEdge(graph4, "b", "d");
+ addEdge(graph4, "a", "d");
+ cde = assertThrows(CycleDetectedException.class, () -> addEdge(graph4,
"c", "a"));
+ assertEquals(Arrays.asList("a", "b", "c", "a"), cde.getCycle());
+
+ Graph graph5 = new Graph();
+ addEdge(graph5, "a", "b");
+ addEdge(graph5, "b", "c");
+ addEdge(graph5, "b", "f");
+ addEdge(graph5, "f", "g");
+ addEdge(graph5, "g", "h");
+ addEdge(graph5, "c", "d");
+ addEdge(graph5, "d", "e");
+ cde = assertThrows(CycleDetectedException.class, () -> addEdge(graph5,
"e", "b"));
+ assertEquals(Arrays.asList("b", "c", "d", "e", "b"), cde.getCycle());
+ assertTrue(hasEdge(graph5, "a", "b"));
+ assertTrue(hasEdge(graph5, "b", "c"));
+ assertTrue(hasEdge(graph5, "b", "f"));
+ assertTrue(hasEdge(graph5, "f", "g"));
+ assertTrue(hasEdge(graph5, "g", "h"));
+ assertTrue(hasEdge(graph5, "c", "d"));
+ assertTrue(hasEdge(graph5, "d", "e"));
+ assertFalse(hasEdge(graph5, "e", "b"));
+ }
+
+ @Test
+ public void testDfs() throws CycleDetectedException {
+ Graph graph1 = new Graph();
+ addEdge(graph1, "a", "b");
+ addEdge(graph1, "b", "c");
+ List<String> expected1 = new ArrayList<>();
+ expected1.add("c");
+ expected1.add("b");
+ expected1.add("a");
+ List<String> actual1 = graph1.visitAll();
+ assertEquals(expected1, actual1);
+
+ Graph graph2 = new Graph();
+ graph2.addVertex("a");
+ graph2.addVertex("b");
+ graph2.addVertex("c");
+ addEdge(graph2, "b", "a");
+ addEdge(graph2, "c", "b");
+ List<String> expected2 = new ArrayList<>();
+ expected2.add("a");
+ expected2.add("b");
+ expected2.add("c");
+ List<String> actual2 = graph2.visitAll();
+ assertEquals(expected2, actual2);
+
+ Graph graph3 = new Graph();
+ graph3.addVertex("a");
+ graph3.addVertex("b");
+ graph3.addVertex("c");
+ graph3.addVertex("d");
+ graph3.addVertex("e");
+ graph3.addVertex("f");
+ addEdge(graph3, "a", "b");
+ addEdge(graph3, "b", "c");
+ addEdge(graph3, "b", "d");
+ addEdge(graph3, "c", "d");
+ addEdge(graph3, "c", "e");
+ addEdge(graph3, "f", "d");
+ addEdge(graph3, "e", "f");
+ addEdge(graph3, "f", "g");
+ List<String> expected3 = new ArrayList<>();
+ expected3.add("d");
+ expected3.add("g");
+ expected3.add("f");
+ expected3.add("e");
+ expected3.add("c");
+ expected3.add("b");
+ expected3.add("a");
+ List<String> actual3 = graph3.visitAll();
+ assertEquals(expected3, actual3);
+
+ Graph graph4 = new Graph();
+ graph4.addVertex("f");
+ graph4.addVertex("e");
+ graph4.addVertex("d");
+ graph4.addVertex("c");
+ graph4.addVertex("a");
+ graph4.addVertex("b");
+ addEdge(graph4, "a", "b");
+ addEdge(graph4, "b", "c");
+ addEdge(graph4, "b", "d");
+ addEdge(graph4, "c", "d");
+ addEdge(graph4, "c", "e");
+ addEdge(graph4, "f", "d");
+ addEdge(graph4, "e", "f");
+
+ List<String> expected4 = new ArrayList<>();
+ expected4.add("d");
+ expected4.add("f");
+ expected4.add("e");
+ expected4.add("c");
+ expected4.add("b");
+ expected4.add("a");
+ List<String> actual4 = graph4.visitAll();
+ assertEquals(expected4, actual4);
+ }
+
+ static void addEdge(Graph graph, String v1, String v2) throws
CycleDetectedException {
+ Vertex vx1 = graph.addVertex(v1);
+ Vertex vx2 = graph.addVertex(v2);
+ graph.addEdge(vx1, vx2);
+ }
+
+ static boolean hasEdge(Graph graph, String v1, String v2) {
+ Vertex vx1 = graph.getVertex(v1);
+ Vertex vx2 = graph.getVertex(v2);
+ return vx1 != null && vx2 != null && vx1.children.contains(vx2);
+ }
+}
