No OneTemporary
Actions

Size

6 KB

Subscribers

None

View Options

	diff --git a/java/src/main/java/org/softwareheritage/graph/utils/TopoSort.java b/java/src/main/java/org/softwareheritage/graph/utils/TopoSort.java
	index 334644c..9866f6b 100644
	--- a/java/src/main/java/org/softwareheritage/graph/utils/TopoSort.java
	+++ b/java/src/main/java/org/softwareheritage/graph/utils/TopoSort.java
	@@ -1,111 +1,125 @@
	/*
	* Copyright (c) 2022 The Software Heritage developers
	* See the AUTHORS file at the top-level directory of this distribution
	* License: GNU General Public License version 3, or any later version
	* See top-level LICENSE file for more information
	*/

	package org.softwareheritage.graph.utils;

	import com.martiansoftware.jsap.*;
	import it.unimi.dsi.big.webgraph.LazyLongIterator;
	import it.unimi.dsi.big.webgraph.NodeIterator;
	import org.softwareheritage.graph.*;

	import java.io.IOException;
	import java.util.*;

	public class TopoSort {
	private Subgraph graph;
	private Subgraph transposedGraph;

	public static void main(String[] args) throws IOException, ClassNotFoundException {
	if (args.length != 2) {
	System.err.println("Syntax: java org.softwareheritage.graph.utils.TopoSort <path/to/graph> <nodeTypes>");
	System.exit(1);
	}
	String graphPath = args[0];
	String nodeTypes = args[1];

	TopoSort toposort = new TopoSort();

	toposort.load_graph(graphPath, nodeTypes);
	toposort.toposortDFS();
	}

	public void load_graph(String graphBasename, String nodeTypes) throws IOException {
	System.err.println("Loading graph " + graphBasename + " ...");
	var underlyingGraph = SwhBidirectionalGraph.loadMapped(graphBasename);
	System.err.println("Selecting subgraphs.");
	graph = new Subgraph(underlyingGraph, new AllowedNodes(nodeTypes));
	transposedGraph = graph.transpose();
	System.err.println("Graph loaded.");
	}

	/* Prints nodes in topological order, based on a DFS. */
	public void toposortDFS() {
	HashSet<Long> visited = new HashSet<Long>();
	Stack<Long> ready = new Stack<>();

	/* First, push all leaves to the stack */
	System.err.println("Listing leaves.");
	long total_nodes = 0;
	NodeIterator nodeIterator = graph.nodeIterator();
	for (long currentNodeId = nodeIterator.nextLong(); nodeIterator
	.hasNext(); currentNodeId = nodeIterator.nextLong()) {
	total_nodes++;
	// SWHID currentNodeSWHID = graph.getSWHID(currentNodeId);
	// if (graph.outdegree(currentNodeId) > 0) {
	long firstSuccessor = graph.successors(currentNodeId).nextLong();
	if (firstSuccessor != -1) {
	/* The node has ancestor, so it is not a leaf. */
	// SWHID firstSuccessorNodeSWHID = graph.getSWHID(firstSuccessor);
	// System.err.format("not leaf: %s, has succ: %s\n", currentNodeSWHID, firstSuccessorNodeSWHID);
	continue;
	}
	// System.err.format("is leaf: %s\n", currentNodeSWHID);
	ready.push(currentNodeId);
	if (ready.size() % 10000000 == 0) {
	float ready_size_f = ready.size();
	float total_nodes_f = total_nodes;
	System.err.printf("Listed %.02f B leaves (out of %.02f B nodes)\n", ready_size_f / 1000000000.,
	total_nodes_f / 1000000000.);
	}
	}
	System.err.println("Leaves loaded, starting DFS.");

	+ System.out.format("SWHID,ancestors,successors,sample_ancestor1,sample_ancestor2\n");
	while (!ready.isEmpty()) {
	long currentNodeId = ready.pop();
	visited.add(currentNodeId);

	- /*
	- * Print the node TODO: print its depth too?
	- */
	- SWHID currentNodeSWHID = graph.getSWHID(currentNodeId);
	- System.out.format("%s\n", currentNodeSWHID);
	-
	/* Find its successors which are ready */
	LazyLongIterator successors = transposedGraph.successors(currentNodeId);
	+ long successorCount = 0;
	for (long successorNodeId; (successorNodeId = successors.nextLong()) != -1;) {
	+ successorCount++;
	LazyLongIterator successorAncestors = graph.successors(successorNodeId);
	boolean isReady = true;
	for (long successorAncestorNodeId; (successorAncestorNodeId = successorAncestors.nextLong()) != -1;) {
	if (!visited.contains(successorAncestorNodeId)) {
	/*
	* This ancestor of the success is not yet visited, so the ancestor is not ready.
	*/
	// SWHID successorNodeSWHID = graph.getSWHID(successorNodeId);
	// SWHID successorAncestorNodeSWHID = graph.getSWHID(successorAncestorNodeId);
	// System.err.format("successor %s of %s is not ready, has unvisited ancestor: %s\n",
	// successorNodeSWHID, currentNodeSWHID, successorAncestorNodeSWHID);
	isReady = false;
	break;
	}
	}
	if (isReady) {
	ready.push(successorNodeId);
	}
	}
	+
	+ String[] sampleAncestors = {"", ""};
	+ long ancestorCount = 0;
	+ LazyLongIterator ancestors = graph.successors(currentNodeId);
	+ for (long ancestorNodeId; (ancestorNodeId = ancestors.nextLong()) != -1;) {
	+ if (ancestorCount < sampleAncestors.length) {
	+ sampleAncestors[(int) ancestorCount] = graph.getSWHID(ancestorNodeId).toString();
	+ }
	+ ancestorCount++;
	+ }
	+
	+ /*
	+ * Print the node TODO: print its depth too?
	+ */
	+ SWHID currentNodeSWHID = graph.getSWHID(currentNodeId);
	+ System.out.format("%s,%d,%d,%s,%s\n", currentNodeSWHID, ancestorCount, successorCount, sampleAncestors[0],
	+ sampleAncestors[1]);
	}
	}
	}

File Metadata

Mime Type: text/x-diff
Expires: Fri, Jul 4, 3:24 PM (6 d, 13 h ago)
Storage Engine: blob
Storage Format: Raw Data
Storage Handle: 3272110

No OneTemporaryActions

View Options

File Metadata

Event Timeline

No OneTemporary
Actions