Page Menu
Home
Software Heritage
Search
Configure Global Search
Log In
Files
F7122843
D1700.diff
No One
Temporary
Actions
View File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Award Token
Flag For Later
Size
59 KB
Subscribers
None
D1700.diff
View Options
diff --git a/api/server/src/main/java/org/softwareheritage/graph/App.java b/api/server/src/main/java/org/softwareheritage/graph/App.java
--- a/api/server/src/main/java/org/softwareheritage/graph/App.java
+++ b/api/server/src/main/java/org/softwareheritage/graph/App.java
@@ -12,11 +12,8 @@
import org.softwareheritage.graph.Graph;
import org.softwareheritage.graph.SwhId;
-import org.softwareheritage.graph.algo.Leaves;
-import org.softwareheritage.graph.algo.Neighbors;
import org.softwareheritage.graph.algo.Stats;
-import org.softwareheritage.graph.algo.Visit;
-import org.softwareheritage.graph.algo.Walk;
+import org.softwareheritage.graph.algo.Traversal;
public class App {
public static void main(String[] args) throws IOException {
@@ -58,8 +55,8 @@
String direction = ctx.queryParam("direction", "forward");
String edgesFmt = ctx.queryParam("edges", "*");
- Leaves leaves = new Leaves(graph, src, edgesFmt, direction);
- ctx.json(leaves.getLeaves());
+ Traversal traversal = new Traversal(graph, direction, edgesFmt);
+ ctx.json(traversal.leavesEndpoint(src));
});
app.get("/neighbors/:src", ctx -> {
@@ -67,26 +64,27 @@
String direction = ctx.queryParam("direction", "forward");
String edgesFmt = ctx.queryParam("edges", "*");
- Neighbors neighbors = new Neighbors(graph, src, edgesFmt, direction);
- ctx.json(neighbors.getNeighbors());
+ Traversal traversal = new Traversal(graph, direction, edgesFmt);
+ ctx.json(traversal.neighborsEndpoint(src));
});
- app.get("/visit/:src", ctx -> {
+ // TODO: anonymous class to return both nodes/paths? (waiting on node types map merged/refactor)
+ /*app.get("/visit/:src", ctx -> {
SwhId src = new SwhId(ctx.pathParam("src"));
String direction = ctx.queryParam("direction", "forward");
String edgesFmt = ctx.queryParam("edges", "*");
Visit visit = new Visit(graph, src, edgesFmt, direction, Visit.OutputFmt.NODES_AND_PATHS);
ctx.json(visit);
- });
+ });*/
app.get("/visit/nodes/:src", ctx -> {
SwhId src = new SwhId(ctx.pathParam("src"));
String direction = ctx.queryParam("direction", "forward");
String edgesFmt = ctx.queryParam("edges", "*");
- Visit visit = new Visit(graph, src, edgesFmt, direction, Visit.OutputFmt.ONLY_NODES);
- ctx.json(visit.getNodes());
+ Traversal traversal = new Traversal(graph, direction, edgesFmt);
+ ctx.json(traversal.visitNodesEndpoint(src));
});
app.get("/visit/paths/:src", ctx -> {
@@ -94,8 +92,8 @@
String direction = ctx.queryParam("direction", "forward");
String edgesFmt = ctx.queryParam("edges", "*");
- Visit visit = new Visit(graph, src, edgesFmt, direction, Visit.OutputFmt.ONLY_PATHS);
- ctx.json(visit.getPaths());
+ Traversal traversal = new Traversal(graph, direction, edgesFmt);
+ ctx.json(traversal.visitPathsEndpoint(src));
});
app.get("/walk/:src/:dst", ctx -> {
@@ -103,10 +101,10 @@
String dstFmt = ctx.pathParam("dst");
String direction = ctx.queryParam("direction", "forward");
String edgesFmt = ctx.queryParam("edges", "*");
- String traversal = ctx.queryParam("traversal", "dfs");
+ String algorithm = ctx.queryParam("traversal", "dfs");
- Walk walk = new Walk(graph, src, dstFmt, edgesFmt, direction, traversal);
- ctx.json(walk.getPath());
+ Traversal traversal = new Traversal(graph, direction, edgesFmt);
+ ctx.json(traversal.walkEndpoint(src, dstFmt, algorithm));
});
app.exception(IllegalArgumentException.class, (e, ctx) -> {
diff --git a/api/server/src/main/java/org/softwareheritage/graph/Graph.java b/api/server/src/main/java/org/softwareheritage/graph/Graph.java
--- a/api/server/src/main/java/org/softwareheritage/graph/Graph.java
+++ b/api/server/src/main/java/org/softwareheritage/graph/Graph.java
@@ -3,7 +3,6 @@
import java.io.IOException;
import it.unimi.dsi.big.webgraph.BVGraph;
-import it.unimi.dsi.big.webgraph.LazyLongIterator;
import org.softwareheritage.graph.SwhId;
import org.softwareheritage.graph.backend.NodeIdMap;
@@ -45,16 +44,16 @@
return graph.numArcs();
}
- public LazyLongIterator successors(long nodeId) {
- return graph.successors(nodeId);
+ public long[][] successors(long nodeId) {
+ return graph.successorBigArray(nodeId);
}
public long outdegree(long nodeId) {
return graph.outdegree(nodeId);
}
- public LazyLongIterator predecessors(long nodeId) {
- return graphTransposed.successors(nodeId);
+ public long[][] predecessors(long nodeId) {
+ return graphTransposed.successorBigArray(nodeId);
}
public long indegree(long nodeId) {
@@ -65,7 +64,7 @@
return (useTransposed) ? indegree(nodeId) : outdegree(nodeId);
}
- public LazyLongIterator neighbors(long nodeId, boolean useTransposed) {
+ public long[][] neighbors(long nodeId, boolean useTransposed) {
return (useTransposed) ? predecessors(nodeId) : successors(nodeId);
}
}
diff --git a/api/server/src/main/java/org/softwareheritage/graph/Neighbors.java b/api/server/src/main/java/org/softwareheritage/graph/Neighbors.java
new file mode 100644
--- /dev/null
+++ b/api/server/src/main/java/org/softwareheritage/graph/Neighbors.java
@@ -0,0 +1,60 @@
+package org.softwareheritage.graph;
+
+import java.util.Iterator;
+
+import it.unimi.dsi.fastutil.longs.LongBigArrays;
+
+import org.softwareheritage.graph.AllowedEdges;
+import org.softwareheritage.graph.Graph;
+import org.softwareheritage.graph.SwhId;
+
+public class Neighbors implements Iterable<Long> {
+ Graph graph;
+ boolean useTransposed;
+ AllowedEdges edges;
+ SwhId src;
+
+ public Neighbors(Graph graph, boolean useTransposed, AllowedEdges edges, SwhId src) {
+ this.graph = graph;
+ this.useTransposed = useTransposed;
+ this.edges = edges;
+ this.src = src;
+ }
+
+ @Override
+ public Iterator<Long> iterator() {
+ return new NeighborsIterator();
+ }
+
+ public class NeighborsIterator implements Iterator<Long> {
+ long nextNeighborIdx;
+ long nbNeighbors;
+ long[][] neighbors;
+
+ public NeighborsIterator() {
+ long srcNodeId = graph.getNodeId(src);
+
+ this.nextNeighborIdx = -1;
+ this.nbNeighbors = graph.degree(srcNodeId, useTransposed);
+ this.neighbors = graph.neighbors(srcNodeId, useTransposed);
+ }
+
+ // Look ahead because with edge restriction not all neighbors are considered
+ public boolean hasNext() {
+ for (long lookAheadIdx = nextNeighborIdx + 1; lookAheadIdx < nbNeighbors; lookAheadIdx++) {
+ long nextNodeId = LongBigArrays.get(neighbors, lookAheadIdx);
+ SwhId nextSwhId = graph.getSwhId(nextNodeId);
+ if (edges.isAllowed(src.getType(), nextSwhId.getType())) {
+ nextNeighborIdx = lookAheadIdx;
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public Long next() {
+ long nextNodeId = LongBigArrays.get(neighbors, nextNeighborIdx);
+ return nextNodeId;
+ }
+ }
+}
diff --git a/api/server/src/main/java/org/softwareheritage/graph/algo/Leaves.java b/api/server/src/main/java/org/softwareheritage/graph/algo/Leaves.java
deleted file mode 100644
--- a/api/server/src/main/java/org/softwareheritage/graph/algo/Leaves.java
+++ /dev/null
@@ -1,64 +0,0 @@
-package org.softwareheritage.graph.algo;
-
-import java.util.ArrayList;
-
-import it.unimi.dsi.big.webgraph.LazyLongIterator;
-import it.unimi.dsi.bits.LongArrayBitVector;
-
-import org.softwareheritage.graph.AllowedEdges;
-import org.softwareheritage.graph.Graph;
-import org.softwareheritage.graph.Node;
-import org.softwareheritage.graph.SwhId;
-
-public class Leaves {
- Graph graph;
- boolean useTransposed;
- AllowedEdges edges;
-
- ArrayList<SwhId> leaves;
- LongArrayBitVector visited;
-
- public Leaves(Graph graph, SwhId src, String edgesFmt, String direction) {
- if (!direction.matches("forward|backward")) {
- throw new IllegalArgumentException("Unknown traversal direction: " + direction);
- }
-
- this.graph = graph;
- this.useTransposed = (direction.equals("backward"));
- this.edges = new AllowedEdges(edgesFmt);
- this.leaves = new ArrayList<SwhId>();
- this.visited = LongArrayBitVector.ofLength(graph.getNbNodes());
-
- long nodeId = graph.getNodeId(src);
- dfs(nodeId);
- }
-
- public ArrayList<SwhId> getLeaves() {
- return leaves;
- }
-
- private void dfs(long currentNodeId) {
- visited.set(currentNodeId);
- SwhId currentSwhId = graph.getSwhId(currentNodeId);
-
- long degree = graph.degree(currentNodeId, useTransposed);
- LazyLongIterator neighbors = graph.neighbors(currentNodeId, useTransposed);
- long neighborsCnt = 0;
-
- while (degree-- > 0) {
- long neighborNodeId = neighbors.nextLong();
- Node.Type currentNodeType = currentSwhId.getType();
- Node.Type neighborNodeType = graph.getSwhId(neighborNodeId).getType();
- if (edges.isAllowed(currentNodeType, neighborNodeType)) {
- neighborsCnt++;
- if (!visited.getBoolean(neighborNodeId)) {
- dfs(neighborNodeId);
- }
- }
- }
-
- if (neighborsCnt == 0) {
- leaves.add(currentSwhId);
- }
- }
-}
diff --git a/api/server/src/main/java/org/softwareheritage/graph/algo/Neighbors.java b/api/server/src/main/java/org/softwareheritage/graph/algo/Neighbors.java
deleted file mode 100644
--- a/api/server/src/main/java/org/softwareheritage/graph/algo/Neighbors.java
+++ /dev/null
@@ -1,49 +0,0 @@
-package org.softwareheritage.graph.algo;
-
-import java.util.ArrayList;
-
-import it.unimi.dsi.big.webgraph.LazyLongIterator;
-
-import org.softwareheritage.graph.AllowedEdges;
-import org.softwareheritage.graph.Graph;
-import org.softwareheritage.graph.SwhId;
-
-public class Neighbors {
- Graph graph;
- boolean useTransposed;
- AllowedEdges edges;
-
- ArrayList<SwhId> neighbors;
-
- public Neighbors(Graph graph, SwhId src, String edgesFmt, String direction) {
- if (!direction.matches("forward|backward")) {
- throw new IllegalArgumentException("Unknown traversal direction: " + direction);
- }
-
- this.graph = graph;
- this.useTransposed = (direction.equals("backward"));
- this.edges = new AllowedEdges(edgesFmt);
- this.neighbors = new ArrayList<SwhId>();
-
- iterateNeighbors(src);
- }
-
- public ArrayList<SwhId> getNeighbors() {
- return neighbors;
- }
-
- private void iterateNeighbors(SwhId swhId) {
- long nodeId = graph.getNodeId(swhId);
- long degree = graph.degree(nodeId, useTransposed);
- LazyLongIterator neighborsNodeIds = graph.neighbors(nodeId, useTransposed);
-
- while (degree-- > 0) {
- long neighborNodeId = neighborsNodeIds.nextLong();
- SwhId neighborSwhId = graph.getSwhId(neighborNodeId);
- if (edges.isAllowed(swhId.getType(), neighborSwhId.getType())) {
- neighbors.add(neighborSwhId);
- }
- }
- }
-}
-
diff --git a/api/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java b/api/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java
new file mode 100644
--- /dev/null
+++ b/api/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java
@@ -0,0 +1,254 @@
+package org.softwareheritage.graph.algo;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.LinkedList;
+import java.util.Queue;
+import java.util.Stack;
+
+import it.unimi.dsi.bits.LongArrayBitVector;
+import it.unimi.dsi.fastutil.longs.LongBigArrays;
+
+import org.softwareheritage.graph.AllowedEdges;
+import org.softwareheritage.graph.Graph;
+import org.softwareheritage.graph.Neighbors;
+import org.softwareheritage.graph.Node;
+import org.softwareheritage.graph.SwhId;
+
+public class Traversal {
+ Graph graph;
+ boolean useTransposed;
+ AllowedEdges edges;
+
+ // Big array storing if we have visited a node
+ LongArrayBitVector visited;
+ // Big array storing parents to retrieve the path when backtracking
+ long[][] nodeParent;
+
+ public Traversal(Graph graph, String direction, String edgesFmt) {
+ if (!direction.matches("forward|backward")) {
+ throw new IllegalArgumentException("Unknown traversal direction: " + direction);
+ }
+
+ this.graph = graph;
+ this.useTransposed = (direction.equals("backward"));
+ this.edges = new AllowedEdges(edgesFmt);
+
+ long nbNodes = graph.getNbNodes();
+ this.visited = LongArrayBitVector.ofLength(nbNodes);
+ this.nodeParent = LongBigArrays.newBigArray(nbNodes);
+ }
+
+ // TODO: better separation between internal/external ids (waiting on node types map to be merged)
+ private ArrayList<SwhId> convertToSwhIds(ArrayList<Long> nodeIds) {
+ ArrayList<SwhId> swhIds = new ArrayList<SwhId>();
+ for (long nodeId : nodeIds) {
+ swhIds.add(graph.getSwhId(nodeId));
+ }
+ return swhIds;
+ }
+
+ public ArrayList<SwhId> leavesEndpoint(SwhId src) {
+ long nodeId = graph.getNodeId(src);
+ ArrayList<Long> leavesNodeIds = leavesInternalEndpoint(nodeId);
+ return convertToSwhIds(leavesNodeIds);
+ }
+
+ public ArrayList<SwhId> neighborsEndpoint(SwhId src) {
+ long nodeId = graph.getNodeId(src);
+ ArrayList<Long> neighborsNodeIds = neighborsInternalEndpoint(nodeId);
+ return convertToSwhIds(neighborsNodeIds);
+ }
+
+ public ArrayList<SwhId> walkEndpoint(SwhId src, String dstFmt, String traversal) {
+ if (!traversal.matches("dfs|bfs")) {
+ throw new IllegalArgumentException("Unknown traversal algorithm: " + traversal);
+ }
+
+ long srcNodeId = graph.getNodeId(src);
+ long dstNodeId = (traversal.equals("dfs")) ? dfs(srcNodeId, dstFmt) : bfs(srcNodeId, dstFmt);
+ if (dstNodeId == -1) {
+ throw new IllegalArgumentException("Unable to find destination point: " + dstFmt);
+ }
+
+ ArrayList<Long> path = backtracking(srcNodeId, dstNodeId);
+ return convertToSwhIds(path);
+ }
+
+ public ArrayList<SwhId> visitNodesEndpoint(SwhId src) {
+ long nodeId = graph.getNodeId(src);
+ ArrayList<Long> nodes = visitNodesInternalEndpoint(nodeId);
+ return convertToSwhIds(nodes);
+ }
+
+ public ArrayList<ArrayList<SwhId>> visitPathsEndpoint(SwhId src) {
+ long nodeId = graph.getNodeId(src);
+ ArrayList<ArrayList<Long>> pathNodeIds = new ArrayList<>();
+ Stack<Long> currentPath = new Stack<Long>();
+ visitPathsInternalEndpoint(nodeId, pathNodeIds, currentPath);
+
+ ArrayList<ArrayList<SwhId>> paths = new ArrayList<>();
+ for (ArrayList<Long> nodeIds : pathNodeIds) {
+ paths.add(convertToSwhIds(nodeIds));
+ }
+ return paths;
+ }
+
+ private ArrayList<Long> leavesInternalEndpoint(long srcNodeId) {
+ ArrayList<Long> leaves = new ArrayList<Long>();
+ Stack<Long> stack = new Stack<Long>();
+ this.visited.clear();
+
+ stack.push(srcNodeId);
+ visited.set(srcNodeId);
+
+ while (!stack.isEmpty()) {
+ long currentNodeId = stack.pop();
+ SwhId currentSwhId = graph.getSwhId(currentNodeId);
+
+ long neighborsCnt = 0;
+ for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentSwhId)) {
+ neighborsCnt++;
+ if (!visited.getBoolean(neighborNodeId)) {
+ stack.push(neighborNodeId);
+ visited.set(neighborNodeId);
+ }
+ }
+
+ if (neighborsCnt == 0) {
+ leaves.add(currentNodeId);
+ }
+ }
+
+ return leaves;
+ }
+
+ private ArrayList<Long> neighborsInternalEndpoint(long srcNodeId) {
+ SwhId srcSwhId = graph.getSwhId(srcNodeId);
+ ArrayList<Long> neighbors = new ArrayList<Long>();
+ for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, srcSwhId)) {
+ neighbors.add(neighborNodeId);
+ }
+ return neighbors;
+ }
+
+ private ArrayList<Long> visitNodesInternalEndpoint(long srcNodeId) {
+ // No specific destination point
+ String dstFmt = null;
+ dfs(srcNodeId, dstFmt);
+
+ ArrayList<Long> nodes = new ArrayList<Long>();
+ for (long nodeId = 0; nodeId < graph.getNbNodes(); nodeId++) {
+ if (this.visited.getBoolean(nodeId)) {
+ nodes.add(nodeId);
+ }
+ }
+ return nodes;
+ }
+
+ private void visitPathsInternalEndpoint(
+ long currentNodeId, ArrayList<ArrayList<Long>> paths, Stack<Long> currentPath) {
+ SwhId currentSwhId = graph.getSwhId(currentNodeId);
+ currentPath.push(currentNodeId);
+
+ long visitedNeighbors = 0;
+ for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentSwhId)) {
+ visitPathsInternalEndpoint(neighborNodeId, paths, currentPath);
+ visitedNeighbors++;
+ }
+
+ if (visitedNeighbors == 0) {
+ ArrayList<Long> path = new ArrayList<Long>();
+ for (long nodeId : currentPath) {
+ path.add(nodeId);
+ }
+ paths.add(path);
+ }
+
+ currentPath.pop();
+ }
+
+ private ArrayList<Long> backtracking(long srcNodeId, long dstNodeId) {
+ ArrayList<Long> path = new ArrayList<Long>();
+ long currentNodeId = dstNodeId;
+ while (currentNodeId != srcNodeId) {
+ path.add(currentNodeId);
+ currentNodeId = LongBigArrays.get(nodeParent, currentNodeId);
+ }
+ path.add(srcNodeId);
+ Collections.reverse(path);
+ return path;
+ }
+
+ private long dfs(long srcNodeId, String dstFmt) {
+ Stack<Long> stack = new Stack<Long>();
+ this.visited.clear();
+
+ stack.push(srcNodeId);
+ visited.set(srcNodeId);
+
+ while (!stack.isEmpty()) {
+ long currentNodeId = stack.pop();
+ SwhId currentSwhId = graph.getSwhId(currentNodeId);
+ if (isDestinationNode(currentSwhId, dstFmt)) {
+ return currentNodeId;
+ }
+
+ for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentSwhId)) {
+ if (!visited.getBoolean(neighborNodeId)) {
+ stack.push(neighborNodeId);
+ visited.set(neighborNodeId);
+ LongBigArrays.set(nodeParent, neighborNodeId, currentNodeId);
+ }
+ }
+ }
+
+ return -1;
+ }
+
+ private long bfs(long srcNodeId, String dstFmt) {
+ Queue<Long> queue = new LinkedList<Long>();
+ this.visited.clear();
+
+ queue.add(srcNodeId);
+ visited.set(srcNodeId);
+
+ while (!queue.isEmpty()) {
+ long currentNodeId = queue.poll();
+ SwhId currentSwhId = graph.getSwhId(currentNodeId);
+ if (isDestinationNode(currentSwhId, dstFmt)) {
+ return currentNodeId;
+ }
+
+ for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentSwhId)) {
+ if (!visited.getBoolean(neighborNodeId)) {
+ queue.add(neighborNodeId);
+ visited.set(neighborNodeId);
+ LongBigArrays.set(nodeParent, neighborNodeId, currentNodeId);
+ }
+ }
+ }
+
+ return -1;
+ }
+
+ private boolean isDestinationNode(SwhId swhId, String dstFmt) {
+ // No destination node, early exit
+ if (dstFmt == null) {
+ return false;
+ }
+
+ // SwhId as destination node
+ if (swhId.toString().equals(dstFmt)) {
+ return true;
+ }
+
+ // Node.Type as destination node
+ try {
+ Node.Type dstType = Node.Type.fromStr(dstFmt);
+ return (swhId.getType().equals(dstType));
+ } catch (IllegalArgumentException e) {
+ return false;
+ }
+ }
+}
diff --git a/api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java b/api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java
deleted file mode 100644
--- a/api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java
+++ /dev/null
@@ -1,104 +0,0 @@
-package org.softwareheritage.graph.algo;
-
-import java.util.ArrayList;
-import java.util.LinkedHashSet;
-import java.util.Stack;
-
-import it.unimi.dsi.big.webgraph.LazyLongIterator;
-import it.unimi.dsi.bits.LongArrayBitVector;
-
-import org.softwareheritage.graph.AllowedEdges;
-import org.softwareheritage.graph.Graph;
-import org.softwareheritage.graph.Node;
-import org.softwareheritage.graph.SwhId;
-import org.softwareheritage.graph.SwhPath;
-
-public class Visit {
- public enum OutputFmt { ONLY_NODES, ONLY_PATHS, NODES_AND_PATHS }
-
- Graph graph;
- boolean useTransposed;
- AllowedEdges edges;
-
- // LinkedHashSet is necessary to preserve insertion order
- LinkedHashSet<SwhId> nodes;
- ArrayList<SwhPath> paths;
- Stack<Long> currentPath;
- LongArrayBitVector visited;
-
- public Visit(Graph graph, SwhId src, String edgesFmt, String direction, OutputFmt output) {
- if (!direction.matches("forward|backward")) {
- throw new IllegalArgumentException("Unknown traversal direction: " + direction);
- }
-
- this.graph = graph;
- this.useTransposed = (direction.equals("backward"));
- this.edges = new AllowedEdges(edgesFmt);
- this.nodes = new LinkedHashSet<SwhId>();
- this.paths = new ArrayList<SwhPath>();
- this.currentPath = new Stack<Long>();
- this.visited = LongArrayBitVector.ofLength(graph.getNbNodes());
-
- long nodeId = graph.getNodeId(src);
- if (output == OutputFmt.ONLY_NODES) {
- dfsOutputOnlyNodes(nodeId);
- } else {
- dfs(nodeId);
- }
- }
-
- public LinkedHashSet<SwhId> getNodes() {
- return nodes;
- }
-
- public ArrayList<SwhPath> getPaths() {
- return paths;
- }
-
- private void dfs(long currentNodeId) {
- nodes.add(graph.getSwhId(currentNodeId));
- currentPath.push(currentNodeId);
-
- long degree = graph.degree(currentNodeId, useTransposed);
- LazyLongIterator neighbors = graph.neighbors(currentNodeId, useTransposed);
- long visitedNeighbors = 0;
-
- while (degree-- > 0) {
- long neighborNodeId = neighbors.nextLong();
- Node.Type currentNodeType = graph.getSwhId(currentNodeId).getType();
- Node.Type neighborNodeType = graph.getSwhId(neighborNodeId).getType();
- if (edges.isAllowed(currentNodeType, neighborNodeType)) {
- dfs(neighborNodeId);
- visitedNeighbors++;
- }
- }
-
- if (visitedNeighbors == 0) {
- SwhPath path = new SwhPath();
- for (long nodeId : currentPath) {
- path.add(graph.getSwhId(nodeId));
- }
- paths.add(path);
- }
-
- currentPath.pop();
- }
-
- private void dfsOutputOnlyNodes(long currentNodeId) {
- nodes.add(graph.getSwhId(currentNodeId));
- visited.set(currentNodeId);
-
- long degree = graph.degree(currentNodeId, useTransposed);
- LazyLongIterator neighbors = graph.neighbors(currentNodeId, useTransposed);
-
- while (degree-- > 0) {
- long neighborNodeId = neighbors.nextLong();
- Node.Type currentNodeType = graph.getSwhId(currentNodeId).getType();
- Node.Type neighborNodeType = graph.getSwhId(neighborNodeId).getType();
- if (!visited.getBoolean(neighborNodeId)
- && edges.isAllowed(currentNodeType, neighborNodeType)) {
- dfsOutputOnlyNodes(neighborNodeId);
- }
- }
- }
-}
diff --git a/api/server/src/main/java/org/softwareheritage/graph/algo/Walk.java b/api/server/src/main/java/org/softwareheritage/graph/algo/Walk.java
deleted file mode 100644
--- a/api/server/src/main/java/org/softwareheritage/graph/algo/Walk.java
+++ /dev/null
@@ -1,148 +0,0 @@
-package org.softwareheritage.graph.algo;
-
-import java.util.Stack;
-import java.util.Queue;
-import java.util.LinkedList;
-
-import it.unimi.dsi.big.webgraph.LazyLongIterator;
-import it.unimi.dsi.bits.LongArrayBitVector;
-import it.unimi.dsi.fastutil.longs.LongBigArrays;
-
-import org.softwareheritage.graph.AllowedEdges;
-import org.softwareheritage.graph.Graph;
-import org.softwareheritage.graph.Node;
-import org.softwareheritage.graph.SwhId;
-import org.softwareheritage.graph.SwhPath;
-
-public class Walk {
- Graph graph;
- boolean useTransposed;
- AllowedEdges edges;
-
- SwhPath path;
- long[][] nodeParent;
-
- public Walk(
- Graph graph, SwhId src, String dstFmt, String edgesFmt, String direction, String traversal) {
- if (!traversal.matches("dfs|bfs")) {
- throw new IllegalArgumentException("Unknown traversal algorithm: " + traversal);
- }
- if (!direction.matches("forward|backward")) {
- throw new IllegalArgumentException("Unknown traversal direction: " + direction);
- }
-
- this.graph = graph;
- this.useTransposed = (direction.equals("backward"));
- this.edges = new AllowedEdges(edgesFmt);
- this.path = new SwhPath();
- this.nodeParent = LongBigArrays.newBigArray(graph.getNbNodes());
- LongBigArrays.fill(nodeParent, -1);
-
- long srcNodeId = graph.getNodeId(src);
- long dstNodeId;
- if (traversal.equals("dfs")) {
- dstNodeId = dfs(srcNodeId, dstFmt);
- } else {
- dstNodeId = bfs(srcNodeId, dstFmt);
- }
-
- if (dstNodeId == -1) {
- throw new IllegalArgumentException("Unable to find destination point: " + dstFmt);
- } else {
- backtracking(srcNodeId, dstNodeId);
- }
- }
-
- public SwhPath getPath() {
- return path;
- }
-
- private void backtracking(long srcNodeId, long dstNodeId) {
- long currentNodeId = dstNodeId;
- while (currentNodeId != srcNodeId) {
- path.add(graph.getSwhId(currentNodeId));
- currentNodeId = LongBigArrays.get(nodeParent, currentNodeId);
- }
- path.add(graph.getSwhId(srcNodeId));
- path.reverse();
- }
-
- private long dfs(long srcNodeId, String dstFmt) {
- Stack<Long> stack = new Stack<Long>();
- LongArrayBitVector visited = LongArrayBitVector.ofLength(graph.getNbNodes());
-
- stack.push(srcNodeId);
- visited.set(srcNodeId);
-
- while (!stack.isEmpty()) {
- long currentNodeId = stack.pop();
- SwhId currentSwhId = graph.getSwhId(currentNodeId);
- if (isDestinationNode(currentSwhId, dstFmt)) {
- return currentNodeId;
- }
-
- long degree = graph.degree(currentNodeId, useTransposed);
- LazyLongIterator neighbors = graph.neighbors(currentNodeId, useTransposed);
-
- while (degree-- > 0) {
- long neighborNodeId = neighbors.nextLong();
- SwhId neighborSwhId = graph.getSwhId(neighborNodeId);
- if (!visited.getBoolean(neighborNodeId)
- && edges.isAllowed(currentSwhId.getType(), neighborSwhId.getType())) {
- stack.push(neighborNodeId);
- visited.set(neighborNodeId);
- LongBigArrays.set(nodeParent, neighborNodeId, currentNodeId);
- }
- }
- }
-
- return -1;
- }
-
- private long bfs(long srcNodeId, String dstFmt) {
- Queue<Long> queue = new LinkedList<Long>();
- LongArrayBitVector visited = LongArrayBitVector.ofLength(graph.getNbNodes());
-
- queue.add(srcNodeId);
- visited.set(srcNodeId);
-
- while (!queue.isEmpty()) {
- long currentNodeId = queue.poll();
- SwhId currentSwhId = graph.getSwhId(currentNodeId);
- if (isDestinationNode(currentSwhId, dstFmt)) {
- return currentNodeId;
- }
-
- long degree = graph.degree(currentNodeId, useTransposed);
- LazyLongIterator neighbors = graph.neighbors(currentNodeId, useTransposed);
-
- while (degree-- > 0) {
- long neighborNodeId = neighbors.nextLong();
- SwhId neighborSwhId = graph.getSwhId(neighborNodeId);
- if (!visited.getBoolean(neighborNodeId)
- && edges.isAllowed(currentSwhId.getType(), neighborSwhId.getType())) {
- queue.add(neighborNodeId);
- visited.set(neighborNodeId);
- LongBigArrays.set(nodeParent, neighborNodeId, currentNodeId);
- }
- }
- }
-
- return -1;
- }
-
- private boolean isDestinationNode(SwhId swhId, String dstFmt) {
- // dstFmt is either a SwhId...
- if (swhId.toString().equals(dstFmt)) {
- return true;
- }
-
- // ...or a Node.Type
- try {
- Node.Type dstType = Node.Type.fromStr(dstFmt);
- return (swhId.getType().equals(dstType));
- } catch (IllegalArgumentException e) {
- return false;
- }
- }
-}
diff --git a/api/server/src/main/java/org/softwareheritage/graph/benchmark/LinuxLog.java b/api/server/src/main/java/org/softwareheritage/graph/benchmark/LinuxLog.java
--- a/api/server/src/main/java/org/softwareheritage/graph/benchmark/LinuxLog.java
+++ b/api/server/src/main/java/org/softwareheritage/graph/benchmark/LinuxLog.java
@@ -4,7 +4,7 @@
import org.softwareheritage.graph.Graph;
import org.softwareheritage.graph.SwhId;
-import org.softwareheritage.graph.algo.Visit;
+import org.softwareheritage.graph.algo.Traversal;
public class LinuxLog {
public static void main(String[] args) throws IOException {
@@ -18,14 +18,14 @@
System.out.println("Expecting " + expectedCount + " commits");
long startTime = System.nanoTime();
- Visit visit = new Visit(graph, commit, "rev:rev", "forward", Visit.OutputFmt.ONLY_NODES);
+ Traversal traversal = new Traversal(graph, "forward", "rev:rev");
+ long count = traversal.visitNodesEndpoint(commit).size();
+ if (count != expectedCount) {
+ throw new IllegalArgumentException("Counted " + count + " commits");
+ }
long endTime = System.nanoTime();
double duration = (double) (endTime - startTime) / 1_000_000_000;
System.out.println("Visit operation done in: " + duration + " seconds");
- long count = visit.getNodes().size();
- if (count != expectedCount) {
- throw new IllegalArgumentException("Counted " + count + " commits");
- }
}
}
diff --git a/api/server/src/test/java/org/softwareheritage/graph/LeavesTest.java b/api/server/src/test/java/org/softwareheritage/graph/LeavesTest.java
--- a/api/server/src/test/java/org/softwareheritage/graph/LeavesTest.java
+++ b/api/server/src/test/java/org/softwareheritage/graph/LeavesTest.java
@@ -7,14 +7,14 @@
import org.softwareheritage.graph.Graph;
import org.softwareheritage.graph.GraphTest;
import org.softwareheritage.graph.SwhId;
-import org.softwareheritage.graph.algo.Leaves;
+import org.softwareheritage.graph.algo.Traversal;
public class LeavesTest extends GraphTest {
@Test
public void forwardFromSnp() {
Graph graph = getGraph();
SwhId src = new SwhId("swh:1:snp:0000000000000000000000000000000000000020");
- Leaves leaves = new Leaves(graph, src, "*", "forward");
+ Traversal traversal = new Traversal(graph, "forward", "*");
ArrayList<SwhId> expectedLeaves = new ArrayList<>();
expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000001"));
@@ -22,14 +22,14 @@
expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000005"));
expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007"));
- GraphTest.assertEqualsAnyOrder(expectedLeaves, leaves.getLeaves());
+ assertEquals(expectedLeaves, traversal.leavesEndpoint(src));
}
@Test
public void forwardFromRel() {
Graph graph = getGraph();
SwhId src = new SwhId("swh:1:rel:0000000000000000000000000000000000000019");
- Leaves leaves = new Leaves(graph, src, "*", "forward");
+ Traversal traversal = new Traversal(graph, "forward", "*");
ArrayList<SwhId> expectedLeaves = new ArrayList<>();
expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000015"));
@@ -40,44 +40,43 @@
expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007"));
expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000011"));
- GraphTest.assertEqualsAnyOrder(expectedLeaves, leaves.getLeaves());
+ assertEquals(expectedLeaves, traversal.leavesEndpoint(src));
}
@Test
public void backwardFromLeaf() {
Graph graph = getGraph();
+ Traversal traversal = new Traversal(graph, "backward", "*");
SwhId src1 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000015");
- Leaves leaves1 = new Leaves(graph, src1, "*", "backward");
ArrayList<SwhId> expectedLeaves1 = new ArrayList<>();
expectedLeaves1.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000019"));
- GraphTest.assertEqualsAnyOrder(expectedLeaves1, leaves1.getLeaves());
+ assertEquals(expectedLeaves1, traversal.leavesEndpoint(src1));
SwhId src2 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000004");
- Leaves leaves2 = new Leaves(graph, src2, "*", "backward");
ArrayList<SwhId> expectedLeaves2 = new ArrayList<>();
expectedLeaves2.add(new SwhId("swh:1:snp:0000000000000000000000000000000000000020"));
expectedLeaves2.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000019"));
- GraphTest.assertEqualsAnyOrder(expectedLeaves2, leaves2.getLeaves());
+ assertEquals(expectedLeaves2, traversal.leavesEndpoint(src2));
}
@Test
public void forwardRevToRevOnly() {
Graph graph = getGraph();
SwhId src = new SwhId("swh:1:rev:0000000000000000000000000000000000000018");
- Leaves leaves = new Leaves(graph, src, "rev:rev", "forward");
+ Traversal traversal = new Traversal(graph, "forward", "rev:rev");
ArrayList<SwhId> expectedLeaves = new ArrayList<>();
expectedLeaves.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000003"));
- GraphTest.assertEqualsAnyOrder(expectedLeaves, leaves.getLeaves());
+ assertEquals(expectedLeaves, traversal.leavesEndpoint(src));
}
@Test
public void forwardDirToAll() {
Graph graph = getGraph();
SwhId src = new SwhId("swh:1:dir:0000000000000000000000000000000000000008");
- Leaves leaves = new Leaves(graph, src, "dir:*", "forward");
+ Traversal traversal = new Traversal(graph, "forward", "dir:*");
ArrayList<SwhId> expectedLeaves = new ArrayList<>();
expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000004"));
@@ -85,18 +84,18 @@
expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000001"));
expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007"));
- GraphTest.assertEqualsAnyOrder(expectedLeaves, leaves.getLeaves());
+ assertEquals(expectedLeaves, traversal.leavesEndpoint(src));
}
@Test
public void backwardCntToDirDirToDir() {
Graph graph = getGraph();
SwhId src = new SwhId("swh:1:cnt:0000000000000000000000000000000000000005");
- Leaves leaves = new Leaves(graph, src, "cnt:dir,dir:dir", "backward");
+ Traversal traversal = new Traversal(graph, "backward", "cnt:dir,dir:dir");
ArrayList<SwhId> expectedLeaves = new ArrayList<>();
expectedLeaves.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000012"));
- GraphTest.assertEqualsAnyOrder(expectedLeaves, leaves.getLeaves());
+ assertEquals(expectedLeaves, traversal.leavesEndpoint(src));
}
}
diff --git a/api/server/src/test/java/org/softwareheritage/graph/NeighborsTest.java b/api/server/src/test/java/org/softwareheritage/graph/NeighborsTest.java
--- a/api/server/src/test/java/org/softwareheritage/graph/NeighborsTest.java
+++ b/api/server/src/test/java/org/softwareheritage/graph/NeighborsTest.java
@@ -7,7 +7,7 @@
import org.softwareheritage.graph.Graph;
import org.softwareheritage.graph.GraphTest;
import org.softwareheritage.graph.SwhId;
-import org.softwareheritage.graph.algo.Neighbors;
+import org.softwareheritage.graph.algo.Traversal;
public class NeighborsTest extends GraphTest {
@Test
@@ -16,24 +16,24 @@
ArrayList<SwhId> expectedNodes = new ArrayList<>();
SwhId src1 = new SwhId("swh:1:snp:0000000000000000000000000000000000000020");
- Neighbors neighbors1 = new Neighbors(graph, src1, "*", "backward");
- GraphTest.assertEqualsAnyOrder(expectedNodes, neighbors1.getNeighbors());
+ Traversal traversal1 = new Traversal(graph, "backward", "*");
+ GraphTest.assertEqualsAnyOrder(expectedNodes, traversal1.neighborsEndpoint(src1));
SwhId src2 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000004");
- Neighbors neighbors2 = new Neighbors(graph, src2, "*", "forward");
- GraphTest.assertEqualsAnyOrder(expectedNodes, neighbors2.getNeighbors());
+ Traversal traversal2 = new Traversal(graph, "forward", "*");
+ GraphTest.assertEqualsAnyOrder(expectedNodes, traversal2.neighborsEndpoint(src2));
SwhId src3 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000015");
- Neighbors neighbors3 = new Neighbors(graph, src3, "*", "forward");
- GraphTest.assertEqualsAnyOrder(expectedNodes, neighbors3.getNeighbors());
+ Traversal traversal3 = new Traversal(graph, "forward", "*");
+ GraphTest.assertEqualsAnyOrder(expectedNodes, traversal3.neighborsEndpoint(src3));
SwhId src4 = new SwhId("swh:1:rel:0000000000000000000000000000000000000019");
- Neighbors neighbors4 = new Neighbors(graph, src4, "*", "backward");
- GraphTest.assertEqualsAnyOrder(expectedNodes, neighbors4.getNeighbors());
+ Traversal traversal4 = new Traversal(graph, "backward", "*");
+ GraphTest.assertEqualsAnyOrder(expectedNodes, traversal4.neighborsEndpoint(src4));
SwhId src5 = new SwhId("swh:1:dir:0000000000000000000000000000000000000008");
- Neighbors neighbors5 = new Neighbors(graph, src5, "snp:*,rev:*,rel:*", "forward");
- GraphTest.assertEqualsAnyOrder(expectedNodes, neighbors5.getNeighbors());
+ Traversal traversal5 = new Traversal(graph, "forward", "snp:*,rev:*,rel:*");
+ GraphTest.assertEqualsAnyOrder(expectedNodes, traversal5.neighborsEndpoint(src5));
}
@Test
@@ -41,28 +41,28 @@
Graph graph = getGraph();
SwhId src1 = new SwhId("swh:1:rev:0000000000000000000000000000000000000003");
- Neighbors neighbors1 = new Neighbors(graph, src1, "*", "forward");
+ Traversal traversal1 = new Traversal(graph, "forward", "*");
ArrayList<SwhId> expectedNodes1 = new ArrayList<>();
expectedNodes1.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000002"));
- GraphTest.assertEqualsAnyOrder(expectedNodes1, neighbors1.getNeighbors());
+ GraphTest.assertEqualsAnyOrder(expectedNodes1, traversal1.neighborsEndpoint(src1));
SwhId src2 = new SwhId("swh:1:dir:0000000000000000000000000000000000000017");
- Neighbors neighbors2 = new Neighbors(graph, src2, "dir:cnt", "forward");
+ Traversal traversal2 = new Traversal(graph, "forward", "dir:cnt");
ArrayList<SwhId> expectedNodes2 = new ArrayList<>();
expectedNodes2.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000014"));
- GraphTest.assertEqualsAnyOrder(expectedNodes2, neighbors2.getNeighbors());
+ GraphTest.assertEqualsAnyOrder(expectedNodes2, traversal2.neighborsEndpoint(src2));
SwhId src3 = new SwhId("swh:1:dir:0000000000000000000000000000000000000012");
- Neighbors neighbors3 = new Neighbors(graph, src3, "*", "backward");
+ Traversal traversal3 = new Traversal(graph, "backward", "*");
ArrayList<SwhId> expectedNodes3 = new ArrayList<>();
expectedNodes3.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000013"));
- GraphTest.assertEqualsAnyOrder(expectedNodes3, neighbors3.getNeighbors());
+ GraphTest.assertEqualsAnyOrder(expectedNodes3, traversal3.neighborsEndpoint(src3));
SwhId src4 = new SwhId("swh:1:rev:0000000000000000000000000000000000000009");
- Neighbors neighbors4 = new Neighbors(graph, src4, "rev:rev", "backward");
+ Traversal traversal4 = new Traversal(graph, "backward", "rev:rev");
ArrayList<SwhId> expectedNodes4 = new ArrayList<>();
expectedNodes4.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000013"));
- GraphTest.assertEqualsAnyOrder(expectedNodes4, neighbors4.getNeighbors());
+ GraphTest.assertEqualsAnyOrder(expectedNodes4, traversal4.neighborsEndpoint(src4));
}
@Test
@@ -70,32 +70,32 @@
Graph graph = getGraph();
SwhId src1 = new SwhId("swh:1:snp:0000000000000000000000000000000000000020");
- Neighbors neighbors1 = new Neighbors(graph, src1, "*", "forward");
+ Traversal traversal1 = new Traversal(graph, "forward", "*");
ArrayList<SwhId> expectedNodes1 = new ArrayList<>();
expectedNodes1.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000010"));
expectedNodes1.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000009"));
- GraphTest.assertEqualsAnyOrder(expectedNodes1, neighbors1.getNeighbors());
+ GraphTest.assertEqualsAnyOrder(expectedNodes1, traversal1.neighborsEndpoint(src1));
SwhId src2 = new SwhId("swh:1:dir:0000000000000000000000000000000000000008");
- Neighbors neighbors2 = new Neighbors(graph, src2, "dir:cnt", "forward");
+ Traversal traversal2 = new Traversal(graph, "forward", "dir:cnt");
ArrayList<SwhId> expectedNodes2 = new ArrayList<>();
expectedNodes2.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000001"));
expectedNodes2.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007"));
- GraphTest.assertEqualsAnyOrder(expectedNodes2, neighbors2.getNeighbors());
+ GraphTest.assertEqualsAnyOrder(expectedNodes2, traversal2.neighborsEndpoint(src2));
SwhId src3 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000001");
- Neighbors neighbors3 = new Neighbors(graph, src3, "*", "backward");
+ Traversal traversal3 = new Traversal(graph, "backward", "*");
ArrayList<SwhId> expectedNodes3 = new ArrayList<>();
expectedNodes3.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000008"));
expectedNodes3.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000002"));
- GraphTest.assertEqualsAnyOrder(expectedNodes3, neighbors3.getNeighbors());
+ GraphTest.assertEqualsAnyOrder(expectedNodes3, traversal3.neighborsEndpoint(src3));
SwhId src4 = new SwhId("swh:1:rev:0000000000000000000000000000000000000009");
- Neighbors neighbors4 = new Neighbors(graph, src4, "rev:snp,rev:rel", "backward");
+ Traversal traversal4 = new Traversal(graph, "backward", "rev:snp,rev:rel");
ArrayList<SwhId> expectedNodes4 = new ArrayList<>();
expectedNodes4.add(new SwhId("swh:1:snp:0000000000000000000000000000000000000020"));
expectedNodes4.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000010"));
- GraphTest.assertEqualsAnyOrder(expectedNodes4, neighbors4.getNeighbors());
+ GraphTest.assertEqualsAnyOrder(expectedNodes4, traversal4.neighborsEndpoint(src4));
}
@Test
@@ -103,19 +103,19 @@
Graph graph = getGraph();
SwhId src1 = new SwhId("swh:1:dir:0000000000000000000000000000000000000008");
- Neighbors neighbors1 = new Neighbors(graph, src1, "*", "forward");
+ Traversal traversal1 = new Traversal(graph, "forward", "*");
ArrayList<SwhId> expectedNodes1 = new ArrayList<>();
expectedNodes1.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000006"));
expectedNodes1.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000001"));
expectedNodes1.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007"));
- GraphTest.assertEqualsAnyOrder(expectedNodes1, neighbors1.getNeighbors());
+ GraphTest.assertEqualsAnyOrder(expectedNodes1, traversal1.neighborsEndpoint(src1));
SwhId src2 = new SwhId("swh:1:rev:0000000000000000000000000000000000000009");
- Neighbors neighbors2 = new Neighbors(graph, src2, "*", "backward");
+ Traversal traversal2 = new Traversal(graph, "backward", "*");
ArrayList<SwhId> expectedNodes2 = new ArrayList<>();
expectedNodes2.add(new SwhId("swh:1:snp:0000000000000000000000000000000000000020"));
expectedNodes2.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000010"));
expectedNodes2.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000013"));
- GraphTest.assertEqualsAnyOrder(expectedNodes2, neighbors2.getNeighbors());
+ GraphTest.assertEqualsAnyOrder(expectedNodes2, traversal2.neighborsEndpoint(src2));
}
}
diff --git a/api/server/src/test/java/org/softwareheritage/graph/VisitTest.java b/api/server/src/test/java/org/softwareheritage/graph/VisitTest.java
--- a/api/server/src/test/java/org/softwareheritage/graph/VisitTest.java
+++ b/api/server/src/test/java/org/softwareheritage/graph/VisitTest.java
@@ -9,11 +9,9 @@
import org.softwareheritage.graph.GraphTest;
import org.softwareheritage.graph.SwhId;
import org.softwareheritage.graph.SwhPath;
-import org.softwareheritage.graph.algo.Visit;
+import org.softwareheritage.graph.algo.Traversal;
public class VisitTest extends GraphTest {
- Visit.OutputFmt outputFmt = Visit.OutputFmt.NODES_AND_PATHS;
-
private void assertSameNodesFromPaths(ArrayList<SwhPath> paths, LinkedHashSet<SwhId> nodes) {
LinkedHashSet<SwhId> expectedNodes = new LinkedHashSet<SwhId>();
for (SwhPath path : paths) {
@@ -28,9 +26,9 @@
public void forwardFromRoot() {
Graph graph = getGraph();
SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020");
- Visit visit = new Visit(graph, swhId, "*", "forward", outputFmt);
- ArrayList<SwhPath> paths = visit.getPaths();
- LinkedHashSet<SwhId> nodes = visit.getNodes();
+ Traversal traversal = new Traversal(graph, "forward", "*");
+ ArrayList<SwhPath> paths = traversal.visitPathsEndpoint(swhId);
+ ArrayList<SwhId> nodes = traversal.visitNodesEndpoint(swhId);
ArrayList<SwhPath> expectedPaths = new ArrayList<SwhPath>();
expectedPaths.add(
@@ -123,9 +121,9 @@
public void forwardFromMiddle() {
Graph graph = getGraph();
SwhId swhId = new SwhId("swh:1:dir:0000000000000000000000000000000000000012");
- Visit visit = new Visit(graph, swhId, "*", "forward", outputFmt);
- ArrayList<SwhPath> paths = visit.getPaths();
- LinkedHashSet<SwhId> nodes = visit.getNodes();
+ Traversal traversal = new Traversal(graph, "forward", "*");
+ ArrayList<SwhPath> paths = traversal.visitPathsEndpoint(swhId);
+ ArrayList<SwhId> nodes = traversal.visitNodesEndpoint(swhId);
ArrayList<SwhPath> expectedPaths = new ArrayList<SwhPath>();
expectedPaths.add(
@@ -168,9 +166,9 @@
public void forwardFromLeaf() {
Graph graph = getGraph();
SwhId swhId = new SwhId("swh:1:cnt:0000000000000000000000000000000000000004");
- Visit visit = new Visit(graph, swhId, "*", "forward", outputFmt);
- ArrayList<SwhPath> paths = visit.getPaths();
- LinkedHashSet<SwhId> nodes = visit.getNodes();
+ Traversal traversal = new Traversal(graph, "forward", "*");
+ ArrayList<SwhPath> paths = traversal.visitPathsEndpoint(swhId);
+ ArrayList<SwhId> nodes = traversal.visitNodesEndpoint(swhId);
ArrayList<SwhPath> expectedPaths = new ArrayList<SwhPath>();
expectedPaths.add(
@@ -186,9 +184,9 @@
public void backwardFromRoot() {
Graph graph = getGraph();
SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020");
- Visit visit = new Visit(graph, swhId, "*", "backward", outputFmt);
- ArrayList<SwhPath> paths = visit.getPaths();
- LinkedHashSet<SwhId> nodes = visit.getNodes();
+ Traversal traversal = new Traversal(graph, "backward", "*");
+ ArrayList<SwhPath> paths = traversal.visitPathsEndpoint(swhId);
+ ArrayList<SwhId> nodes = traversal.visitNodesEndpoint(swhId);
ArrayList<SwhPath> expectedPaths = new ArrayList<SwhPath>();
expectedPaths.add(
@@ -204,9 +202,9 @@
public void backwardFromMiddle() {
Graph graph = getGraph();
SwhId swhId = new SwhId("swh:1:dir:0000000000000000000000000000000000000012");
- Visit visit = new Visit(graph, swhId, "*", "backward", outputFmt);
- ArrayList<SwhPath> paths = visit.getPaths();
- LinkedHashSet<SwhId> nodes = visit.getNodes();
+ Traversal traversal = new Traversal(graph, "backward", "*");
+ ArrayList<SwhPath> paths = traversal.visitPathsEndpoint(swhId);
+ ArrayList<SwhId> nodes = traversal.visitNodesEndpoint(swhId);
ArrayList<SwhPath> expectedPaths = new ArrayList<SwhPath>();
expectedPaths.add(
@@ -225,9 +223,9 @@
public void backwardFromLeaf() {
Graph graph = getGraph();
SwhId swhId = new SwhId("swh:1:cnt:0000000000000000000000000000000000000004");
- Visit visit = new Visit(graph, swhId, "*", "backward", outputFmt);
- ArrayList<SwhPath> paths = visit.getPaths();
- LinkedHashSet<SwhId> nodes = visit.getNodes();
+ Traversal traversal = new Traversal(graph, "backward", "*");
+ ArrayList<SwhPath> paths = traversal.visitPathsEndpoint(swhId);
+ ArrayList<SwhId> nodes = traversal.visitNodesEndpoint(swhId);
ArrayList<SwhPath> expectedPaths = new ArrayList<SwhPath>();
expectedPaths.add(
@@ -276,9 +274,9 @@
public void forwardSnpToRev() {
Graph graph = getGraph();
SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020");
- Visit visit = new Visit(graph, swhId, "snp:rev", "forward", outputFmt);
- ArrayList<SwhPath> paths = visit.getPaths();
- LinkedHashSet<SwhId> nodes = visit.getNodes();
+ Traversal traversal = new Traversal(graph, "forward", "snp:rev");
+ ArrayList<SwhPath> paths = traversal.visitPathsEndpoint(swhId);
+ ArrayList<SwhId> nodes = traversal.visitNodesEndpoint(swhId);
ArrayList<SwhPath> expectedPaths = new ArrayList<SwhPath>();
expectedPaths.add(
@@ -295,9 +293,9 @@
public void forwardRelToRevRevToRev() {
Graph graph = getGraph();
SwhId swhId = new SwhId("swh:1:rel:0000000000000000000000000000000000000010");
- Visit visit = new Visit(graph, swhId, "rel:rev,rev:rev", "forward", outputFmt);
- ArrayList<SwhPath> paths = visit.getPaths();
- LinkedHashSet<SwhId> nodes = visit.getNodes();
+ Traversal traversal = new Traversal(graph, "forward", "rel:rev,rev:rev");
+ ArrayList<SwhPath> paths = traversal.visitPathsEndpoint(swhId);
+ ArrayList<SwhId> nodes = traversal.visitNodesEndpoint(swhId);
ArrayList<SwhPath> expectedPaths = new ArrayList<SwhPath>();
expectedPaths.add(
@@ -315,9 +313,9 @@
public void forwardRevToAllDirToAll() {
Graph graph = getGraph();
SwhId swhId = new SwhId("swh:1:rev:0000000000000000000000000000000000000013");
- Visit visit = new Visit(graph, swhId, "rev:*,dir:*", "forward", outputFmt);
- ArrayList<SwhPath> paths = visit.getPaths();
- LinkedHashSet<SwhId> nodes = visit.getNodes();
+ Traversal traversal = new Traversal(graph, "forward", "rev:*,dir:*");
+ ArrayList<SwhPath> paths = traversal.visitPathsEndpoint(swhId);
+ ArrayList<SwhId> nodes = traversal.visitNodesEndpoint(swhId);
ArrayList<SwhPath> expectedPaths = new ArrayList<SwhPath>();
expectedPaths.add(
@@ -403,9 +401,9 @@
public void forwardSnpToAllRevToAll() {
Graph graph = getGraph();
SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020");
- Visit visit = new Visit(graph, swhId, "snp:*,rev:*", "forward", outputFmt);
- ArrayList<SwhPath> paths = visit.getPaths();
- LinkedHashSet<SwhId> nodes = visit.getNodes();
+ Traversal traversal = new Traversal(graph, "forward", "snp:*,rev:*");
+ ArrayList<SwhPath> paths = traversal.visitPathsEndpoint(swhId);
+ ArrayList<SwhId> nodes = traversal.visitNodesEndpoint(swhId);
ArrayList<SwhPath> expectedPaths = new ArrayList<SwhPath>();
expectedPaths.add(
@@ -435,9 +433,9 @@
public void forwardNoEdges() {
Graph graph = getGraph();
SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020");
- Visit visit = new Visit(graph, swhId, "", "forward", outputFmt);
- ArrayList<SwhPath> paths = visit.getPaths();
- LinkedHashSet<SwhId> nodes = visit.getNodes();
+ Traversal traversal = new Traversal(graph, "forward", "");
+ ArrayList<SwhPath> paths = traversal.visitPathsEndpoint(swhId);
+ ArrayList<SwhId> nodes = traversal.visitNodesEndpoint(swhId);
ArrayList<SwhPath> expectedPaths = new ArrayList<SwhPath>();
expectedPaths.add(
@@ -453,9 +451,9 @@
public void backwardRevToRevRevToRel() {
Graph graph = getGraph();
SwhId swhId = new SwhId("swh:1:rev:0000000000000000000000000000000000000003");
- Visit visit = new Visit(graph, swhId, "rev:rev,rev:rel", "backward", outputFmt);
- ArrayList<SwhPath> paths = visit.getPaths();
- LinkedHashSet<SwhId> nodes = visit.getNodes();
+ Traversal traversal = new Traversal(graph, "backward", "rev:rev,rev:rel");
+ ArrayList<SwhPath> paths = traversal.visitPathsEndpoint(swhId);
+ ArrayList<SwhId> nodes = traversal.visitNodesEndpoint(swhId);
ArrayList<SwhPath> expectedPaths = new ArrayList<SwhPath>();
expectedPaths.add(
@@ -481,10 +479,10 @@
public void forwardFromRootNodesOnly() {
Graph graph = getGraph();
SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020");
- Visit visit = new Visit(graph, swhId, "*", "forward", Visit.OutputFmt.ONLY_NODES);
- LinkedHashSet<SwhId> nodes = visit.getNodes();
+ Traversal traversal = new Traversal(graph, "forward", "*");
+ ArrayList<SwhId> nodes = traversal.visitNodesEndpoint(swhId);
- LinkedHashSet<SwhId> expectedNodes = new LinkedHashSet<SwhId>();
+ ArrayList<SwhId> expectedNodes = new ArrayList<SwhId>();
expectedNodes.add(new SwhId("swh:1:snp:0000000000000000000000000000000000000020"));
expectedNodes.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000010"));
expectedNodes.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000009"));
@@ -504,10 +502,10 @@
public void backwardRevToAllNodesOnly() {
Graph graph = getGraph();
SwhId swhId = new SwhId("swh:1:rev:0000000000000000000000000000000000000003");
- Visit visit = new Visit(graph, swhId, "rev:*", "backward", Visit.OutputFmt.ONLY_NODES);
- LinkedHashSet<SwhId> nodes = visit.getNodes();
+ Traversal traversal = new Traversal(graph, "backward", "rev:*");
+ ArrayList<SwhId> nodes = traversal.visitNodesEndpoint(swhId);
- LinkedHashSet<SwhId> expectedNodes = new LinkedHashSet<SwhId>();
+ ArrayList<SwhId> expectedNodes = new ArrayList<SwhId>();
expectedNodes.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000003"));
expectedNodes.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000009"));
expectedNodes.add(new SwhId("swh:1:snp:0000000000000000000000000000000000000020"));
diff --git a/api/server/src/test/java/org/softwareheritage/graph/WalkTest.java b/api/server/src/test/java/org/softwareheritage/graph/WalkTest.java
--- a/api/server/src/test/java/org/softwareheritage/graph/WalkTest.java
+++ b/api/server/src/test/java/org/softwareheritage/graph/WalkTest.java
@@ -11,19 +11,17 @@
import org.softwareheritage.graph.GraphTest;
import org.softwareheritage.graph.SwhId;
import org.softwareheritage.graph.SwhPath;
-import org.softwareheritage.graph.algo.Walk;
+import org.softwareheritage.graph.algo.Traversal;
public class WalkTest extends GraphTest {
@Test
public void forwardRootToLeaf() {
Graph graph = getGraph();
+ Traversal traversal = new Traversal(graph, "forward", "*");
SwhId src = new SwhId("swh:1:snp:0000000000000000000000000000000000000020");
String dstFmt = "swh:1:cnt:0000000000000000000000000000000000000005";
- Walk dfsWalk = new Walk(graph, src, dstFmt, "*", "forward", "dfs");
- Walk bfsWalk = new Walk(graph, src, dstFmt, "*", "forward", "bfs");
-
- SwhPath dfsPath = dfsWalk.getPath();
+ SwhPath dfsPath = traversal.walkEndpoint(src, dstFmt, "dfs");
SwhPath dfsExpectedPath =
new SwhPath(
"swh:1:snp:0000000000000000000000000000000000000020",
@@ -35,40 +33,36 @@
Assert.assertEquals(dfsExpectedPath, dfsPath);
// Most of DFS and BFS traversal outputs are the same because it is a small test graph
- SwhPath bfsPath = bfsWalk.getPath();
+ SwhPath bfsPath = traversal.walkEndpoint(src, dstFmt, "bfs");
Assert.assertEquals(dfsExpectedPath, bfsPath);
}
@Test
public void forwardLeafToLeaf() {
Graph graph = getGraph();
+ Traversal traversal = new Traversal(graph, "forward", "*");
SwhId src = new SwhId("swh:1:cnt:0000000000000000000000000000000000000007");
String dstFmt = "cnt";
- Walk dfsWalk = new Walk(graph, src, dstFmt, "*", "forward", "dfs");
- Walk bfsWalk = new Walk(graph, src, dstFmt, "*", "forward", "bfs");
-
- SwhPath dfsPath = dfsWalk.getPath();
+ SwhPath dfsPath = traversal.walkEndpoint(src, dstFmt, "dfs");
SwhPath dfsExpectedPath =
new SwhPath(
"swh:1:cnt:0000000000000000000000000000000000000007"
);
Assert.assertEquals(dfsExpectedPath, dfsPath);
- SwhPath bfsPath = bfsWalk.getPath();
+ SwhPath bfsPath = traversal.walkEndpoint(src, dstFmt, "bfs");
Assert.assertEquals(dfsExpectedPath, bfsPath);
}
@Test
public void forwardRevToRev() {
Graph graph = getGraph();
+ Traversal traversal = new Traversal(graph, "forward", "rev:rev");
SwhId src = new SwhId("swh:1:rev:0000000000000000000000000000000000000018");
String dstFmt = "swh:1:rev:0000000000000000000000000000000000000003";
- Walk dfsWalk = new Walk(graph, src, dstFmt, "rev:rev", "forward", "dfs");
- Walk bfsWalk = new Walk(graph, src, dstFmt, "rev:rev", "forward", "bfs");
-
- SwhPath dfsPath = dfsWalk.getPath();
+ SwhPath dfsPath = traversal.walkEndpoint(src, dstFmt, "dfs");
SwhPath dfsExpectedPath =
new SwhPath(
"swh:1:rev:0000000000000000000000000000000000000018",
@@ -78,20 +72,18 @@
);
Assert.assertEquals(dfsExpectedPath, dfsPath);
- SwhPath bfsPath = bfsWalk.getPath();
+ SwhPath bfsPath = traversal.walkEndpoint(src, dstFmt, "bfs");
Assert.assertEquals(dfsExpectedPath, bfsPath);
}
@Test
public void backwardRevToRev() {
Graph graph = getGraph();
+ Traversal traversal = new Traversal(graph, "backward", "rev:rev");
SwhId src = new SwhId("swh:1:rev:0000000000000000000000000000000000000003");
String dstFmt = "swh:1:rev:0000000000000000000000000000000000000018";
- Walk dfsWalk = new Walk(graph, src, dstFmt, "rev:rev", "backward", "dfs");
- Walk bfsWalk = new Walk(graph, src, dstFmt, "rev:rev", "backward", "bfs");
-
- SwhPath dfsPath = dfsWalk.getPath();
+ SwhPath dfsPath = traversal.walkEndpoint(src, dstFmt, "dfs");
SwhPath dfsExpectedPath =
new SwhPath(
"swh:1:rev:0000000000000000000000000000000000000003",
@@ -101,20 +93,18 @@
);
Assert.assertEquals(dfsExpectedPath, dfsPath);
- SwhPath bfsPath = bfsWalk.getPath();
+ SwhPath bfsPath = traversal.walkEndpoint(src, dstFmt, "bfs");
Assert.assertEquals(dfsExpectedPath, bfsPath);
}
@Test
public void backwardCntToFirstSnp() {
Graph graph = getGraph();
+ Traversal traversal = new Traversal(graph, "backward", "*");
SwhId src = new SwhId("swh:1:cnt:0000000000000000000000000000000000000001");
String dstFmt = "snp";
- Walk dfsWalk = new Walk(graph, src, dstFmt, "*", "backward", "dfs");
- Walk bfsWalk = new Walk(graph, src, dstFmt, "*", "backward", "bfs");
-
- SwhPath dfsPath = dfsWalk.getPath();
+ SwhPath dfsPath = traversal.walkEndpoint(src, dstFmt, "dfs");
SwhPath dfsExpectedPath =
new SwhPath(
"swh:1:cnt:0000000000000000000000000000000000000001",
@@ -125,7 +115,7 @@
);
Assert.assertEquals(dfsExpectedPath, dfsPath);
- SwhPath bfsPath = bfsWalk.getPath();
+ SwhPath bfsPath = traversal.walkEndpoint(src, dstFmt, "bfs");
SwhPath bfsExpectedPath =
new SwhPath(
"swh:1:cnt:0000000000000000000000000000000000000001",
@@ -139,13 +129,11 @@
@Test
public void forwardRevToFirstCnt() {
Graph graph = getGraph();
+ Traversal traversal = new Traversal(graph, "forward", "rev:*,dir:*");
SwhId src = new SwhId("swh:1:rev:0000000000000000000000000000000000000013");
String dstFmt = "cnt";
- Walk dfsWalk = new Walk(graph, src, dstFmt, "rev:*,dir:*", "forward", "dfs");
- Walk bfsWalk = new Walk(graph, src, dstFmt, "rev:*,dir:*", "forward", "bfs");
-
- SwhPath dfsPath = dfsWalk.getPath();
+ SwhPath dfsPath = traversal.walkEndpoint(src, dstFmt, "dfs");
SwhPath dfsExpectedPath =
new SwhPath(
"swh:1:rev:0000000000000000000000000000000000000013",
@@ -154,20 +142,18 @@
);
Assert.assertEquals(dfsExpectedPath, dfsPath);
- SwhPath bfsPath = bfsWalk.getPath();
+ SwhPath bfsPath = traversal.walkEndpoint(src, dstFmt, "bfs");
Assert.assertEquals(dfsExpectedPath, bfsPath);
}
@Test
public void backwardDirToFirstRel() {
Graph graph = getGraph();
+ Traversal traversal = new Traversal(graph, "backward", "dir:dir,dir:rev,rev:*");
SwhId src = new SwhId("swh:1:dir:0000000000000000000000000000000000000016");
String dstFmt = "rel";
- Walk dfsWalk = new Walk(graph, src, dstFmt, "dir:dir,dir:rev,rev:*", "backward", "dfs");
- Walk bfsWalk = new Walk(graph, src, dstFmt, "dir:dir,dir:rev,rev:*", "backward", "bfs");
-
- SwhPath dfsPath = dfsWalk.getPath();
+ SwhPath dfsPath = traversal.walkEndpoint(src, dstFmt, "dfs");
SwhPath dfsExpectedPath =
new SwhPath(
"swh:1:dir:0000000000000000000000000000000000000016",
@@ -177,7 +163,7 @@
);
Assert.assertEquals(dfsExpectedPath, dfsPath);
- SwhPath bfsPath = bfsWalk.getPath();
+ SwhPath bfsPath = traversal.walkEndpoint(src, dstFmt, "bfs");
Assert.assertEquals(dfsExpectedPath, bfsPath);
}
}
File Metadata
Details
Attached
Mime Type
text/plain
Expires
Tue, Dec 17, 6:24 AM (2 w, 1 d ago)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
3220026
Attached To
D1700: swh-graph: refactor algo implementations
Event Timeline
Log In to Comment