Differential D5577 Diff 20266 java/src/main/java/org/softwareheritage/graph/Traversal.java

Changeset View

Standalone View

java/src/main/java/org/softwareheritage/graph/Traversal.java

package org.softwareheritage.graph;		package org.softwareheritage.graph;

import it.unimi.dsi.big.webgraph.LazyLongIterator;		import java.util.ArrayDeque;
import org.softwareheritage.graph.server.Endpoint;		import java.util.ArrayList;
		import java.util.Collections;
import java.util.*;		import java.util.HashMap;
		import java.util.HashSet;
		import java.util.LinkedList;
		import java.util.Map;
		import java.util.Queue;
		import java.util.Random;
		import java.util.Stack;
import java.util.function.Consumer;		import java.util.function.Consumer;
import java.util.function.LongConsumer;		import java.util.function.LongConsumer;

		import org.softwareheritage.graph.server.Endpoint;

		import it.unimi.dsi.big.webgraph.LazyLongIterator;

/**		/**
* Traversal algorithms on the compressed graph.		* Traversal algorithms on the compressed graph.
* <p>		* <p>
* Internal implementation of the traversal API endpoints. These methods only input/output internal		* Internal implementation of the traversal API endpoints. These methods only input/output internal
* long ids, which are converted in the {@link Endpoint} higher-level class to {@link SWHID}.		* long ids, which are converted in the {@link Endpoint} higher-level class to {@link SWHID}.
*		*
* @author The Software Heritage developers		* @author The Software Heritage developers
* @see Endpoint		* @see Endpoint
Show All 9 Lines	public class Traversal {
HashSet<Long> visited;		HashSet<Long> visited;
/** Hash map storing parent node id for each nodes during a traversal */		/** Hash map storing parent node id for each nodes during a traversal */
Map<Long, Long> parentNode;		Map<Long, Long> parentNode;
/** Number of edges accessed during traversal */		/** Number of edges accessed during traversal */
long nbEdgesAccessed;		long nbEdgesAccessed;

/** The anti Dos limit of edges traversed while a visit */		/** The anti Dos limit of edges traversed while a visit */
long maxEdges;		long maxEdges;
		/** The string represent the set of type restriction */
		NodesFiltering ndsfilter;

/** random number generator, for random walks */		/** random number generator, for random walks */
Random rng;		Random rng;

/**		/**
* Constructor.		* Constructor.
*		*
* @param graph graph used in the traversal		* @param graph graph used in the traversal
* @param direction a string (either "forward" or "backward") specifying edge orientation		* @param direction a string (either "forward" or "backward") specifying edge orientation
* @param edgesFmt a formatted string describing <a href=		* @param edgesFmt a formatted string describing <a href=
* "https://docs.softwareheritage.org/devel/swh-graph/api.html#terminology">allowed		* "https://docs.softwareheritage.org/devel/swh-graph/api.html#terminology">allowed
* edges</a>		* edges</a>
*/		*/

public Traversal(Graph graph, String direction, String edgesFmt) {		public Traversal(Graph graph, String direction, String edgesFmt) {
this(graph, direction, edgesFmt, 0);		this(graph, direction, edgesFmt, 0);
}		}

public Traversal(Graph graph, String direction, String edgesFmt, long maxEdges) {		public Traversal(Graph graph, String direction, String edgesFmt, long maxEdges) {
		this(graph, direction, edgesFmt, 0, "*");
		}

		public Traversal(Graph graph, String direction, String edgesFmt, long maxEdges, String returnTypes) {
if (!direction.matches("forward\|backward")) {		if (!direction.matches("forward\|backward")) {
throw new IllegalArgumentException("Unknown traversal direction: " + direction);		throw new IllegalArgumentException("Unknown traversal direction: " + direction);
}		}

if (direction.equals("backward")) {		if (direction.equals("backward")) {
this.graph = graph.transpose();		this.graph = graph.transpose();
} else {		} else {
this.graph = graph;		this.graph = graph;
}		}
this.edges = new AllowedEdges(edgesFmt);		this.edges = new AllowedEdges(edgesFmt);

this.visited = new HashSet<>();		this.visited = new HashSet<>();
this.parentNode = new HashMap<>();		this.parentNode = new HashMap<>();
this.nbEdgesAccessed = 0;		this.nbEdgesAccessed = 0;
this.maxEdges = maxEdges;		this.maxEdges = maxEdges;
this.rng = new Random();		this.rng = new Random();

		if (returnTypes.equals("*")) {
		this.ndsfilter = new NodesFiltering();
		} else {
		this.ndsfilter = new NodesFiltering(returnTypes);
		}
}		}

