Differential D1846 Diff 6214 java/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java

Changeset View

Standalone View

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

Show All 34 Lines	public class Traversal {
boolean useTransposed;		boolean useTransposed;
/** Graph edge restriction */		/** Graph edge restriction */
AllowedEdges edges;		AllowedEdges edges;

/** Bit array storing if we have visited a node */		/** Bit array storing if we have visited a node */
LongArrayBitVector visited;		LongArrayBitVector visited;
/** LongBigArray storing parent node id for each nodes during a traversal */		/** LongBigArray storing parent node id for each nodes during a traversal */
long[][] nodeParent;		long[][] nodeParent;
		/** Number of edges accessed during traversal */
		long nbEdgesAccessed;

/**		/**
* 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		* @param edgesFmt a formatted string describing <a
* href="https://docs.softwareheritage.org/devel/swh-graph/api.html#terminology">allowed edges</a>		* href="https://docs.softwareheritage.org/devel/swh-graph/api.html#terminology">allowed edges</a>
*/		*/
public Traversal(Graph graph, String direction, String edgesFmt) {		public Traversal(Graph graph, String direction, String edgesFmt) {
if (!direction.matches("forward\|backward")) {		if (!direction.matches("forward\|backward")) {
throw new IllegalArgumentException("Unknown traversal direction: " + direction);		throw new IllegalArgumentException("Unknown traversal direction: " + direction);
}		}

this.graph = graph;		this.graph = graph;
this.useTransposed = (direction.equals("backward"));		this.useTransposed = (direction.equals("backward"));
this.edges = new AllowedEdges(graph, edgesFmt);		this.edges = new AllowedEdges(graph, edgesFmt);

long nbNodes = graph.getNbNodes();		long nbNodes = graph.getNbNodes();
this.visited = LongArrayBitVector.ofLength(nbNodes);		this.visited = LongArrayBitVector.ofLength(nbNodes);
this.nodeParent = LongBigArrays.newBigArray(nbNodes);		this.nodeParent = LongBigArrays.newBigArray(nbNodes);
		this.nbEdgesAccessed = 0;
		}

		/**
		* Returns number of accessed edges during traversal.
		*
		* @return number of edges accessed in last traversal
		*/
		public long getnbEdgesAccessed() {
		return nbEdgesAccessed;
}		}

/**		/**
* 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>();
Stack<Long> stack = new Stack<Long>();		Stack<Long> stack = new Stack<Long>();
this.visited.fill(false);		this.visited.fill(false);
		this.nbEdgesAccessed = 0;

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

while (!stack.isEmpty()) {		while (!stack.isEmpty()) {
long currentNodeId = stack.pop();		long currentNodeId = stack.pop();

long neighborsCnt = 0;		long neighborsCnt = 0;
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {		for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
neighborsCnt++;		neighborsCnt++;
		nbEdgesAccessed++;
if (!visited.getBoolean(neighborNodeId)) {		if (!visited.getBoolean(neighborNodeId)) {
stack.push(neighborNodeId);		stack.push(neighborNodeId);
visited.set(neighborNodeId);		visited.set(neighborNodeId);
}		}
}		}

if (neighborsCnt == 0) {		if (neighborsCnt == 0) {
nodeIds.add(currentNodeId);		nodeIds.add(currentNodeId);
}		}
}		}

return nodeIds;		return nodeIds;
}		}

/**		/**
* 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<Long>();		ArrayList<Long> nodeIds = new ArrayList<Long>();
		this.nbEdgesAccessed = 0;
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, srcNodeId)) {		for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, srcNodeId)) {
nodeIds.add(neighborNodeId);		nodeIds.add(neighborNodeId);
		nbEdgesAccessed++;
}		}
return nodeIds;		return nodeIds;
}		}

/**		/**
* 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>();
Stack<Long> stack = new Stack<Long>();		Stack<Long> stack = new Stack<Long>();
this.visited.fill(false);		this.visited.fill(false);
		this.nbEdgesAccessed = 0;

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

while (!stack.isEmpty()) {		while (!stack.isEmpty()) {
long currentNodeId = stack.pop();		long currentNodeId = stack.pop();
nodeIds.add(currentNodeId);		nodeIds.add(currentNodeId);

for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {		for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
		nbEdgesAccessed++;
if (!visited.getBoolean(neighborNodeId)) {		if (!visited.getBoolean(neighborNodeId)) {
stack.push(neighborNodeId);		stack.push(neighborNodeId);
visited.set(neighborNodeId);		visited.set(neighborNodeId);
}		}
}		}
}		}

return nodeIds;		return nodeIds;
}		}

/**		/**
* Performs a graph traversal and returns explored paths.		* Performs a graph traversal and returns explored paths.
*		*
* @param srcNodeId source node		* @param srcNodeId source node
* @return list of explored paths (represented as a list of node ids)		* @return list of explored paths (represented as a list of node ids)
*/		*/
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<>();
Stack<Long> currentPath = new Stack<Long>();		Stack<Long> currentPath = new Stack<Long>();
		this.nbEdgesAccessed = 0;
visitPathsInternal(srcNodeId, paths, currentPath);		visitPathsInternal(srcNodeId, paths, currentPath);
return paths;		return paths;
}		}

