Differential D6954 Diff 25256 java/src/main/java/org/softwareheritage/graph/Traversal.java

Changeset View

Standalone View

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

Show All 24 Lines
*		*
* @author The Software Heritage developers		* @author The Software Heritage developers
* @see Endpoint		* @see Endpoint
*/		*/

public class Traversal {		public class Traversal {
/** Graph used in the traversal */		/** Graph used in the traversal */
SwhBidirectionalGraph graph;		SwhBidirectionalGraph graph;
/** Graph edge restrictions */		/** Type filter on the returned nodes */
AllowedEdges edges;		AllowedNodes nodesFilter;
		/** Restrictions on which edges can be traversed */
		AllowedEdges edgesRestrictions;

/** Hash set storing if we have visited a node */		/** Hash set storing if we have visited a node */
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
Show All 17 Lines	public Traversal(SwhBidirectionalGraph graph, String direction, String edgesFmt, long maxEdges,
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.nodesFilter = new AllowedNodes(returnTypes);
		this.edgesRestrictions = 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 66 Lines • ▼ Show 20 Lines	public void leavesVisitor(long srcNodeId, NodeIdConsumer cb) {

long neighborsCnt = 0;		long neighborsCnt = 0;
nbEdgesAccessed += graph.outdegree(currentNodeId);		nbEdgesAccessed += graph.outdegree(currentNodeId);
if (this.maxEdges > 0) {		if (this.maxEdges > 0) {
if (nbEdgesAccessed >= this.maxEdges) {		if (nbEdgesAccessed >= this.maxEdges) {
break;		break;
}		}
}		}
LazyLongIterator it = filterSuccessors(currentNodeId, edges);		LazyLongIterator it = filterSuccessors(currentNodeId, edgesRestrictions);
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {		for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
neighborsCnt++;		neighborsCnt++;
if (!visited.contains(neighborNodeId)) {		if (!visited.contains(neighborNodeId)) {
stack.push(neighborNodeId);		stack.push(neighborNodeId);
visited.add(neighborNodeId);		visited.add(neighborNodeId);
}		}
}		}

if (neighborsCnt == 0) {		if (neighborsCnt == 0) {
		if (nodesFilter.isAllowed(graph.getNodeType(currentNodeId))) {
cb.accept(currentNodeId);		cb.accept(currentNodeId);
}		}
}		}
}		}
		}

/**		/**
* 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<Long>();		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);
if (this.maxEdges > 0) {		if (this.maxEdges > 0) {
if (nbEdgesAccessed >= this.maxEdges) {		if (nbEdgesAccessed >= this.maxEdges) {
return;		return;
}		}
}		}
LazyLongIterator it = filterSuccessors(srcNodeId, edges);		LazyLongIterator it = filterSuccessors(srcNodeId, edgesRestrictions);
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {		for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
		if (nodesFilter.isAllowed(graph.getNodeType(neighborNodeId))) {
cb.accept(neighborNodeId);		cb.accept(neighborNodeId);
}		}
}		}
		}

/**		/**
* 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<>();
this.nbEdgesAccessed = 0;		this.nbEdgesAccessed = 0;

stack.push(srcNodeId);		stack.push(srcNodeId);
visited.add(srcNodeId);		visited.add(srcNodeId);

while (!stack.isEmpty()) {		while (!stack.isEmpty()) {
long currentNodeId = stack.pop();		long currentNodeId = stack.pop();
if (nodeCb != null) {		if (nodeCb != null) {
		if (nodesFilter.isAllowed(graph.getNodeType(currentNodeId))) {
nodeCb.accept(currentNodeId);		nodeCb.accept(currentNodeId);
}		}
		}
nbEdgesAccessed += graph.outdegree(currentNodeId);		nbEdgesAccessed += graph.outdegree(currentNodeId);
if (this.maxEdges > 0) {		if (this.maxEdges > 0) {
if (nbEdgesAccessed >= this.maxEdges) {		if (nbEdgesAccessed >= this.maxEdges) {
break;		break;
}		}
}		}
LazyLongIterator it = filterSuccessors(currentNodeId, edges);		LazyLongIterator it = filterSuccessors(currentNodeId, edgesRestrictions);
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {		for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
if (edgeCb != null) {		if (edgeCb != null) {
		if (nodesFilter.isAllowed(graph.getNodeType(currentNodeId))) {
edgeCb.accept(currentNodeId, neighborNodeId);		edgeCb.accept(currentNodeId, neighborNodeId);
}		}
		}
if (!visited.contains(neighborNodeId)) {		if (!visited.contains(neighborNodeId)) {
stack.push(neighborNodeId);		stack.push(neighborNodeId);
visited.add(neighborNodeId);		visited.add(neighborNodeId);
}		}
}		}
}		}
}		}

/** One-argument version to handle callbacks properly */		/** One-argument version to handle callbacks properly */
public void visitNodesVisitor(long srcNodeId, NodeIdConsumer cb) {		public void visitNodesVisitor(long srcNodeId, NodeIdConsumer cb) {
visitNodesVisitor(srcNodeId, cb, null);		visitNodesVisitor(srcNodeId, cb, null);
}		}

