Page Menu
Home
Software Heritage
Search
Configure Global Search
Log In
Files
F9345553
No One
Temporary
Actions
View File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Award Token
Flag For Later
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
Details
Attached
Mime Type
text/x-diff
Expires
Fri, Jul 4, 3:24 PM (5 d, 22 h ago)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
3272110
Attached To
rDGRPH Compressed graph representation
Event Timeline
Log In to Comment