Differential D4028 Diff 14692 java/src/main/java/org/softwareheritage/graph/experiments/forks/FindPath.java
Changeset View
Changeset View
Standalone View
Standalone View
java/src/main/java/org/softwareheritage/graph/experiments/forks/FindPath.java
Show All 16 Lines | private void load_graph(String graphBasename) throws IOException { | ||||
this.graph = new Graph(graphBasename).symmetrize(); | this.graph = new Graph(graphBasename).symmetrize(); | ||||
System.err.println("Graph loaded."); | System.err.println("Graph loaded."); | ||||
this.emptySnapshot = null; | this.emptySnapshot = null; | ||||
} | } | ||||
private static JSAPResult parse_args(String[] args) { | private static JSAPResult parse_args(String[] args) { | ||||
JSAPResult config = null; | JSAPResult config = null; | ||||
try { | try { | ||||
SimpleJSAP jsap = new SimpleJSAP( | SimpleJSAP jsap = new SimpleJSAP(FindPath.class.getName(), "", | ||||
FindPath.class.getName(), | new Parameter[]{new FlaggedOption("graphPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, | ||||
"", | 'g', "graph", "Basename of the compressed graph"),}); | ||||
new Parameter[] { | |||||
new FlaggedOption("graphPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, | |||||
'g', "graph", "Basename of the compressed graph"), | |||||
} | |||||
); | |||||
config = jsap.parse(args); | config = jsap.parse(args); | ||||
if (jsap.messagePrinted()) { | if (jsap.messagePrinted()) { | ||||
System.exit(1); | System.exit(1); | ||||
} | } | ||||
} catch (JSAPException e) { | } catch (JSAPException e) { | ||||
e.printStackTrace(); | e.printStackTrace(); | ||||
} | } | ||||
return config; | return config; | ||||
} | } | ||||
private boolean nodeIsEmptySnapshot(Long node) { | private boolean nodeIsEmptySnapshot(Long node) { | ||||
if (this.emptySnapshot == null | if (this.emptySnapshot == null && this.graph.getNodeType(node) == Node.Type.SNP | ||||
&& this.graph.getNodeType(node) == Node.Type.SNP | |||||
&& this.graph.outdegree(node) == 0) { | && this.graph.outdegree(node) == 0) { | ||||
System.err.println("Found empty snapshot: " + node); | System.err.println("Found empty snapshot: " + node); | ||||
this.emptySnapshot = node; | this.emptySnapshot = node; | ||||
} | } | ||||
return node.equals(this.emptySnapshot); | return node.equals(this.emptySnapshot); | ||||
} | } | ||||
private Boolean shouldVisit(Long node){ | private Boolean shouldVisit(Long node) { | ||||
Node.Type nt = this.graph.getNodeType(node); | Node.Type nt = this.graph.getNodeType(node); | ||||
if (nt != Node.Type.REV && nt != Node.Type.REL | if (nt != Node.Type.REV && nt != Node.Type.REL && nt != Node.Type.SNP && nt != Node.Type.ORI) { | ||||
&& nt != Node.Type.SNP && nt != Node.Type.ORI) { | |||||
return false; | return false; | ||||
} | } | ||||
if (this.nodeIsEmptySnapshot(node)) | if (this.nodeIsEmptySnapshot(node)) | ||||
return false; | return false; | ||||
return true; | return true; | ||||
} | } | ||||
private ArrayList<Long> findPath(Long src, Long dst) { | private ArrayList<Long> findPath(Long src, Long dst) { | ||||
HashSet<Long> visited = new HashSet<>(); | HashSet<Long> visited = new HashSet<>(); | ||||
Queue<Long> queue = new ArrayDeque<>(); | Queue<Long> queue = new ArrayDeque<>(); | ||||
Map<Long, Long> parentNode = new HashMap<>(); | Map<Long, Long> parentNode = new HashMap<>(); | ||||
queue.add(src); | queue.add(src); | ||||
visited.add(src); | visited.add(src); | ||||
while (!queue.isEmpty()) { | while (!queue.isEmpty()) { | ||||
long currentNode = queue.poll(); | long currentNode = queue.poll(); | ||||
final LazyLongIterator iterator = graph.successors(currentNode); | final LazyLongIterator iterator = graph.successors(currentNode); | ||||
long succ; | long succ; | ||||
while ((succ = iterator.nextLong()) != -1) { | while ((succ = iterator.nextLong()) != -1) { | ||||
if (!shouldVisit(succ) || visited.contains(succ)) continue; | if (!shouldVisit(succ) || visited.contains(succ)) | ||||
continue; | |||||
visited.add(succ); | visited.add(succ); | ||||
queue.add(succ); | queue.add(succ); | ||||
parentNode.put(succ, currentNode); | parentNode.put(succ, currentNode); | ||||
if (succ == dst) { | if (succ == dst) { | ||||
ArrayList<Long> path = new ArrayList<>(); | ArrayList<Long> path = new ArrayList<>(); | ||||
long n = dst; | long n = dst; | ||||
while (n != src) { | while (n != src) { | ||||
Show All 28 Lines | public static void main(String[] args) { | ||||
long rhsNode = input.nextLong(); | long rhsNode = input.nextLong(); | ||||
ArrayList<Long> path = fpath.findPath(lhsNode, rhsNode); | ArrayList<Long> path = fpath.findPath(lhsNode, rhsNode); | ||||
if (path != null) { | if (path != null) { | ||||
for (Long n : path) { | for (Long n : path) { | ||||
System.out.format("%d ", n); | System.out.format("%d ", n); | ||||
} | } | ||||
System.out.println(); | System.out.println(); | ||||
} | } else { | ||||
else { | |||||
System.out.println("null"); | System.out.println("null"); | ||||
} | } | ||||
} | } | ||||
} | } | ||||
} | } |