This is an automated email from the ASF dual-hosted git repository.
martin_s pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/archiva-components.git
The following commit(s) were added to refs/heads/master by this push:
new ba45f3c Better naming and improving traversal
ba45f3c is described below
commit ba45f3c5d2deda3de8399b1853e7fdd07ab8b7ad
Author: Martin Stockhammer <[email protected]>
AuthorDate: Fri Nov 15 17:25:26 2019 +0100
Better naming and improving traversal
---
.../graph/api/{VisitError.java => Category.java} | 20 +-
.../apache/archiva/components/graph/api/Edge.java | 10 +-
.../apache/archiva/components/graph/api/Graph.java | 119 +++-
.../graph/api/{Vertex.java => Node.java} | 21 +-
.../api/{VisitError.java => RelationType.java} | 27 +-
.../{VisitError.java => StandardRelationType.java} | 21 +-
.../components/graph/api/TraversalStatus.java | 18 +-
.../archiva/components/graph/api/VisitError.java | 12 +-
.../archiva/components/graph/base/BaseEdge.java | 37 +-
.../components/graph/base/DirectedGraph.java | 121 +++-
.../archiva/components/graph/base/SimpleGraph.java | 41 +-
.../base/{SimpleVertex.java => SimpleNode.java} | 51 +-
.../archiva/components/graph/util/Traversal.java | 192 ++++--
.../components/graph/util/TraversalFlags.java | 67 ++
.../components/graph/base/BaseEdgeTest.java | 38 +-
.../components/graph/base/SimpleGraphTest.java | 92 ++-
.../{SimpleVertexTest.java => SimpleNodeTest.java} | 22 +-
.../components/graph/util/TraversalTest.java | 717 ++++++++++++---------
18 files changed, 1091 insertions(+), 535 deletions(-)
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/api/VisitError.java
b/graph/src/main/java/org/apache/archiva/components/graph/api/Category.java
similarity index 70%
copy from
graph/src/main/java/org/apache/archiva/components/graph/api/VisitError.java
copy to
graph/src/main/java/org/apache/archiva/components/graph/api/Category.java
index 41f1c09..16fb9cb 100644
---
a/graph/src/main/java/org/apache/archiva/components/graph/api/VisitError.java
+++ b/graph/src/main/java/org/apache/archiva/components/graph/api/Category.java
@@ -18,21 +18,11 @@ package org.apache.archiva.components.graph.api;
* under the License.
*/
-public class VisitError<V extends Vertex<V>> {
-
- private final Throwable exception;
- private final V vertex;
-
- public VisitError(V vertex, Throwable exception) {
- this.exception = exception;
- this.vertex = vertex;
- }
+/**
+ * The category is used to shape the domain by grouping nodes.
+ */
+public interface Category {
- public Throwable getException() {
- return exception;
- }
+ String name();
- public V getVertex() {
- return vertex;
- }
}
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/api/Edge.java
b/graph/src/main/java/org/apache/archiva/components/graph/api/Edge.java
index 5254ec8..032da50 100644
--- a/graph/src/main/java/org/apache/archiva/components/graph/api/Edge.java
+++ b/graph/src/main/java/org/apache/archiva/components/graph/api/Edge.java
@@ -24,7 +24,7 @@ package org.apache.archiva.components.graph.api;
*
* @param <V> The vertex implementation.
*/
-public interface Edge<V extends Vertex<V>> {
+public interface Edge<V extends Node<V>> {
/**
* Returns the identifier of this edge. The id must be unique for given
graph.
@@ -74,7 +74,13 @@ public interface Edge<V extends Vertex<V>> {
*/
double getWeight();
-
+ /**
+ * Returns the RelationType of the edge. If nothing is set, the {@link
StandardRelationType#DEFAULT} should
+ * be returned.
+ *
+ * @return the type of the edge
+ */
+ RelationType getType();
}
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/api/Graph.java
b/graph/src/main/java/org/apache/archiva/components/graph/api/Graph.java
index 13cdb90..af1c347 100644
--- a/graph/src/main/java/org/apache/archiva/components/graph/api/Graph.java
+++ b/graph/src/main/java/org/apache/archiva/components/graph/api/Graph.java
@@ -18,8 +18,7 @@ package org.apache.archiva.components.graph.api;
* under the License.
*/
-import org.apache.archiva.components.graph.base.SimpleVertex;
-
+import java.util.List;
import java.util.Set;
/**
@@ -29,21 +28,123 @@ import java.util.Set;
*
* @param <V>
*/
-public interface Graph<V extends Vertex<V>> {
+public interface Graph<V extends Node<V>> {
+
+ /**
+ * Creates a node with the given label in the graph. The id of the node is
generated
+ * by the graph implementation.
+ * The method returns always a new node instance, even if a node with the
given label
+ * exists already.
+ *
+ * @param label the label of the new node
+ * @return a new node instance with the given label and a generated id
+ */
+ V newNode(String label);
+
+ /**
+ * Adds a new node if the id does not exist yet, otherwise returns the
node with the given id
+ * and the new label set.
+ *
+ * @param id the id of the node
+ * @param label the label of the node
+ * @return a new node instance or the existing node with the given id
+ */
+ V addNode(String id, String label);
+
+ void removeNode(V node);
+
+
+ /**
+ * Creates a new edge instance with the given label. The method returns
always a new edge instance,
+ * even if a edge with the given label exists already.
+ * The type is set to {@link StandardRelationType#DEFAULT}
+ *
+ * @param label the edge label
+ * @param sourceNode the source node
+ * @param destinationNode the destination node
+ * @throws IllegalArgumentException if source or destination is
<code>null</code>
+ * @return a new edge instance
+ */
+ Edge<V> newEdge(String label, V sourceNode, V destinationNode) throws
IllegalArgumentException;
+
+ /**
+ * Creates a new edge instance with the given label. The method returns
always a new edge instance,
+ * even if a edge with the given label exists already.
+ *
+ * @param type the edge type
+ * @param label the edge label
+ * @param sourceNode the source node
+ * @param destinationNode the destination node
+ * @throws IllegalArgumentException if the source or destination node is
<code>null</code>
+ * @return a new edge instance
+ */
+ Edge<V> newEdge(RelationType type, String label, V sourceNode, V
destinationNode) throws IllegalArgumentException;
- V addVertex(String label);
+ /**
+ * Creates a new edge instance with the given id or returns the edge
instance with the given id and
+ * type.
+ * If a edge with the id exists already but with a different type it will
throw a {@link IllegalArgumentException}
+ *
+ * @param type the type of the edge
+ * @param id the id
+ * @param label the edge label
+ * @param sourceNode the source node
+ * @param destinationNode the destination node
+ * @throws IllegalArgumentException if a edge instance with the given id
but a different type exists already. Or if
+ * source or destination node is <code>null</code>
+ * @return
+ */
+ Edge<V> addEdge(RelationType type, String id, String label, V sourceNode,
V destinationNode) throws IllegalArgumentException;
- void removeVertex(V vertex);
+ /**
+ * Creates a new edge instance with the given id or returns the edge
instance with the given id.
+ * If the edge is newly created it will get the type {@link
StandardRelationType#DEFAULT}
+ *
+ * @param id the id
+ * @param label the edge label
+ * @param sourceNode the source node
+ * @param destinationNode the destination node
+ * @throws IllegalArgumentException if source or destination is
<code>null</code>
+ * @return
+ */
+ Edge<V> addEdge(String id, String label, V sourceNode, V destinationNode)
throws IllegalArgumentException;
- Edge<V> addEdge(String label, V inVertex, V outVertex);
+ /**
+ * Removes the edge from the graph and unregisters it from the source and
destination
+ *
+ * @param edge the edge to remove
+ */
+ void removeEdge(Edge<V> edge);
- void removeEdge(Edge<SimpleVertex> edge);
+ /**
+ * Returns the node with the given id
+ *
+ * @param id the node id
+ * @return the found node, or <code>null</code>, if it does not exist
+ */
+ V getNode(String id);
- V getVertex(String id);
+ /**
+ * Finds nodes using a given query. The query syntax depends on the graph
implementation.
+ *
+ * @param query the query to find nodes
+ * @return the found nodes, or a empty list
+ */
+ List<V> findNodes(String query);
+ /**
+ * Returns the edge with the given id.
+ *
+ * @param id the edge id
+ * @return the found edge instance, or <code>null</code>, if it does not
exist
+ */
Edge<V> getEdge(String id);
- Set<V> getVertices();
+ /**
+ * Returns all nodes of the graph
+ * @return
+ */
+ Set<V> getNodes();
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/api/Vertex.java
b/graph/src/main/java/org/apache/archiva/components/graph/api/Node.java
similarity index 81%
rename from
graph/src/main/java/org/apache/archiva/components/graph/api/Vertex.java
rename to graph/src/main/java/org/apache/archiva/components/graph/api/Node.java
index d3937f3..e8a1c1c 100644
--- a/graph/src/main/java/org/apache/archiva/components/graph/api/Vertex.java
+++ b/graph/src/main/java/org/apache/archiva/components/graph/api/Node.java
@@ -26,7 +26,7 @@ import java.util.List;
*
* @param <V> The vertex implementation
*/
-public interface Vertex<V extends Vertex<V>> {
+public interface Node<V extends Node<V>> {
/**
* Returns the identifier of this vertex. The identifier is unique for a
given graph.
@@ -66,5 +66,24 @@ public interface Vertex<V extends Vertex<V>> {
*/
List<Edge<V>> getInEdges();
+ /**
+ * Returns the categories of the vertex.
+ *
+ * @return the list of categories of the vertex
+ */
+ List<Category> getCategories();
+
+ /**
+ * Adds a category to the node
+ * @param category the category to add
+ */
+ void addCategory(Category category);
+
+ /**
+ * Removes a category from the node.
+ *
+ * @param category the category to remove
+ */
+ void removeCategory(Category category);
}
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/api/VisitError.java
b/graph/src/main/java/org/apache/archiva/components/graph/api/RelationType.java
similarity index 69%
copy from
graph/src/main/java/org/apache/archiva/components/graph/api/VisitError.java
copy to
graph/src/main/java/org/apache/archiva/components/graph/api/RelationType.java
index 41f1c09..dc83c01 100644
---
a/graph/src/main/java/org/apache/archiva/components/graph/api/VisitError.java
+++
b/graph/src/main/java/org/apache/archiva/components/graph/api/RelationType.java
@@ -18,21 +18,16 @@ package org.apache.archiva.components.graph.api;
* under the License.
*/
-public class VisitError<V extends Vertex<V>> {
-
- private final Throwable exception;
- private final V vertex;
-
- public VisitError(V vertex, Throwable exception) {
- this.exception = exception;
- this.vertex = vertex;
- }
-
- public Throwable getException() {
- return exception;
- }
+/**
+ * A edge must always have a single relation type.
+ * You can use enums to define the type for a specific domain.
+ *
+ */
+public interface RelationType {
- public V getVertex() {
- return vertex;
- }
+ /**
+ * The type name
+ * @return
+ */
+ String name();
}
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/api/VisitError.java
b/graph/src/main/java/org/apache/archiva/components/graph/api/StandardRelationType.java
similarity index 69%
copy from
graph/src/main/java/org/apache/archiva/components/graph/api/VisitError.java
copy to
graph/src/main/java/org/apache/archiva/components/graph/api/StandardRelationType.java
index 41f1c09..21c45f8 100644
---
a/graph/src/main/java/org/apache/archiva/components/graph/api/VisitError.java
+++
b/graph/src/main/java/org/apache/archiva/components/graph/api/StandardRelationType.java
@@ -18,21 +18,6 @@ package org.apache.archiva.components.graph.api;
* under the License.
*/
-public class VisitError<V extends Vertex<V>> {
-
- private final Throwable exception;
- private final V vertex;
-
- public VisitError(V vertex, Throwable exception) {
- this.exception = exception;
- this.vertex = vertex;
- }
-
- public Throwable getException() {
- return exception;
- }
-
- public V getVertex() {
- return vertex;
- }
-}
+public enum StandardRelationType implements RelationType {
+ DEFAULT,DIRECTED;
+}
\ No newline at end of file
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/api/TraversalStatus.java
b/graph/src/main/java/org/apache/archiva/components/graph/api/TraversalStatus.java
index eb589ce..1675537 100644
---
a/graph/src/main/java/org/apache/archiva/components/graph/api/TraversalStatus.java
+++
b/graph/src/main/java/org/apache/archiva/components/graph/api/TraversalStatus.java
@@ -27,11 +27,11 @@ import java.util.List;
*
* @param <V>
*/
-public class TraversalStatus<V extends Vertex<V>> {
+public class TraversalStatus<V extends Node<V>> {
private int cycles = 0;
private List<VisitError<V>> errorList;
- private List<Vertex<V>> cycleVertices;
+ private List<V> cycleNodes;
public TraversalStatus() {
@@ -68,14 +68,14 @@ public class TraversalStatus<V extends Vertex<V>> {
/**
* Add another cycle to the counter
- * @param vertex
+ * @param node
*/
- public void registerCycle(Vertex<V> vertex) {
+ public void registerCycle(V node) {
cycles++;
- if (cycleVertices==null) {
- cycleVertices = new ArrayList<>();
+ if (cycleNodes ==null) {
+ cycleNodes = new ArrayList<>();
}
- cycleVertices.add(vertex);
+ cycleNodes.add(node);
}
/**
@@ -101,7 +101,7 @@ public class TraversalStatus<V extends Vertex<V>> {
*
* @return the list of vertices where cycles were detected
*/
- public List<Vertex<V>> getCycleVertices() {
- return cycleVertices;
+ public List<V> getCycleNodes() {
+ return cycleNodes;
}
}
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/api/VisitError.java
b/graph/src/main/java/org/apache/archiva/components/graph/api/VisitError.java
index 41f1c09..7e116a7 100644
---
a/graph/src/main/java/org/apache/archiva/components/graph/api/VisitError.java
+++
b/graph/src/main/java/org/apache/archiva/components/graph/api/VisitError.java
@@ -18,21 +18,21 @@ package org.apache.archiva.components.graph.api;
* under the License.
*/
-public class VisitError<V extends Vertex<V>> {
+public class VisitError<V extends Node<V>> {
private final Throwable exception;
- private final V vertex;
+ private final V node;
- public VisitError(V vertex, Throwable exception) {
+ public VisitError(V node, Throwable exception) {
this.exception = exception;
- this.vertex = vertex;
+ this.node = node;
}
public Throwable getException() {
return exception;
}
- public V getVertex() {
- return vertex;
+ public V getNode() {
+ return node;
}
}
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/base/BaseEdge.java
b/graph/src/main/java/org/apache/archiva/components/graph/base/BaseEdge.java
index bdf274e..39cb5cf 100644
--- a/graph/src/main/java/org/apache/archiva/components/graph/base/BaseEdge.java
+++ b/graph/src/main/java/org/apache/archiva/components/graph/base/BaseEdge.java
@@ -18,26 +18,33 @@ package org.apache.archiva.components.graph.base;
* under the License.
*/
-import org.apache.archiva.components.graph.api.Edge;
-import org.apache.archiva.components.graph.api.Graph;
-import org.apache.archiva.components.graph.api.Vertex;
+import org.apache.archiva.components.graph.api.*;
-public class BaseEdge<V extends Vertex<V>> implements Edge<V>,
Comparable<BaseEdge<V>> {
+public class BaseEdge<V extends Node<V>> implements Edge<V>,
Comparable<BaseEdge<V>> {
private final String id;
private String label;
private double weight = 1.0;
- private V sourceVertex;
- private V destinationVertex;
+ private V sourceNode;
+ private V destinationNode;
private final Graph<V> graph;
+ private final RelationType type;
- public BaseEdge(Graph<V> graph, String id, V sourceVertex, V
destinationVertex) {
+ public BaseEdge(Graph<V> graph, String id, V sourceNode, V
destinationNode) {
this.id = id;
this.graph = graph;
- this.sourceVertex = sourceVertex;
- this.destinationVertex = destinationVertex;
+ this.sourceNode = sourceNode;
+ this.destinationNode = destinationNode;
+ this.type = StandardRelationType.DEFAULT;
}
+ public BaseEdge(Graph<V> graph, RelationType type, String id, V
sourceNode, V destinationNode) {
+ this.id = id;
+ this.graph = graph;
+ this.sourceNode = sourceNode;
+ this.destinationNode = destinationNode;
+ this.type = type;
+ }
@Override
public String getId() {
return id;
@@ -63,12 +70,12 @@ public class BaseEdge<V extends Vertex<V>> implements
Edge<V>, Comparable<BaseEd
@Override
public V getSource() {
- return sourceVertex;
+ return sourceNode;
}
@Override
public V getDestination() {
- return destinationVertex;
+ return destinationNode;
}
@Override
@@ -77,13 +84,18 @@ public class BaseEdge<V extends Vertex<V>> implements
Edge<V>, Comparable<BaseEd
}
@Override
+ public RelationType getType() {
+ return type;
+ }
+
+ @Override
public int hashCode() {
return this.id.hashCode();
}
@Override
public String toString() {
- return this.id+"|"+this.label+": "+ sourceVertex.toString() + " -> " +
destinationVertex.toString();
+ return this.id+"("+this.label+")("+ sourceNode.getId()+ " -> " +
destinationNode.getId()+")";
}
@Override
@@ -94,4 +106,5 @@ public class BaseEdge<V extends Vertex<V>> implements
Edge<V>, Comparable<BaseEd
return this.id.compareTo(o.getId());
}
}
+
}
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/base/DirectedGraph.java
b/graph/src/main/java/org/apache/archiva/components/graph/base/DirectedGraph.java
index eb946b1..d53557b 100644
---
a/graph/src/main/java/org/apache/archiva/components/graph/base/DirectedGraph.java
+++
b/graph/src/main/java/org/apache/archiva/components/graph/base/DirectedGraph.java
@@ -18,12 +18,11 @@ package org.apache.archiva.components.graph.base;
* under the License.
*/
-import org.apache.archiva.components.graph.api.Edge;
-import org.apache.archiva.components.graph.api.Graph;
-import org.apache.archiva.components.graph.api.Vertex;
+import org.apache.archiva.components.graph.api.*;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
-import java.util.Set;
-import java.util.TreeMap;
+import java.util.*;
import java.util.stream.Collectors;
@@ -31,51 +30,114 @@ import java.util.stream.Collectors;
* Abstract implementation of a directed graph
* @param <V> The vertex implementation.
*/
-public abstract class DirectedGraph<V extends Vertex<V>> implements Graph<V> {
+public abstract class DirectedGraph<V extends Node<V>> implements Graph<V> {
+ private static final Logger log =
LoggerFactory.getLogger(DirectedGraph.class);
- protected TreeMap<String, V> vertices = new TreeMap<>();
+ protected TreeMap<String, V> nodes = new TreeMap<>();
protected TreeMap<String, Edge<V>> edges = new TreeMap<>();
- public V addVertex(String label) {
- V vtx = createNewVertex();
+ public V newNode(String label) {
+ V vtx = createNewNode();
vtx.setLabel(label);
- this.vertices.put(vtx.getId(), vtx);
+ this.nodes.put(vtx.getId(), vtx);
return vtx;
}
+ @Override
+ public V addNode(String id, String label) {
+ V node;
+ if (nodes.containsKey(id)) {
+ node = nodes.get(id);
+ } else {
+ node = createNewNode(id);
+ this.nodes.put(id, node);
+ }
+ node.setLabel(label);
+ return node;
+ }
+
+
+ protected V createNewNode() {
+ return createNewNode(UUID.randomUUID().toString());
+ }
+
/**
* Subclasses that implement this method must return a new vertex instance
for
* each call. The vertex should not be connected with any edges.
*
* @return A new vertex instance.
*/
- abstract V createNewVertex();
+ abstract V createNewNode(String id);
+
+
+ protected Edge<V> createNewEdge(RelationType type, V sourceVertex, V
destinationVertex) {
+ return createNewEdge(type, UUID.randomUUID().toString(), sourceVertex,
destinationVertex);
+ }
+
/**
* Subclasses that implement this method must return a new instance of the
edge with
* the given source and destination vertices. The vertices must be linked
by the new
* edge.
*
+ * @param type the type of the edge
* @param sourceVertex the source vertex
* @param destinationVertex the destination vertex
* @return A new edge instance.
*/
- abstract Edge<V> createNewEdge(V sourceVertex, V destinationVertex);
+ abstract Edge<V> createNewEdge(RelationType type, String id, V
sourceVertex, V destinationVertex);
+ @Override
+ public Edge<V> newEdge(String label, V sourceNode, V destinationNode) {
+ return newEdge(StandardRelationType.DEFAULT, label, sourceNode,
destinationNode);
+ }
@Override
- public Edge<V> addEdge(String label, V sourceVertex, V destinationVertex) {
- Edge<V> edge = createNewEdge(sourceVertex, destinationVertex);
+ public Edge<V> newEdge(RelationType type, String label, V sourceNode, V
destinationNode) {
+ if (sourceNode==null) {
+ throw new IllegalArgumentException("Source node may not be null");
+ }
+ if (destinationNode==null) {
+ throw new IllegalArgumentException("Destination node may not be
null");
+ }
+ Edge<V> edge = createNewEdge(type, sourceNode, destinationNode);
edge.setLabel(label);
this.edges.put(edge.getId(), edge);
return edge;
}
@Override
- public V getVertex(String id) {
- return vertices.get(id);
+ public Edge<V> addEdge(final RelationType type, final String id, final
String label,
+ final V sourceNode, final V destinationNode) throws
IllegalArgumentException {
+ if (sourceNode==null) {
+ throw new IllegalArgumentException("Source node may not be null");
+ }
+ if (destinationNode==null) {
+ throw new IllegalArgumentException("Destination node may not be
null");
+ }
+ Edge<V> edge;
+ if (this.edges.containsKey(id)) {
+ log.debug("Edge found " + id);
+ edge = this.edges.get(id);
+ } else {
+ edge = createNewEdge(type, id, sourceNode, destinationNode);
+ this.edges.put(id, edge);
+ }
+ edge.setLabel(label);
+ log.debug("Adding edge " + edge.toString());
+ return edge;
+ }
+
+ @Override
+ public Edge<V> addEdge(String id, String label, V sourceNode, V
destinationNode) throws IllegalArgumentException {
+ return addEdge(StandardRelationType.DEFAULT, id, label, sourceNode,
destinationNode);
+ }
+
+ @Override
+ public V getNode(String id) {
+ return nodes.get(id);
}
@Override
@@ -84,8 +146,31 @@ public abstract class DirectedGraph<V extends Vertex<V>>
implements Graph<V> {
}
@Override
- public Set<V> getVertices() {
- return vertices.values().stream().collect(Collectors.toSet());
+ public Set<V> getNodes() {
+ return nodes.values().stream().collect(Collectors.toSet());
+ }
+
+ @Override
+ public List<V> findNodes(String query) {
+ return Collections.EMPTY_LIST;
+ }
+
+ @Override
+ public void removeNode(V node) {
+ List<Edge<V>> rmEdges = new ArrayList<>(node.getInEdges());
+ for (Edge<V> edge : rmEdges) {
+ removeEdge(edge);
+ }
+ rmEdges = new ArrayList<>(node.getOutEdges());
+ for (Edge<V> edge : rmEdges) {
+ removeEdge(edge);
+ }
+ nodes.remove(node.getId());
+ }
+
+ @Override
+ public void removeEdge(Edge<V> edge) {
+ edges.remove(edge.getId());
}
}
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/base/SimpleGraph.java
b/graph/src/main/java/org/apache/archiva/components/graph/base/SimpleGraph.java
index 9c51115..3497b07 100644
---
a/graph/src/main/java/org/apache/archiva/components/graph/base/SimpleGraph.java
+++
b/graph/src/main/java/org/apache/archiva/components/graph/base/SimpleGraph.java
@@ -19,8 +19,9 @@ package org.apache.archiva.components.graph.base;
*/
import org.apache.archiva.components.graph.api.Edge;
+import org.apache.archiva.components.graph.api.RelationType;
-import java.util.UUID;
+import java.util.List;
/**
* Simple directed graph implementation that uses UUIDs as unique identifiers
for
@@ -28,39 +29,39 @@ import java.util.UUID;
*
*
*/
-public class SimpleGraph extends DirectedGraph<SimpleVertex> {
+public class SimpleGraph extends DirectedGraph<SimpleNode> {
+
@Override
- SimpleVertex createNewVertex() {
- return new SimpleVertex(this, UUID.randomUUID().toString());
+ SimpleNode createNewNode(String id) {
+ return new SimpleNode(this, id);
}
+
+
@Override
- Edge<SimpleVertex> createNewEdge(SimpleVertex sourceVertex, SimpleVertex
destinationVertex) {
- BaseEdge edge = new BaseEdge<>(this, UUID.randomUUID().toString(),
sourceVertex, destinationVertex);
- addEdgeToVertex(sourceVertex, edge);
- addEdgeToVertex(destinationVertex, edge);
+ Edge<SimpleNode> createNewEdge(RelationType type, String id, SimpleNode
sourceVertex, SimpleNode destinationVertex) {
+ BaseEdge edge = new BaseEdge<>(this, id, sourceVertex,
destinationVertex);
+ addEdgeToNode(sourceVertex, edge);
+ addEdgeToNode(destinationVertex, edge);
return edge;
}
- private void addEdgeToVertex(SimpleVertex vertex, Edge<SimpleVertex> edge)
{
+ private void addEdgeToNode(SimpleNode vertex, Edge<SimpleNode> edge) {
vertex.addEdge(edge);
}
+
@Override
- public void removeEdge(Edge<SimpleVertex> edge) {
- edges.remove(edge);
- edge.getSource().removeEdge(edge);
- edge.getDestination().removeEdge(edge);
+ public List<SimpleNode> findNodes(String query) {
+ return null;
}
+
@Override
- public void removeVertex(SimpleVertex vertex) {
- for (Edge<SimpleVertex> edge : vertex.getInEdges()) {
- removeEdge(edge);
- }
- for (Edge<SimpleVertex> edge : vertex.getOutEdges()) {
- removeEdge(edge);
- }
+ public void removeEdge(Edge<SimpleNode> edge) {
+ super.removeEdge(edge);
+ edge.getSource().removeEdge(edge);
+ edge.getDestination().removeEdge(edge);
}
}
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/base/SimpleVertex.java
b/graph/src/main/java/org/apache/archiva/components/graph/base/SimpleNode.java
similarity index 63%
rename from
graph/src/main/java/org/apache/archiva/components/graph/base/SimpleVertex.java
rename to
graph/src/main/java/org/apache/archiva/components/graph/base/SimpleNode.java
index 4cd3aa2..9f1dfd0 100644
---
a/graph/src/main/java/org/apache/archiva/components/graph/base/SimpleVertex.java
+++
b/graph/src/main/java/org/apache/archiva/components/graph/base/SimpleNode.java
@@ -18,9 +18,10 @@ package org.apache.archiva.components.graph.base;
* under the License.
*/
+import org.apache.archiva.components.graph.api.Category;
import org.apache.archiva.components.graph.api.Edge;
import org.apache.archiva.components.graph.api.Graph;
-import org.apache.archiva.components.graph.api.Vertex;
+import org.apache.archiva.components.graph.api.Node;
import java.util.ArrayList;
import java.util.List;
@@ -29,16 +30,17 @@ import java.util.List;
* Simple vertex implementation. The hash value is based on the id.
* Comparation is by label, if exists, otherwise by id.
*/
-public class SimpleVertex implements Vertex<SimpleVertex>,
Comparable<SimpleVertex>
+public class SimpleNode implements Node<SimpleNode>, Comparable<SimpleNode>
{
private final String id;
private String label;
- private final Graph<SimpleVertex> graph;
- private List<Edge<SimpleVertex>> outEdges = new ArrayList<>();
- private List<Edge<SimpleVertex>> inEdges = new ArrayList<>();
+ private final Graph<SimpleNode> graph;
+ private List<Edge<SimpleNode>> outEdges = new ArrayList<>();
+ private List<Edge<SimpleNode>> inEdges = new ArrayList<>();
+ private List<Category> categories;
- SimpleVertex(Graph<SimpleVertex> graph, String id) {
+ SimpleNode(Graph<SimpleNode> graph, String id) {
this.id = id;
this.graph = graph;
}
@@ -59,21 +61,21 @@ public class SimpleVertex implements Vertex<SimpleVertex>,
Comparable<SimpleVert
}
@Override
- public Graph<SimpleVertex> getGraph() {
+ public Graph<SimpleNode> getGraph() {
return graph;
}
@Override
- public List<Edge<SimpleVertex>> getOutEdges() {
+ public List<Edge<SimpleNode>> getOutEdges() {
return outEdges;
}
@Override
- public List<Edge<SimpleVertex>> getInEdges() {
+ public List<Edge<SimpleNode>> getInEdges() {
return inEdges;
}
- protected void addEdge(Edge<SimpleVertex> edge) {
+ protected void addEdge(Edge<SimpleNode> edge) {
if (edge.getSource() == this) {
outEdges.add(edge);
} else if (edge.getDestination() == this) {
@@ -90,10 +92,10 @@ public class SimpleVertex implements Vertex<SimpleVertex>,
Comparable<SimpleVert
@Override
public String toString() {
- return this.id+"|"+this.label;
+ return this.id+"("+this.label+")";
}
- public void removeEdge(Edge<SimpleVertex> edge) {
+ public void removeEdge(Edge<SimpleNode> edge) {
if (edge.getDestination()==this) {
inEdges.remove(edge);
} else if (edge.getSource()==this) {
@@ -102,11 +104,34 @@ public class SimpleVertex implements
Vertex<SimpleVertex>, Comparable<SimpleVert
}
@Override
- public int compareTo(SimpleVertex o) {
+ public int compareTo(SimpleNode o) {
if (label!=null && o.getLabel()!=null) {
return this.label.compareTo(o.getLabel());
} else {
return this.id.compareTo(o.getId());
}
}
+
+ public void addCategory(Category category) {
+ if (this.categories == null) {
+ this.categories = new ArrayList<>();
+ }
+ if (!this.categories.contains(category)) {
+ this.categories.add(category);
+ }
+ }
+
+ public void removeCategory(Category category) {
+ if (this.categories != null) {
+ this.categories.remove(category);
+ }
+ }
+
+ @Override
+ public List<Category> getCategories() {
+ if (this.categories ==null) {
+ this.categories = new ArrayList<>();
+ }
+ return categories;
+ }
}
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/util/Traversal.java
b/graph/src/main/java/org/apache/archiva/components/graph/util/Traversal.java
index e80f26a..e55f7f9 100644
---
a/graph/src/main/java/org/apache/archiva/components/graph/util/Traversal.java
+++
b/graph/src/main/java/org/apache/archiva/components/graph/util/Traversal.java
@@ -19,14 +19,13 @@ package org.apache.archiva.components.graph.util;
*/
import org.apache.archiva.components.graph.api.Edge;
+import org.apache.archiva.components.graph.api.Node;
import org.apache.archiva.components.graph.api.TraversalStatus;
-import org.apache.archiva.components.graph.api.Vertex;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.*;
-import java.util.function.Consumer;
-import java.util.function.Function;
+import java.util.function.BiFunction;
/**
* Utility class for graph traversal.
@@ -46,84 +45,96 @@ public class Traversal {
* @param start the start node
* @param consumer The consumer function. The function must return
<code>true</code>, if the traversal should
* continue, otherwise <code>false</code>
- * @param directed If true, only outgoing edges are used to
navigate to neighbours, otherwise incoming and outgoing
- * edges are used.
- * @param continueOnError If true, the traversal continues, even if the
consumer function threw an error
+ * @param flags Sets some flags for traversal behaviour
* @param <V>
* @return The traversal status
*/
- @SuppressWarnings("Duplicates")
- public static <V extends Vertex<V>> TraversalStatus<V> depthFirst(final V
start, final Function<V, Boolean> consumer,
- final
boolean directed, final boolean continueOnError) {
+ public static <V extends Node<V>> TraversalStatus<V> depthFirst(final V
start, final BiFunction<V, TraversalStatus<V>, Boolean> consumer,
+ final
BiFunction<V, TraversalStatus<V>, Boolean> afterChildConsumer,
+ final
TraversalFlags flags) {
TraversalStatus<V> status = new TraversalStatus<>();
Set<V> visited = new LinkedHashSet<>();
Stack<V> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
- V vertex = stack.pop();
- if (!visited.contains(vertex)) {
+ V node = stack.peek();
+ if (!visited.contains(node)) {
Boolean continueTraversal = Boolean.TRUE;
try {
- continueTraversal = consumer.apply(vertex);
+ continueTraversal = consumer.apply(node, status);
} catch (Throwable e) {
- log.debug("Error during visit. Vertex: {}, Message: {}",
vertex, e.getMessage());
- status.addError(vertex, e);
- if (!continueOnError) {
+ log.debug("Error during visit. Node: {}, Message: {}",
node, e.getMessage());
+ status.addError(node, e);
+ if (!flags.isContinueOnError()) {
break;
}
}
- visited.add(vertex);
- log.debug("Visited: " + vertex);
+ visited.add(node);
+ log.debug("Visited: " + node);
if (!continueTraversal) {
+ log.debug("Aborting from consumer on node {}",
node.getId());
break;
}
// We traverse using the order of the edges. This is a stack,
so the elements that
// should be visited first are pushed last on the stack.
- final List<Edge<V>> outEdges = vertex.getOutEdges();
- final int outEdgeMaxIdx = vertex.getOutEdges().size() - 1;
+ final List<Edge<V>> outEdges = node.getOutEdges();
+ final int outEdgeMaxIdx = node.getOutEdges().size() - 1;
for (int i = outEdgeMaxIdx; i >= 0; i--) {
try {
Edge<V> v = outEdges.get(i);
- log.debug("Directed destination: " +
v.getDestination());
- stack.push(v.getDestination());
+ V dest = v.getDestination();
+ log.debug("Directed destination: {}", dest.getId());
+ if (!visited.contains(dest)) {
+ log.debug("Adding to stack {}", dest.getId());
+ stack.push(dest);
+ } else if (stack.contains(dest)) {
+ log.debug("Cycle detected {}", dest.getId());
+ status.registerCycle(dest);
+ }
} catch (IndexOutOfBoundsException e) {
- log.warn("Modification of graph during traversal of
output edges: " + vertex + " Index: " + i);
+ log.warn("Modification of graph during traversal of
output edges: " + node + " Index: " + i);
}
}
- if (!directed) {
- final List<Edge<V>> inEdges = vertex.getInEdges();
- final int inEdgeMaxIdx = vertex.getOutEdges().size() - 1;
+ if (!flags.isDirected()) {
+ final List<Edge<V>> inEdges = node.getInEdges();
+ final int inEdgeMaxIdx = node.getOutEdges().size() - 1;
for (int i = inEdgeMaxIdx; i >= 0; i--) {
try {
Edge<V> v = inEdges.get(i);
+ V source = v.getSource();
log.debug("Undirected source: " + v.getSource());
- stack.push(v.getSource());
+ if (!visited.contains(source)) {
+ stack.push(source);
+ } else if (stack.contains(source)) {
+ status.registerCycle(source);
+ }
} catch (IndexOutOfBoundsException e) {
- log.warn("Modification of graph during traversal
of input edges: " + vertex + " Index: " + i);
+ log.warn("Modification of graph during traversal
of input edges: " + node + " Index: " + i);
}
}
}
} else {
- status.registerCycle(vertex);
+ node = stack.pop();
+ if (!afterChildConsumer.apply(node, status)) {
+ log.debug("Aborting from after child consumer on node {}",
node.getId());
+ break;
+ }
}
}
return status;
}
- /**
- * Same as {@link #depthFirst(Vertex, Function, boolean, boolean)} but
sets the <code>continueOnError</code> parameter to <code>true</code>.
- */
- public static <V extends Vertex<V>> TraversalStatus<V> depthFirst(V start,
Function<V, Boolean> consumer,
- boolean
directed) {
- return depthFirst(start, consumer, directed, true);
+ public static <V extends Node<V>> TraversalStatus<V> depthFirst(final V
start, final BiFunction<V, TraversalStatus<V>, Boolean> consumer,
+ final
TraversalFlags flags) {
+ return depthFirst(start, consumer, (v, s) -> true, flags);
}
/**
- * Same as {@link #depthFirst(Vertex, Function, boolean, boolean)} but
sets the <code>continueOnError</code>
+ * Same as {@link #depthFirst(Node, BiFunction, TraversalFlags)} but sets
the <code>continueOnError</code>
* parameter to <code>true</code> and <code>directed</code> parameter to
<code>true</code>.
*/
- public static <V extends Vertex<V>> TraversalStatus<V> depthFirst(V start,
Function<V, Boolean> consumer) {
- return depthFirst(start, consumer, true, true);
+ public static <V extends Node<V>> TraversalStatus<V> depthFirst(V start,
BiFunction<V, TraversalStatus<V>, Boolean> consumer) {
+ return depthFirst(start, consumer, new TraversalFlags());
}
/**
@@ -133,70 +144,123 @@ public class Traversal {
* traversal should continue.
* If the directed flag is set to true, only outgoing edges are used for
traversal from one one
* to the other, otherwise, incoming edges are used too.
+ * This breadth first algorithm is not able to detect cycles, in a
directed graph. Only in undirected.
*
* @param start the start node
* @param consumer The consumer function. The function must return
<code>true</code>, if the traversal should
* continue, otherwise <code>false</code>
- * @param directed If true, only outgoing edges are used to
navigate to neighbours, otherwise incoming and outgoing
- * edges are used.
- * @param continueOnError If true, the traversal continues, even if the
consumer function threw an error
+ * @param flags flags that control traversal behaviour
* @param <V>
* @return The traversal status
*/
@SuppressWarnings("Duplicates")
- public static <V extends Vertex<V>> TraversalStatus<V> breadthFirst(final
V start, final Function<V, Boolean> consumer,
- final
boolean directed, final boolean continueOnError) {
+ public static <V extends Node<V>> TraversalStatus<V> breadthFirst(final V
start,
+ final
BiFunction<V, TraversalStatus<V>, Boolean> consumer,
+ final
TraversalFlags flags) {
final TraversalStatus<V> status = new TraversalStatus<>();
final Set<V> visited = new LinkedHashSet<>();
final Queue<V> queue = new LinkedList<>();
queue.add(start);
while (!queue.isEmpty()) {
- V vertex = queue.poll();
- if (!visited.contains(vertex)) {
+ V node = queue.poll();
+ if (!visited.contains(node)) {
Boolean continueTraversal = Boolean.TRUE;
try {
- continueTraversal = consumer.apply(vertex);
+ continueTraversal = consumer.apply(node, status);
} catch (Throwable e) {
- log.debug("Error during visit. Vertex: {}, Message: {}",
vertex, e.getMessage());
- status.addError(vertex, e);
- if (!continueOnError) {
+ log.debug("Error during visit. Node: {}, Message: {}",
node, e.getMessage());
+ status.addError(node, e);
+ if (!flags.isContinueOnError()) {
break;
}
}
- visited.add(vertex);
- log.debug("Visited: " + vertex);
+ visited.add(node);
+ log.debug("Visited: " + node);
if (!continueTraversal) {
break;
}
- for (Edge<V> v : vertex.getOutEdges()) {
+ for (Edge<V> v : node.getOutEdges()) {
queue.add(v.getDestination());
}
- if (!directed) {
- for (Edge<V> v : vertex.getInEdges()) {
- queue.add(v.getSource());
+ if (!flags.isDirected()) {
+ for (Edge<V> v : node.getInEdges()) {
+ queue.add(v.getSource());
}
}
- } else {
- status.registerCycle(vertex);
+ } else if (!flags.isDirected()) {
+ status.registerCycle(node);
}
}
return status;
}
/**
- * Same as {@link #breadthFirst(Vertex, Function, boolean, boolean)} but
sets <code>continueOnError</code> to <code>true</code>.
+ * Same as {@link #breadthFirst(Node, BiFunction, TraversalFlags)} but
sets <code>continueOnError</code> to <code>true</code>
+ * and <code>directed</code> to <code>true</code>.
*/
- public static <V extends Vertex<V>> TraversalStatus<V> breadthFirst(final
V start, final Function<V, Boolean> consumer,
- final
boolean directed) {
- return breadthFirst(start, consumer, directed, true);
+ public static <V extends Node<V>> TraversalStatus<V> breadthFirst(final V
start, final BiFunction<V, TraversalStatus<V>, Boolean> consumer) {
+ return breadthFirst(start, consumer, new TraversalFlags());
}
/**
- * Same as {@link #breadthFirst(Vertex, Function, boolean, boolean)} but
sets <code>continueOnError</code> to <code>true</code>
- * and <code>directed</code> to <code>true</code>.
+ * Traverses the graph, stops and returns <code>true</code> if it founds a
cycle, otherwise returns
+ * <code>false</code>
+ *
+ * @param startNode the start node where the traversal starts
+ * @param <V>
+ * @return <code>true</code>, if a cycle was found, otherwise
<code>false</code>
+ */
+ public static <V extends Node<V>> boolean hasCycle(final V startNode) {
+ TraversalStatus<V> status = depthFirst(startNode, (n, s) ->
!s.hasCycles());
+ return status.hasCycles();
+ }
+
+ /**
+ * Traverses the graph and if a cycle was detected returns the node where
the cycle was detected.
+ * Otherwise returns <code>null</code>
+ * @param startNode the start node, where the traversal starts
+ * @param <V>
+ * @return the node, where the cycle was detected, otherwise
<code>null</code>
+ */
+ public static <V extends Node<V>> V findFirstCycleNode(final V startNode) {
+ TraversalStatus<V> status = depthFirst(startNode, (n, s) ->
!s.hasCycles());
+ if (status.hasCycles()) {
+ return status.getCycleNodes().get(0);
+ } else {
+ return null;
+ }
+ }
+
+ /**
+ * Traverses the graph and if a cycle was detected returns the node where
the cycle was detected.
+ * Otherwise returns <code>null</code>
+ * @param startNode the start node, where the traversal starts
+ * @param <V>
+ * @return the node, where the cycle was detected, otherwise
<code>null</code>
+ */
+ public static <V extends Node<V>> List<V> findAllCycleNodes(final V
startNode) {
+ TraversalStatus<V> status = depthFirst(startNode, (n, s) -> true);
+ if (status.hasCycles()) {
+ return status.getCycleNodes();
+ } else {
+ return Collections.emptyList();
+ }
+ }
+
+ /**
+ * Sorts the graph starting at the <code>startNode</code> in topological
order. That means
+ * for a given path the deepest nodes are before their ancestors.
+ * For nodes of the same level the order is the order of the edges on the
source node.
+ *
+ * @param startNode the node where the traversal will start
+ * @param <V>
+ * @return A list of sorted nodes
*/
- public static <V extends Vertex<V>> TraversalStatus<V> breadthFirst(final
V start, final Function<V, Boolean> consumer) {
- return breadthFirst(start, consumer, true, true);
+ public static <V extends Node<V>> List<V> topologialSort(final V
startNode) {
+ List<V> nodeList = new ArrayList<>();
+ TraversalStatus<V> status = depthFirst(startNode, (n, s) -> true,
+ (n,s)->{nodeList.add(n); return true;}, new TraversalFlags());
+ return nodeList;
}
}
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/util/TraversalFlags.java
b/graph/src/main/java/org/apache/archiva/components/graph/util/TraversalFlags.java
new file mode 100644
index 0000000..1019a54
--- /dev/null
+++
b/graph/src/main/java/org/apache/archiva/components/graph/util/TraversalFlags.java
@@ -0,0 +1,67 @@
+package org.apache.archiva.components.graph.util;
+/*
+ * 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.
+ */
+
+/**
+ * Flags that control traversal behaviour
+ */
+public class TraversalFlags {
+ private final boolean directed;
+ private final boolean continueOnError;
+
+ public TraversalFlags() {
+ this.directed = true;
+ this.continueOnError = true;
+ }
+
+ public TraversalFlags(boolean directed, boolean continueOnError) {
+ this.directed = directed;
+ this.continueOnError = continueOnError;
+ }
+
+ public TraversalFlags(boolean directed, boolean continueOnError, boolean
consumeParentAfterChild) {
+ this.directed = directed;
+ this.continueOnError = continueOnError;
+ }
+
+ /**
+ * If the <code>directed=true</code>, traversal will only use source to
destination links not reverse.
+ * If the value is <code>false</code> traversal will use every edge from a
given node regardless of the
+ * direction.
+ * Default is <code>true</code>
+ *
+ * @return true, if the graph is directed otherwise false
+ */
+ public boolean isDirected() {
+ return directed;
+ }
+
+ /**
+ * If this flag is <code>true</code>, the traversal will continue, if the
consumer function
+ * throws an error. Otherwise the traversal will be stopped.
+ * Default is <code>true</code>
+ *
+ * @return <code>true</code>, if traversal should continue on error,
otherwise <code>false</code>
+ */
+ public boolean isContinueOnError() {
+ return continueOnError;
+ }
+
+
+}
diff --git
a/graph/src/test/java/org/apache/archiva/components/graph/base/BaseEdgeTest.java
b/graph/src/test/java/org/apache/archiva/components/graph/base/BaseEdgeTest.java
index 22f2e3d..02e3f47 100644
---
a/graph/src/test/java/org/apache/archiva/components/graph/base/BaseEdgeTest.java
+++
b/graph/src/test/java/org/apache/archiva/components/graph/base/BaseEdgeTest.java
@@ -26,14 +26,14 @@ import static org.junit.jupiter.api.Assertions.*;
class BaseEdgeTest {
- private Graph<SimpleVertex> graph = new SimpleGraph();
+ private Graph<SimpleNode> graph = new SimpleGraph();
@Test
void getId() {
- SimpleVertex vtx1 = new SimpleVertex(graph, "vtx1");
- SimpleVertex vtx2 = new SimpleVertex(graph, "vtx2");
+ SimpleNode vtx1 = new SimpleNode(graph, "vtx1");
+ SimpleNode vtx2 = new SimpleNode(graph, "vtx2");
- BaseEdge<SimpleVertex> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
+ BaseEdge<SimpleNode> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
assertNotNull(edge.getId());
assertEquals("edge01", edge.getId());
@@ -43,10 +43,10 @@ class BaseEdgeTest {
@Test
void getLabel() {
- SimpleVertex vtx1 = new SimpleVertex(graph, "vtx1");
- SimpleVertex vtx2 = new SimpleVertex(graph, "vtx2");
+ SimpleNode vtx1 = new SimpleNode(graph, "vtx1");
+ SimpleNode vtx2 = new SimpleNode(graph, "vtx2");
- BaseEdge<SimpleVertex> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
+ BaseEdge<SimpleNode> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
assertNull(edge.getLabel());
@@ -61,10 +61,10 @@ class BaseEdgeTest {
@Test
void setWeight() {
- SimpleVertex vtx1 = new SimpleVertex(graph, "vtx1");
- SimpleVertex vtx2 = new SimpleVertex(graph, "vtx2");
+ SimpleNode vtx1 = new SimpleNode(graph, "vtx1");
+ SimpleNode vtx2 = new SimpleNode(graph, "vtx2");
- BaseEdge<SimpleVertex> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
+ BaseEdge<SimpleNode> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
assertEquals(1.0, edge.getWeight());
@@ -77,30 +77,30 @@ class BaseEdgeTest {
@Test
void getGraph() {
- SimpleVertex vtx1 = new SimpleVertex(graph, "vtx1");
- SimpleVertex vtx2 = new SimpleVertex(graph, "vtx2");
+ SimpleNode vtx1 = new SimpleNode(graph, "vtx1");
+ SimpleNode vtx2 = new SimpleNode(graph, "vtx2");
- BaseEdge<SimpleVertex> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
+ BaseEdge<SimpleNode> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
assertNotNull(edge.getGraph());
assertTrue(edge.getGraph() == graph);
}
@Test
void getInVertex() {
- SimpleVertex vtx1 = new SimpleVertex(graph, "vtx1");
- SimpleVertex vtx2 = new SimpleVertex(graph, "vtx2");
+ SimpleNode vtx1 = new SimpleNode(graph, "vtx1");
+ SimpleNode vtx2 = new SimpleNode(graph, "vtx2");
- BaseEdge<SimpleVertex> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
+ BaseEdge<SimpleNode> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
assertEquals(vtx1, edge.getSource());
}
@Test
void getOutVertex() {
- SimpleVertex vtx1 = new SimpleVertex(graph, "vtx1");
- SimpleVertex vtx2 = new SimpleVertex(graph, "vtx2");
+ SimpleNode vtx1 = new SimpleNode(graph, "vtx1");
+ SimpleNode vtx2 = new SimpleNode(graph, "vtx2");
- BaseEdge<SimpleVertex> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
+ BaseEdge<SimpleNode> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
assertEquals(vtx2, edge.getDestination());
}
diff --git
a/graph/src/test/java/org/apache/archiva/components/graph/base/SimpleGraphTest.java
b/graph/src/test/java/org/apache/archiva/components/graph/base/SimpleGraphTest.java
index 6455528..859a002 100644
---
a/graph/src/test/java/org/apache/archiva/components/graph/base/SimpleGraphTest.java
+++
b/graph/src/test/java/org/apache/archiva/components/graph/base/SimpleGraphTest.java
@@ -19,6 +19,7 @@ package org.apache.archiva.components.graph.base;
*/
import org.apache.archiva.components.graph.api.Edge;
+import org.apache.archiva.components.graph.api.StandardRelationType;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
@@ -26,9 +27,9 @@ import static org.junit.jupiter.api.Assertions.*;
class SimpleGraphTest {
@Test
- void createNewVertex() {
+ void createNewNode() {
SimpleGraph graph = new SimpleGraph();
- SimpleVertex vtx = graph.createNewVertex();
+ SimpleNode vtx = graph.createNewNode();
assertNotNull(vtx);
assertNotNull(vtx.getId());
assertNotNull(java.util.UUID.fromString(vtx.getId()));
@@ -37,9 +38,9 @@ class SimpleGraphTest {
@Test
void createNewEdge() {
SimpleGraph graph = new SimpleGraph();
- SimpleVertex vtx1 = graph.createNewVertex();
- SimpleVertex vtx2 = graph.createNewVertex();
- Edge<SimpleVertex> edge = graph.createNewEdge(vtx1, vtx2);
+ SimpleNode vtx1 = graph.createNewNode();
+ SimpleNode vtx2 = graph.createNewNode();
+ Edge<SimpleNode> edge =
graph.createNewEdge(StandardRelationType.DEFAULT, vtx1, vtx2);
assertNotNull(edge);
assertNotNull(edge.getId());
assertNotNull(java.util.UUID.fromString(edge.getId()));
@@ -51,9 +52,9 @@ class SimpleGraphTest {
@Test
void removeEdge() {
SimpleGraph graph = new SimpleGraph();
- SimpleVertex vtx1 = graph.createNewVertex();
- SimpleVertex vtx2 = graph.createNewVertex();
- Edge<SimpleVertex> edge = graph.createNewEdge(vtx1, vtx2);
+ SimpleNode vtx1 = graph.createNewNode();
+ SimpleNode vtx2 = graph.createNewNode();
+ Edge<SimpleNode> edge =
graph.createNewEdge(StandardRelationType.DEFAULT, vtx1, vtx2);
graph.removeEdge(edge);
@@ -65,6 +66,79 @@ class SimpleGraphTest {
}
@Test
- void removeVertex() {
+ void removeNode() {
+ String label = "root";
+ SimpleGraph graph = new SimpleGraph();
+ SimpleNode node = graph.newNode(label);
+
+ assertNotNull(node);
+ assertNotNull(graph.getNode(node.getId()));
+
+ graph.removeNode(node);
+ assertNull(graph.getNode(node.getId()));
+
+ }
+
+ @Test
+ void removeNodeWithEdges() {
+ String label = "root";
+ SimpleGraph graph = new SimpleGraph();
+ SimpleNode node1 = graph.newNode("1");
+ SimpleNode node2 = graph.newNode("2");
+ Edge<SimpleNode> edge1 = graph.newEdge("1:2", node1, node2);
+ Edge<SimpleNode> edge2 = graph.newEdge("2:1", node2, node1);
+
+
+
+ assertNotNull(node1);
+ assertNotNull(graph.getNode(node1.getId()));
+
+ graph.removeNode(node1);
+
+ assertNull(graph.getNode(node1.getId()));
+
+ assertEquals(0, node2.getInEdges().size());
+ assertEquals(0, node2.getOutEdges().size());
+
+
+ }
+
+ @Test
+ void getNode() {
+ String label = "root";
+ SimpleGraph graph = new SimpleGraph();
+ SimpleNode node = graph.newNode(label);
+
+ assertNotNull(node);
+ SimpleNode foundNode = graph.getNode(node.getId());
+ assertNotNull(foundNode);
+ assertEquals(node, foundNode);
+ assertEquals(label, foundNode.getLabel());
+
+ }
+
+
+ @Test
+ void newNode() {
+ String label = "root";
+ SimpleGraph graph = new SimpleGraph();
+ SimpleNode node = graph.newNode(label);
+
+ assertNotNull(node);
+ assertEquals(label, node.getLabel());
+
}
+
+ @Test
+ void addNode() {
+ String id = "root";
+ SimpleGraph graph = new SimpleGraph();
+ SimpleNode node = graph.addNode(id, id);
+
+ assertNotNull(node);
+ assertNotNull(graph.getNode(id));
+ assertEquals(id, graph.getNode(id).getLabel());
+
+ }
+
}
\ No newline at end of file
diff --git
a/graph/src/test/java/org/apache/archiva/components/graph/base/SimpleVertexTest.java
b/graph/src/test/java/org/apache/archiva/components/graph/base/SimpleNodeTest.java
similarity index 86%
rename from
graph/src/test/java/org/apache/archiva/components/graph/base/SimpleVertexTest.java
rename to
graph/src/test/java/org/apache/archiva/components/graph/base/SimpleNodeTest.java
index e468e48..9b849d2 100644
---
a/graph/src/test/java/org/apache/archiva/components/graph/base/SimpleVertexTest.java
+++
b/graph/src/test/java/org/apache/archiva/components/graph/base/SimpleNodeTest.java
@@ -24,26 +24,26 @@ import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
-class SimpleVertexTest {
+class SimpleNodeTest {
- private Graph<SimpleVertex> graph = new SimpleGraph();
+ private Graph<SimpleNode> graph = new SimpleGraph();
@Test
void getId() {
- SimpleVertex vtx = new SimpleVertex(graph, "testid001");
+ SimpleNode vtx = new SimpleNode(graph, "testid001");
assertNotNull(vtx.getId());
assertEquals("testid001", vtx.getId());
}
@Test
void getLabel() {
- SimpleVertex vtx = new SimpleVertex(graph, "testid001");
+ SimpleNode vtx = new SimpleNode(graph, "testid001");
assertNull(vtx.getLabel());
vtx.setLabel("test");
assertEquals("test", vtx.getLabel());
- vtx = new SimpleVertex(graph, "testid001");
+ vtx = new SimpleNode(graph, "testid001");
vtx.setLabel("Another label with more characters üy@~ ---");
assertNotNull(vtx.getLabel());
assertEquals("Another label with more characters üy@~ ---",
vtx.getLabel());
@@ -53,15 +53,15 @@ class SimpleVertexTest {
@Test
void getGraph() {
- SimpleVertex vtx = new SimpleVertex(graph, "test");
+ SimpleNode vtx = new SimpleNode(graph, "test");
assertNotNull(vtx.getGraph());
assertTrue(vtx.getGraph() == graph);
}
@Test
void getInOutEdges() {
- SimpleVertex vtx1 = new SimpleVertex(graph, "test1");
- SimpleVertex vtx2 = new SimpleVertex(graph, "test2");
+ SimpleNode vtx1 = new SimpleNode(graph, "test1");
+ SimpleNode vtx2 = new SimpleNode(graph, "test2");
vtx1.addEdge(new BaseEdge<>(graph, "edge11_1to2", vtx1, vtx2));
vtx1.addEdge(new BaseEdge<>(graph, "edge12_1to2", vtx1, vtx2));
vtx1.addEdge(new BaseEdge<>(graph, "edge13_1to2", vtx1, vtx2));
@@ -85,8 +85,8 @@ class SimpleVertexTest {
@Test
void removeEdge() {
- SimpleVertex vtx1 = new SimpleVertex(graph, "test1");
- SimpleVertex vtx2 = new SimpleVertex(graph, "test2");
+ SimpleNode vtx1 = new SimpleNode(graph, "test1");
+ SimpleNode vtx2 = new SimpleNode(graph, "test2");
vtx1.addEdge(new BaseEdge<>(graph, "edge11_1to2", vtx1, vtx2));
vtx1.addEdge(new BaseEdge<>(graph, "edge12_1to2", vtx1, vtx2));
vtx1.addEdge(new BaseEdge<>(graph, "edge13_1to2", vtx1, vtx2));
@@ -100,7 +100,7 @@ class SimpleVertexTest {
vtx1.addEdge(new BaseEdge<>(graph, "edge15_2to1", vtx2, vtx1));
vtx1.addEdge(new BaseEdge<>(graph, "edge16_2to1", vtx2, vtx1));
vtx2.addEdge(new BaseEdge<>(graph, "edge21_2to1", vtx2, vtx1));
- Edge<SimpleVertex> edge = vtx1.getOutEdges().get(0);
+ Edge<SimpleNode> edge = vtx1.getOutEdges().get(0);
vtx1.removeEdge(edge);
edge = vtx1.getInEdges().get(0);
vtx1.removeEdge(edge);
diff --git
a/graph/src/test/java/org/apache/archiva/components/graph/util/TraversalTest.java
b/graph/src/test/java/org/apache/archiva/components/graph/util/TraversalTest.java
index cbc26f1..7ae9f33 100644
---
a/graph/src/test/java/org/apache/archiva/components/graph/util/TraversalTest.java
+++
b/graph/src/test/java/org/apache/archiva/components/graph/util/TraversalTest.java
@@ -20,12 +20,13 @@ package org.apache.archiva.components.graph.util;
import org.apache.archiva.components.graph.api.TraversalStatus;
import org.apache.archiva.components.graph.base.SimpleGraph;
-import org.apache.archiva.components.graph.base.SimpleVertex;
+import org.apache.archiva.components.graph.base.SimpleNode;
import org.junit.jupiter.api.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.ArrayList;
+import java.util.Collections;
import java.util.List;
import static org.junit.jupiter.api.Assertions.*;
@@ -37,55 +38,55 @@ class TraversalTest {
@Test
void depthFirstWithoutCycleAndWithoutError() {
SimpleGraph graph = new SimpleGraph();
- SimpleVertex vtx0 = graph.addVertex("root");
- SimpleVertex vtx1 = graph.addVertex("vertex1");
- SimpleVertex vtx11 = graph.addVertex("vertex11");
- SimpleVertex vtx12 = graph.addVertex("vertex12");
- SimpleVertex vtx2 = graph.addVertex("vertex2");
- SimpleVertex vtx21 = graph.addVertex("vertex21");
- SimpleVertex vtx211 = graph.addVertex("vertex211");
- SimpleVertex vtx212 = graph.addVertex("vertex212");
-
- SimpleVertex vtx22 = graph.addVertex("vertex22");
- SimpleVertex vtx221 = graph.addVertex("vertex221");
- SimpleVertex vtx222 = graph.addVertex("vertex222");
- SimpleVertex vtx223 = graph.addVertex("vertex223");
-
- SimpleVertex vtx3 = graph.addVertex("vertex3");
- SimpleVertex vtx31 = graph.addVertex("vertex31");
- SimpleVertex vtx32 = graph.addVertex("vertex32");
- SimpleVertex vtx33 = graph.addVertex("vertex33");
-
- graph.addEdge("root->1", vtx0, vtx1);
- graph.addEdge("root->2", vtx0, vtx2);
- graph.addEdge("root->3", vtx0, vtx3);
-
- graph.addEdge("1->11", vtx1, vtx11);
- graph.addEdge("1->12", vtx1, vtx12);
-
- graph.addEdge("2->21", vtx2, vtx21);
- graph.addEdge("2->22", vtx2, vtx22);
-
- graph.addEdge("21->211", vtx21, vtx211);
- graph.addEdge("21->212", vtx21, vtx212);
-
- graph.addEdge("22->221", vtx22, vtx221);
- graph.addEdge("22->222", vtx22, vtx222);
- graph.addEdge("22->223", vtx22, vtx223);
-
- graph.addEdge("3->31", vtx3, vtx31);
- graph.addEdge("3->32", vtx3, vtx32);
- graph.addEdge("3->33", vtx3, vtx33);
-
- List<SimpleVertex> visitedNodes = new ArrayList<>();
- TraversalStatus<SimpleVertex> status = Traversal.depthFirst(vtx0, v ->
{
+ SimpleNode vtx0 = graph.newNode("root");
+ SimpleNode vtx1 = graph.newNode("vertex1");
+ SimpleNode vtx11 = graph.newNode("vertex11");
+ SimpleNode vtx12 = graph.newNode("vertex12");
+ SimpleNode vtx2 = graph.newNode("vertex2");
+ SimpleNode vtx21 = graph.newNode("vertex21");
+ SimpleNode vtx211 = graph.newNode("vertex211");
+ SimpleNode vtx212 = graph.newNode("vertex212");
+
+ SimpleNode vtx22 = graph.newNode("vertex22");
+ SimpleNode vtx221 = graph.newNode("vertex221");
+ SimpleNode vtx222 = graph.newNode("vertex222");
+ SimpleNode vtx223 = graph.newNode("vertex223");
+
+ SimpleNode vtx3 = graph.newNode("vertex3");
+ SimpleNode vtx31 = graph.newNode("vertex31");
+ SimpleNode vtx32 = graph.newNode("vertex32");
+ SimpleNode vtx33 = graph.newNode("vertex33");
+
+ graph.newEdge("root->1", vtx0, vtx1);
+ graph.newEdge("root->2", vtx0, vtx2);
+ graph.newEdge("root->3", vtx0, vtx3);
+
+ graph.newEdge("1->11", vtx1, vtx11);
+ graph.newEdge("1->12", vtx1, vtx12);
+
+ graph.newEdge("2->21", vtx2, vtx21);
+ graph.newEdge("2->22", vtx2, vtx22);
+
+ graph.newEdge("21->211", vtx21, vtx211);
+ graph.newEdge("21->212", vtx21, vtx212);
+
+ graph.newEdge("22->221", vtx22, vtx221);
+ graph.newEdge("22->222", vtx22, vtx222);
+ graph.newEdge("22->223", vtx22, vtx223);
+
+ graph.newEdge("3->31", vtx3, vtx31);
+ graph.newEdge("3->32", vtx3, vtx32);
+ graph.newEdge("3->33", vtx3, vtx33);
+
+ List<SimpleNode> visitedNodes = new ArrayList<>();
+ TraversalStatus<SimpleNode> status = Traversal.depthFirst(vtx0, ( v, s
) -> {
log.debug("Visiting vertex " + v);
if (visitedNodes.contains(v)) {
throw new RuntimeException("Double visit of vertex: " + v);
}
visitedNodes.add(v);
return true;
- }, true);
+ });
assertEquals(vtx0, visitedNodes.get(0));
assertEquals(vtx1, visitedNodes.get(1));
@@ -111,57 +112,57 @@ class TraversalTest {
@Test
void depthFirstWithCycleAndWithoutError() {
SimpleGraph graph = new SimpleGraph();
- SimpleVertex vtx0 = graph.addVertex("root");
- SimpleVertex vtx1 = graph.addVertex("vertex1");
- SimpleVertex vtx11 = graph.addVertex("vertex11");
- SimpleVertex vtx12 = graph.addVertex("vertex12");
- SimpleVertex vtx2 = graph.addVertex("vertex2");
- SimpleVertex vtx21 = graph.addVertex("vertex21");
- SimpleVertex vtx211 = graph.addVertex("vertex211");
- SimpleVertex vtx212 = graph.addVertex("vertex212");
-
- SimpleVertex vtx22 = graph.addVertex("vertex22");
- SimpleVertex vtx221 = graph.addVertex("vertex221");
- SimpleVertex vtx222 = graph.addVertex("vertex222");
- SimpleVertex vtx223 = graph.addVertex("vertex223");
-
- SimpleVertex vtx3 = graph.addVertex("vertex3");
- SimpleVertex vtx31 = graph.addVertex("vertex31");
- SimpleVertex vtx32 = graph.addVertex("vertex32");
- SimpleVertex vtx33 = graph.addVertex("vertex33");
-
- graph.addEdge("root->1", vtx0, vtx1);
- graph.addEdge("root->2", vtx0, vtx2);
- graph.addEdge("root->3", vtx0, vtx3);
-
- graph.addEdge("1->11", vtx1, vtx11);
- graph.addEdge("1->12", vtx1, vtx12);
-
- graph.addEdge("2->21", vtx2, vtx21);
- graph.addEdge("2->22", vtx2, vtx22);
- graph.addEdge("22->2", vtx22, vtx2);
-
- graph.addEdge("21->211", vtx21, vtx211);
- graph.addEdge("21->212", vtx21, vtx212);
-
- graph.addEdge("22->221", vtx22, vtx221);
- graph.addEdge("22->222", vtx22, vtx222);
- graph.addEdge("22->223", vtx22, vtx223);
- graph.addEdge("223->root", vtx223, vtx0);
-
- graph.addEdge("3->31", vtx3, vtx31);
- graph.addEdge("3->32", vtx3, vtx32);
- graph.addEdge("3->33", vtx3, vtx33);
-
- List<SimpleVertex> visitedNodes = new ArrayList<>();
- TraversalStatus<SimpleVertex> status = Traversal.depthFirst(vtx0, v ->
{
+ SimpleNode vtx0 = graph.newNode("root");
+ SimpleNode vtx1 = graph.newNode("vertex1");
+ SimpleNode vtx11 = graph.newNode("vertex11");
+ SimpleNode vtx12 = graph.newNode("vertex12");
+ SimpleNode vtx2 = graph.newNode("vertex2");
+ SimpleNode vtx21 = graph.newNode("vertex21");
+ SimpleNode vtx211 = graph.newNode("vertex211");
+ SimpleNode vtx212 = graph.newNode("vertex212");
+
+ SimpleNode vtx22 = graph.newNode("vertex22");
+ SimpleNode vtx221 = graph.newNode("vertex221");
+ SimpleNode vtx222 = graph.newNode("vertex222");
+ SimpleNode vtx223 = graph.newNode("vertex223");
+
+ SimpleNode vtx3 = graph.newNode("vertex3");
+ SimpleNode vtx31 = graph.newNode("vertex31");
+ SimpleNode vtx32 = graph.newNode("vertex32");
+ SimpleNode vtx33 = graph.newNode("vertex33");
+
+ graph.newEdge("root->1", vtx0, vtx1);
+ graph.newEdge("root->2", vtx0, vtx2);
+ graph.newEdge("root->3", vtx0, vtx3);
+
+ graph.newEdge("1->11", vtx1, vtx11);
+ graph.newEdge("1->12", vtx1, vtx12);
+
+ graph.newEdge("2->21", vtx2, vtx21);
+ graph.newEdge("2->22", vtx2, vtx22);
+ graph.newEdge("22->2", vtx22, vtx2);
+
+ graph.newEdge("21->211", vtx21, vtx211);
+ graph.newEdge("21->212", vtx21, vtx212);
+
+ graph.newEdge("22->221", vtx22, vtx221);
+ graph.newEdge("22->222", vtx22, vtx222);
+ graph.newEdge("22->223", vtx22, vtx223);
+ graph.newEdge("223->root", vtx223, vtx0);
+
+ graph.newEdge("3->31", vtx3, vtx31);
+ graph.newEdge("3->32", vtx3, vtx32);
+ graph.newEdge("3->33", vtx3, vtx33);
+
+ List<SimpleNode> visitedNodes = new ArrayList<>();
+ TraversalStatus<SimpleNode> status = Traversal.depthFirst(vtx0, (v, s)
-> {
log.debug("Visiting vertex " + v);
if (visitedNodes.contains(v)) {
throw new RuntimeException("Double visit of vertex: " + v);
}
visitedNodes.add(v);
return true;
- }, true);
+ });
assertEquals(vtx0, visitedNodes.get(0));
assertEquals(vtx1, visitedNodes.get(1));
@@ -189,50 +190,50 @@ class TraversalTest {
@Test
void depthFirstWithCycleAndWithError() {
SimpleGraph graph = new SimpleGraph();
- SimpleVertex vtx0 = graph.addVertex("root");
- SimpleVertex vtx1 = graph.addVertex("vertex1");
- SimpleVertex vtx11 = graph.addVertex("vertex11");
- SimpleVertex vtx12 = graph.addVertex("vertex12");
- SimpleVertex vtx2 = graph.addVertex("vertex2");
- SimpleVertex vtx21 = graph.addVertex("vertex21");
- SimpleVertex vtx211 = graph.addVertex("vertex211");
- SimpleVertex vtx212 = graph.addVertex("vertex212");
-
- SimpleVertex vtx22 = graph.addVertex("vertex22");
- SimpleVertex vtx221 = graph.addVertex("vertex221");
- SimpleVertex vtx222 = graph.addVertex("vertex222");
- SimpleVertex vtx223 = graph.addVertex("vertex223");
-
- SimpleVertex vtx3 = graph.addVertex("vertex3");
- SimpleVertex vtx31 = graph.addVertex("vertex31");
- SimpleVertex vtx32 = graph.addVertex("vertex32");
- SimpleVertex vtx33 = graph.addVertex("vertex33");
-
- graph.addEdge("root->1", vtx0, vtx1);
- graph.addEdge("root->2", vtx0, vtx2);
- graph.addEdge("root->3", vtx0, vtx3);
-
- graph.addEdge("1->11", vtx1, vtx11);
- graph.addEdge("1->12", vtx1, vtx12);
-
- graph.addEdge("2->21", vtx2, vtx21);
- graph.addEdge("2->22", vtx2, vtx22);
- graph.addEdge("22->2", vtx22, vtx2);
-
- graph.addEdge("21->211", vtx21, vtx211);
- graph.addEdge("21->212", vtx21, vtx212);
-
- graph.addEdge("22->221", vtx22, vtx221);
- graph.addEdge("22->222", vtx22, vtx222);
- graph.addEdge("22->223", vtx22, vtx223);
- graph.addEdge("223->root", vtx223, vtx0);
-
- graph.addEdge("3->31", vtx3, vtx31);
- graph.addEdge("3->32", vtx3, vtx32);
- graph.addEdge("3->33", vtx3, vtx33);
-
- List<SimpleVertex> visitedNodes = new ArrayList<>();
- TraversalStatus<SimpleVertex> status = Traversal.depthFirst(vtx0, v ->
{
+ SimpleNode vtx0 = graph.newNode("root");
+ SimpleNode vtx1 = graph.newNode("vertex1");
+ SimpleNode vtx11 = graph.newNode("vertex11");
+ SimpleNode vtx12 = graph.newNode("vertex12");
+ SimpleNode vtx2 = graph.newNode("vertex2");
+ SimpleNode vtx21 = graph.newNode("vertex21");
+ SimpleNode vtx211 = graph.newNode("vertex211");
+ SimpleNode vtx212 = graph.newNode("vertex212");
+
+ SimpleNode vtx22 = graph.newNode("vertex22");
+ SimpleNode vtx221 = graph.newNode("vertex221");
+ SimpleNode vtx222 = graph.newNode("vertex222");
+ SimpleNode vtx223 = graph.newNode("vertex223");
+
+ SimpleNode vtx3 = graph.newNode("vertex3");
+ SimpleNode vtx31 = graph.newNode("vertex31");
+ SimpleNode vtx32 = graph.newNode("vertex32");
+ SimpleNode vtx33 = graph.newNode("vertex33");
+
+ graph.newEdge("root->1", vtx0, vtx1);
+ graph.newEdge("root->2", vtx0, vtx2);
+ graph.newEdge("root->3", vtx0, vtx3);
+
+ graph.newEdge("1->11", vtx1, vtx11);
+ graph.newEdge("1->12", vtx1, vtx12);
+
+ graph.newEdge("2->21", vtx2, vtx21);
+ graph.newEdge("2->22", vtx2, vtx22);
+ graph.newEdge("22->2", vtx22, vtx2);
+
+ graph.newEdge("21->211", vtx21, vtx211);
+ graph.newEdge("21->212", vtx21, vtx212);
+
+ graph.newEdge("22->221", vtx22, vtx221);
+ graph.newEdge("22->222", vtx22, vtx222);
+ graph.newEdge("22->223", vtx22, vtx223);
+ graph.newEdge("223->root", vtx223, vtx0);
+
+ graph.newEdge("3->31", vtx3, vtx31);
+ graph.newEdge("3->32", vtx3, vtx32);
+ graph.newEdge("3->33", vtx3, vtx33);
+
+ List<SimpleNode> visitedNodes = new ArrayList<>();
+ TraversalStatus<SimpleNode> status = Traversal.depthFirst(vtx0, (v,s)
-> {
log.debug("Visiting vertex " + v);
if (visitedNodes.contains(v)) {
throw new RuntimeException("Double visit of vertex: " + v);
@@ -242,7 +243,7 @@ class TraversalTest {
throw new RuntimeException("Error for node " + v);
}
return true;
- }, true);
+ });
assertEquals(vtx0, visitedNodes.get(0));
assertEquals(vtx1, visitedNodes.get(1));
@@ -270,57 +271,106 @@ class TraversalTest {
}
@Test
+ void hasCycle() {
+ SimpleGraph graph = new SimpleGraph();
+ SimpleNode vtx0 = graph.newNode("root");
+ SimpleNode vtx1 = graph.newNode("vertex1");
+ SimpleNode vtx11 = graph.newNode("vertex11");
+ SimpleNode vtx12 = graph.newNode("vertex12");
+ SimpleNode vtx2 = graph.newNode("vertex2");
+ SimpleNode vtx21 = graph.newNode("vertex21");
+ SimpleNode vtx211 = graph.newNode("vertex211");
+ SimpleNode vtx212 = graph.newNode("vertex212");
+
+ SimpleNode vtx22 = graph.newNode("vertex22");
+ SimpleNode vtx221 = graph.newNode("vertex221");
+ SimpleNode vtx222 = graph.newNode("vertex222");
+ SimpleNode vtx223 = graph.newNode("vertex223");
+
+ SimpleNode vtx3 = graph.newNode("vertex3");
+ SimpleNode vtx31 = graph.newNode("vertex31");
+ SimpleNode vtx32 = graph.newNode("vertex32");
+ SimpleNode vtx33 = graph.newNode("vertex33");
+
+ graph.newEdge("root->1", vtx0, vtx1);
+ graph.newEdge("root->2", vtx0, vtx2);
+ graph.newEdge("root->3", vtx0, vtx3);
+
+ graph.newEdge("1->11", vtx1, vtx11);
+ graph.newEdge("1->12", vtx1, vtx12);
+
+ graph.newEdge("2->21", vtx2, vtx21);
+ graph.newEdge("2->22", vtx2, vtx22);
+ graph.newEdge("22->2", vtx22, vtx2);
+
+ graph.newEdge("21->211", vtx21, vtx211);
+ graph.newEdge("21->212", vtx21, vtx212);
+
+ graph.newEdge("22->221", vtx22, vtx221);
+ graph.newEdge("22->222", vtx22, vtx222);
+ graph.newEdge("22->223", vtx22, vtx223);
+ graph.newEdge("223->root", vtx223, vtx0);
+
+ graph.newEdge("3->31", vtx3, vtx31);
+ graph.newEdge("3->32", vtx3, vtx32);
+ graph.newEdge("3->33", vtx3, vtx33);
+
+ assertTrue(Traversal.hasCycle(vtx0));
+ assertFalse(Traversal.hasCycle(vtx1));
+ }
+
+ @Test
void breadthFirstWithoutCyclesAndWithoutError() {
SimpleGraph graph = new SimpleGraph();
- SimpleVertex vtx0 = graph.addVertex("root");
- SimpleVertex vtx1 = graph.addVertex("vertex1");
- SimpleVertex vtx11 = graph.addVertex("vertex11");
- SimpleVertex vtx12 = graph.addVertex("vertex12");
- SimpleVertex vtx2 = graph.addVertex("vertex2");
- SimpleVertex vtx21 = graph.addVertex("vertex21");
- SimpleVertex vtx211 = graph.addVertex("vertex211");
- SimpleVertex vtx212 = graph.addVertex("vertex212");
-
- SimpleVertex vtx22 = graph.addVertex("vertex22");
- SimpleVertex vtx221 = graph.addVertex("vertex221");
- SimpleVertex vtx222 = graph.addVertex("vertex222");
- SimpleVertex vtx223 = graph.addVertex("vertex223");
-
- SimpleVertex vtx3 = graph.addVertex("vertex3");
- SimpleVertex vtx31 = graph.addVertex("vertex31");
- SimpleVertex vtx32 = graph.addVertex("vertex32");
- SimpleVertex vtx33 = graph.addVertex("vertex33");
-
- graph.addEdge("root->1", vtx0, vtx1);
- graph.addEdge("root->2", vtx0, vtx2);
- graph.addEdge("root->3", vtx0, vtx3);
-
- graph.addEdge("1->11", vtx1, vtx11);
- graph.addEdge("1->12", vtx1, vtx12);
-
- graph.addEdge("2->21", vtx2, vtx21);
- graph.addEdge("2->22", vtx2, vtx22);
-
- graph.addEdge("21->211", vtx21, vtx211);
- graph.addEdge("21->212", vtx21, vtx212);
-
- graph.addEdge("22->221", vtx22, vtx221);
- graph.addEdge("22->222", vtx22, vtx222);
- graph.addEdge("22->223", vtx22, vtx223);
-
- graph.addEdge("3->31", vtx3, vtx31);
- graph.addEdge("3->32", vtx3, vtx32);
- graph.addEdge("3->33", vtx3, vtx33);
-
- List<SimpleVertex> visitedNodes = new ArrayList<>();
- TraversalStatus<SimpleVertex> status = Traversal.breadthFirst(vtx0, v
-> {
+ SimpleNode vtx0 = graph.newNode("root");
+ SimpleNode vtx1 = graph.newNode("vertex1");
+ SimpleNode vtx11 = graph.newNode("vertex11");
+ SimpleNode vtx12 = graph.newNode("vertex12");
+ SimpleNode vtx2 = graph.newNode("vertex2");
+ SimpleNode vtx21 = graph.newNode("vertex21");
+ SimpleNode vtx211 = graph.newNode("vertex211");
+ SimpleNode vtx212 = graph.newNode("vertex212");
+
+ SimpleNode vtx22 = graph.newNode("vertex22");
+ SimpleNode vtx221 = graph.newNode("vertex221");
+ SimpleNode vtx222 = graph.newNode("vertex222");
+ SimpleNode vtx223 = graph.newNode("vertex223");
+
+ SimpleNode vtx3 = graph.newNode("vertex3");
+ SimpleNode vtx31 = graph.newNode("vertex31");
+ SimpleNode vtx32 = graph.newNode("vertex32");
+ SimpleNode vtx33 = graph.newNode("vertex33");
+
+ graph.newEdge("root->1", vtx0, vtx1);
+ graph.newEdge("root->2", vtx0, vtx2);
+ graph.newEdge("root->3", vtx0, vtx3);
+
+ graph.newEdge("1->11", vtx1, vtx11);
+ graph.newEdge("1->12", vtx1, vtx12);
+
+ graph.newEdge("2->21", vtx2, vtx21);
+ graph.newEdge("2->22", vtx2, vtx22);
+
+ graph.newEdge("21->211", vtx21, vtx211);
+ graph.newEdge("21->212", vtx21, vtx212);
+
+ graph.newEdge("22->221", vtx22, vtx221);
+ graph.newEdge("22->222", vtx22, vtx222);
+ graph.newEdge("22->223", vtx22, vtx223);
+
+ graph.newEdge("3->31", vtx3, vtx31);
+ graph.newEdge("3->32", vtx3, vtx32);
+ graph.newEdge("3->33", vtx3, vtx33);
+
+ List<SimpleNode> visitedNodes = new ArrayList<>();
+ TraversalStatus<SimpleNode> status = Traversal.breadthFirst(vtx0,
(v,s) -> {
log.debug("Visiting vertex " + v);
if (visitedNodes.contains(v)) {
throw new RuntimeException("Double visit of vertex: " + v);
}
visitedNodes.add(v);
return true;
- }, true);
+ });
assertEquals(vtx0, visitedNodes.get(0));
assertEquals(vtx1, visitedNodes.get(1));
@@ -346,127 +396,128 @@ class TraversalTest {
@Test
void breadthFirstWithCyclesAndWithoutError() {
SimpleGraph graph = new SimpleGraph();
- SimpleVertex vtx0 = graph.addVertex("root");
- SimpleVertex vtx1 = graph.addVertex("vertex1");
- SimpleVertex vtx11 = graph.addVertex("vertex11");
- SimpleVertex vtx12 = graph.addVertex("vertex12");
- SimpleVertex vtx2 = graph.addVertex("vertex2");
- SimpleVertex vtx21 = graph.addVertex("vertex21");
- SimpleVertex vtx211 = graph.addVertex("vertex211");
- SimpleVertex vtx212 = graph.addVertex("vertex212");
-
- SimpleVertex vtx22 = graph.addVertex("vertex22");
- SimpleVertex vtx221 = graph.addVertex("vertex221");
- SimpleVertex vtx222 = graph.addVertex("vertex222");
- SimpleVertex vtx223 = graph.addVertex("vertex223");
-
- SimpleVertex vtx3 = graph.addVertex("vertex3");
- SimpleVertex vtx31 = graph.addVertex("vertex31");
- SimpleVertex vtx32 = graph.addVertex("vertex32");
- SimpleVertex vtx33 = graph.addVertex("vertex33");
-
- graph.addEdge("root->1", vtx0, vtx1);
- graph.addEdge("root->2", vtx0, vtx2);
- graph.addEdge("root->3", vtx0, vtx3);
-
- graph.addEdge("1->11", vtx1, vtx11);
- graph.addEdge("1->12", vtx1, vtx12);
-
- graph.addEdge("2->21", vtx2, vtx21);
- graph.addEdge("2->22", vtx2, vtx22);
-
- graph.addEdge("21->211", vtx21, vtx211);
- graph.addEdge("21->212", vtx21, vtx212);
- graph.addEdge("211->21", vtx211, vtx21);
-
- graph.addEdge("22->221", vtx22, vtx221);
- graph.addEdge("22->222", vtx22, vtx222);
- graph.addEdge("22->223", vtx22, vtx223);
- graph.addEdge("223->root", vtx223, vtx0);
-
- graph.addEdge("3->31", vtx3, vtx31);
- graph.addEdge("3->32", vtx3, vtx32);
- graph.addEdge("3->33", vtx3, vtx33);
-
- List<SimpleVertex> visitedNodes = new ArrayList<>();
- TraversalStatus<SimpleVertex> status = Traversal.breadthFirst(vtx0, v
-> {
+ SimpleNode vtx0 = graph.newNode("root");
+ SimpleNode vtx1 = graph.newNode("vertex1");
+ SimpleNode vtx11 = graph.newNode("vertex11");
+ SimpleNode vtx12 = graph.newNode("vertex12");
+ SimpleNode vtx2 = graph.newNode("vertex2");
+ SimpleNode vtx21 = graph.newNode("vertex21");
+ SimpleNode vtx211 = graph.newNode("vertex211");
+ SimpleNode vtx212 = graph.newNode("vertex212");
+
+ SimpleNode vtx22 = graph.newNode("vertex22");
+ SimpleNode vtx221 = graph.newNode("vertex221");
+ SimpleNode vtx222 = graph.newNode("vertex222");
+ SimpleNode vtx223 = graph.newNode("vertex223");
+
+ SimpleNode vtx3 = graph.newNode("vertex3");
+ SimpleNode vtx31 = graph.newNode("vertex31");
+ SimpleNode vtx32 = graph.newNode("vertex32");
+ SimpleNode vtx33 = graph.newNode("vertex33");
+
+ graph.newEdge("root->1", vtx0, vtx1);
+ graph.newEdge("root->2", vtx0, vtx2);
+ graph.newEdge("root->3", vtx0, vtx3);
+
+ graph.newEdge("1->11", vtx1, vtx11);
+ graph.newEdge("1->12", vtx1, vtx12);
+
+ graph.newEdge("2->21", vtx2, vtx21);
+ graph.newEdge("2->22", vtx2, vtx22);
+
+ graph.newEdge("21->211", vtx21, vtx211);
+ graph.newEdge("21->212", vtx21, vtx212);
+ graph.newEdge("211->21", vtx211, vtx21);
+
+ graph.newEdge("22->221", vtx22, vtx221);
+ graph.newEdge("22->222", vtx22, vtx222);
+ graph.newEdge("22->223", vtx22, vtx223);
+ graph.newEdge("223->root", vtx223, vtx0);
+
+ graph.newEdge("3->31", vtx3, vtx31);
+ graph.newEdge("3->32", vtx3, vtx32);
+ graph.newEdge("3->33", vtx3, vtx33);
+
+ List<SimpleNode> visitedNodes = new ArrayList<>();
+ TraversalStatus<SimpleNode> status = Traversal.breadthFirst(vtx0, (v,
s) -> {
log.debug("Visiting vertex " + v);
if (visitedNodes.contains(v)) {
throw new RuntimeException("Double visit of vertex: " + v);
}
visitedNodes.add(v);
return true;
- }, true);
+ }, new TraversalFlags(false, true));
assertEquals(vtx0, visitedNodes.get(0));
assertEquals(vtx1, visitedNodes.get(1));
assertEquals(vtx2, visitedNodes.get(2));
assertEquals(vtx3, visitedNodes.get(3));
- assertEquals(vtx11, visitedNodes.get(4));
- assertEquals(vtx12, visitedNodes.get(5));
- assertEquals(vtx21, visitedNodes.get(6));
- assertEquals(vtx22, visitedNodes.get(7));
- assertEquals(vtx31, visitedNodes.get(8));
- assertEquals(vtx32, visitedNodes.get(9));
- assertEquals(vtx33, visitedNodes.get(10));
- assertEquals(vtx211, visitedNodes.get(11));
- assertEquals(vtx212, visitedNodes.get(12));
- assertEquals(vtx221, visitedNodes.get(13));
- assertEquals(vtx222, visitedNodes.get(14));
- assertEquals(vtx223, visitedNodes.get(15));
+ assertEquals(vtx223, visitedNodes.get(4));
+ assertEquals(vtx11, visitedNodes.get(5));
+ assertEquals(vtx12, visitedNodes.get(6));
+ assertEquals(vtx21, visitedNodes.get(7));
+ assertEquals(vtx22, visitedNodes.get(8));
+ assertEquals(vtx31, visitedNodes.get(9));
+ assertEquals(vtx32, visitedNodes.get(10));
+ assertEquals(vtx33, visitedNodes.get(11));
+ assertEquals(vtx211, visitedNodes.get(12));
+ assertEquals(vtx212, visitedNodes.get(13));
+ assertEquals(vtx221, visitedNodes.get(14));
+ assertEquals(vtx222, visitedNodes.get(15));
+
assertTrue(status.hasCycles());
- assertEquals(2, status.getCycleCount());
+ assertEquals(19, status.getCycleCount());
assertFalse(status.hasErrors());
}
@Test
void breadthFirstWithCyclesAndWithError() {
SimpleGraph graph = new SimpleGraph();
- SimpleVertex vtx0 = graph.addVertex("root");
- SimpleVertex vtx1 = graph.addVertex("vertex1");
- SimpleVertex vtx11 = graph.addVertex("vertex11");
- SimpleVertex vtx12 = graph.addVertex("vertex12");
- SimpleVertex vtx2 = graph.addVertex("vertex2");
- SimpleVertex vtx21 = graph.addVertex("vertex21");
- SimpleVertex vtx211 = graph.addVertex("vertex211");
- SimpleVertex vtx212 = graph.addVertex("vertex212");
-
- SimpleVertex vtx22 = graph.addVertex("vertex22");
- SimpleVertex vtx221 = graph.addVertex("vertex221");
- SimpleVertex vtx222 = graph.addVertex("vertex222");
- SimpleVertex vtx223 = graph.addVertex("vertex223");
-
- SimpleVertex vtx3 = graph.addVertex("vertex3");
- SimpleVertex vtx31 = graph.addVertex("vertex31");
- SimpleVertex vtx32 = graph.addVertex("vertex32");
- SimpleVertex vtx33 = graph.addVertex("vertex33");
-
- graph.addEdge("root->1", vtx0, vtx1);
- graph.addEdge("root->2", vtx0, vtx2);
- graph.addEdge("root->3", vtx0, vtx3);
-
- graph.addEdge("1->11", vtx1, vtx11);
- graph.addEdge("1->12", vtx1, vtx12);
-
- graph.addEdge("2->21", vtx2, vtx21);
- graph.addEdge("2->22", vtx2, vtx22);
-
- graph.addEdge("21->211", vtx21, vtx211);
- graph.addEdge("21->212", vtx21, vtx212);
- graph.addEdge("211->21", vtx211, vtx21);
-
- graph.addEdge("22->221", vtx22, vtx221);
- graph.addEdge("22->222", vtx22, vtx222);
- graph.addEdge("22->223", vtx22, vtx223);
- graph.addEdge("223->root", vtx223, vtx0);
-
- graph.addEdge("3->31", vtx3, vtx31);
- graph.addEdge("3->32", vtx3, vtx32);
- graph.addEdge("3->33", vtx3, vtx33);
-
- List<SimpleVertex> visitedNodes = new ArrayList<>();
- TraversalStatus<SimpleVertex> status = Traversal.breadthFirst(vtx0, v
-> {
+ SimpleNode vtx0 = graph.newNode("root");
+ SimpleNode vtx1 = graph.newNode("vertex1");
+ SimpleNode vtx11 = graph.newNode("vertex11");
+ SimpleNode vtx12 = graph.newNode("vertex12");
+ SimpleNode vtx2 = graph.newNode("vertex2");
+ SimpleNode vtx21 = graph.newNode("vertex21");
+ SimpleNode vtx211 = graph.newNode("vertex211");
+ SimpleNode vtx212 = graph.newNode("vertex212");
+
+ SimpleNode vtx22 = graph.newNode("vertex22");
+ SimpleNode vtx221 = graph.newNode("vertex221");
+ SimpleNode vtx222 = graph.newNode("vertex222");
+ SimpleNode vtx223 = graph.newNode("vertex223");
+
+ SimpleNode vtx3 = graph.newNode("vertex3");
+ SimpleNode vtx31 = graph.newNode("vertex31");
+ SimpleNode vtx32 = graph.newNode("vertex32");
+ SimpleNode vtx33 = graph.newNode("vertex33");
+
+ graph.newEdge("root->1", vtx0, vtx1);
+ graph.newEdge("root->2", vtx0, vtx2);
+ graph.newEdge("root->3", vtx0, vtx3);
+
+ graph.newEdge("1->11", vtx1, vtx11);
+ graph.newEdge("1->12", vtx1, vtx12);
+
+ graph.newEdge("2->21", vtx2, vtx21);
+ graph.newEdge("2->22", vtx2, vtx22);
+
+ graph.newEdge("21->211", vtx21, vtx211);
+ graph.newEdge("21->212", vtx21, vtx212);
+ graph.newEdge("211->21", vtx211, vtx21);
+
+ graph.newEdge("22->221", vtx22, vtx221);
+ graph.newEdge("22->222", vtx22, vtx222);
+ graph.newEdge("22->223", vtx22, vtx223);
+ graph.newEdge("223->root", vtx223, vtx0);
+
+ graph.newEdge("3->31", vtx3, vtx31);
+ graph.newEdge("3->32", vtx3, vtx32);
+ graph.newEdge("3->33", vtx3, vtx33);
+
+ List<SimpleNode> visitedNodes = new ArrayList<>();
+ TraversalStatus<SimpleNode> status = Traversal.breadthFirst(vtx0, (v,
s) -> {
log.debug("Visiting vertex " + v);
if (visitedNodes.contains(v)) {
throw new RuntimeException("Double visit of vertex: " + v);
@@ -476,30 +527,110 @@ class TraversalTest {
throw new RuntimeException("Error on node: " + v);
}
return true;
- }, true);
+ }, new TraversalFlags(false, true));
assertEquals(vtx0, visitedNodes.get(0));
assertEquals(vtx1, visitedNodes.get(1));
assertEquals(vtx2, visitedNodes.get(2));
assertEquals(vtx3, visitedNodes.get(3));
- assertEquals(vtx11, visitedNodes.get(4));
- assertEquals(vtx12, visitedNodes.get(5));
- assertEquals(vtx21, visitedNodes.get(6));
- assertEquals(vtx22, visitedNodes.get(7));
- assertEquals(vtx31, visitedNodes.get(8));
- assertEquals(vtx32, visitedNodes.get(9));
- assertEquals(vtx33, visitedNodes.get(10));
- assertEquals(vtx211, visitedNodes.get(11));
- assertEquals(vtx212, visitedNodes.get(12));
- assertEquals(vtx221, visitedNodes.get(13));
- assertEquals(vtx222, visitedNodes.get(14));
- assertEquals(vtx223, visitedNodes.get(15));
+ assertEquals(vtx223, visitedNodes.get(4));
+ assertEquals(vtx11, visitedNodes.get(5));
+ assertEquals(vtx12, visitedNodes.get(6));
+ assertEquals(vtx21, visitedNodes.get(7));
+ assertEquals(vtx22, visitedNodes.get(8));
+ assertEquals(vtx31, visitedNodes.get(9));
+ assertEquals(vtx32, visitedNodes.get(10));
+ assertEquals(vtx33, visitedNodes.get(11));
+ assertEquals(vtx211, visitedNodes.get(12));
+ assertEquals(vtx212, visitedNodes.get(13));
+ assertEquals(vtx221, visitedNodes.get(14));
+ assertEquals(vtx222, visitedNodes.get(15));
assertTrue(status.hasCycles());
- assertEquals(2, status.getCycleCount());
+ // Undirected graph
+ assertEquals(19, status.getCycleCount());
assertTrue(status.hasErrors());
assertEquals(3, status.getErrorList().size());
assertTrue(status.getErrorList().get(0).getException().getMessage().startsWith("Error
on node"));
}
+
+ @Test
+ void topologicalSort() {
+ SimpleGraph graph = new SimpleGraph();
+ SimpleNode vtx0 = graph.newNode("root");
+ SimpleNode vtx1 = graph.newNode("vertex1");
+ SimpleNode vtx11 = graph.newNode("vertex11");
+ SimpleNode vtx12 = graph.newNode("vertex12");
+ SimpleNode vtx2 = graph.newNode("vertex2");
+ SimpleNode vtx21 = graph.newNode("vertex21");
+ SimpleNode vtx211 = graph.newNode("vertex211");
+ SimpleNode vtx212 = graph.newNode("vertex212");
+
+ SimpleNode vtx22 = graph.newNode("vertex22");
+ SimpleNode vtx221 = graph.newNode("vertex221");
+ SimpleNode vtx222 = graph.newNode("vertex222");
+ SimpleNode vtx223 = graph.newNode("vertex223");
+
+ SimpleNode vtx3 = graph.newNode("vertex3");
+ SimpleNode vtx31 = graph.newNode("vertex31");
+ SimpleNode vtx32 = graph.newNode("vertex32");
+ SimpleNode vtx33 = graph.newNode("vertex33");
+ SimpleNode vtx331 = graph.newNode("vertex331");
+ SimpleNode vtx3311 = graph.newNode("vertex3311");
+
+
+ graph.newEdge("root->1", vtx0, vtx1);
+ graph.newEdge("root->2", vtx0, vtx2);
+ graph.newEdge("root->3", vtx0, vtx3);
+
+ graph.newEdge("1->11", vtx1, vtx11);
+ graph.newEdge("1->12", vtx1, vtx12);
+
+ graph.newEdge("2->21", vtx2, vtx21);
+ graph.newEdge("2->22", vtx2, vtx22);
+ graph.newEdge("22->2", vtx22, vtx2);
+
+ graph.newEdge("21->211", vtx21, vtx211);
+ graph.newEdge("21->212", vtx21, vtx212);
+
+ graph.newEdge("22->221", vtx22, vtx221);
+ graph.newEdge("22->222", vtx22, vtx222);
+ graph.newEdge("22->223", vtx22, vtx223);
+ graph.newEdge("223->root", vtx223, vtx0);
+
+ graph.newEdge("3->31", vtx3, vtx31);
+ graph.newEdge("3->32", vtx3, vtx32);
+ graph.newEdge("3->33", vtx3, vtx33);
+ graph.newEdge("33->331", vtx33, vtx331);
+ graph.newEdge("331->3311", vtx331, vtx3311);
+ graph.newEdge("22->33", vtx22, vtx33);
+ // graph.newEdge("33->22", vtx33, vtx22);
+
+
+ List<SimpleNode> result = Traversal.topologialSort(vtx0);
+
+ assertEquals(vtx11, result.get(0));
+ assertEquals(vtx12, result.get(1));
+ assertEquals(vtx1, result.get(2));
+ assertEquals(vtx211, result.get(3));
+ assertEquals(vtx212, result.get(4));
+ assertEquals(vtx21, result.get(5));
+ assertEquals(vtx221, result.get(6));
+ assertEquals(vtx222, result.get(7));
+ assertEquals(vtx223, result.get(8));
+ assertEquals(vtx3311, result.get(9));
+ assertEquals(vtx331, result.get(10));
+ assertEquals(vtx33, result.get(11));
+ assertEquals(vtx22, result.get(12));
+ assertEquals(vtx2, result.get(13));
+ assertEquals(vtx31, result.get(14));
+ assertEquals(vtx32, result.get(15));
+ assertEquals(vtx3, result.get(16));
+ assertEquals(vtx0, result.get(17));
+
+
+ }
+
+
}
\ No newline at end of file
