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 8e4b26c Reformatting code
8e4b26c is described below
commit 8e4b26c80bf8ad2a58c0dc33447ef16cbda4b19a
Author: Martin Stockhammer <[email protected]>
AuthorDate: Sat Nov 16 15:40:21 2019 +0100
Reformatting code
---
.../archiva/components/graph/api/Category.java | 5 +-
.../apache/archiva/components/graph/api/Edge.java | 35 +-
.../apache/archiva/components/graph/api/Graph.java | 68 +-
.../apache/archiva/components/graph/api/Node.java | 54 +-
.../archiva/components/graph/api/RelationType.java | 7 +-
.../components/graph/api/StandardRelationType.java | 5 +-
.../components/graph/api/TraversalStatus.java | 59 +-
.../archiva/components/graph/api/VisitError.java | 12 +-
.../archiva/components/graph/base/BaseEdge.java | 75 +-
.../components/graph/base/DirectedGraph.java | 198 ++--
.../archiva/components/graph/base/SimpleGraph.java | 39 +-
.../archiva/components/graph/base/SimpleNode.java | 114 +-
.../archiva/components/graph/util/Traversal.java | 297 ++++--
.../components/graph/util/TraversalFlags.java | 18 +-
.../components/graph/base/BaseEdgeTest.java | 90 +-
.../components/graph/base/SimpleGraphTest.java | 140 +--
.../components/graph/base/SimpleNodeTest.java | 134 +--
.../components/graph/util/TraversalTest.java | 1122 ++++++++++----------
graph/src/test/resources/log4j2-test.xml | 2 +-
19 files changed, 1361 insertions(+), 1113 deletions(-)
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/api/Category.java
b/graph/src/main/java/org/apache/archiva/components/graph/api/Category.java
index 16fb9cb..37de9ad 100644
--- a/graph/src/main/java/org/apache/archiva/components/graph/api/Category.java
+++ b/graph/src/main/java/org/apache/archiva/components/graph/api/Category.java
@@ -21,8 +21,9 @@ package org.apache.archiva.components.graph.api;
/**
* The category is used to shape the domain by grouping nodes.
*/
-public interface Category {
+public interface Category
+{
- String name();
+ String name( );
}
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 032da50..3d90b3f 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
@@ -19,52 +19,57 @@ package org.apache.archiva.components.graph.api;
*/
/**
- * The edge links a source vertex to a destination vertex.
+ * The edge links a source node to a destination node.
* A edge instance is always part of a certain graph instance.
*
- * @param <V> The vertex implementation.
+ * @param <V> The node implementation.
*/
-public interface Edge<V extends Node<V>> {
+public interface Edge<V extends Node<V>>
+{
/**
* Returns the identifier of this edge. The id must be unique for given
graph.
*
* @return the identifier of this edge
*/
- String getId();
+ String getId( );
/**
* Returns the label of this edge. The label must not be unique.
* If the label was not set, it should return an empty string.
+ *
* @return the label of this edge, or a empty string
*/
- String getLabel();
+ String getLabel( );
/**
* Sets the label of this edge to the given string.
+ *
* @param label the label string, that must not be <code>null</code>
* @throws NullPointerException if the label parameter is <code>null</code>
*/
- void setLabel(String label) throws NullPointerException;
+ void setLabel( String label ) throws NullPointerException;
/**
* Returns the graph where this edge was created.
*
* @return the graph instance
*/
- Graph<V> getGraph();
+ Graph<V> getGraph( );
/**
- * Returns the vertex, that is on the source end of this edge.
- * @return the source vertex
+ * Returns the node, that is on the source end of this edge.
+ *
+ * @return the source node
*/
- V getSource();
+ V getSource( );
/**
- * Returns the vertex, that is on the destination end of this edge.
- * @return the destination vertex
+ * Returns the node, that is on the destination end of this edge.
+ *
+ * @return the destination node
*/
- V getDestination();
+ V getDestination( );
/**
* Returns the weight of this edge. For standard graph implementations the
default should be 1.0, but
@@ -72,7 +77,7 @@ public interface Edge<V extends Node<V>> {
*
* @return the weight of this edge
*/
- double getWeight();
+ double getWeight( );
/**
* Returns the RelationType of the edge. If nothing is set, the {@link
StandardRelationType#DEFAULT} should
@@ -80,7 +85,7 @@ public interface Edge<V extends Node<V>> {
*
* @return the type of the edge
*/
- RelationType getType();
+ 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 af1c347..24715fc 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
@@ -22,13 +22,13 @@ import java.util.List;
import java.util.Set;
/**
- *
- * A graph is the container for vertices. The vertices are connected by edges.
Each vertex and
+ * A graph is the container for nodes. The nodes are connected by edges. Each
node and
* edge instance is coupled to the graph where it was created.
*
* @param <V>
*/
-public interface Graph<V extends Node<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
@@ -39,19 +39,19 @@ public interface Graph<V extends Node<V>> {
* @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);
+ 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 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);
+ V addNode( String id, String label );
- void removeNode(V node);
+ void removeNode( V node );
/**
@@ -59,62 +59,62 @@ public interface Graph<V extends Node<V>> {
* 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 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
+ * @throws IllegalArgumentException if source or destination is
<code>null</code>
*/
- Edge<V> newEdge(String label, V sourceNode, V destinationNode) throws
IllegalArgumentException;
+ 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 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
+ * @throws IllegalArgumentException if the source or destination node is
<code>null</code>
*/
- Edge<V> newEdge(RelationType type, String label, V sourceNode, V
destinationNode) throws IllegalArgumentException;
+ Edge<V> newEdge( RelationType type, String label, V sourceNode, V
destinationNode ) throws IllegalArgumentException;
/**
* 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 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
+ * @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>
*/
- Edge<V> addEdge(RelationType type, String id, String label, V sourceNode,
V destinationNode) throws IllegalArgumentException;
+ Edge<V> addEdge( RelationType type, String id, String label, V sourceNode,
V destinationNode ) throws IllegalArgumentException;
/**
* 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 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
+ * @throws IllegalArgumentException if source or destination is
<code>null</code>
*/
- Edge<V> addEdge(String id, String label, V sourceNode, V destinationNode)
throws IllegalArgumentException;
+ Edge<V> addEdge( String id, String label, V sourceNode, V destinationNode
) throws IllegalArgumentException;
/**
* 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<V> edge );
/**
* Returns the node with the given id
@@ -122,7 +122,7 @@ public interface Graph<V extends Node<V>> {
* @param id the node id
* @return the found node, or <code>null</code>, if it does not exist
*/
- V getNode(String id);
+ V getNode( String id );
/**
* Finds nodes using a given query. The query syntax depends on the graph
implementation.
@@ -130,7 +130,7 @@ public interface Graph<V extends Node<V>> {
* @param query the query to find nodes
* @return the found nodes, or a empty list
*/
- List<V> findNodes(String query);
+ List<V> findNodes( String query );
/**
* Returns the edge with the given id.
@@ -138,14 +138,14 @@ public interface Graph<V extends Node<V>> {
* @param id the edge id
* @return the found edge instance, or <code>null</code>, if it does not
exist
*/
- Edge<V> getEdge(String id);
+ Edge<V> getEdge( String id );
/**
* Returns all nodes of the graph
+ *
* @return
*/
- Set<V> getNodes();
-
+ Set<V> getNodes( );
}
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/api/Node.java
b/graph/src/main/java/org/apache/archiva/components/graph/api/Node.java
index e8a1c1c..be8b7d3 100644
--- a/graph/src/main/java/org/apache/archiva/components/graph/api/Node.java
+++ b/graph/src/main/java/org/apache/archiva/components/graph/api/Node.java
@@ -21,63 +21,71 @@ package org.apache.archiva.components.graph.api;
import java.util.List;
/**
- * The vertex is a node in a graph structure. The vertex may have connections
to and from
- * other vertices (edges).
+ * The node is a single entity in a graph structure. The node may have
connections to and from
+ * other nodes (represented by edges).
*
- * @param <V> The vertex implementation
+ * @param <V> The node implementation
*/
-public interface Node<V extends Node<V>> {
+public interface Node<V extends Node<V>>
+{
/**
- * Returns the identifier of this vertex. The identifier is unique for a
given graph.
+ * Returns the identifier of this node. The identifier is unique for a
given graph.
+ *
* @return the identifier
*/
- String getId();
+ String getId( );
/**
- * Returns the label of this vertex. The label is a name and must not be
unique.
+ * Returns the label of this node. The label is a name and must not be
unique.
* If the label was not set it should return a empty string.
- * @return the label of the vertex or a empty string
+ *
+ * @return the label of the node or a empty string
*/
- String getLabel();
+ String getLabel( );
/**
- * Sets the label of the vertex
+ * Sets the label of the node
+ *
* @param label sets the label string, must not be <code>null</code>
* @throws NullPointerException if the given label is <code>null</code>
*/
- void setLabel(String label) throws NullPointerException;
+ void setLabel( String label ) throws NullPointerException;
/**
- * Returns the graph where this vertex was created.
+ * Returns the graph where this node was created.
+ *
* @return the graph instance
*/
- Graph<V> getGraph();
+ Graph<V> getGraph( );
/**
* Returns all edges that connect to other nodes
- * @return the edges where this vertex is the source
+ *
+ * @return the edges where this node is the source
*/
- List<Edge<V>> getOutEdges();
+ List<Edge<V>> getOutEdges( );
/**
- * Returns all edges that connect other nodes to this vertex
- * @return the edges where this vertex is the destination
+ * Returns all edges that connect other nodes to this node
+ *
+ * @return the edges where this node is the destination
*/
- List<Edge<V>> getInEdges();
+ List<Edge<V>> getInEdges( );
/**
- * Returns the categories of the vertex.
+ * Returns the categories of the node.
*
- * @return the list of categories of the vertex
+ * @return the list of categories of the node
*/
- List<Category> getCategories();
+ List<Category> getCategories( );
/**
* Adds a category to the node
+ *
* @param category the category to add
*/
- void addCategory(Category category);
+ void addCategory( Category category );
/**
@@ -85,5 +93,5 @@ public interface Node<V extends Node<V>> {
*
* @param category the category to remove
*/
- void removeCategory(Category category);
+ void removeCategory( Category category );
}
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/api/RelationType.java
b/graph/src/main/java/org/apache/archiva/components/graph/api/RelationType.java
index dc83c01..5e93912 100644
---
a/graph/src/main/java/org/apache/archiva/components/graph/api/RelationType.java
+++
b/graph/src/main/java/org/apache/archiva/components/graph/api/RelationType.java
@@ -21,13 +21,14 @@ package org.apache.archiva.components.graph.api;
/**
* 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 interface RelationType
+{
/**
* The type name
+ *
* @return
*/
- String name();
+ String name( );
}
diff --git
a/graph/src/main/java/org/apache/archiva/components/graph/api/StandardRelationType.java
b/graph/src/main/java/org/apache/archiva/components/graph/api/StandardRelationType.java
index 21c45f8..30569d1 100644
---
a/graph/src/main/java/org/apache/archiva/components/graph/api/StandardRelationType.java
+++
b/graph/src/main/java/org/apache/archiva/components/graph/api/StandardRelationType.java
@@ -18,6 +18,7 @@ package org.apache.archiva.components.graph.api;
* under the License.
*/
-public enum StandardRelationType implements RelationType {
- DEFAULT,DIRECTED;
+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 1675537..ee8edd0 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,63 +27,76 @@ import java.util.List;
*
* @param <V>
*/
-public class TraversalStatus<V extends Node<V>> {
+public class TraversalStatus<V extends Node<V>>
+{
private int cycles = 0;
private List<VisitError<V>> errorList;
private List<V> cycleNodes;
- public TraversalStatus() {
+ public TraversalStatus( )
+ {
}
/**
* Returns the list of errors
- * @return a list of errors encountered while executing the consumer
function on vertices
+ *
+ * @return a list of errors encountered while executing the consumer
function on nodes
*/
- public List<VisitError<V>> getErrorList() {
+ public List<VisitError<V>> getErrorList( )
+ {
return errorList;
}
/**
* Returns true, if there were errors while running the consumer function.
+ *
* @return true, if errors occured on the consumer function, otherwise
false
*/
- public boolean hasErrors() {
- return errorList!=null && errorList.size()>0;
+ public boolean hasErrors( )
+ {
+ return errorList != null && errorList.size( ) > 0;
}
/**
* Add the given error to the list.
*
- * @param vertex the vertex, where the error occured
- * @param e the exception
+ * @param node the node, where the error occurred
+ * @param e the exception
*/
- public void addError(V vertex, Throwable e) {
- if (errorList==null) {
- errorList = new ArrayList<>();
+ public void addError( V node, Throwable e )
+ {
+ if ( errorList == null )
+ {
+ errorList = new ArrayList<>( );
}
- errorList.add(new VisitError(vertex, e));
+ errorList.add( new VisitError( node, e ) );
}
/**
* Add another cycle to the counter
+ *
* @param node
*/
- public void registerCycle(V node) {
+ public void registerCycle( V node )
+ {
cycles++;
- if (cycleNodes ==null) {
- cycleNodes = new ArrayList<>();
+ if ( cycleNodes == null )
+ {
+ cycleNodes = new ArrayList<>( );
}
- cycleNodes.add(node);
+ cycleNodes.add( node );
}
/**
* Returns true, if the traversal encountered a cycle.
+ *
* @return true, if cycle was encountered, otherwise false
*/
- public boolean hasCycles() {
- return cycles>0;
+ public boolean hasCycles( )
+ {
+ return cycles > 0;
}
/**
@@ -91,17 +104,19 @@ public class TraversalStatus<V extends Node<V>> {
*
* @return
*/
- public int getCycleCount() {
+ public int getCycleCount( )
+ {
return cycles;
}
/**
- * Returns the vertices, where cycles were detected. The list may contain
+ * Returns the nodes, where cycles were detected. The list may contain
* duplicated entries, if cycles where detected on different paths.
*
- * @return the list of vertices where cycles were detected
+ * @return the list of nodes where cycles were detected
*/
- public List<V> getCycleNodes() {
+ 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 7e116a7..2205947 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,25 @@ package org.apache.archiva.components.graph.api;
* under the License.
*/
-public class VisitError<V extends Node<V>> {
+public class VisitError<V extends Node<V>>
+{
private final Throwable exception;
private final V node;
- public VisitError(V node, Throwable exception) {
+ public VisitError( V node, Throwable exception )
+ {
this.exception = exception;
this.node = node;
}
- public Throwable getException() {
+ public Throwable getException( )
+ {
return exception;
}
- public V getNode() {
+ 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 39cb5cf..1b6cb55 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,9 +18,20 @@ package org.apache.archiva.components.graph.base;
* under the License.
*/
-import org.apache.archiva.components.graph.api.*;
-
-public class BaseEdge<V extends Node<V>> implements Edge<V>,
Comparable<BaseEdge<V>> {
+import org.apache.archiva.components.graph.api.Edge;
+import org.apache.archiva.components.graph.api.Graph;
+import org.apache.archiva.components.graph.api.Node;
+import org.apache.archiva.components.graph.api.RelationType;
+import org.apache.archiva.components.graph.api.StandardRelationType;
+
+/**
+ * Base edge implementation.
+ * Uses a default weight of 1.0
+ *
+ * @param <V>
+ */
+public class BaseEdge<V extends Node<V>> implements Edge<V>,
Comparable<BaseEdge<V>>
+{
private final String id;
private String label;
@@ -30,7 +41,8 @@ public class BaseEdge<V extends Node<V>> implements Edge<V>,
Comparable<BaseEdge
private final Graph<V> graph;
private final RelationType type;
- public BaseEdge(Graph<V> graph, String id, V sourceNode, V
destinationNode) {
+ public BaseEdge( Graph<V> graph, String id, V sourceNode, V
destinationNode )
+ {
this.id = id;
this.graph = graph;
this.sourceNode = sourceNode;
@@ -38,72 +50,89 @@ public class BaseEdge<V extends Node<V>> implements
Edge<V>, Comparable<BaseEdge
this.type = StandardRelationType.DEFAULT;
}
- public BaseEdge(Graph<V> graph, RelationType type, String id, V
sourceNode, V destinationNode) {
+ 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() {
+ public String getId( )
+ {
return id;
}
@Override
- public String getLabel() {
+ public String getLabel( )
+ {
return label;
}
- public void setLabel(String label) {
+ public void setLabel( String label )
+ {
this.label = label;
}
- public void setWeight(double weight) {
+ public void setWeight( double weight )
+ {
this.weight = weight;
}
@Override
- public Graph<V> getGraph() {
+ public Graph<V> getGraph( )
+ {
return graph;
}
@Override
- public V getSource() {
+ public V getSource( )
+ {
return sourceNode;
}
@Override
- public V getDestination() {
+ public V getDestination( )
+ {
return destinationNode;
}
@Override
- public double getWeight() {
+ public double getWeight( )
+ {
return weight;
}
@Override
- public RelationType getType() {
+ public RelationType getType( )
+ {
return type;
}
@Override
- public int hashCode() {
- return this.id.hashCode();
+ public int hashCode( )
+ {
+ return this.id.hashCode( );
}
@Override
- public String toString() {
- return this.id+"("+this.label+")("+ sourceNode.getId()+ " -> " +
destinationNode.getId()+")";
+ public String toString( )
+ {
+ return this.id + "(" + this.label + ")(" + sourceNode.getId( ) + " ->
" + destinationNode.getId( ) + ")";
}
@Override
- public int compareTo(BaseEdge<V> o) {
- if (this.label!=null || o.getLabel()!=null) {
- return this.label.compareTo(o.getLabel());
- } else {
- return this.id.compareTo(o.getId());
+ public int compareTo( BaseEdge<V> o )
+ {
+ if ( this.label != null || o.getLabel( ) != null )
+ {
+ return this.label.compareTo( o.getLabel( ) );
+ }
+ else
+ {
+ 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 d53557b..d541b63 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,159 +18,205 @@ package org.apache.archiva.components.graph.base;
* under the License.
*/
-import org.apache.archiva.components.graph.api.*;
+import org.apache.archiva.components.graph.api.Edge;
+import org.apache.archiva.components.graph.api.Graph;
+import org.apache.archiva.components.graph.api.Node;
+import org.apache.archiva.components.graph.api.RelationType;
+import org.apache.archiva.components.graph.api.StandardRelationType;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
-import java.util.*;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Set;
+import java.util.TreeMap;
+import java.util.UUID;
import java.util.stream.Collectors;
/**
* Abstract implementation of a directed graph
- * @param <V> The vertex implementation.
+ *
+ * @param <V> The node implementation.
*/
-public abstract class DirectedGraph<V extends Node<V>> implements Graph<V> {
+public abstract class DirectedGraph<V extends Node<V>> implements Graph<V>
+{
- private static final Logger log =
LoggerFactory.getLogger(DirectedGraph.class);
+ private static final Logger log = LoggerFactory.getLogger(
DirectedGraph.class );
- protected TreeMap<String, V> nodes = new TreeMap<>();
- protected TreeMap<String, Edge<V>> edges = new TreeMap<>();
+ protected TreeMap<String, V> nodes = new TreeMap<>( );
+ protected TreeMap<String, Edge<V>> edges = new TreeMap<>( );
- public V newNode(String label) {
- V vtx = createNewNode();
- vtx.setLabel(label);
- this.nodes.put(vtx.getId(), vtx);
- return vtx;
+ @Override
+ public V newNode( String label )
+ {
+ V node = createNewNode( );
+ node.setLabel( label );
+ this.nodes.put( node.getId( ), node );
+ return node;
}
@Override
- public V addNode(String id, String label) {
+ 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);
+ if ( nodes.containsKey( id ) )
+ {
+ node = nodes.get( id );
}
- node.setLabel(label);
+ else
+ {
+ node = createNewNode( id );
+ this.nodes.put( id, node );
+ }
+ node.setLabel( label );
return node;
}
- protected V createNewNode() {
- return createNewNode(UUID.randomUUID().toString());
+ 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.
+ * Subclasses that implement this method must return a new node instance
for
+ * each call. The node should not be connected with any edges.
*
- * @return A new vertex instance.
+ * @return A new node instance.
*/
- abstract V createNewNode(String id);
-
+ abstract V createNewNode( String id );
- protected Edge<V> createNewEdge(RelationType type, V sourceVertex, V
destinationVertex) {
- return createNewEdge(type, UUID.randomUUID().toString(), sourceVertex,
destinationVertex);
+ /**
+ * Creates a new edge instance on each method call. The id will be a
generated UUID.
+ *
+ * @param type the relation type
+ * @param sourceNode the source node
+ * @param destinationNode the destination node
+ * @return the new edge instance
+ */
+ protected Edge<V> createNewEdge( RelationType type, V sourceNode, V
destinationNode )
+ {
+ return createNewEdge( type, UUID.randomUUID( ).toString( ),
sourceNode, destinationNode );
}
/**
* 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
+ * the given source and destination nodes. The nodes must be linked by the
new
* edge.
*
- * @param type the type of the edge
- * @param sourceVertex the source vertex
- * @param destinationVertex the destination vertex
+ * @param type the type of the edge
+ * @param id the id of the new edge
+ * @param sourceNode the source node
+ * @param destinationNode the destination node
* @return A new edge instance.
*/
- abstract Edge<V> createNewEdge(RelationType type, String id, V
sourceVertex, V destinationVertex);
+ abstract Edge<V> createNewEdge( RelationType type, String id, V
sourceNode, V destinationNode );
@Override
- public Edge<V> newEdge(String label, V sourceNode, V destinationNode) {
- return newEdge(StandardRelationType.DEFAULT, label, sourceNode,
destinationNode);
+ public Edge<V> newEdge( String label, V sourceNode, V destinationNode )
+ {
+ return newEdge( StandardRelationType.DEFAULT, label, sourceNode,
destinationNode );
}
@Override
- public Edge<V> newEdge(RelationType type, String label, V sourceNode, V
destinationNode) {
- if (sourceNode==null) {
- throw new IllegalArgumentException("Source node may not be null");
+ 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");
+ 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);
+ Edge<V> edge = createNewEdge( type, sourceNode, destinationNode );
+ edge.setLabel( label );
+ this.edges.put( edge.getId( ), edge );
return edge;
}
@Override
- 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");
+ 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");
+ 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);
+ 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());
+ 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);
+ 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);
+ public V getNode( String id )
+ {
+ return nodes.get( id );
}
@Override
- public Edge<V> getEdge(String id) {
- return edges.get(id);
+ public Edge<V> getEdge( String id )
+ {
+ return edges.get( id );
}
@Override
- public Set<V> getNodes() {
- return nodes.values().stream().collect(Collectors.toSet());
+ public Set<V> getNodes( )
+ {
+ return nodes.values( ).stream( ).collect( Collectors.toSet( ) );
}
@Override
- public List<V> findNodes(String query) {
+ 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);
+ 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);
+ rmEdges = new ArrayList<>( node.getOutEdges( ) );
+ for ( Edge<V> edge : rmEdges )
+ {
+ removeEdge( edge );
}
- nodes.remove(node.getId());
+ nodes.remove( node.getId( ) );
}
@Override
- public void removeEdge(Edge<V> edge) {
- edges.remove(edge.getId());
+ 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 3497b07..baa379e 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
@@ -25,43 +25,46 @@ import java.util.List;
/**
* Simple directed graph implementation that uses UUIDs as unique identifiers
for
- * each vertex and edge.
- *
- *
+ * each node and edge.
*/
-public class SimpleGraph extends DirectedGraph<SimpleNode> {
+public class SimpleGraph extends DirectedGraph<SimpleNode>
+{
@Override
- SimpleNode createNewNode(String id) {
- return new SimpleNode(this, id);
+ SimpleNode createNewNode( String id )
+ {
+ return new SimpleNode( this, id );
}
-
@Override
- 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);
+ Edge<SimpleNode> createNewEdge( RelationType type, String id, SimpleNode
sourceNode, SimpleNode destinationNode )
+ {
+ BaseEdge edge = new BaseEdge<>( this, id, sourceNode, destinationNode
);
+ addEdgeToNode( sourceNode, edge );
+ addEdgeToNode( destinationNode, edge );
return edge;
}
- private void addEdgeToNode(SimpleNode vertex, Edge<SimpleNode> edge) {
- vertex.addEdge(edge);
+ private void addEdgeToNode( SimpleNode node, Edge<SimpleNode> edge )
+ {
+ node.addEdge( edge );
}
@Override
- public List<SimpleNode> findNodes(String query) {
+ public List<SimpleNode> findNodes( String query )
+ {
return null;
}
@Override
- public void removeEdge(Edge<SimpleNode> edge) {
- super.removeEdge(edge);
- edge.getSource().removeEdge(edge);
- edge.getDestination().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/SimpleNode.java
b/graph/src/main/java/org/apache/archiva/components/graph/base/SimpleNode.java
index 9f1dfd0..aba5ec8 100644
---
a/graph/src/main/java/org/apache/archiva/components/graph/base/SimpleNode.java
+++
b/graph/src/main/java/org/apache/archiva/components/graph/base/SimpleNode.java
@@ -27,7 +27,7 @@ import java.util.ArrayList;
import java.util.List;
/**
- * Simple vertex implementation. The hash value is based on the id.
+ * Simple node implementation. The hash value is based on the id.
* Comparation is by label, if exists, otherwise by id.
*/
public class SimpleNode implements Node<SimpleNode>, Comparable<SimpleNode>
@@ -36,101 +36,131 @@ public class SimpleNode implements Node<SimpleNode>,
Comparable<SimpleNode>
private final String id;
private String label;
private final Graph<SimpleNode> graph;
- private List<Edge<SimpleNode>> outEdges = new ArrayList<>();
- private List<Edge<SimpleNode>> inEdges = new ArrayList<>();
+ private List<Edge<SimpleNode>> outEdges = new ArrayList<>( );
+ private List<Edge<SimpleNode>> inEdges = new ArrayList<>( );
private List<Category> categories;
- SimpleNode(Graph<SimpleNode> graph, String id) {
+ SimpleNode( Graph<SimpleNode> graph, String id )
+ {
this.id = id;
this.graph = graph;
}
@Override
- public String getId() {
+ public String getId( )
+ {
return id;
}
@Override
- public String getLabel() {
+ public String getLabel( )
+ {
return label;
}
@Override
- public void setLabel(String label) {
+ public void setLabel( String label )
+ {
this.label = label;
}
@Override
- public Graph<SimpleNode> getGraph() {
+ public Graph<SimpleNode> getGraph( )
+ {
return graph;
}
@Override
- public List<Edge<SimpleNode>> getOutEdges() {
+ public List<Edge<SimpleNode>> getOutEdges( )
+ {
return outEdges;
}
@Override
- public List<Edge<SimpleNode>> getInEdges() {
+ public List<Edge<SimpleNode>> getInEdges( )
+ {
return inEdges;
}
- protected void addEdge(Edge<SimpleNode> edge) {
- if (edge.getSource() == this) {
- outEdges.add(edge);
- } else if (edge.getDestination() == this) {
- inEdges.add(edge);
- } else {
- throw new IllegalArgumentException("The given edge does not
contain this vertex");
+ protected void addEdge( Edge<SimpleNode> edge )
+ {
+ if ( edge.getSource( ) == this )
+ {
+ outEdges.add( edge );
+ }
+ else if ( edge.getDestination( ) == this )
+ {
+ inEdges.add( edge );
+ }
+ else
+ {
+ throw new IllegalArgumentException( "The given edge does not
contain this node" );
}
}
@Override
- public int hashCode() {
- return this.id.hashCode();
+ public int hashCode( )
+ {
+ return this.id.hashCode( );
}
@Override
- public String toString() {
- return this.id+"("+this.label+")";
+ public String toString( )
+ {
+ return this.id + "(" + this.label + ")";
}
- public void removeEdge(Edge<SimpleNode> edge) {
- if (edge.getDestination()==this) {
- inEdges.remove(edge);
- } else if (edge.getSource()==this) {
- outEdges.remove(edge);
+ public void removeEdge( Edge<SimpleNode> edge )
+ {
+ if ( edge.getDestination( ) == this )
+ {
+ inEdges.remove( edge );
+ }
+ else if ( edge.getSource( ) == this )
+ {
+ outEdges.remove( edge );
}
}
@Override
- 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 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<>();
+ public void addCategory( Category category )
+ {
+ if ( this.categories == null )
+ {
+ this.categories = new ArrayList<>( );
}
- if (!this.categories.contains(category)) {
- this.categories.add(category);
+ if ( !this.categories.contains( category ) )
+ {
+ this.categories.add( category );
}
}
- public void removeCategory(Category category) {
- if (this.categories != null) {
- this.categories.remove(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<>();
+ 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 e55f7f9..918ae0e 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
@@ -24,15 +24,23 @@ import
org.apache.archiva.components.graph.api.TraversalStatus;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
-import java.util.*;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Queue;
+import java.util.Set;
+import java.util.Stack;
import java.util.function.BiFunction;
/**
* Utility class for graph traversal.
*/
-public class Traversal {
+public class Traversal
+{
- private static final Logger log = LoggerFactory.getLogger(Traversal.class);
+ private static final Logger log = LoggerFactory.getLogger( Traversal.class
);
/**
* Traverses the graph starting at the start node and using a depth first
algorithm.
@@ -42,81 +50,107 @@ public class Traversal {
* 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.
*
- * @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 flags Sets some flags for traversal behaviour
+ * @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 flags Sets some flags for traversal behaviour
* @param <V>
* @return The traversal status
*/
- 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 node = stack.peek();
- if (!visited.contains(node)) {
+ 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 node = stack.peek( );
+ if ( !visited.contains( node ) )
+ {
Boolean continueTraversal = Boolean.TRUE;
- try {
- continueTraversal = consumer.apply(node, status);
- } catch (Throwable e) {
- log.debug("Error during visit. Node: {}, Message: {}",
node, e.getMessage());
- status.addError(node, e);
- if (!flags.isContinueOnError()) {
+ try
+ {
+ continueTraversal = consumer.apply( node, status );
+ }
+ catch ( Throwable e )
+ {
+ log.debug( "Error during visit. Node: {}, Message: {}",
node, e.getMessage( ) );
+ status.addError( node, e );
+ if ( !flags.isContinueOnError( ) )
+ {
break;
}
}
- visited.add(node);
- log.debug("Visited: " + node);
- if (!continueTraversal) {
- log.debug("Aborting from consumer on node {}",
node.getId());
+ 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 = node.getOutEdges();
- final int outEdgeMaxIdx = node.getOutEdges().size() - 1;
- for (int i = outEdgeMaxIdx; i >= 0; i--) {
- try {
- Edge<V> v = outEdges.get(i);
- 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);
+ 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 );
+ 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: " + node + " Index: " + i);
+ }
+ catch ( IndexOutOfBoundsException e )
+ {
+ log.warn( "Modification of graph during traversal of
output edges: " + node + " Index: " + i );
}
}
- 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());
- if (!visited.contains(source)) {
- stack.push(source);
- } else if (stack.contains(source)) {
- status.registerCycle(source);
+ 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( )
);
+ if ( !visited.contains( source ) )
+ {
+ stack.push( source );
}
- } catch (IndexOutOfBoundsException e) {
- log.warn("Modification of graph during traversal
of input edges: " + node + " Index: " + i);
+ else if ( stack.contains( source ) )
+ {
+ status.registerCycle( source );
+ }
+ }
+ catch ( IndexOutOfBoundsException e )
+ {
+ log.warn( "Modification of graph during traversal
of input edges: " + node + " Index: " + i );
}
}
}
- } else {
- node = stack.pop();
- if (!afterChildConsumer.apply(node, status)) {
- log.debug("Aborting from after child consumer on node {}",
node.getId());
+ }
+ else
+ {
+ node = stack.pop( );
+ if ( !afterChildConsumer.apply( node, status ) )
+ {
+ log.debug( "Aborting from after child consumer on node
{}", node.getId( ) );
break;
}
}
@@ -124,17 +158,19 @@ public class Traversal {
return status;
}
- 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);
+ 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(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 Node<V>> TraversalStatus<V> depthFirst(V start,
BiFunction<V, TraversalStatus<V>, Boolean> consumer) {
- return depthFirst(start, consumer, new TraversalFlags());
+ public static <V extends Node<V>> TraversalStatus<V> depthFirst( V start,
BiFunction<V, TraversalStatus<V>, Boolean> consumer )
+ {
+ return depthFirst( start, consumer, new TraversalFlags( ) );
}
/**
@@ -146,49 +182,62 @@ public class Traversal {
* 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 flags flags that control traversal behaviour
+ * @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 flags flags that control traversal behaviour
* @param <V>
* @return The traversal status
*/
- @SuppressWarnings("Duplicates")
- 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 node = queue.poll();
- if (!visited.contains(node)) {
+ @SuppressWarnings( "Duplicates" )
+ 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 node = queue.poll( );
+ if ( !visited.contains( node ) )
+ {
Boolean continueTraversal = Boolean.TRUE;
- try {
- continueTraversal = consumer.apply(node, status);
- } catch (Throwable e) {
- log.debug("Error during visit. Node: {}, Message: {}",
node, e.getMessage());
- status.addError(node, e);
- if (!flags.isContinueOnError()) {
+ try
+ {
+ continueTraversal = consumer.apply( node, status );
+ }
+ catch ( Throwable e )
+ {
+ log.debug( "Error during visit. Node: {}, Message: {}",
node, e.getMessage( ) );
+ status.addError( node, e );
+ if ( !flags.isContinueOnError( ) )
+ {
break;
}
}
- visited.add(node);
- log.debug("Visited: " + node);
- if (!continueTraversal) {
+ visited.add( node );
+ log.debug( "Visited: " + node );
+ if ( !continueTraversal )
+ {
break;
}
- for (Edge<V> v : node.getOutEdges()) {
- queue.add(v.getDestination());
+ for ( Edge<V> v : node.getOutEdges( ) )
+ {
+ queue.add( v.getDestination( ) );
}
- if (!flags.isDirected()) {
- for (Edge<V> v : node.getInEdges()) {
- queue.add(v.getSource());
+ if ( !flags.isDirected( ) )
+ {
+ for ( Edge<V> v : node.getInEdges( ) )
+ {
+ queue.add( v.getSource( ) );
}
}
- } else if (!flags.isDirected()) {
- status.registerCycle(node);
+ }
+ else if ( !flags.isDirected( ) )
+ {
+ status.registerCycle( node );
}
}
return status;
@@ -198,8 +247,9 @@ public class Traversal {
* 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 Node<V>> TraversalStatus<V> breadthFirst(final V
start, final BiFunction<V, TraversalStatus<V>, Boolean> consumer) {
- return breadthFirst(start, consumer, new TraversalFlags());
+ 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( ) );
}
/**
@@ -210,23 +260,29 @@ public class Traversal {
* @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();
+ 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 {
+ 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;
}
}
@@ -234,16 +290,21 @@ public class Traversal {
/**
* 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();
+ 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( );
}
}
@@ -256,10 +317,14 @@ public class Traversal {
* @param <V>
* @return A list of sorted nodes
*/
- 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());
+ 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
index 1019a54..8481401 100644
---
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
@@ -21,21 +21,25 @@ package org.apache.archiva.components.graph.util;
/**
* Flags that control traversal behaviour
*/
-public class TraversalFlags {
+public class TraversalFlags
+{
private final boolean directed;
private final boolean continueOnError;
- public TraversalFlags() {
+ public TraversalFlags( )
+ {
this.directed = true;
this.continueOnError = true;
}
- public TraversalFlags(boolean directed, boolean continueOnError) {
+ public TraversalFlags( boolean directed, boolean continueOnError )
+ {
this.directed = directed;
this.continueOnError = continueOnError;
}
- public TraversalFlags(boolean directed, boolean continueOnError, boolean
consumeParentAfterChild) {
+ public TraversalFlags( boolean directed, boolean continueOnError, boolean
consumeParentAfterChild )
+ {
this.directed = directed;
this.continueOnError = continueOnError;
}
@@ -48,7 +52,8 @@ public class TraversalFlags {
*
* @return true, if the graph is directed otherwise false
*/
- public boolean isDirected() {
+ public boolean isDirected( )
+ {
return directed;
}
@@ -59,7 +64,8 @@ public class TraversalFlags {
*
* @return <code>true</code>, if traversal should continue on error,
otherwise <code>false</code>
*/
- public boolean isContinueOnError() {
+ 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 02e3f47..acc3490 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
@@ -23,86 +23,92 @@ import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
-class BaseEdgeTest {
+class BaseEdgeTest
+{
- private Graph<SimpleNode> graph = new SimpleGraph();
+ private Graph<SimpleNode> graph = new SimpleGraph( );
@Test
- void getId() {
- SimpleNode vtx1 = new SimpleNode(graph, "vtx1");
- SimpleNode vtx2 = new SimpleNode(graph, "vtx2");
+ void getId( )
+ {
+ SimpleNode vtx1 = new SimpleNode( graph, "vtx1" );
+ SimpleNode vtx2 = new SimpleNode( graph, "vtx2" );
- BaseEdge<SimpleNode> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
+ BaseEdge<SimpleNode> edge = new BaseEdge<>( graph, "edge01", vtx1,
vtx2 );
- assertNotNull(edge.getId());
- assertEquals("edge01", edge.getId());
+ assertNotNull( edge.getId( ) );
+ assertEquals( "edge01", edge.getId( ) );
}
@Test
- void getLabel() {
- SimpleNode vtx1 = new SimpleNode(graph, "vtx1");
- SimpleNode vtx2 = new SimpleNode(graph, "vtx2");
+ void getLabel( )
+ {
+ SimpleNode vtx1 = new SimpleNode( graph, "vtx1" );
+ SimpleNode vtx2 = new SimpleNode( graph, "vtx2" );
- BaseEdge<SimpleNode> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
+ BaseEdge<SimpleNode> edge = new BaseEdge<>( graph, "edge01", vtx1,
vtx2 );
- assertNull(edge.getLabel());
+ assertNull( edge.getLabel( ) );
- edge.setLabel("edgelabel01");
+ edge.setLabel( "edgelabel01" );
- assertEquals("edgelabel01", edge.getLabel());
+ assertEquals( "edgelabel01", edge.getLabel( ) );
- edge.setLabel("Another label with exotic characters äÄö~§");
- assertEquals("Another label with exotic characters äÄö~§",
edge.getLabel());
+ edge.setLabel( "Another label with exotic characters äÄö~§" );
+ assertEquals( "Another label with exotic characters äÄö~§",
edge.getLabel( ) );
}
@Test
- void setWeight() {
- SimpleNode vtx1 = new SimpleNode(graph, "vtx1");
- SimpleNode vtx2 = new SimpleNode(graph, "vtx2");
+ void setWeight( )
+ {
+ SimpleNode vtx1 = new SimpleNode( graph, "vtx1" );
+ SimpleNode vtx2 = new SimpleNode( graph, "vtx2" );
- BaseEdge<SimpleNode> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
+ BaseEdge<SimpleNode> edge = new BaseEdge<>( graph, "edge01", vtx1,
vtx2 );
- assertEquals(1.0, edge.getWeight());
-
- edge.setWeight(1.5);
- assertEquals(1.5, edge.getWeight());
+ assertEquals( 1.0, edge.getWeight( ) );
+ edge.setWeight( 1.5 );
+ assertEquals( 1.5, edge.getWeight( ) );
}
@Test
- void getGraph() {
- SimpleNode vtx1 = new SimpleNode(graph, "vtx1");
- SimpleNode vtx2 = new SimpleNode(graph, "vtx2");
-
- BaseEdge<SimpleNode> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
- assertNotNull(edge.getGraph());
- assertTrue(edge.getGraph() == graph);
+ void getGraph( )
+ {
+ SimpleNode vtx1 = new SimpleNode( graph, "vtx1" );
+ SimpleNode vtx2 = new SimpleNode( graph, "vtx2" );
+
+ BaseEdge<SimpleNode> edge = new BaseEdge<>( graph, "edge01", vtx1,
vtx2 );
+ assertNotNull( edge.getGraph( ) );
+ assertTrue( edge.getGraph( ) == graph );
}
@Test
- void getInVertex() {
- SimpleNode vtx1 = new SimpleNode(graph, "vtx1");
- SimpleNode vtx2 = new SimpleNode(graph, "vtx2");
+ void getInVertex( )
+ {
+ SimpleNode vtx1 = new SimpleNode( graph, "vtx1" );
+ SimpleNode vtx2 = new SimpleNode( graph, "vtx2" );
- BaseEdge<SimpleNode> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
+ BaseEdge<SimpleNode> edge = new BaseEdge<>( graph, "edge01", vtx1,
vtx2 );
- assertEquals(vtx1, edge.getSource());
+ assertEquals( vtx1, edge.getSource( ) );
}
@Test
- void getOutVertex() {
- SimpleNode vtx1 = new SimpleNode(graph, "vtx1");
- SimpleNode vtx2 = new SimpleNode(graph, "vtx2");
+ void getOutVertex( )
+ {
+ SimpleNode vtx1 = new SimpleNode( graph, "vtx1" );
+ SimpleNode vtx2 = new SimpleNode( graph, "vtx2" );
- BaseEdge<SimpleNode> edge = new BaseEdge<>(graph, "edge01", vtx1,
vtx2);
+ BaseEdge<SimpleNode> edge = new BaseEdge<>( graph, "edge01", vtx1,
vtx2 );
- assertEquals(vtx2, edge.getDestination());
+ assertEquals( vtx2, edge.getDestination( ) );
}
}
\ No newline at end of file
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 859a002..97c6943 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
@@ -24,120 +24,128 @@ import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
-class SimpleGraphTest {
+class SimpleGraphTest
+{
@Test
- void createNewNode() {
- SimpleGraph graph = new SimpleGraph();
- SimpleNode vtx = graph.createNewNode();
- assertNotNull(vtx);
- assertNotNull(vtx.getId());
- assertNotNull(java.util.UUID.fromString(vtx.getId()));
+ void createNewNode( )
+ {
+ SimpleGraph graph = new SimpleGraph( );
+ SimpleNode vtx = graph.createNewNode( );
+ assertNotNull( vtx );
+ assertNotNull( vtx.getId( ) );
+ assertNotNull( java.util.UUID.fromString( vtx.getId( ) ) );
}
@Test
- void createNewEdge() {
- SimpleGraph graph = new SimpleGraph();
- 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()));
- assertEquals(vtx1, edge.getSource());
- assertEquals(vtx2, edge.getDestination());
+ void createNewEdge( )
+ {
+ SimpleGraph graph = new SimpleGraph( );
+ 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( ) ) );
+ assertEquals( vtx1, edge.getSource( ) );
+ assertEquals( vtx2, edge.getDestination( ) );
}
@Test
- void removeEdge() {
- SimpleGraph graph = new SimpleGraph();
- SimpleNode vtx1 = graph.createNewNode();
- SimpleNode vtx2 = graph.createNewNode();
- Edge<SimpleNode> edge =
graph.createNewEdge(StandardRelationType.DEFAULT, vtx1, vtx2);
+ void removeEdge( )
+ {
+ SimpleGraph graph = new SimpleGraph( );
+ SimpleNode vtx1 = graph.createNewNode( );
+ SimpleNode vtx2 = graph.createNewNode( );
+ Edge<SimpleNode> edge = graph.createNewEdge(
StandardRelationType.DEFAULT, vtx1, vtx2 );
- graph.removeEdge(edge);
+ graph.removeEdge( edge );
- assertEquals(0, vtx1.getInEdges().size());
- assertEquals(0, vtx2.getInEdges().size());
- assertEquals(0, vtx1.getOutEdges().size());
- assertEquals(0, vtx2.getOutEdges().size());
+ assertEquals( 0, vtx1.getInEdges( ).size( ) );
+ assertEquals( 0, vtx2.getInEdges( ).size( ) );
+ assertEquals( 0, vtx1.getOutEdges( ).size( ) );
+ assertEquals( 0, vtx2.getOutEdges( ).size( ) );
}
@Test
- void removeNode() {
+ void removeNode( )
+ {
String label = "root";
- SimpleGraph graph = new SimpleGraph();
- SimpleNode node = graph.newNode(label);
+ SimpleGraph graph = new SimpleGraph( );
+ SimpleNode node = graph.newNode( label );
- assertNotNull(node);
- assertNotNull(graph.getNode(node.getId()));
+ assertNotNull( node );
+ assertNotNull( graph.getNode( node.getId( ) ) );
- graph.removeNode(node);
- assertNull(graph.getNode(node.getId()));
+ graph.removeNode( node );
+ assertNull( graph.getNode( node.getId( ) ) );
}
@Test
- void removeNodeWithEdges() {
+ 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);
+ 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( ) ) );
- assertNotNull(node1);
- assertNotNull(graph.getNode(node1.getId()));
+ graph.removeNode( node1 );
- graph.removeNode(node1);
+ assertNull( graph.getNode( node1.getId( ) ) );
- assertNull(graph.getNode(node1.getId()));
-
- assertEquals(0, node2.getInEdges().size());
- assertEquals(0, node2.getOutEdges().size());
+ assertEquals( 0, node2.getInEdges( ).size( ) );
+ assertEquals( 0, node2.getOutEdges( ).size( ) );
}
@Test
- void getNode() {
+ void getNode( )
+ {
String label = "root";
- SimpleGraph graph = new SimpleGraph();
- SimpleNode node = graph.newNode(label);
+ 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());
+ assertNotNull( node );
+ SimpleNode foundNode = graph.getNode( node.getId( ) );
+ assertNotNull( foundNode );
+ assertEquals( node, foundNode );
+ assertEquals( label, foundNode.getLabel( ) );
}
@Test
- void newNode() {
+ void newNode( )
+ {
String label = "root";
- SimpleGraph graph = new SimpleGraph();
- SimpleNode node = graph.newNode(label);
+ SimpleGraph graph = new SimpleGraph( );
+ SimpleNode node = graph.newNode( label );
- assertNotNull(node);
- assertEquals(label, node.getLabel());
+ assertNotNull( node );
+ assertEquals( label, node.getLabel( ) );
}
@Test
- void addNode() {
+ void addNode( )
+ {
String id = "root";
- SimpleGraph graph = new SimpleGraph();
- SimpleNode node = graph.addNode(id, id);
+ SimpleGraph graph = new SimpleGraph( );
+ SimpleNode node = graph.addNode( id, id );
- assertNotNull(node);
- assertNotNull(graph.getNode(id));
- assertEquals(id, graph.getNode(id).getLabel());
+ assertNotNull( node );
+ assertNotNull( graph.getNode( id ) );
+ assertEquals( id, graph.getNode( id ).getLabel( ) );
}
diff --git
a/graph/src/test/java/org/apache/archiva/components/graph/base/SimpleNodeTest.java
b/graph/src/test/java/org/apache/archiva/components/graph/base/SimpleNodeTest.java
index 9b849d2..c71eeee 100644
---
a/graph/src/test/java/org/apache/archiva/components/graph/base/SimpleNodeTest.java
+++
b/graph/src/test/java/org/apache/archiva/components/graph/base/SimpleNodeTest.java
@@ -24,89 +24,93 @@ import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
-class SimpleNodeTest {
+class SimpleNodeTest
+{
- private Graph<SimpleNode> graph = new SimpleGraph();
+ private Graph<SimpleNode> graph = new SimpleGraph( );
@Test
-
- void getId() {
- SimpleNode vtx = new SimpleNode(graph, "testid001");
- assertNotNull(vtx.getId());
- assertEquals("testid001", vtx.getId());
+ void getId( )
+ {
+ SimpleNode vtx = new SimpleNode( graph, "testid001" );
+ assertNotNull( vtx.getId( ) );
+ assertEquals( "testid001", vtx.getId( ) );
}
@Test
- void getLabel() {
- SimpleNode vtx = new SimpleNode(graph, "testid001");
- assertNull(vtx.getLabel());
- vtx.setLabel("test");
- assertEquals("test", vtx.getLabel());
+ void getLabel( )
+ {
+ SimpleNode vtx = new SimpleNode( graph, "testid001" );
+ assertNull( vtx.getLabel( ) );
+ vtx.setLabel( "test" );
+ assertEquals( "test", vtx.getLabel( ) );
- 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());
+ 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( ) );
}
@Test
- void getGraph() {
- SimpleNode vtx = new SimpleNode(graph, "test");
- assertNotNull(vtx.getGraph());
- assertTrue(vtx.getGraph() == graph);
+ void getGraph( )
+ {
+ SimpleNode vtx = new SimpleNode( graph, "test" );
+ assertNotNull( vtx.getGraph( ) );
+ assertTrue( vtx.getGraph( ) == graph );
}
@Test
- void getInOutEdges() {
- 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));
- vtx1.addEdge(new BaseEdge<>(graph, "edge14_1to2", vtx1, vtx2));
- vtx2.addEdge(new BaseEdge<>(graph, "edge21_1to2", vtx1, vtx2));
- vtx2.addEdge(new BaseEdge<>(graph, "edge22_1to2", vtx1, vtx2));
- vtx1.addEdge(new BaseEdge<>(graph, "edge11_2to1", vtx2, vtx1));
- vtx1.addEdge(new BaseEdge<>(graph, "edge12_2to1", vtx2, vtx1));
- vtx1.addEdge(new BaseEdge<>(graph, "edge13_2to1", vtx2, vtx1));
- vtx1.addEdge(new BaseEdge<>(graph, "edge14_2to1", vtx2, vtx1));
- 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));
- assertEquals(6, vtx1.getInEdges().size());
- assertEquals(2, vtx2.getInEdges().size());
- assertEquals(4, vtx1.getOutEdges().size());
- assertEquals(1, vtx2.getOutEdges().size());
+ void getInOutEdges( )
+ {
+ 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 ) );
+ vtx1.addEdge( new BaseEdge<>( graph, "edge14_1to2", vtx1, vtx2 ) );
+ vtx2.addEdge( new BaseEdge<>( graph, "edge21_1to2", vtx1, vtx2 ) );
+ vtx2.addEdge( new BaseEdge<>( graph, "edge22_1to2", vtx1, vtx2 ) );
+ vtx1.addEdge( new BaseEdge<>( graph, "edge11_2to1", vtx2, vtx1 ) );
+ vtx1.addEdge( new BaseEdge<>( graph, "edge12_2to1", vtx2, vtx1 ) );
+ vtx1.addEdge( new BaseEdge<>( graph, "edge13_2to1", vtx2, vtx1 ) );
+ vtx1.addEdge( new BaseEdge<>( graph, "edge14_2to1", vtx2, vtx1 ) );
+ 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 ) );
+ assertEquals( 6, vtx1.getInEdges( ).size( ) );
+ assertEquals( 2, vtx2.getInEdges( ).size( ) );
+ assertEquals( 4, vtx1.getOutEdges( ).size( ) );
+ assertEquals( 1, vtx2.getOutEdges( ).size( ) );
}
-
@Test
- void removeEdge() {
- 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));
- vtx1.addEdge(new BaseEdge<>(graph, "edge14_1to2", vtx1, vtx2));
- vtx2.addEdge(new BaseEdge<>(graph, "edge21_1to2", vtx1, vtx2));
- vtx2.addEdge(new BaseEdge<>(graph, "edge22_1to2", vtx1, vtx2));
- vtx1.addEdge(new BaseEdge<>(graph, "edge11_2to1", vtx2, vtx1));
- vtx1.addEdge(new BaseEdge<>(graph, "edge12_2to1", vtx2, vtx1));
- vtx1.addEdge(new BaseEdge<>(graph, "edge13_2to1", vtx2, vtx1));
- vtx1.addEdge(new BaseEdge<>(graph, "edge14_2to1", vtx2, vtx1));
- 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<SimpleNode> edge = vtx1.getOutEdges().get(0);
- vtx1.removeEdge(edge);
- edge = vtx1.getInEdges().get(0);
- vtx1.removeEdge(edge);
- assertEquals(5, vtx1.getInEdges().size());
- assertEquals(2, vtx2.getInEdges().size());
- assertEquals(3, vtx1.getOutEdges().size());
- assertEquals(1, vtx2.getOutEdges().size());
+ void removeEdge( )
+ {
+ 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 ) );
+ vtx1.addEdge( new BaseEdge<>( graph, "edge14_1to2", vtx1, vtx2 ) );
+ vtx2.addEdge( new BaseEdge<>( graph, "edge21_1to2", vtx1, vtx2 ) );
+ vtx2.addEdge( new BaseEdge<>( graph, "edge22_1to2", vtx1, vtx2 ) );
+ vtx1.addEdge( new BaseEdge<>( graph, "edge11_2to1", vtx2, vtx1 ) );
+ vtx1.addEdge( new BaseEdge<>( graph, "edge12_2to1", vtx2, vtx1 ) );
+ vtx1.addEdge( new BaseEdge<>( graph, "edge13_2to1", vtx2, vtx1 ) );
+ vtx1.addEdge( new BaseEdge<>( graph, "edge14_2to1", vtx2, vtx1 ) );
+ 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<SimpleNode> edge = vtx1.getOutEdges( ).get( 0 );
+ vtx1.removeEdge( edge );
+ edge = vtx1.getInEdges( ).get( 0 );
+ vtx1.removeEdge( edge );
+ assertEquals( 5, vtx1.getInEdges( ).size( ) );
+ assertEquals( 2, vtx2.getInEdges( ).size( ) );
+ assertEquals( 3, vtx1.getOutEdges( ).size( ) );
+ assertEquals( 1, vtx2.getOutEdges( ).size( ) );
}
}
\ No newline at end of file
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 7ae9f33..19634a8 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
@@ -26,608 +26,624 @@ 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.*;
-class TraversalTest {
+class TraversalTest
+{
- private static final Logger log =
LoggerFactory.getLogger(TraversalTest.class);
+ private static final Logger log = LoggerFactory.getLogger(
TraversalTest.class );
@Test
- void depthFirstWithoutCycleAndWithoutError() {
- 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("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);
+ void depthFirstWithoutCycleAndWithoutError( )
+ {
+ 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( "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);
+ visitedNodes.add( v );
return true;
- });
-
- assertEquals(vtx0, visitedNodes.get(0));
- assertEquals(vtx1, visitedNodes.get(1));
- assertEquals(vtx11, visitedNodes.get(2));
- assertEquals(vtx12, visitedNodes.get(3));
- assertEquals(vtx2, visitedNodes.get(4));
- assertEquals(vtx21, visitedNodes.get(5));
- assertEquals(vtx211, visitedNodes.get(6));
- assertEquals(vtx212, visitedNodes.get(7));
- assertEquals(vtx22, visitedNodes.get(8));
- assertEquals(vtx221, visitedNodes.get(9));
- assertEquals(vtx222, visitedNodes.get(10));
- assertEquals(vtx223, visitedNodes.get(11));
- assertEquals(vtx3, visitedNodes.get(12));
- assertEquals(vtx31, visitedNodes.get(13));
- assertEquals(vtx32, visitedNodes.get(14));
- assertEquals(vtx33, visitedNodes.get(15));
-
- assertFalse(status.hasCycles());
- assertFalse(status.hasErrors());
+ } );
+
+ assertEquals( vtx0, visitedNodes.get( 0 ) );
+ assertEquals( vtx1, visitedNodes.get( 1 ) );
+ assertEquals( vtx11, visitedNodes.get( 2 ) );
+ assertEquals( vtx12, visitedNodes.get( 3 ) );
+ assertEquals( vtx2, visitedNodes.get( 4 ) );
+ assertEquals( vtx21, visitedNodes.get( 5 ) );
+ assertEquals( vtx211, visitedNodes.get( 6 ) );
+ assertEquals( vtx212, visitedNodes.get( 7 ) );
+ assertEquals( vtx22, visitedNodes.get( 8 ) );
+ assertEquals( vtx221, visitedNodes.get( 9 ) );
+ assertEquals( vtx222, visitedNodes.get( 10 ) );
+ assertEquals( vtx223, visitedNodes.get( 11 ) );
+ assertEquals( vtx3, visitedNodes.get( 12 ) );
+ assertEquals( vtx31, visitedNodes.get( 13 ) );
+ assertEquals( vtx32, visitedNodes.get( 14 ) );
+ assertEquals( vtx33, visitedNodes.get( 15 ) );
+
+ assertFalse( status.hasCycles( ) );
+ assertFalse( status.hasErrors( ) );
}
@Test
- void depthFirstWithCycleAndWithoutError() {
- 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);
-
- 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);
+ void depthFirstWithCycleAndWithoutError( )
+ {
+ 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 );
+
+ 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);
+ visitedNodes.add( v );
return true;
- });
-
- assertEquals(vtx0, visitedNodes.get(0));
- assertEquals(vtx1, visitedNodes.get(1));
- assertEquals(vtx11, visitedNodes.get(2));
- assertEquals(vtx12, visitedNodes.get(3));
- assertEquals(vtx2, visitedNodes.get(4));
- assertEquals(vtx21, visitedNodes.get(5));
- assertEquals(vtx211, visitedNodes.get(6));
- assertEquals(vtx212, visitedNodes.get(7));
- assertEquals(vtx22, visitedNodes.get(8));
- assertEquals(vtx221, visitedNodes.get(9));
- assertEquals(vtx222, visitedNodes.get(10));
- assertEquals(vtx223, visitedNodes.get(11));
- assertEquals(vtx3, visitedNodes.get(12));
- assertEquals(vtx31, visitedNodes.get(13));
- assertEquals(vtx32, visitedNodes.get(14));
- assertEquals(vtx33, visitedNodes.get(15));
-
- assertTrue(status.hasCycles());
- assertEquals(2, status.getCycleCount());
- assertFalse(status.hasErrors());
+ } );
+
+ assertEquals( vtx0, visitedNodes.get( 0 ) );
+ assertEquals( vtx1, visitedNodes.get( 1 ) );
+ assertEquals( vtx11, visitedNodes.get( 2 ) );
+ assertEquals( vtx12, visitedNodes.get( 3 ) );
+ assertEquals( vtx2, visitedNodes.get( 4 ) );
+ assertEquals( vtx21, visitedNodes.get( 5 ) );
+ assertEquals( vtx211, visitedNodes.get( 6 ) );
+ assertEquals( vtx212, visitedNodes.get( 7 ) );
+ assertEquals( vtx22, visitedNodes.get( 8 ) );
+ assertEquals( vtx221, visitedNodes.get( 9 ) );
+ assertEquals( vtx222, visitedNodes.get( 10 ) );
+ assertEquals( vtx223, visitedNodes.get( 11 ) );
+ assertEquals( vtx3, visitedNodes.get( 12 ) );
+ assertEquals( vtx31, visitedNodes.get( 13 ) );
+ assertEquals( vtx32, visitedNodes.get( 14 ) );
+ assertEquals( vtx33, visitedNodes.get( 15 ) );
+
+ assertTrue( status.hasCycles( ) );
+ assertEquals( 2, status.getCycleCount( ) );
+ assertFalse( status.hasErrors( ) );
}
@Test
- void depthFirstWithCycleAndWithError() {
- 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);
-
- 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);
+ void depthFirstWithCycleAndWithError( )
+ {
+ 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 );
+
+ 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);
- if (v == vtx223 || v == vtx33 || v == vtx212) {
- throw new RuntimeException("Error for node " + v);
+ visitedNodes.add( v );
+ if ( v == vtx223 || v == vtx33 || v == vtx212 )
+ {
+ throw new RuntimeException( "Error for node " + v );
}
return true;
- });
-
- assertEquals(vtx0, visitedNodes.get(0));
- assertEquals(vtx1, visitedNodes.get(1));
- assertEquals(vtx11, visitedNodes.get(2));
- assertEquals(vtx12, visitedNodes.get(3));
- assertEquals(vtx2, visitedNodes.get(4));
- assertEquals(vtx21, visitedNodes.get(5));
- assertEquals(vtx211, visitedNodes.get(6));
- assertEquals(vtx212, visitedNodes.get(7));
- assertEquals(vtx22, visitedNodes.get(8));
- assertEquals(vtx221, visitedNodes.get(9));
- assertEquals(vtx222, visitedNodes.get(10));
- assertEquals(vtx223, visitedNodes.get(11));
- assertEquals(vtx3, visitedNodes.get(12));
- assertEquals(vtx31, visitedNodes.get(13));
- assertEquals(vtx32, visitedNodes.get(14));
- assertEquals(vtx33, visitedNodes.get(15));
-
- assertTrue(status.hasCycles());
- assertEquals(2, status.getCycleCount());
- assertTrue(status.hasErrors());
- assertEquals(3, status.getErrorList().size());
-
assertTrue(status.getErrorList().get(0).getException().getMessage().startsWith("Error
for node"));
+ } );
+
+ assertEquals( vtx0, visitedNodes.get( 0 ) );
+ assertEquals( vtx1, visitedNodes.get( 1 ) );
+ assertEquals( vtx11, visitedNodes.get( 2 ) );
+ assertEquals( vtx12, visitedNodes.get( 3 ) );
+ assertEquals( vtx2, visitedNodes.get( 4 ) );
+ assertEquals( vtx21, visitedNodes.get( 5 ) );
+ assertEquals( vtx211, visitedNodes.get( 6 ) );
+ assertEquals( vtx212, visitedNodes.get( 7 ) );
+ assertEquals( vtx22, visitedNodes.get( 8 ) );
+ assertEquals( vtx221, visitedNodes.get( 9 ) );
+ assertEquals( vtx222, visitedNodes.get( 10 ) );
+ assertEquals( vtx223, visitedNodes.get( 11 ) );
+ assertEquals( vtx3, visitedNodes.get( 12 ) );
+ assertEquals( vtx31, visitedNodes.get( 13 ) );
+ assertEquals( vtx32, visitedNodes.get( 14 ) );
+ assertEquals( vtx33, visitedNodes.get( 15 ) );
+
+ assertTrue( status.hasCycles( ) );
+ assertEquals( 2, status.getCycleCount( ) );
+ assertTrue( status.hasErrors( ) );
+ assertEquals( 3, status.getErrorList( ).size( ) );
+ assertTrue( status.getErrorList( ).get( 0 ).getException(
).getMessage( ).startsWith( "Error for node" ) );
}
@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));
+ 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();
- 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);
+ void breadthFirstWithoutCyclesAndWithoutError( )
+ {
+ 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( "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);
+ visitedNodes.add( v );
return 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));
-
- assertFalse(status.hasCycles());
- assertFalse(status.hasErrors());
+ } );
+
+ 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 ) );
+
+ assertFalse( status.hasCycles( ) );
+ assertFalse( status.hasErrors( ) );
}
@Test
- void breadthFirstWithCyclesAndWithoutError() {
- 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("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);
+ void breadthFirstWithCyclesAndWithoutError( )
+ {
+ 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( "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);
+ visitedNodes.add( v );
return 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(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(19, status.getCycleCount());
- assertFalse(status.hasErrors());
+ }, 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( 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( 19, status.getCycleCount( ) );
+ assertFalse( status.hasErrors( ) );
}
@Test
- void breadthFirstWithCyclesAndWithError() {
- 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("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);
+ void breadthFirstWithCyclesAndWithError( )
+ {
+ 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( "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);
- if (v == vtx212 || v == vtx31 || v == vtx21) {
- throw new RuntimeException("Error on node: " + v);
+ visitedNodes.add( v );
+ if ( v == vtx212 || v == vtx31 || v == vtx21 )
+ {
+ throw new RuntimeException( "Error on node: " + v );
}
return 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(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());
+ }, 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( 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( ) );
// 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"));
+ 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);
+ 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));
+ 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 ) );
}
diff --git a/graph/src/test/resources/log4j2-test.xml
b/graph/src/test/resources/log4j2-test.xml
index 4ed4e77..8389489 100644
--- a/graph/src/test/resources/log4j2-test.xml
+++ b/graph/src/test/resources/log4j2-test.xml
@@ -25,7 +25,7 @@
</appenders>
<loggers>
<logger name="org.apache.archiva" level="info"/>
- <logger name="org.apache.archiva.components.graph" level="info" />
+ <logger name="org.apache.archiva.components.graph" level="info"/>
<root level="error" includeLocation="true">
<appender-ref ref="console"/>
