diff options
| author | Andrew Branson <andrew.branson@cern.ch> | 2012-05-30 08:37:45 +0200 |
|---|---|---|
| committer | Andrew Branson <andrew.branson@cern.ch> | 2012-05-30 08:37:45 +0200 |
| commit | b086f57f56bf0eb9dab9cf321a0f69aaaae84347 (patch) | |
| tree | 8e6e26e8b7eed6abad7a17b093bdbb55c5e6b1ba /src/main/java/com/c2kernel/graph/traversal/GraphTraversal.java | |
| parent | 22088ae8d2d5ff390518dbe1c4372325ffb3a647 (diff) | |
Initial Maven Conversion
Diffstat (limited to 'src/main/java/com/c2kernel/graph/traversal/GraphTraversal.java')
| -rw-r--r-- | src/main/java/com/c2kernel/graph/traversal/GraphTraversal.java | 85 |
1 files changed, 85 insertions, 0 deletions
diff --git a/src/main/java/com/c2kernel/graph/traversal/GraphTraversal.java b/src/main/java/com/c2kernel/graph/traversal/GraphTraversal.java new file mode 100644 index 0000000..0d9c819 --- /dev/null +++ b/src/main/java/com/c2kernel/graph/traversal/GraphTraversal.java @@ -0,0 +1,85 @@ +package com.c2kernel.graph.traversal;
+
+
+import java.util.Vector;
+
+import com.c2kernel.graph.model.GraphModel;
+import com.c2kernel.graph.model.Vertex;
+
+
+public class GraphTraversal
+{
+ public static final int kUp = 1;
+ public static final int kDown = 2;
+
+
+ private GraphTraversal()
+ {
+ }
+
+
+ public static Vertex[] getTraversal(GraphModel graphModel, Vertex startVertex, int direction, boolean ignoreBackLinks)
+ {
+ Vector<Vertex> path = new Vector<Vertex>(10, 10);
+
+ graphModel.clearTags(startVertex);
+ visitVertex(startVertex, graphModel, path, direction, startVertex, ignoreBackLinks);
+
+ return vectorToVertexArray(path);
+ }
+
+
+ private static void visitVertex(Vertex vertex, GraphModel graphModel, Vector<Vertex> path, int direction, Object tag, boolean ignoreBackLinks)
+ {
+ Vertex[] children = null;
+ int i = 0;
+
+ if(direction == kDown)
+ {
+ children = graphModel.getOutVertices(vertex);
+ }
+ else
+ {
+ children = graphModel.getInVertices(vertex);
+ }
+
+ vertex.setTag(tag);
+ path.add(vertex);
+
+ for(i=0; i<children.length; i++)
+ {
+ if(!(children[i].hasTag(tag)))
+ {
+ boolean skipBackLink = false;
+ if ( ignoreBackLinks &&
+ ((vertex.isJoin() && direction == kUp) ||
+ (vertex.isLoop() && direction == kDown))) {
+ Vertex[] following = getTraversal(graphModel, children[i], direction, false);
+ for (Vertex element : following) {
+ if (element == vertex) {
+ skipBackLink = true;
+ break;
+ }
+ }
+ }
+ if (!skipBackLink)
+ visitVertex(children[i], graphModel, path, direction, tag, ignoreBackLinks);
+ }
+ }
+ }
+
+
+ private static Vertex[] vectorToVertexArray(Vector<Vertex> vector)
+ {
+ Vertex[] vertices = new Vertex[vector.size()];
+ int i = 0;
+
+
+ for(i=0; i<vertices.length; i++)
+ {
+ vertices[i] = vector.elementAt(i);
+ }
+
+ return vertices;
+ }
+}
|