diff --git a/api/server/src/main/java/org/softwareheritage/graph/App.java b/api/server/src/main/java/org/softwareheritage/graph/App.java index 924147a..a4541db 100644 --- a/api/server/src/main/java/org/softwareheritage/graph/App.java +++ b/api/server/src/main/java/org/softwareheritage/graph/App.java @@ -1,70 +1,70 @@ package org.softwareheritage.graph; import java.io.IOException; import java.util.List; import java.util.Map; import com.fasterxml.jackson.databind.ObjectMapper; import com.fasterxml.jackson.databind.PropertyNamingStrategy; import io.javalin.Javalin; import io.javalin.plugin.json.JavalinJackson; import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.SwhId; import org.softwareheritage.graph.algo.Stats; import org.softwareheritage.graph.algo.Visit; public class App { public static void main(String[] args) throws IOException { String path = args[0]; Graph graph = new Graph(path); Stats stats = new Stats(path); // Clean up on exit Runtime.getRuntime().addShutdownHook(new Thread() { public void run() { try { graph.cleanUp(); } catch (IOException e) { System.out.println("Could not clean up graph on exit: " + e); } } }); // Configure Jackson JSON to use snake case naming style ObjectMapper objectMapper = JavalinJackson.getObjectMapper(); objectMapper.setPropertyNamingStrategy(PropertyNamingStrategy.SNAKE_CASE); JavalinJackson.configure(objectMapper); Javalin app = Javalin.create().start(5009); app.get("/stats", ctx -> { ctx.json(stats); }); app.get("/visit/:swh_id", ctx -> { try { Map> queryParamMap = ctx.queryParamMap(); for (String key : queryParamMap.keySet()) { if (!key.matches("direction|edges|traversal")) { throw new IllegalArgumentException("Unknown query string: " + key); } } SwhId swhId = new SwhId(ctx.pathParam("swh_id")); // By default, traversal is a forward DFS using all edges String traversal = ctx.queryParam("traversal", "dfs"); String direction = ctx.queryParam("direction", "forward"); - String edges = ctx.queryParam("edges", "all"); + String edges = ctx.queryParam("edges", "*"); ctx.json(new Visit(graph, swhId, edges, traversal, direction)); } catch (IllegalArgumentException e) { ctx.status(400); ctx.result(e.getMessage()); } }); app.error(404, ctx -> { ctx.result("Not found"); }); } } diff --git a/api/server/src/main/java/org/softwareheritage/graph/Edges.java b/api/server/src/main/java/org/softwareheritage/graph/Edges.java new file mode 100644 index 0000000..bafa19a --- /dev/null +++ b/api/server/src/main/java/org/softwareheritage/graph/Edges.java @@ -0,0 +1,47 @@ +package org.softwareheritage.graph; + +import java.util.ArrayList; + +import org.softwareheritage.graph.Node; + +public class Edges { + boolean[][] allowed; + + public Edges(String edgesFmt) { + int nbNodeTypes = Node.Type.values().length; + this.allowed = new boolean[nbNodeTypes][nbNodeTypes]; + // Special values (null, empty, "*") + if (edgesFmt == null || edgesFmt.isEmpty()) { + return; + } + if (edgesFmt.equals("*")) { + for (int i = 0; i < nbNodeTypes; i++) { + for (int j = 0; j < nbNodeTypes; j++) { + allowed[i][j] = true; + } + } + return; + } + + // Format: "src1:dst1,src2:dst2,[...]" + String[] edgeTypes = edgesFmt.split(","); + for (String edgeType : edgeTypes) { + String[] nodeTypes = edgeType.split(":"); + if (nodeTypes.length != 2) { + throw new IllegalArgumentException("Cannot parse edge type: " + edgeType); + } + + ArrayList srcTypes = Node.Type.parse(nodeTypes[0]); + ArrayList dstTypes = Node.Type.parse(nodeTypes[1]); + for (Node.Type srcType : srcTypes) { + for (Node.Type dstType : dstTypes) { + allowed[srcType.ordinal()][dstType.ordinal()] = true; + } + } + } + } + + public boolean isAllowed(Node.Type currentType, Node.Type neighborType) { + return allowed[currentType.ordinal()][neighborType.ordinal()]; + } +} diff --git a/api/server/src/main/java/org/softwareheritage/graph/Node.java b/api/server/src/main/java/org/softwareheritage/graph/Node.java new file mode 100644 index 0000000..9668331 --- /dev/null +++ b/api/server/src/main/java/org/softwareheritage/graph/Node.java @@ -0,0 +1,32 @@ +package org.softwareheritage.graph; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.List; + +public class Node { + public enum Type { + CNT, + DIR, + REL, + REV, + SNP; + + public static Node.Type fromStr(String strType) { + return Node.Type.valueOf(strType.toUpperCase()); + } + + public static ArrayList parse(String strType) { + ArrayList types = new ArrayList<>(); + + if (strType.equals("*")) { + List nodeTypes = Arrays.asList(Node.Type.values()); + types.addAll(nodeTypes); + } else { + types.add(Node.Type.fromStr(strType)); + } + + return types; + } + } +} diff --git a/api/server/src/main/java/org/softwareheritage/graph/SwhId.java b/api/server/src/main/java/org/softwareheritage/graph/SwhId.java index 49dab71..eeb6584 100644 --- a/api/server/src/main/java/org/softwareheritage/graph/SwhId.java +++ b/api/server/src/main/java/org/softwareheritage/graph/SwhId.java @@ -1,59 +1,62 @@ package org.softwareheritage.graph; import com.fasterxml.jackson.annotation.JsonValue; +import org.softwareheritage.graph.Node; + public class SwhId { public static final int HASH_LENGTH = 40; String swhId; - String type; + Node.Type type; String hash; // SWH ID format: 'swh:1:type:hash' // https://docs.softwareheritage.org/devel/swh-model/persistent-identifiers.html public SwhId(String swhId) { this.swhId = swhId; String[] parts = swhId.split(":"); if (parts.length != 4 || !parts[0].equals("swh") || !parts[1].equals("1")) { throw new IllegalArgumentException("Expected SWH ID format to be 'swh:1:type:hash', got: " + swhId); } - this.type = parts[2]; + String type = parts[2]; if (!type.matches("cnt|dir|rel|rev|snp")) { throw new IllegalArgumentException("Unknown SWH ID type in: " + swhId); } + this.type = Node.Type.fromStr(type); this.hash = parts[3]; if (!hash.matches("[0-9a-f]{" + HASH_LENGTH + "}")) { throw new IllegalArgumentException("Wrong SWH ID hash format in: " + swhId); } } @Override public boolean equals(Object otherObj) { if (otherObj == this) return true; if (!(otherObj instanceof SwhId)) return false; SwhId other = (SwhId) otherObj; return swhId.equals(other.getSwhId()); } @Override public String toString() { return swhId; } @JsonValue public String getSwhId() { return swhId; } - public String getType() { + public Node.Type getType() { return type; } public String getHash() { return hash; } } 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 index 0037604..23e4e5f 100644 --- a/api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java +++ b/api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java @@ -1,80 +1,72 @@ package org.softwareheritage.graph.algo; import java.util.ArrayList; import java.util.Stack; import it.unimi.dsi.big.webgraph.LazyLongIterator; +import org.softwareheritage.graph.Edges; import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.Node; import org.softwareheritage.graph.SwhId; import org.softwareheritage.graph.SwhPath; public class Visit { Graph graph; boolean useTransposed; - String allowedEdges; + Edges edges; Stack currentPath; ArrayList paths; public Visit(Graph graph, SwhId swhId, String allowedEdges, String algorithm, String direction) { if (!algorithm.matches("dfs|bfs")) { throw new IllegalArgumentException("Unknown traversal algorithm: " + algorithm); } if (!direction.matches("forward|backward")) { throw new IllegalArgumentException("Unknown traversal direction: " + direction); } this.graph = graph; this.useTransposed = (direction.equals("backward")); - this.allowedEdges = allowedEdges; + this.edges = new Edges(allowedEdges); this.paths = new ArrayList(); this.currentPath = new Stack(); if (algorithm.equals("dfs")) { dfs(graph.getNodeId(swhId)); } } // Allow Jackson JSON to only serialize the 'paths' field public ArrayList getPaths() { return paths; } private void dfs(long 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(); - if (isEdgeAllowed(currentNodeId, neighborNodeId)) { + 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 boolean isEdgeAllowed(long currentNodeId, long neighborNodeId) { - if (allowedEdges.equals("all")) { - return true; - } - - String currentType = graph.getSwhId(currentNodeId).getType(); - String neighborType = graph.getSwhId(neighborNodeId).getType(); - String edgeType = currentType + ":" + neighborType; - String edgeTypeRev = neighborType + ":" + currentType; - return allowedEdges.contains(edgeType) || allowedEdges.contains(edgeTypeRev); - } }