Differential D6953 Diff 25200 java/src/main/java/org/softwareheritage/graph/experiments/topology/ClusteringCoefficient.java
Changeset View
Changeset View
Standalone View
Standalone View
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("SwhBidirectionalGraph 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 22 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 |