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 { + 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 iterator() { + return new NeighborsIterator(); + } + + public class NeighborsIterator implements Iterator { + 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 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(); - this.visited = LongArrayBitVector.ofLength(graph.getNbNodes()); - - long nodeId = graph.getNodeId(src); - dfs(nodeId); - } - - public ArrayList 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 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(); - - iterateNeighbors(src); - } - - public ArrayList 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 convertToSwhIds(ArrayList nodeIds) { + ArrayList swhIds = new ArrayList(); + for (long nodeId : nodeIds) { + swhIds.add(graph.getSwhId(nodeId)); + } + return swhIds; + } + + public ArrayList leavesEndpoint(SwhId src) { + long nodeId = graph.getNodeId(src); + ArrayList leavesNodeIds = leavesInternalEndpoint(nodeId); + return convertToSwhIds(leavesNodeIds); + } + + public ArrayList neighborsEndpoint(SwhId src) { + long nodeId = graph.getNodeId(src); + ArrayList neighborsNodeIds = neighborsInternalEndpoint(nodeId); + return convertToSwhIds(neighborsNodeIds); + } + + public ArrayList 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 path = backtracking(srcNodeId, dstNodeId); + return convertToSwhIds(path); + } + + public ArrayList visitNodesEndpoint(SwhId src) { + long nodeId = graph.getNodeId(src); + ArrayList nodes = visitNodesInternalEndpoint(nodeId); + return convertToSwhIds(nodes); + } + + public ArrayList> visitPathsEndpoint(SwhId src) { + long nodeId = graph.getNodeId(src); + ArrayList> pathNodeIds = new ArrayList<>(); + Stack currentPath = new Stack(); + visitPathsInternalEndpoint(nodeId, pathNodeIds, currentPath); + + ArrayList> paths = new ArrayList<>(); + for (ArrayList nodeIds : pathNodeIds) { + paths.add(convertToSwhIds(nodeIds)); + } + return paths; + } + + private ArrayList leavesInternalEndpoint(long srcNodeId) { + ArrayList leaves = new ArrayList(); + Stack stack = new Stack(); + 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 neighborsInternalEndpoint(long srcNodeId) { + SwhId srcSwhId = graph.getSwhId(srcNodeId); + ArrayList neighbors = new ArrayList(); + for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, srcSwhId)) { + neighbors.add(neighborNodeId); + } + return neighbors; + } + + private ArrayList visitNodesInternalEndpoint(long srcNodeId) { + // No specific destination point + String dstFmt = null; + dfs(srcNodeId, dstFmt); + + ArrayList nodes = new ArrayList(); + for (long nodeId = 0; nodeId < graph.getNbNodes(); nodeId++) { + if (this.visited.getBoolean(nodeId)) { + nodes.add(nodeId); + } + } + return nodes; + } + + private void visitPathsInternalEndpoint( + long currentNodeId, ArrayList> paths, Stack 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 path = new ArrayList(); + for (long nodeId : currentPath) { + path.add(nodeId); + } + paths.add(path); + } + + currentPath.pop(); + } + + private ArrayList backtracking(long srcNodeId, long dstNodeId) { + ArrayList path = new ArrayList(); + 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 stack = new Stack(); + 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 queue = new LinkedList(); + 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 nodes; - ArrayList paths; - Stack 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(); - this.paths = new ArrayList(); - this.currentPath = new Stack(); - this.visited = LongArrayBitVector.ofLength(graph.getNbNodes()); - - long nodeId = graph.getNodeId(src); - if (output == OutputFmt.ONLY_NODES) { - dfsOutputOnlyNodes(nodeId); - } else { - dfs(nodeId); - } - } - - public LinkedHashSet getNodes() { - return nodes; - } - - public ArrayList 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 stack = new Stack(); - 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 queue = new LinkedList(); - 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 paths, LinkedHashSet nodes) { LinkedHashSet expectedNodes = new LinkedHashSet(); 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 paths = visit.getPaths(); - LinkedHashSet nodes = visit.getNodes(); + Traversal traversal = new Traversal(graph, "forward", "*"); + ArrayList paths = traversal.visitPathsEndpoint(swhId); + ArrayList nodes = traversal.visitNodesEndpoint(swhId); ArrayList expectedPaths = new ArrayList(); 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 paths = visit.getPaths(); - LinkedHashSet nodes = visit.getNodes(); + Traversal traversal = new Traversal(graph, "forward", "*"); + ArrayList paths = traversal.visitPathsEndpoint(swhId); + ArrayList nodes = traversal.visitNodesEndpoint(swhId); ArrayList expectedPaths = new ArrayList(); 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 paths = visit.getPaths(); - LinkedHashSet nodes = visit.getNodes(); + Traversal traversal = new Traversal(graph, "forward", "*"); + ArrayList paths = traversal.visitPathsEndpoint(swhId); + ArrayList nodes = traversal.visitNodesEndpoint(swhId); ArrayList expectedPaths = new ArrayList(); 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 paths = visit.getPaths(); - LinkedHashSet nodes = visit.getNodes(); + Traversal traversal = new Traversal(graph, "backward", "*"); + ArrayList paths = traversal.visitPathsEndpoint(swhId); + ArrayList nodes = traversal.visitNodesEndpoint(swhId); ArrayList expectedPaths = new ArrayList(); 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 paths = visit.getPaths(); - LinkedHashSet nodes = visit.getNodes(); + Traversal traversal = new Traversal(graph, "backward", "*"); + ArrayList paths = traversal.visitPathsEndpoint(swhId); + ArrayList nodes = traversal.visitNodesEndpoint(swhId); ArrayList expectedPaths = new ArrayList(); 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 paths = visit.getPaths(); - LinkedHashSet nodes = visit.getNodes(); + Traversal traversal = new Traversal(graph, "backward", "*"); + ArrayList paths = traversal.visitPathsEndpoint(swhId); + ArrayList nodes = traversal.visitNodesEndpoint(swhId); ArrayList expectedPaths = new ArrayList(); 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 paths = visit.getPaths(); - LinkedHashSet nodes = visit.getNodes(); + Traversal traversal = new Traversal(graph, "forward", "snp:rev"); + ArrayList paths = traversal.visitPathsEndpoint(swhId); + ArrayList nodes = traversal.visitNodesEndpoint(swhId); ArrayList expectedPaths = new ArrayList(); 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 paths = visit.getPaths(); - LinkedHashSet nodes = visit.getNodes(); + Traversal traversal = new Traversal(graph, "forward", "rel:rev,rev:rev"); + ArrayList paths = traversal.visitPathsEndpoint(swhId); + ArrayList nodes = traversal.visitNodesEndpoint(swhId); ArrayList expectedPaths = new ArrayList(); 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 paths = visit.getPaths(); - LinkedHashSet nodes = visit.getNodes(); + Traversal traversal = new Traversal(graph, "forward", "rev:*,dir:*"); + ArrayList paths = traversal.visitPathsEndpoint(swhId); + ArrayList nodes = traversal.visitNodesEndpoint(swhId); ArrayList expectedPaths = new ArrayList(); 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 paths = visit.getPaths(); - LinkedHashSet nodes = visit.getNodes(); + Traversal traversal = new Traversal(graph, "forward", "snp:*,rev:*"); + ArrayList paths = traversal.visitPathsEndpoint(swhId); + ArrayList nodes = traversal.visitNodesEndpoint(swhId); ArrayList expectedPaths = new ArrayList(); 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 paths = visit.getPaths(); - LinkedHashSet nodes = visit.getNodes(); + Traversal traversal = new Traversal(graph, "forward", ""); + ArrayList paths = traversal.visitPathsEndpoint(swhId); + ArrayList nodes = traversal.visitNodesEndpoint(swhId); ArrayList expectedPaths = new ArrayList(); 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 paths = visit.getPaths(); - LinkedHashSet nodes = visit.getNodes(); + Traversal traversal = new Traversal(graph, "backward", "rev:rev,rev:rel"); + ArrayList paths = traversal.visitPathsEndpoint(swhId); + ArrayList nodes = traversal.visitNodesEndpoint(swhId); ArrayList expectedPaths = new ArrayList(); 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 nodes = visit.getNodes(); + Traversal traversal = new Traversal(graph, "forward", "*"); + ArrayList nodes = traversal.visitNodesEndpoint(swhId); - LinkedHashSet expectedNodes = new LinkedHashSet(); + ArrayList expectedNodes = new ArrayList(); 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 nodes = visit.getNodes(); + Traversal traversal = new Traversal(graph, "backward", "rev:*"); + ArrayList nodes = traversal.visitNodesEndpoint(swhId); - LinkedHashSet expectedNodes = new LinkedHashSet(); + ArrayList expectedNodes = new ArrayList(); 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); } }