Skip to content

Commit fe24632

Browse files
eduramibaeduramiba
committed
Fix #1419 Getting null pointer error when trying to calculate modularity
Fix #713 Modularity Calculation Throws Exception On Empty Graph
1 parent c204611 commit fe24632

File tree

2 files changed

+103
-76
lines changed

2 files changed

+103
-76
lines changed

‎modules/StatisticsPlugin/src/main/java/org/gephi/statistics/plugin/Modularity.java‎

Lines changed: 88 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -133,26 +133,27 @@ class CommunityStructure {
133133
Graph graph;
134134
double[] weights;
135135
double graphWeightSum;
136-
LinkedList<ModEdge>[] topology;
137-
LinkedList<Community> communities;
136+
List<ModEdge>[] topology;
137+
List<Community> communities;
138138
int N;
139139
HashMap<Integer, Community> invMap;
140140

141-
CommunityStructure(Graph hgraph) {
142-
this.graph = hgraph;
143-
N = hgraph.getNodeCount();
141+
CommunityStructure(Graph graph) {
142+
this.graph = graph;
143+
N = graph.getNodeCount();
144144
invMap = new HashMap<>();
145145
nodeConnectionsWeight = new HashMap[N];
146146
nodeConnectionsCount = new HashMap[N];
147147
nodeCommunities = new Community[N];
148148
map = new HashMap<>();
149-
topology = new LinkedList[N];
150-
communities = new LinkedList<>();
149+
topology = new ArrayList[N];
150+
communities = new ArrayList<>();
151151
int index = 0;
152152
weights = new double[N];
153-
for (Node node : hgraph.getNodes()) {
153+
for (Node node : graph.getNodes()) {
154154
map.put(node, index);
155155
nodeCommunities[index] = new Community(this);
156+
156157
nodeConnectionsWeight[index] = new HashMap<>();
157158
nodeConnectionsCount[index] = new HashMap<>();
158159
weights[index] = 0;
@@ -167,34 +168,47 @@ class CommunityStructure {
167168
}
168169
}
169170

170-
for (Node node : hgraph.getNodes()) {
171+
for (Node node : graph.getNodes()) {
171172
int node_index = map.get(node);
172-
topology[node_index] = new LinkedList<>();
173-
174-
for (Edge edge : hgraph.getEdges(node)) {
175-
Node neighbor = hgraph.getOpposite(node, edge);
173+
topology[node_index] = new ArrayList<>();
176174

175+
Set<Node> uniqueNeighbors = new HashSet<>(graph.getNeighbors(node).toCollection());
176+
for (Node neighbor : uniqueNeighbors) {
177177
if (node == neighbor) {
178178
continue;
179179
}
180180
int neighbor_index = map.get(neighbor);
181-
float weight = 1;
182-
if (useWeight) {
183-
weight = (float) edge.getWeight(graph.getView());
181+
float weight = 0;
182+
183+
//Sum all parallel edges weight:
184+
for (Edge edge : graph.getEdges(node, neighbor)) {
185+
if (useWeight) {
186+
weight += edge.getWeight(graph.getView());
187+
} else {
188+
weight += 1;
189+
}
184190
}
185191

192+
//Finally add a single edge with the summed weight of all parallel edges:
193+
//Fixes issue #1419 Getting null pointer error when trying to calculate modularity
186194
weights[node_index] += weight;
187195
Modularity.ModEdge me = new ModEdge(node_index, neighbor_index, weight);
188196
topology[node_index].add(me);
189197
Community adjCom = nodeCommunities[neighbor_index];
198+
190199
nodeConnectionsWeight[node_index].put(adjCom, weight);
191200
nodeConnectionsCount[node_index].put(adjCom, 1);
192-
nodeCommunities[node_index].connectionsWeight.put(adjCom, weight);
193-
nodeCommunities[node_index].connectionsCount.put(adjCom, 1);
194-
nodeConnectionsWeight[neighbor_index].put(nodeCommunities[node_index], weight);
195-
nodeConnectionsCount[neighbor_index].put(nodeCommunities[node_index], 1);
196-
nodeCommunities[neighbor_index].connectionsWeight.put(nodeCommunities[node_index], weight);
197-
nodeCommunities[neighbor_index].connectionsCount.put(nodeCommunities[node_index], 1);
201+
202+
Community nodeCom = nodeCommunities[node_index];
203+
nodeCom.connectionsWeight.put(adjCom, weight);
204+
nodeCom.connectionsCount.put(adjCom, 1);
205+
206+
nodeConnectionsWeight[neighbor_index].put(nodeCom, weight);
207+
nodeConnectionsCount[neighbor_index].put(nodeCom, 1);
208+
209+
adjCom.connectionsWeight.put(nodeCom, weight);
210+
adjCom.connectionsCount.put(nodeCom, 1);
211+
198212
graphWeightSum += weight;
199213
}
200214

@@ -206,7 +220,7 @@ class CommunityStructure {
206220
}
207221

208222
private void addNodeTo(int node, Community to) {
209-
to.add(new Integer(node));
223+
to.add(node);
210224
nodeCommunities[node] = to;
211225

212226
for (ModEdge e : topology[node]) {
@@ -276,8 +290,7 @@ private void addNodeTo(int node, Community to) {
276290
}
277291
}
278292

279-
private void removeNodeFrom(int node, Community from) {
280-
293+
private void removeNodeFromItsCommunity(int node) {
281294
Community community = nodeCommunities[node];
282295
for (ModEdge e : topology[node]) {
283296
int neighbor = e.target;
@@ -334,18 +347,17 @@ private void removeNodeFrom(int node, Community from) {
334347
}
335348

336349
}
337-
from.remove(new Integer(node));
350+
community.remove(node);
338351
}
339352

340353
private void moveNodeTo(int node, Community to) {
341-
Community from = nodeCommunities[node];
342-
removeNodeFrom(node, from);
354+
removeNodeFromItsCommunity(node);
343355
addNodeTo(node, to);
344356
}
345357

346358
private void zoomOut() {
347359
int M = communities.size();
348-
LinkedList<ModEdge>[] newTopology = new LinkedList[M];
360+
ArrayList<ModEdge>[] newTopology = new ArrayList[M];
349361
int index = 0;
350362
nodeCommunities = new Community[M];
351363
nodeConnectionsWeight = new HashMap[M];
@@ -355,7 +367,8 @@ private void zoomOut() {
355367
Community com = communities.get(i);
356368
nodeConnectionsWeight[index] = new HashMap<>();
357369
nodeConnectionsCount[index] = new HashMap<>();
358-
newTopology[index] = new LinkedList<>();
370+
371+
newTopology[index] = new ArrayList<>();
359372
nodeCommunities[index] = new Community(com);
360373
Set<Community> iter = com.connectionsWeight.keySet();
361374
double weightSum = 0;
@@ -406,7 +419,7 @@ class Community {
406419

407420
double weightSum;
408421
CommunityStructure structure;
409-
LinkedList<Integer> nodes;
422+
List<Integer> nodes;
410423
HashMap<Modularity.Community, Float> connectionsWeight;
411424
HashMap<Modularity.Community, Integer> connectionsCount;
412425

@@ -418,15 +431,15 @@ public Community(Modularity.Community com) {
418431
structure = com.structure;
419432
connectionsWeight = new HashMap<>();
420433
connectionsCount = new HashMap<>();
421-
nodes = new LinkedList<>();
434+
nodes = new ArrayList<>();
422435
//mHidden = pCom.mHidden;
423436
}
424437

425438
public Community(CommunityStructure structure) {
426439
this.structure = structure;
427440
connectionsWeight = new HashMap<>();
428441
connectionsCount = new HashMap<>();
429-
nodes = new LinkedList<>();
442+
nodes = new ArrayList<>();
430443
}
431444

432445
public void seed(int node) {
@@ -435,13 +448,13 @@ public void seed(int node) {
435448
}
436449

437450
public boolean add(int node) {
438-
nodes.addLast(new Integer(node));
451+
nodes.add(node);
439452
weightSum += structure.weights[node];
440453
return true;
441454
}
442455

443456
public boolean remove(int node) {
444-
boolean result = nodes.remove(new Integer(node));
457+
boolean result = nodes.remove((Integer) node);
445458
weightSum -= structure.weights[node];
446459
if (nodes.isEmpty()) {
447460
structure.communities.remove(this);
@@ -452,29 +465,33 @@ public boolean remove(int node) {
452465

453466
@Override
454467
public void execute(GraphModel graphModel) {
455-
Graph hgraph = graphModel.getUndirectedGraphVisible();
456-
execute(hgraph);
468+
Graph graph = graphModel.getUndirectedGraphVisible();
469+
execute(graph);
457470
}
458471

459-
public void execute(Graph hgraph) {
472+
public void execute(Graph graph) {
460473
isCanceled = false;
461474

462-
hgraph.readLock();
463-
464-
structure = new Modularity.CommunityStructure(hgraph);
465-
int[] comStructure = new int[hgraph.getNodeCount()];
475+
graph.readLock();
466476

467-
HashMap<String, Double> computedModularityMetrics = computeModularity(hgraph, structure, comStructure, resolution, isRandomized, useWeight);
477+
structure = new Modularity.CommunityStructure(graph);
478+
int[] comStructure = new int[graph.getNodeCount()];
468479

469-
modularity = computedModularityMetrics.get("modularity");
470-
modularityResolution = computedModularityMetrics.get("modularityResolution");
480+
if (graph.getNodeCount() > 0) {//Fixes issue #713 Modularity Calculation Throws Exception On Empty Graph
481+
HashMap<String, Double> computedModularityMetrics = computeModularity(graph, structure, comStructure, resolution, isRandomized, useWeight);
482+
modularity = computedModularityMetrics.get("modularity");
483+
modularityResolution = computedModularityMetrics.get("modularityResolution");
484+
} else {
485+
modularity = 0;
486+
modularityResolution = 0;
487+
}
471488

472-
saveValues(comStructure, hgraph, structure);
489+
saveValues(comStructure, graph, structure);
473490

474-
hgraph.readUnlock();
491+
graph.readUnlock();
475492
}
476493

477-
protected HashMap<String, Double> computeModularity(Graph hgraph, CommunityStructure theStructure, int[] comStructure,
494+
protected HashMap<String, Double> computeModularity(Graph graph, CommunityStructure theStructure, int[] comStructure,
478495
double currentResolution, boolean randomized, boolean weighted) {
479496
isCanceled = false;
480497
Progress.start(progress);
@@ -486,7 +503,7 @@ protected HashMap<String, Double> computeModularity(Graph hgraph, CommunityStruc
486503
HashMap<String, Double> results = new HashMap<>();
487504

488505
if (isCanceled) {
489-
hgraph.readUnlockAll();
506+
graph.readUnlockAll();
490507
return results;
491508
}
492509
boolean someChange = true;
@@ -508,13 +525,13 @@ protected HashMap<String, Double> computeModularity(Graph hgraph, CommunityStruc
508525
localChange = true;
509526
}
510527
if (isCanceled) {
511-
hgraph.readUnlockAll();
528+
graph.readUnlockAll();
512529
return results;
513530
}
514531
}
515532
someChange = localChange || someChange;
516533
if (isCanceled) {
517-
hgraph.readUnlockAll();
534+
graph.readUnlockAll();
518535
return results;
519536
}
520537
}
@@ -524,24 +541,24 @@ protected HashMap<String, Double> computeModularity(Graph hgraph, CommunityStruc
524541
}
525542
}
526543

527-
fillComStructure(hgraph, theStructure, comStructure);
528-
double[] degreeCount = fillDegreeCount(hgraph, theStructure, comStructure, nodeDegrees, weighted);
544+
fillComStructure(graph, theStructure, comStructure);
545+
double[] degreeCount = fillDegreeCount(graph, theStructure, comStructure, nodeDegrees, weighted);
529546

530-
double computedModularity = finalQ(comStructure, degreeCount, hgraph, theStructure, totalWeight, 1., weighted);
531-
double computedModularityResolution = finalQ(comStructure, degreeCount, hgraph, theStructure, totalWeight, currentResolution, weighted);
547+
double computedModularity = finalQ(comStructure, degreeCount, graph, theStructure, totalWeight, 1., weighted);
548+
double computedModularityResolution = finalQ(comStructure, degreeCount, graph, theStructure, totalWeight, currentResolution, weighted);
532549

533550
results.put("modularity", computedModularity);
534551
results.put("modularityResolution", computedModularityResolution);
535552

536553
return results;
537554
}
538555

539-
Community updateBestCommunity(CommunityStructure theStructure, int i, double currentResolution) {
556+
private Community updateBestCommunity(CommunityStructure theStructure, int node_id, double currentResolution) {
540557
double best = 0.;
541558
Community bestCommunity = null;
542-
Set<Community> iter = theStructure.nodeConnectionsWeight[i].keySet();
559+
Set<Community> iter = theStructure.nodeConnectionsWeight[node_id].keySet();
543560
for (Community com : iter) {
544-
double qValue = q(i, com, theStructure, currentResolution);
561+
double qValue = q(node_id, com, theStructure, currentResolution);
545562
if (qValue > best) {
546563
best = qValue;
547564
bestCommunity = com;
@@ -550,8 +567,7 @@ Community updateBestCommunity(CommunityStructure theStructure, int i, double cur
550567
return bestCommunity;
551568
}
552569

553-
int[] fillComStructure(Graph hgraph, CommunityStructure theStructure, int[] comStructure) {
554-
// int[] comStructure = new int[hgraph.getNodeCount()];
570+
private int[] fillComStructure(Graph graph, CommunityStructure theStructure, int[] comStructure) {
555571
int count = 0;
556572

557573
for (Community com : theStructure.communities) {
@@ -566,37 +582,37 @@ int[] fillComStructure(Graph hgraph, CommunityStructure theStructure, int[] comS
566582
return comStructure;
567583
}
568584

569-
double[] fillDegreeCount(Graph hgraph, CommunityStructure theStructure, int[] comStructure, double[] nodeDegrees, boolean weighted) {
585+
private double[] fillDegreeCount(Graph graph, CommunityStructure theStructure, int[] comStructure, double[] nodeDegrees, boolean weighted) {
570586
double[] degreeCount = new double[theStructure.communities.size()];
571587

572-
for (Node node : hgraph.getNodes()) {
588+
for (Node node : graph.getNodes()) {
573589
int index = theStructure.map.get(node);
574590
if (weighted) {
575591
degreeCount[comStructure[index]] += nodeDegrees[index];
576592
} else {
577-
degreeCount[comStructure[index]] += hgraph.getDegree(node);
593+
degreeCount[comStructure[index]] += graph.getDegree(node);
578594
}
579595

580596
}
581597
return degreeCount;
582598
}
583599

584-
private double finalQ(int[] struct, double[] degrees, Graph hgraph,
600+
private double finalQ(int[] struct, double[] degrees, Graph graph,
585601
CommunityStructure theStructure, double totalWeight, double usedResolution, boolean weighted) {
586602

587603
double res = 0;
588604
double[] internal = new double[degrees.length];
589-
for (Node n : hgraph.getNodes()) {
605+
for (Node n : graph.getNodes()) {
590606
int n_index = theStructure.map.get(n);
591-
for (Edge edge : hgraph.getEdges(n)) {
592-
Node neighbor = hgraph.getOpposite(n, edge);
607+
for (Edge edge : graph.getEdges(n)) {
608+
Node neighbor = graph.getOpposite(n, edge);
593609
if (n == neighbor) {
594610
continue;
595611
}
596612
int neigh_index = theStructure.map.get(neighbor);
597613
if (struct[neigh_index] == struct[n_index]) {
598614
if (weighted) {
599-
internal[struct[neigh_index]] += edge.getWeight(hgraph.getView());
615+
internal[struct[neigh_index]] += edge.getWeight(graph.getView());
600616
} else {
601617
internal[struct[neigh_index]]++;
602618
}
@@ -610,13 +626,13 @@ private double finalQ(int[] struct, double[] degrees, Graph hgraph,
610626
return res;
611627
}
612628

613-
private void saveValues(int[] struct, Graph hgraph, CommunityStructure theStructure) {
614-
Table nodeTable = hgraph.getModel().getNodeTable();
629+
private void saveValues(int[] struct, Graph graph, CommunityStructure theStructure) {
630+
Table nodeTable = graph.getModel().getNodeTable();
615631
Column modCol = nodeTable.getColumn(MODULARITY_CLASS);
616632
if (modCol == null) {
617-
modCol = nodeTable.addColumn(MODULARITY_CLASS, "Modularity Class", Integer.class, new Integer(0));
633+
modCol = nodeTable.addColumn(MODULARITY_CLASS, "Modularity Class", Integer.class, 0);
618634
}
619-
for (Node n : hgraph.getNodes()) {
635+
for (Node n : graph.getNodes()) {
620636
int n_index = theStructure.map.get(n);
621637
n.setAttribute(modCol, struct[n_index]);
622638
}

0 commit comments

Comments
 (0)