Differential D6953 Diff 25202 java/src/main/java/org/softwareheritage/graph/Traversal.java

Changeset View

Standalone View

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

Show All 23 Lines
* 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
*/		*/

public class Traversal {		public class Traversal {
/** Graph used in the traversal */		/** Graph used in the traversal */
Graph graph;		SwhBidirectionalGraph graph;
/** Graph edge restriction */		/** Graph edge restrictions */
AllowedEdges edges;		AllowedEdges edges;

/** 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;
Show All 11 Lines	public class Traversal {
*		*
* @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(SwhBidirectionalGraph 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(SwhBidirectionalGraph graph, String direction, String edgesFmt, long maxEdges) {
this(graph, direction, edgesFmt, maxEdges, "*");		this(graph, direction, edgesFmt, maxEdges, "*");
}		}

public Traversal(Graph graph, String direction, String edgesFmt, long maxEdges, String returnTypes) {		public Traversal(SwhBidirectionalGraph 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;
Show All 27 Lines	public class Traversal {
*		*
* @return number of nodes accessed in last traversal		* @return number of nodes accessed in last traversal
*/		*/
public long getNbNodesAccessed() {		public long getNbNodesAccessed() {
return this.visited.size();		return this.visited.size();
}		}

/**		/**
		* Returns lazy iterator of successors of a node while following a specific set of edge types.
		*
		* @param g input graph
		* @param nodeId node specified as a long id
		* @param allowedEdges the specification of which edges can be traversed
		* @return lazy iterator of successors of the node, specified as a
		* <a href="http://webgraph.di.unimi.it/">WebGraph</a> LazyLongIterator
		*/
		public static LazyLongIterator filterSuccessors(SwhBidirectionalGraph g, long nodeId, AllowedEdges allowedEdges) {
		if (allowedEdges.restrictedTo == null) {
		// All edges are allowed, bypass edge check
		return g.successors(nodeId);
		} else {
		LazyLongIterator allSuccessors = g.successors(nodeId);
		return new LazyLongIterator() {
		@Override
		public long nextLong() {
		long neighbor;
		while ((neighbor = allSuccessors.nextLong()) != -1) {
		if (allowedEdges.isAllowed(g.getNodeType(nodeId), g.getNodeType(neighbor))) {
		return neighbor;
		}
		}
		return -1;
		}

		@Override
		public long skip(final long n) {
		long i;
		for (i = 0; i < n && nextLong() != -1; i++)
		;
		return i;
		}
		};
		}
		}

		private LazyLongIterator filterSuccessors(long nodeId, AllowedEdges allowedEdges) {
		return filterSuccessors(graph, nodeId, allowedEdges);
		}

		/**
* 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 (this.maxEdges > 0) {
if (nbEdgesAccessed >= this.maxEdges) {		if (nbEdgesAccessed >= this.maxEdges) {
break;		break;
}		}
}		}
LazyLongIterator it = graph.successors(currentNodeId, edges);		LazyLongIterator it = filterSuccessors(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 23 Lines	public class Traversal {
*/		*/
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 = graph.successors(srcNodeId, edges);		LazyLongIterator it = filterSuccessors(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 25 Lines	public void visitNodesVisitor(long srcNodeId, NodeIdConsumer nodeCb, EdgeIdConsumer edgeCb) {
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 = graph.successors(currentNodeId, edges);		LazyLongIterator it = filterSuccessors(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 20 Lines • Show All 50 Lines • ▼ Show 20 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 = graph.successors(currentNodeId, edges);		LazyLongIterator it = filterSuccessors(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);
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 = graph.successors(curNodeId, edges);		LazyLongIterator successors = filterSuccessors(curNodeId, edges);
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;
▲ Show 20 Lines • Show All 50 Lines • ▼ Show 20 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 = graph.successors(currentNodeId, edges);		LazyLongIterator it = filterSuccessors(currentNodeId, edges);
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 = graph.successors(currentNodeId, edges);		LazyLongIterator it = filterSuccessors(currentNodeId, edges);
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 = graph.successors(curNode, edges);		LazyLongIterator it = filterSuccessors(curNode, edges);
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 = graph.successors(curNode, edges);		LazyLongIterator it = filterSuccessors(curNode, edges);
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