/**		/**
* Internal recursive function of {@link #visitPaths}.		* Internal recursive function of {@link #visitPaths}.
*		*
* @param currentNodeId current node		* @param currentNodeId current node
* @param paths list of currently stored paths		* @param paths list of currently stored paths
* @param currentPath current path as node ids		* @param currentPath current path as node ids
*/		*/
private void visitPathsInternal(		private void visitPathsInternal(
long currentNodeId, ArrayList<ArrayList<Long>> paths, Stack<Long> currentPath) {		long currentNodeId, ArrayList<ArrayList<Long>> paths, Stack<Long> currentPath) {
currentPath.push(currentNodeId);		currentPath.push(currentNodeId);

long visitedNeighbors = 0;		long visitedNeighbors = 0;
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {		for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
visitPathsInternal(neighborNodeId, paths, currentPath);		visitPathsInternal(neighborNodeId, paths, currentPath);
visitedNeighbors++;		visitedNeighbors++;
		this.nbEdgesAccessed++;
}		}

if (visitedNeighbors == 0) {		if (visitedNeighbors == 0) {
ArrayList<Long> path = new ArrayList<Long>();		ArrayList<Long> path = new ArrayList<Long>();
for (long nodeId : currentPath) {		for (long nodeId : currentPath) {
path.add(nodeId);		path.add(nodeId);
}		}
paths.add(path);		paths.add(path);
Show All 32 Lines	public class Traversal {
*		*
* @param srcNodeId source node		* @param srcNodeId source node
* @param dst destination (either a node or a node type)		* @param dst destination (either a node or a node type)
* @return final destination node or -1 if no path found		* @return final destination node or -1 if no path found
*/		*/
private <T> long walkInternalDfs(long srcNodeId, T dst) {		private <T> long walkInternalDfs(long srcNodeId, T dst) {
Stack<Long> stack = new Stack<Long>();		Stack<Long> stack = new Stack<Long>();
this.visited.fill(false);		this.visited.fill(false);
		this.nbEdgesAccessed = 0;

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

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;
}		}

for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {		for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
		nbEdgesAccessed++;
if (!visited.getBoolean(neighborNodeId)) {		if (!visited.getBoolean(neighborNodeId)) {
stack.push(neighborNodeId);		stack.push(neighborNodeId);
visited.set(neighborNodeId);		visited.set(neighborNodeId);
LongBigArrays.set(nodeParent, neighborNodeId, currentNodeId);		LongBigArrays.set(nodeParent, neighborNodeId, currentNodeId);
}		}
}		}
}		}

return -1;		return -1;
}		}

/**		/**
* Internal BFS function of {@link #walk}.		* Internal BFS function of {@link #walk}.
*		*
* @param srcNodeId source node		* @param srcNodeId source node
* @param dst destination (either a node or a node type)		* @param dst destination (either a node or a node type)
* @return final destination node or -1 if no path found		* @return final destination node or -1 if no path found
*/		*/
private <T> long walkInternalBfs(long srcNodeId, T dst) {		private <T> long walkInternalBfs(long srcNodeId, T dst) {
Queue<Long> queue = new LinkedList<Long>();		Queue<Long> queue = new LinkedList<Long>();
this.visited.fill(false);		this.visited.fill(false);
		this.nbEdgesAccessed = 0;

queue.add(srcNodeId);		queue.add(srcNodeId);
visited.set(srcNodeId);		visited.set(srcNodeId);

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;
}		}

for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {		for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
		nbEdgesAccessed++;
if (!visited.getBoolean(neighborNodeId)) {		if (!visited.getBoolean(neighborNodeId)) {
queue.add(neighborNodeId);		queue.add(neighborNodeId);
visited.set(neighborNodeId);		visited.set(neighborNodeId);
LongBigArrays.set(nodeParent, neighborNodeId, currentNodeId);		LongBigArrays.set(nodeParent, neighborNodeId, currentNodeId);
}		}
}		}
}		}

▲ Show 20 Lines • Show All 41 Lines • Show Last 20 Lines