Differential D5501 Diff 19993 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	public class Traversal {

/** 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 */
		long maxEdges;

/** 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);
		}

		public Traversal(Graph graph, String direction, String edgesFmt, long maxEdges) {
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.rng = new Random();		this.rng = new Random();
}		}

/**		/**
* 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
*/		*/
Show All 20 Lines	public void leavesVisitor(long srcNodeId, NodeIdConsumer cb) {
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 (!visited.contains(neighborNodeId)) {		if (!visited.contains(neighborNodeId)) {
stack.push(neighborNodeId);		stack.push(neighborNodeId);
visited.add(neighborNodeId);		visited.add(neighborNodeId);
}		}
}		}
Show All 16 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);
		if (this.maxEdges > 0) {
		if (nbEdgesAccessed >= this.maxEdges) {
		return;
		}
		}
LazyLongIterator it = graph.successors(srcNodeId, edges);		LazyLongIterator it = graph.successors(srcNodeId, edges);
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {		for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
cb.accept(neighborNodeId);		cb.accept(neighborNodeId);
}		}
}		}

/**		/**
* Returns node direct neighbors (linked with exactly one edge).		* Returns node direct neighbors (linked with exactly one edge).
Show All 17 Lines	public void visitNodesVisitor(long srcNodeId, NodeIdConsumer nodeCb, EdgeIdConsumer edgeCb) {
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);		nodeCb.accept(currentNodeId);
}		}

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;) {
if (edgeCb != null) {		if (edgeCb != null) {
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);
Show All 40 Lines	public ArrayList<ArrayList<Long>> visitPaths(long srcNodeId) {
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);
		if (this.maxEdges > 0) {
		if (nbEdgesAccessed >= this.maxEdges) {
		currentPath.pop();
		return;
		}
		}
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;) {
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);
▲ Show 20 Lines • Show All 289 Lines • Show Last 20 Lines