/**		/**
* Returns number of accessed edges during traversal.		* Returns number of accessed edges during traversal.
*		*
* @return number of edges accessed in last traversal		* @return number of edges accessed in last traversal
*/		*/
public long getNbEdgesAccessed() {		public long getNbEdgesAccessed() {
▲ Show 20 Lines • Show All 46 Lines • ▼ Show 20 Lines	public class Traversal {

/**		/**
* Returns the leaves of a subgraph rooted at the specified source node.		* Returns the leaves of a subgraph rooted at the specified source node.
*		*
* @param srcNodeId source node		* @param srcNodeId source node
* @return list of node ids corresponding to the leaves		* @return list of node ids corresponding to the leaves
*/		*/
public ArrayList<Long> leaves(long srcNodeId) {		public ArrayList<Long> leaves(long srcNodeId) {
ArrayList<Long> nodeIds = new ArrayList<>();		ArrayList<Long> nodeIds = new ArrayList<Long>();
leavesVisitor(srcNodeId, nodeIds::add);		leavesVisitor(srcNodeId, nodeIds::add);
		if (ndsfilter.restricted) {
		return ndsfilter.filterByNodeTypes(nodeIds, graph);
		}
return nodeIds;		return nodeIds;
}		}

/**		/**
* Push version of {@link #neighbors}: will fire passed callback on each neighbor.		* Push version of {@link #neighbors}: will fire passed callback on each neighbor.
*/		*/
public void neighborsVisitor(long srcNodeId, NodeIdConsumer cb) {		public void neighborsVisitor(long srcNodeId, NodeIdConsumer cb) {
this.nbEdgesAccessed = graph.outdegree(srcNodeId);		this.nbEdgesAccessed = graph.outdegree(srcNodeId);
Show All 12 Lines	public class Traversal {
* Returns node direct neighbors (linked with exactly one edge).		* Returns node direct neighbors (linked with exactly one edge).
*		*
* @param srcNodeId source node		* @param srcNodeId source node
* @return list of node ids corresponding to the neighbors		* @return list of node ids corresponding to the neighbors
*/		*/
public ArrayList<Long> neighbors(long srcNodeId) {		public ArrayList<Long> neighbors(long srcNodeId) {
ArrayList<Long> nodeIds = new ArrayList<>();		ArrayList<Long> nodeIds = new ArrayList<>();
neighborsVisitor(srcNodeId, nodeIds::add);		neighborsVisitor(srcNodeId, nodeIds::add);
		if (ndsfilter.restricted) {
		return ndsfilter.filterByNodeTypes(nodeIds, graph);
		}
return nodeIds;		return nodeIds;
}		}

/**		/**
* Push version of {@link #visitNodes}: will fire passed callback on each visited node.		* Push version of {@link #visitNodes}: will fire passed callback on each visited node.
*/		*/
public void visitNodesVisitor(long srcNodeId, NodeIdConsumer nodeCb, EdgeIdConsumer edgeCb) {		public void visitNodesVisitor(long srcNodeId, NodeIdConsumer nodeCb, EdgeIdConsumer edgeCb) {
Stack<Long> stack = new Stack<>();		Stack<Long> stack = new Stack<>();
Show All 35 Lines	public class Traversal {
* Performs a graph traversal and returns explored nodes.		* Performs a graph traversal and returns explored nodes.
*		*
* @param srcNodeId source node		* @param srcNodeId source node
* @return list of explored node ids		* @return list of explored node ids
*/		*/
public ArrayList<Long> visitNodes(long srcNodeId) {		public ArrayList<Long> visitNodes(long srcNodeId) {
ArrayList<Long> nodeIds = new ArrayList<>();		ArrayList<Long> nodeIds = new ArrayList<>();
visitNodesVisitor(srcNodeId, nodeIds::add);		visitNodesVisitor(srcNodeId, nodeIds::add);
		if (ndsfilter.restricted) {
		return ndsfilter.filterByNodeTypes(nodeIds, graph);
		}
return nodeIds;		return nodeIds;
}		}

/**		/**
* Push version of {@link #visitPaths}: will fire passed callback on each discovered (complete)		* Push version of {@link #visitPaths}: will fire passed callback on each discovered (complete)
* path.		* path.
*/		*/
public void visitPathsVisitor(long srcNodeId, PathConsumer cb) {		public void visitPathsVisitor(long srcNodeId, PathConsumer cb) {
▲ Show 20 Lines • Show All 109 Lines • ▼ Show 20 Lines	public <T> ArrayList<Long> randomWalk(long srcNodeId, T dst, int retries) {
if (isDstNode(curNodeId, dst)) {		if (isDstNode(curNodeId, dst)) {
path.add(curNodeId);		path.add(curNodeId);
found = true;		found = true;
break;		break;
}		}
}		}

if (found) {		if (found) {
		if (ndsfilter.restricted) {
		return ndsfilter.filterByNodeTypes(path, graph);
		}
return path;		return path;
} else if (retries > 0) { // try again		} else if (retries > 0) { // try again
return randomWalk(srcNodeId, dst, retries - 1);		return randomWalk(srcNodeId, dst, retries - 1);
} else { // not found and no retries left		} else { // not found and no retries left
path.clear();		path.clear();
return path;		return path;
}		}
}		}
▲ Show 20 Lines • Show All 201 Lines • Show Last 20 Lines