Differential D3600 Diff 12692 java/src/main/java/org/softwareheritage/graph/algo/Traversal.java

Changeset View

Standalone View

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

Show First 20 Lines • Show All 143 Lines • ▼ Show 20 Lines	public ArrayList<Long> neighbors(long srcNodeId) {
neighborsVisitor(srcNodeId, (nodeId) -> nodeIds.add(nodeId));		neighborsVisitor(srcNodeId, (nodeId) -> nodeIds.add(nodeId));
return nodeIds;		return nodeIds;
}		}

/**		/**
* Push version of {@link visitNodes}: will fire passed callback on each		* Push version of {@link visitNodes}: will fire passed callback on each
* visited node.		* visited node.
*/		*/
public void visitNodesVisitor(long srcNodeId, NodeIdConsumer cb) {		public void visitNodesVisitor(long srcNodeId, NodeIdConsumer nodeCb, EdgeIdConsumer edgeCb) {
Stack<Long> stack = new Stack<Long>();		Stack<Long> stack = new Stack<Long>();
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();
cb.accept(currentNodeId);		if (nodeCb != null) {
		nodeCb.accept(currentNodeId);
		}

nbEdgesAccessed += graph.degree(currentNodeId, useTransposed);		nbEdgesAccessed += graph.degree(currentNodeId, useTransposed);
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {		for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
		if (edgeCb != null) {
		edgeCb.accept(currentNodeId, neighborNodeId);
		}
if (!visited.contains(neighborNodeId)) {		if (!visited.contains(neighborNodeId)) {
stack.push(neighborNodeId);		stack.push(neighborNodeId);
visited.add(neighborNodeId);		visited.add(neighborNodeId);
}		}
		zackUnsubmitted Done Inline Actions Consider the graph A→B, C→B and assume A and B are visited first. I think this implementation of visit_edges will only return one of the two edges, because once you've marked B as visited for one of the two (say, A→B), you will never emit the other edge leading to B (say, C→B). Or am I missing something? zack: Consider the graph A→B, C→B and assume A and B are visited first. I think this implementation…
		seirlAuthorUnsubmitted Done Inline Actions You're right, I don't know how I missed that. This call should be outside the if. Nice catch, thanks. seirl: You're right, I don't know how I missed that. This call should be outside the if. Nice catch…
}		}
}		}
}		}

		/** One-argument version to handle callbacks properly */
		public void visitNodesVisitor(long srcNodeId, NodeIdConsumer cb) {
		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<Long>();		ArrayList<Long> nodeIds = new ArrayList<Long>();
▲ Show 20 Lines • Show All 304 Lines • Show Last 20 Lines