Differential D6953 Diff 25202 java/src/main/java/org/softwareheritage/graph/experiments/topology/ClusteringCoefficient.java

Changeset View

Standalone View

View Options

java/src/main/java/org/softwareheritage/graph/experiments/topology/ClusteringCoefficient.java

package org.softwareheritage.graph.experiments.topology;		package org.softwareheritage.graph.experiments.topology;

import com.martiansoftware.jsap.*;		import com.martiansoftware.jsap.*;
import it.unimi.dsi.Util;		import it.unimi.dsi.Util;
import it.unimi.dsi.big.webgraph.ImmutableGraph;		import it.unimi.dsi.big.webgraph.ImmutableGraph;
import it.unimi.dsi.big.webgraph.LazyLongIterator;		import it.unimi.dsi.big.webgraph.LazyLongIterator;
import it.unimi.dsi.fastutil.BigArrays;		import it.unimi.dsi.fastutil.BigArrays;
import it.unimi.dsi.fastutil.longs.LongBigArrays;		import it.unimi.dsi.fastutil.longs.LongBigArrays;
import it.unimi.dsi.logging.ProgressLogger;		import it.unimi.dsi.logging.ProgressLogger;
import it.unimi.dsi.util.XoRoShiRo128PlusRandom;		import it.unimi.dsi.util.XoRoShiRo128PlusRandom;
import org.softwareheritage.graph.Graph;		import org.softwareheritage.graph.SwhBidirectionalGraph;
import org.softwareheritage.graph.Node;		import org.softwareheritage.graph.Node;

import java.io.*;		import java.io.*;
import java.util.*;		import java.util.*;
import java.util.concurrent.*;		import java.util.concurrent.*;

public class ClusteringCoefficient {		public class ClusteringCoefficient {
private final Graph graph;		private final SwhBidirectionalGraph graph;
private final String outdirPath;		private final String outdirPath;
private final ConcurrentHashMap<Long, Long> result_full;		private final ConcurrentHashMap<Long, Long> result_full;
private final ConcurrentHashMap<Long, Long> result_dircnt;		private final ConcurrentHashMap<Long, Long> result_dircnt;
private final ConcurrentHashMap<Long, Long> result_rev;		private final ConcurrentHashMap<Long, Long> result_rev;
private final ConcurrentHashMap<Long, Long> result_revrel;		private final ConcurrentHashMap<Long, Long> result_revrel;
private final ConcurrentHashMap<Long, Long> result_orisnp;		private final ConcurrentHashMap<Long, Long> result_orisnp;

public ClusteringCoefficient(String graphBasename, String outdirPath) throws IOException {		public ClusteringCoefficient(String graphBasename, String outdirPath) throws IOException {
this.outdirPath = outdirPath;		this.outdirPath = outdirPath;
System.err.println("Loading graph " + graphBasename + " ...");		System.err.println("Loading graph " + graphBasename + " ...");
Graph directedGraph = Graph.loadMapped(graphBasename);		SwhBidirectionalGraph directedGraph = SwhBidirectionalGraph.loadMapped(graphBasename);
this.graph = directedGraph.symmetrize();		this.graph = directedGraph.symmetrize();
System.err.println("Graph loaded.");		System.err.println("Graph loaded.");

result_full = new ConcurrentHashMap<>();		result_full = new ConcurrentHashMap<>();
result_dircnt = new ConcurrentHashMap<>();		result_dircnt = new ConcurrentHashMap<>();
result_rev = new ConcurrentHashMap<>();		result_rev = new ConcurrentHashMap<>();
result_revrel = new ConcurrentHashMap<>();		result_revrel = new ConcurrentHashMap<>();
result_orisnp = new ConcurrentHashMap<>();		result_orisnp = new ConcurrentHashMap<>();
Show All 24 Lines	public class ClusteringCoefficient {
private void run(int numThreads) throws InterruptedException {		private void run(int numThreads) throws InterruptedException {
final long END_OF_QUEUE = -1L;		final long END_OF_QUEUE = -1L;

ArrayBlockingQueue<Long> queue = new ArrayBlockingQueue<>(numThreads);		ArrayBlockingQueue<Long> queue = new ArrayBlockingQueue<>(numThreads);
ExecutorService service = Executors.newFixedThreadPool(numThreads + 1);		ExecutorService service = Executors.newFixedThreadPool(numThreads + 1);

service.submit(() -> {		service.submit(() -> {
try {		try {
Graph thread_graph = graph.copy();		SwhBidirectionalGraph thread_graph = graph.copy();

long[][] randomPerm = Util.identity(thread_graph.numNodes());		long[][] randomPerm = Util.identity(thread_graph.numNodes());
LongBigArrays.shuffle(randomPerm, new XoRoShiRo128PlusRandom());		LongBigArrays.shuffle(randomPerm, new XoRoShiRo128PlusRandom());
long n = thread_graph.numNodes();		long n = thread_graph.numNodes();

ProgressLogger pl = new ProgressLogger();		ProgressLogger pl = new ProgressLogger();
pl.expectedUpdates = n;		pl.expectedUpdates = n;
pl.itemsName = "nodes";		pl.itemsName = "nodes";
Show All 18 Lines	private void run(int numThreads) throws InterruptedException {
}		}
}		}
}		}
});		});

for (int i = 0; i < numThreads; ++i) {		for (int i = 0; i < numThreads; ++i) {
service.submit(() -> {		service.submit(() -> {
try {		try {
Graph thread_graph = graph.copy();		SwhBidirectionalGraph thread_graph = graph.copy();
while (true) {		while (true) {
Long node = null;		Long node = null;
try {		try {
node = queue.take();		node = queue.take();
} catch (InterruptedException e) {		} catch (InterruptedException e) {
e.printStackTrace();		e.printStackTrace();
}		}
if (node == null \|\| node == END_OF_QUEUE) {		if (node == null \|\| node == END_OF_QUEUE) {
return;		return;
}		}

computeAt(thread_graph, node);		computeAt(thread_graph, node);
}		}
} catch (Exception e) {		} catch (Exception e) {
e.printStackTrace();		e.printStackTrace();
}		}
});		});
}		}

service.shutdown();		service.shutdown();
service.awaitTermination(365, TimeUnit.DAYS);		service.awaitTermination(365, TimeUnit.DAYS);
}		}

private void computeAt(Graph graph, long node) {		private void computeAt(SwhBidirectionalGraph graph, long node) {
long d = graph.outdegree(node);		long d = graph.outdegree(node);
if (d < 2) {		if (d < 2) {
return;		return;
}		}
Node.Type nodeType = graph.getNodeType(node);		Node.Type nodeType = graph.getNodeType(node);

HashSet<Long> neighborhood = new HashSet<>();		HashSet<Long> neighborhood = new HashSet<>();
long succ;		long succ;
▲ Show 20 Lines • Show All 187 Lines • Show Last 20 Lines