Differential D5707 Diff 20372 java/src/main/java/org/softwareheritage/graph/Traversal.java

Changeset View

Standalone View

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

Show All 39 Lines	public class Traversal {
/** 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 */		/** The string represent the set of type restriction */
NodesFiltering ndsfilter;		NodesFiltering ndsfilter;

		long currentEdgeAccessed = 0;

/** 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
▲ Show 20 Lines • Show All 54 Lines • ▼ Show 20 Lines	public class Traversal {
}		}

/**		/**
* Push version of {@link #leaves} will fire passed callback for each leaf.		* Push version of {@link #leaves} will fire passed callback for each leaf.
*/		*/
public void leavesVisitor(long srcNodeId, NodeIdConsumer cb) {		public void leavesVisitor(long srcNodeId, NodeIdConsumer cb) {
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();

long neighborsCnt = 0;		long neighborsCnt = 0;
nbEdgesAccessed += graph.outdegree(currentNodeId);		nbEdgesAccessed += graph.outdegree(currentNodeId);
if (this.maxEdges > 0) {
if (nbEdgesAccessed >= this.maxEdges) {
break;
}
}
LazyLongIterator it = graph.successors(currentNodeId, edges);		LazyLongIterator it = graph.successors(currentNodeId, edges);
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {		for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
neighborsCnt++;		neighborsCnt++;
		if (this.maxEdges > 0) {
		if (neighborsCnt >= this.maxEdges) {
		return;
		}
		}
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) {
cb.accept(currentNodeId);		cb.accept(currentNodeId);
Show All 15 Lines	public ArrayList<Long> leaves(long srcNodeId) {
}		}
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);
		int currentEdgeAccessed = 0;
		vlorentzUnsubmitted Not Done Inline Actions Why is it defined both here and as an object attribute? vlorentz: Why is it defined both here and as an object attribute?
		HakimbAuthorUnsubmitted Done Inline Actions an error, my bad Hakimb: an error, my bad
		LazyLongIterator it = graph.successors(srcNodeId, edges);
		for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
		cb.accept(neighborNodeId);
		currentEdgeAccessed++;
if (this.maxEdges > 0) {		if (this.maxEdges > 0) {
if (nbEdgesAccessed >= this.maxEdges) {		if (currentEdgeAccessed >= this.maxEdges) {
		currentEdgeAccessed = 0;
return;		return;
}		}
}		}
LazyLongIterator it = graph.successors(srcNodeId, edges);
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
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) {		if (ndsfilter.restricted) {
return ndsfilter.filterByNodeTypes(nodeIds, graph);		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) {
nodeCb.accept(currentNodeId);
}
nbEdgesAccessed += graph.outdegree(currentNodeId);
if (this.maxEdges > 0) {		if (this.maxEdges > 0) {
if (nbEdgesAccessed >= this.maxEdges) {		// we can go through n arcs, so at the end we must have
		// the source node + n nodes reached through these n arcs
		if (currentEdgeAccessed > this.maxEdges) {
		currentEdgeAccessed = 0;
break;		break;
}		}
}		}
		nodeCb.accept(currentNodeId);
		currentEdgeAccessed++;
		}
		nbEdgesAccessed += graph.outdegree(currentNodeId);
LazyLongIterator it = graph.successors(currentNodeId, edges);		LazyLongIterator it = graph.successors(currentNodeId, edges);
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {		for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
if (edgeCb != null) {		if (edgeCb != null) {
		if (this.maxEdges > 0) {
		if (currentEdgeAccessed >= this.maxEdges) {
		currentEdgeAccessed = 0;
		return;
		}
		}
edgeCb.accept(currentNodeId, neighborNodeId);		edgeCb.accept(currentNodeId, neighborNodeId);
		currentEdgeAccessed++;

}		}
if (!visited.contains(neighborNodeId)) {		if (!visited.contains(neighborNodeId)) {
stack.push(neighborNodeId);		stack.push(neighborNodeId);
visited.add(neighborNodeId);		visited.add(neighborNodeId);
}		}
}		}
}		}
}		}
Show All 37 Lines	public class Traversal {
public ArrayList<ArrayList<Long>> visitPaths(long srcNodeId) {		public ArrayList<ArrayList<Long>> visitPaths(long srcNodeId) {
ArrayList<ArrayList<Long>> paths = new ArrayList<>();		ArrayList<ArrayList<Long>> paths = new ArrayList<>();
visitPathsVisitor(srcNodeId, paths::add);		visitPathsVisitor(srcNodeId, paths::add);
return paths;		return paths;
}		}

private void visitPathsInternalVisitor(long currentNodeId, Stack<Long> currentPath, PathConsumer cb) {		private void visitPathsInternalVisitor(long currentNodeId, Stack<Long> currentPath, PathConsumer cb) {
currentPath.push(currentNodeId);		currentPath.push(currentNodeId);

long visitedNeighbors = 0;		long visitedNeighbors = 0;

nbEdgesAccessed += graph.outdegree(currentNodeId);		nbEdgesAccessed += graph.outdegree(currentNodeId);
		LazyLongIterator it = graph.successors(currentNodeId, edges);
		for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
if (this.maxEdges > 0) {		if (this.maxEdges > 0) {
if (nbEdgesAccessed >= this.maxEdges) {		if (currentEdgeAccessed >= this.maxEdges) {
currentPath.pop();		currentEdgeAccessed = 0;
return;		break;
}		}
}		}
LazyLongIterator it = graph.successors(currentNodeId, edges);		currentEdgeAccessed++;
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 290 Lines • Show Last 20 Lines