Differential D2349 Diff 8083 java/src/main/java/org/softwareheritage/graph/algo/Traversal.java

Changeset View

Standalone View

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

package org.softwareheritage.graph.algo;		package org.softwareheritage.graph.algo;

import java.util.ArrayList;		import java.util.*;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;

import it.unimi.dsi.bits.LongArrayBitVector;		import it.unimi.dsi.bits.LongArrayBitVector;

import org.softwareheritage.graph.AllowedEdges;		import org.softwareheritage.graph.AllowedEdges;
import org.softwareheritage.graph.Endpoint;		import org.softwareheritage.graph.Endpoint;
import org.softwareheritage.graph.Graph;		import org.softwareheritage.graph.Graph;
import org.softwareheritage.graph.Neighbors;		import org.softwareheritage.graph.Neighbors;
import org.softwareheritage.graph.Node;		import org.softwareheritage.graph.Node;
▲ Show 20 Lines • Show All 420 Lines • ▼ Show 20 Lines	private ArrayList<Long> backtracking(long srcNodeId, long dstNodeId) {
while (currentNodeId != srcNodeId) {		while (currentNodeId != srcNodeId) {
path.add(currentNodeId);		path.add(currentNodeId);
currentNodeId = parentNode.get(currentNodeId);		currentNodeId = parentNode.get(currentNodeId);
}		}
path.add(srcNodeId);		path.add(srcNodeId);
Collections.reverse(path);		Collections.reverse(path);
return path;		return path;
}		}

		public Long findCommonDescendant(long lhsNode, long rhsNode) {
		Queue<Long> lhsStack = new ArrayDeque<>();
		Queue<Long> rhsStack = new ArrayDeque<>();
		HashSet<Long> lhsVisited = new HashSet<>();
		HashSet<Long> rhsVisited = new HashSet<>();
		lhsStack.add(lhsNode);
		rhsStack.add(rhsNode);
		lhsVisited.add(lhsNode);
		rhsVisited.add(rhsNode);

		this.nbEdgesAccessed = 0;
		Long curNode;

		while (!lhsStack.isEmpty() \|\| !rhsStack.isEmpty()) {
		if (!lhsStack.isEmpty()) {
		curNode = lhsStack.poll();
		nbEdgesAccessed += graph.degree(curNode, useTransposed);
		for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, curNode)) {
		if (!lhsVisited.contains(neighborNodeId)) {
		if (rhsVisited.contains(neighborNodeId))
		return neighborNodeId;
		lhsStack.add(neighborNodeId);
		lhsVisited.add(neighborNodeId);
		}
		}
		}

		if (!rhsStack.isEmpty()) {
		curNode = rhsStack.poll();
		nbEdgesAccessed += graph.degree(curNode, useTransposed);
		for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, curNode)) {
		if (!rhsVisited.contains(neighborNodeId)) {
		if (lhsVisited.contains(neighborNodeId))
		return neighborNodeId;
		rhsStack.add(neighborNodeId);
		rhsVisited.add(neighborNodeId);
		}
		}
		}
		}

		return null;
		}
}		}