/**		/**
* 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 All 21 Lines	private void visitPathsInternalVisitor(long currentNodeId, Stack<Long> currentPath, PathConsumer cb) {

nbEdgesAccessed += graph.outdegree(currentNodeId);		nbEdgesAccessed += graph.outdegree(currentNodeId);
if (this.maxEdges > 0) {		if (this.maxEdges > 0) {
if (nbEdgesAccessed >= this.maxEdges) {		if (nbEdgesAccessed >= this.maxEdges) {
currentPath.pop();		currentPath.pop();
return;		return;
}		}
}		}
LazyLongIterator it = filterSuccessors(currentNodeId, edges);		LazyLongIterator it = filterSuccessors(currentNodeId, edgesRestrictions);
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {		for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
visitPathsInternalVisitor(neighborNodeId, currentPath, cb);		visitPathsInternalVisitor(neighborNodeId, currentPath, cb);
visitedNeighbors++;		visitedNeighbors++;
}		}

if (visitedNeighbors == 0) {		if (visitedNeighbors == 0) {
ArrayList<Long> path = new ArrayList<>(currentPath);		ArrayList<Long> path = new ArrayList<>(currentPath);
cb.accept(path);		cb.accept(path);
▲ Show 20 Lines • Show All 57 Lines • ▼ Show 20 Lines	public <T> ArrayList<Long> randomWalk(long srcNodeId, T dst, int retries) {
boolean found;		boolean found;

if (retries < 0) {		if (retries < 0) {
throw new IllegalArgumentException("Negative number of retries given: " + retries);		throw new IllegalArgumentException("Negative number of retries given: " + retries);
}		}

while (true) {		while (true) {
path.add(curNodeId);		path.add(curNodeId);
LazyLongIterator successors = filterSuccessors(curNodeId, edges);		LazyLongIterator successors = filterSuccessors(curNodeId, edgesRestrictions);
curNodeId = randomPick(successors);		curNodeId = randomPick(successors);
if (curNodeId < 0) {		if (curNodeId < 0) {
found = false;		found = false;
break;		break;
}		}
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 All 34 Lines	private <T> long walkInternalDFS(long srcNodeId, T dst) {

while (!stack.isEmpty()) {		while (!stack.isEmpty()) {
long currentNodeId = stack.pop();		long currentNodeId = stack.pop();
if (isDstNode(currentNodeId, dst)) {		if (isDstNode(currentNodeId, dst)) {
return currentNodeId;		return currentNodeId;
}		}

nbEdgesAccessed += graph.outdegree(currentNodeId);		nbEdgesAccessed += graph.outdegree(currentNodeId);
LazyLongIterator it = filterSuccessors(currentNodeId, edges);		LazyLongIterator it = filterSuccessors(currentNodeId, edgesRestrictions);
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {		for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
if (!visited.contains(neighborNodeId)) {		if (!visited.contains(neighborNodeId)) {
stack.push(neighborNodeId);		stack.push(neighborNodeId);
visited.add(neighborNodeId);		visited.add(neighborNodeId);
parentNode.put(neighborNodeId, currentNodeId);		parentNode.put(neighborNodeId, currentNodeId);
}		}
}		}
}		}
Show All 17 Lines	private <T> long walkInternalBFS(long srcNodeId, T dst) {

while (!queue.isEmpty()) {		while (!queue.isEmpty()) {
long currentNodeId = queue.poll();		long currentNodeId = queue.poll();
if (isDstNode(currentNodeId, dst)) {		if (isDstNode(currentNodeId, dst)) {
return currentNodeId;		return currentNodeId;
}		}

nbEdgesAccessed += graph.outdegree(currentNodeId);		nbEdgesAccessed += graph.outdegree(currentNodeId);
LazyLongIterator it = filterSuccessors(currentNodeId, edges);		LazyLongIterator it = filterSuccessors(currentNodeId, edgesRestrictions);
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {		for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
if (!visited.contains(neighborNodeId)) {		if (!visited.contains(neighborNodeId)) {
queue.add(neighborNodeId);		queue.add(neighborNodeId);
visited.add(neighborNodeId);		visited.add(neighborNodeId);
parentNode.put(neighborNodeId, currentNodeId);		parentNode.put(neighborNodeId, currentNodeId);
}		}
}		}
}		}
▲ Show 20 Lines • Show All 58 Lines • ▼ Show 20 Lines	public Long findCommonDescendant(long lhsNode, long rhsNode) {

this.nbEdgesAccessed = 0;		this.nbEdgesAccessed = 0;
Long curNode;		Long curNode;

while (!lhsStack.isEmpty() \|\| !rhsStack.isEmpty()) {		while (!lhsStack.isEmpty() \|\| !rhsStack.isEmpty()) {
if (!lhsStack.isEmpty()) {		if (!lhsStack.isEmpty()) {
curNode = lhsStack.poll();		curNode = lhsStack.poll();
nbEdgesAccessed += graph.outdegree(curNode);		nbEdgesAccessed += graph.outdegree(curNode);
LazyLongIterator it = filterSuccessors(curNode, edges);		LazyLongIterator it = filterSuccessors(curNode, edgesRestrictions);
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {		for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
if (!lhsVisited.contains(neighborNodeId)) {		if (!lhsVisited.contains(neighborNodeId)) {
if (rhsVisited.contains(neighborNodeId))		if (rhsVisited.contains(neighborNodeId))
return neighborNodeId;		return neighborNodeId;
lhsStack.add(neighborNodeId);		lhsStack.add(neighborNodeId);
lhsVisited.add(neighborNodeId);		lhsVisited.add(neighborNodeId);
}		}
}		}
}		}

if (!rhsStack.isEmpty()) {		if (!rhsStack.isEmpty()) {
curNode = rhsStack.poll();		curNode = rhsStack.poll();
nbEdgesAccessed += graph.outdegree(curNode);		nbEdgesAccessed += graph.outdegree(curNode);
LazyLongIterator it = filterSuccessors(curNode, edges);		LazyLongIterator it = filterSuccessors(curNode, edgesRestrictions);
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {		for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
if (!rhsVisited.contains(neighborNodeId)) {		if (!rhsVisited.contains(neighborNodeId)) {
if (lhsVisited.contains(neighborNodeId))		if (lhsVisited.contains(neighborNodeId))
return neighborNodeId;		return neighborNodeId;
rhsStack.add(neighborNodeId);		rhsStack.add(neighborNodeId);
rhsVisited.add(neighborNodeId);		rhsVisited.add(neighborNodeId);
}		}
}		}
Show All 27 Lines