22892510196

Committed 10 Mar 2026 07:52AM UTC coverage: 79.569% (+0.1%) from 79.428%

Build # 22892510196

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #1394 from Schwarf/coverage/add_tests_epidemic_simulation

Add tests epidemic simulation

Run Details

23 of 24 new or added lines in 1 file covered. (95.83%)

1 existing line in 1 file now uncovered.

29626 of 37233 relevant lines covered (79.57%)

2265374.08 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

88.42

/networkit/cpp/community/PLM.cpp

/*
 * MLPLM.cpp
 *
 *  Created on: 20.11.2013
 *      Author: cls
 */

#include <omp.h>
#include <sstream>
#include <utility>

#include <networkit/auxiliary/Log.hpp>
#include <networkit/auxiliary/SignalHandling.hpp>
#include <networkit/auxiliary/Timer.hpp>
#include <networkit/coarsening/ClusteringProjector.hpp>
#include <networkit/coarsening/ParallelPartitionCoarsening.hpp>
#include <networkit/community/PLM.hpp>

namespace NetworKit {

PLM::PLM(const Graph &G, bool refine, double gamma, std::string par, count maxIter, bool turbo,
         bool recurse)
    : CommunityDetectionAlgorithm(G), parallelism(std::move(par)), refine(refine), gamma(gamma),
      maxIter(maxIter), turbo(turbo), recurse(recurse) {}

PLM::PLM(const Graph &G, const PLM &other)
    : CommunityDetectionAlgorithm(G), parallelism(other.parallelism), refine(other.refine),
      gamma(other.gamma), maxIter(other.maxIter), turbo(other.turbo), recurse(other.recurse) {}

void PLM::run() {
    Aux::SignalHandler handler;

    count z = G->upperNodeIdBound();

    // init communities to singletons
    Partition zeta(z);
    zeta.allToSingletons();
    index o = zeta.upperBound();

    // init graph-dependent temporaries
    std::vector<double> volNode(z, 0.0);
    // $\omega(E)$
    edgeweight total = G->totalEdgeWeight();
    DEBUG("total edge weight: ", total);
    edgeweight divisor = (2 * total * total); // needed in modularity calculation

    G->parallelForNodes([&](node u) { // calculate and store volume of each node
        volNode[u] += G->weightedDegree(u);
        volNode[u] += G->weight(u, u); // consider self-loop twice
    });

    // init community-dependent temporaries
    std::vector<double> volCommunity(o, 0.0);
    zeta.parallelForEntries([&](node u, index C) { // set volume for all communities
        if (C != none)
            volCommunity[C] = volNode[u];
    });

    // first move phase
    bool moved = false;  // indicates whether any node has been moved in the last pass
    bool change = false; // indicates whether the communities have changed at all

    // stores the affinity for each neighboring community (index), one vector per thread
    std::vector<std::vector<edgeweight>> turboAffinity;
    // stores the list of neighboring communities, one vector per thread
    std::vector<std::vector<index>> neigh_comm;

    if (turbo) {
        // initialize arrays for all threads only when actually needed
        if (this->parallelism != "none" && this->parallelism != "none randomized") {
            turboAffinity.resize(omp_get_max_threads());
            neigh_comm.resize(omp_get_max_threads());
            for (auto &it : turboAffinity) {
                // resize to maximum community id
                it.resize(zeta.upperBound());
            }
        } else { // initialize array only for first thread
            turboAffinity.emplace_back(zeta.upperBound());
            neigh_comm.emplace_back();
        }
    }

    // try to improve modularity by moving a node to neighboring clusters
    auto tryMove = [&](node u) {
        // trying to move node u
        index tid = omp_get_thread_num();

        // collect edge weight to neighbor clusters
        std::map<index, edgeweight> affinity;

        if (turbo) {
            neigh_comm[tid].clear();
            // set all to -1 so we can see when we get to it the first time
            G->forNeighborsOf(u, [&](node v) { turboAffinity[tid][zeta[v]] = -1; });
            turboAffinity[tid][zeta[u]] = 0;
            G->forNeighborsOf(u, [&](node v, edgeweight weight) {
                if (u != v) {
                    index C = zeta[v];
                    if (turboAffinity[tid][C] == -1) {
                        // found the neighbor for the first time, initialize to 0 and add to list of
                        // neighboring communities
                        turboAffinity[tid][C] = 0;
                        neigh_comm[tid].push_back(C);
                    }
                    turboAffinity[tid][C] += weight;
                }
            });
        } else {
            G->forNeighborsOf(u, [&](node v, edgeweight weight) {
                if (u != v) {
                    index C = zeta[v];
                    affinity[C] += weight;
                }
            });
        }

        // sub-functions

        // $\vol(C \ {x})$ - volume of cluster C excluding node x
        auto volCommunityMinusNode = [&](index C, node x) {
            double volC = 0.0;
            double volN = 0.0;
            volC = volCommunity[C];
            if (zeta[x] == C) {
                volN = volNode[x];
                return volC - volN;
            } else {
                return volC;
            }
        };

        auto modGain = [&](node u, index C, index D, edgeweight affinityC, edgeweight affinityD) {
            double volN = 0.0;
            volN = volNode[u];
            double delta =
                (affinityD - affinityC) / total
                + this->gamma * ((volCommunityMinusNode(C, u) - volCommunityMinusNode(D, u)) * volN)
                      / divisor;
            return delta;
        };

        index best = none;
        index C = none;
        double deltaBest = -1;

        C = zeta[u];

        if (turbo) {
            edgeweight affinityC = turboAffinity[tid][C];

            for (index D : neigh_comm[tid]) {

                // consider only nodes in other clusters (and implicitly only nodes other than u)
                if (D != C) {
                    double delta = modGain(u, C, D, affinityC, turboAffinity[tid][D]);

                    if (delta > deltaBest) {
                        deltaBest = delta;
                        best = D;
                    }
                }
            }
        } else {
            edgeweight affinityC = affinity[C];

            for (auto it : affinity) {
                index D = it.first;
                // consider only nodes in other clusters (and implicitly only nodes other than u)
                if (D != C) {
                    double delta = modGain(u, C, D, affinityC, it.second);
                    if (delta > deltaBest) {
                        deltaBest = delta;
                        best = D;
                    }
                }
            }
        }

        if (deltaBest > 0) {                   // if modularity improvement possible
            assert(best != C && best != none); // do not "move" to original cluster

            zeta[u] = best; // move to best cluster
            // node u moved

            // mod update
            double volN = 0.0;
            volN = volNode[u];
// update the volume of the two clusters
#pragma omp atomic
            volCommunity[C] -= volN;
#pragma omp atomic
            volCommunity[best] += volN;

            moved = true; // change to clustering has been made
        }
    };

    // performs node moves
    auto movePhase = [&]() {
        count iter = 0;
        do {
            moved = false;
            // apply node movement according to parallelization strategy
            if (this->parallelism == "none") {
                G->forNodes(tryMove);
            } else if (this->parallelism == "simple") {
                G->parallelForNodes(tryMove);
            } else if (this->parallelism == "balanced") {
                G->balancedParallelForNodes(tryMove);
            } else if (this->parallelism == "none randomized") {
                G->forNodesInRandomOrder(tryMove);
            } else {
                ERROR("unknown parallelization strategy: ", this->parallelism);
                throw std::runtime_error("unknown parallelization strategy");
            }
            if (moved)
                change = true;

            if (iter == maxIter) {
                WARN("move phase aborted after ", maxIter, " iterations");
            }
            iter += 1;
        } while (moved && (iter <= maxIter) && handler.isRunning());
        DEBUG("iterations in move phase: ", iter);
    };
    handler.assureRunning();
    // first move phase
    Aux::Timer timer;
    timer.start();

    movePhase();

    timer.stop();
    timing["move"].push_back(timer.elapsedMilliseconds());
    handler.assureRunning();
    if (recurse && change) {
        DEBUG("nodes moved, so begin coarsening and recursive call");

        timer.start();

        // coarsen graph according to communities
        std::pair<Graph, std::vector<node>> coarsened = coarsen(*G, zeta);

        timer.stop();
        timing["coarsen"].push_back(timer.elapsedMilliseconds());

        PLM onCoarsened(coarsened.first, this->refine, this->gamma, this->parallelism,
                        this->maxIter, this->turbo);
        onCoarsened.run();
        Partition zetaCoarse = onCoarsened.getPartition();

        // get timings
        auto tim = onCoarsened.getTiming();
        for (count t : tim["move"]) {
            timing["move"].push_back(t);
        }
        for (count t : tim["coarsen"]) {
            timing["coarsen"].push_back(t);
        }
        for (count t : tim["refine"]) {
            timing["refine"].push_back(t);
        }

        DEBUG("coarse graph has ", coarsened.first.numberOfNodes(), " nodes and ",
              coarsened.first.numberOfEdges(), " edges");
        // unpack communities in coarse graph onto fine graph
        zeta = prolong(coarsened.first, zetaCoarse, *G, coarsened.second);
        // refinement phase
        if (refine) {
            DEBUG("refinement phase");
            // reinit community-dependent temporaries
            o = zeta.upperBound();
            volCommunity.clear();
            volCommunity.resize(o, 0.0);
            zeta.parallelForEntries([&](node u, index C) { // set volume for all communities
                if (C != none) {
                    edgeweight volN = volNode[u];
#pragma omp atomic
                    volCommunity[C] += volN;
                }
            });
            // second move phase
            timer.start();

            movePhase();

            timer.stop();
            timing["refine"].push_back(timer.elapsedMilliseconds());
        }
    }
    result = std::move(zeta);
    hasRun = true;
}

std::pair<Graph, std::vector<node>> PLM::coarsen(const Graph &G, const Partition &zeta) {
    ParallelPartitionCoarsening parCoarsening(G, zeta);
    parCoarsening.run();
    return {parCoarsening.getCoarseGraph(), parCoarsening.getFineToCoarseNodeMapping()};
}

Partition PLM::prolong(const Graph &, const Partition &zetaCoarse, const Graph &Gfine,
                       std::vector<node> nodeToMetaNode) {
    Partition zetaFine(Gfine.upperNodeIdBound());
    zetaFine.setUpperBound(zetaCoarse.upperBound());

    Gfine.forNodes([&](node v) {
        node mv = nodeToMetaNode[v];
        index cv = zetaCoarse[mv];
        zetaFine[v] = cv;
    });

    return zetaFine;
}

const std::map<std::string, std::vector<count>> &PLM::getTiming() const {
    assureFinished();
    return timing;
}

} /* namespace NetworKit */

1	/*
2	* MLPLM.cpp
3	*
4	* Created on: 20.11.2013
5	* Author: cls
6	*/
7
8	#include <omp.h>
9	#include <sstream>
10	#include <utility>
11
12	#include <networkit/auxiliary/Log.hpp>
13	#include <networkit/auxiliary/SignalHandling.hpp>
14	#include <networkit/auxiliary/Timer.hpp>
15	#include <networkit/coarsening/ClusteringProjector.hpp>
16	#include <networkit/coarsening/ParallelPartitionCoarsening.hpp>
17	#include <networkit/community/PLM.hpp>
18
19	namespace NetworKit {
20
21	PLM::PLM(const Graph &G, bool refine, double gamma, std::string par, count maxIter, bool turbo,	37✔
22	bool recurse)	37✔
23	: CommunityDetectionAlgorithm(G), parallelism(std::move(par)), refine(refine), gamma(gamma),	37✔
24	maxIter(maxIter), turbo(turbo), recurse(recurse) {}	74✔
25
26	PLM::PLM(const Graph &G, const PLM &other)	×
27	: CommunityDetectionAlgorithm(G), parallelism(other.parallelism), refine(other.refine),	×
28	gamma(other.gamma), maxIter(other.maxIter), turbo(other.turbo), recurse(other.recurse) {}	×
29
30	void PLM::run() {	37✔
31	Aux::SignalHandler handler;	37✔
32
33	count z = G->upperNodeIdBound();	37✔
34
35	// init communities to singletons
36	Partition zeta(z);	37✔
37	zeta.allToSingletons();	37✔
38	index o = zeta.upperBound();	37✔
39
40	// init graph-dependent temporaries
41	std::vector<double> volNode(z, 0.0);	37✔
42	// $\omega(E)$
43	edgeweight total = G->totalEdgeWeight();	37✔
44	DEBUG("total edge weight: ", total);	37✔
45	edgeweight divisor = (2 * total * total); // needed in modularity calculation	37✔
46
47	G->parallelForNodes([&](node u) { // calculate and store volume of each node	37✔
48	volNode[u] += G->weightedDegree(u);	57,651✔
49	volNode[u] += G->weight(u, u); // consider self-loop twice	57,651✔
50	});	57,651✔
51
52	// init community-dependent temporaries
53	std::vector<double> volCommunity(o, 0.0);	37✔
54	zeta.parallelForEntries([&](node u, index C) { // set volume for all communities	37✔
55	if (C != none)	57,653✔
56	volCommunity[C] = volNode[u];	57,653✔
57	});	57,653✔
58
59	// first move phase
60	bool moved = false; // indicates whether any node has been moved in the last pass	37✔
61	bool change = false; // indicates whether the communities have changed at all	37✔
62
63	// stores the affinity for each neighboring community (index), one vector per thread
64	std::vector<std::vector<edgeweight>> turboAffinity;	37✔
65	// stores the list of neighboring communities, one vector per thread
66	std::vector<std::vector<index>> neigh_comm;	37✔
67
68	if (turbo) {	37✔
69	// initialize arrays for all threads only when actually needed
70	if (this->parallelism != "none" && this->parallelism != "none randomized") {	37✔
71	turboAffinity.resize(omp_get_max_threads());	33✔
72	neigh_comm.resize(omp_get_max_threads());	33✔
73	for (auto &it : turboAffinity) {	99✔
74	// resize to maximum community id
75	it.resize(zeta.upperBound());	66✔
76	}
77	} else { // initialize array only for first thread
78	turboAffinity.emplace_back(zeta.upperBound());	4✔
79	neigh_comm.emplace_back();	4✔
80	}
81	}
82
83	// try to improve modularity by moving a node to neighboring clusters
84	auto tryMove = [&](node u) {	406,551✔
85	// trying to move node u
86	index tid = omp_get_thread_num();	406,551✔
87
88	// collect edge weight to neighbor clusters
89	std::map<index, edgeweight> affinity;	406,551✔
90
91	if (turbo) {	406,551✔
92	neigh_comm[tid].clear();	406,551✔
93	// set all to -1 so we can see when we get to it the first time
94	G->forNeighborsOf(u, [&](node v) { turboAffinity[tid][zeta[v]] = -1; });	2,687,522✔
95	turboAffinity[tid][zeta[u]] = 0;	406,551✔
96	G->forNeighborsOf(u, [&](node v, edgeweight weight) {	406,551✔
97	if (u != v) {	2,280,971✔
98	index C = zeta[v];	2,217,728✔
99	if (turboAffinity[tid][C] == -1) {	2,217,728✔
100	// found the neighbor for the first time, initialize to 0 and add to list of
101	// neighboring communities
102	turboAffinity[tid][C] = 0;	614,364✔
103	neigh_comm[tid].push_back(C);	614,364✔
104	}
105	turboAffinity[tid][C] += weight;	2,217,728✔
106	}
107	});	2,280,971✔
108	} else {
109	G->forNeighborsOf(u, [&](node v, edgeweight weight) {	×
110	if (u != v) {	×
111	index C = zeta[v];	×
112	affinity[C] += weight;	×
113	}
114	});	×
115	}
116
117	// sub-functions
118
119	// $\vol(C \ {x})$ - volume of cluster C excluding node x
120	auto volCommunityMinusNode = [&](index C, node x) {	1,228,728✔
121	double volC = 0.0;	1,228,728✔
122	double volN = 0.0;	1,228,728✔
123	volC = volCommunity[C];	1,228,728✔
124	if (zeta[x] == C) {	1,228,728✔
125	volN = volNode[x];	614,364✔
126	return volC - volN;	614,364✔
127	} else {
128	return volC;	614,364✔
129	}
130	};	406,551✔
131
132	auto modGain = [&](node u, index C, index D, edgeweight affinityC, edgeweight affinityD) {	614,364✔
133	double volN = 0.0;	614,364✔
134	volN = volNode[u];	614,364✔
135	double delta =
136	(affinityD - affinityC) / total	1,020,915✔
137	+ this->gamma * ((volCommunityMinusNode(C, u) - volCommunityMinusNode(D, u)) * volN)	614,364✔
138	/ divisor;	1,020,915✔
139	return delta;	614,364✔
140	};	406,551✔
141
142	index best = none;	406,551✔
143	index C = none;	406,551✔
144	double deltaBest = -1;	406,551✔
145
146	C = zeta[u];	406,551✔
147
148	if (turbo) {	406,551✔
149	edgeweight affinityC = turboAffinity[tid][C];	406,551✔
150
151	for (index D : neigh_comm[tid]) {	1,020,915✔
152
153	// consider only nodes in other clusters (and implicitly only nodes other than u)
154	if (D != C) {	614,364✔
155	double delta = modGain(u, C, D, affinityC, turboAffinity[tid][D]);	614,364✔
156
157	if (delta > deltaBest) {	614,364✔
158	deltaBest = delta;	292,205✔
159	best = D;	292,205✔
160	}
161	}
162	}
163	} else {
164	edgeweight affinityC = affinity[C];	×
165
166	for (auto it : affinity) {	×
167	index D = it.first;	×
168	// consider only nodes in other clusters (and implicitly only nodes other than u)
169	if (D != C) {	×
170	double delta = modGain(u, C, D, affinityC, it.second);	×
171	if (delta > deltaBest) {	×
172	deltaBest = delta;	×
173	best = D;	×
174	}
175	}
176	}
177	}
178
179	if (deltaBest > 0) { // if modularity improvement possible	406,551✔
180	assert(best != C && best != none); // do not "move" to original cluster	53,688✔
181
182	zeta[u] = best; // move to best cluster	53,688✔
183	// node u moved
184
185	// mod update
186	double volN = 0.0;	53,688✔
187	volN = volNode[u];	53,688✔
188	// update the volume of the two clusters
189	#pragma omp atomic	53,688✔
190	volCommunity[C] -= volN;	53,688✔
191	#pragma omp atomic	53,689✔
192	volCommunity[best] += volN;	53,688✔
193
194	moved = true; // change to clustering has been made	53,688✔
195	}
196	};	406,551✔
197
198	// performs node moves
199	auto movePhase = [&]() {	52✔
200	count iter = 0;	52✔
201	do {
202	moved = false;	522✔
203	// apply node movement according to parallelization strategy
204	if (this->parallelism == "none") {	174✔
205	G->forNodes(tryMove);	×
206	} else if (this->parallelism == "simple") {	174✔
207	G->parallelForNodes(tryMove);	×
208	} else if (this->parallelism == "balanced") {	174✔
209	G->balancedParallelForNodes(tryMove);	162✔
210	} else if (this->parallelism == "none randomized") {	12✔
211	G->forNodesInRandomOrder(tryMove);	12✔
212	} else {
213	ERROR("unknown parallelization strategy: ", this->parallelism);	×
214	throw std::runtime_error("unknown parallelization strategy");	×
215	}
216	if (moved)	174✔
217	change = true;	122✔
218
219	if (iter == maxIter) {	174✔
UNCOV 220	WARN("move phase aborted after ", maxIter, " iterations");	×
221	}
222	iter += 1;	174✔
223	} while (moved && (iter <= maxIter) && handler.isRunning());	174✔
224	DEBUG("iterations in move phase: ", iter);	52✔
225	};	52✔
226	handler.assureRunning();	37✔
227	// first move phase
228	Aux::Timer timer;	37✔
229	timer.start();	37✔
230
231	movePhase();	37✔
232
233	timer.stop();	37✔
234	timing["move"].push_back(timer.elapsedMilliseconds());	37✔
235	handler.assureRunning();	37✔
236	if (recurse && change) {	37✔
237	DEBUG("nodes moved, so begin coarsening and recursive call");	29✔
238
239	timer.start();	29✔
240
241	// coarsen graph according to communities
242	std::pair<Graph, std::vector<node>> coarsened = coarsen(*G, zeta);	29✔
243
244	timer.stop();	29✔
245	timing["coarsen"].push_back(timer.elapsedMilliseconds());	29✔
246
247	PLM onCoarsened(coarsened.first, this->refine, this->gamma, this->parallelism,	58✔
248	this->maxIter, this->turbo);	29✔
249	onCoarsened.run();	29✔
250	Partition zetaCoarse = onCoarsened.getPartition();	29✔
251
252	// get timings
253	auto tim = onCoarsened.getTiming();	29✔
254	for (count t : tim["move"]) {	102✔
255	timing["move"].push_back(t);	73✔
256	}
257	for (count t : tim["coarsen"]) {	73✔
258	timing["coarsen"].push_back(t);	44✔
259	}
260	for (count t : tim["refine"]) {	53✔
261	timing["refine"].push_back(t);	24✔
262	}
263
264	DEBUG("coarse graph has ", coarsened.first.numberOfNodes(), " nodes and ",	29✔
265	coarsened.first.numberOfEdges(), " edges");
266	// unpack communities in coarse graph onto fine graph
267	zeta = prolong(coarsened.first, zetaCoarse, *G, coarsened.second);	29✔
268	// refinement phase
269	if (refine) {	29✔
270	DEBUG("refinement phase");	15✔
271	// reinit community-dependent temporaries
272	o = zeta.upperBound();	15✔
273	volCommunity.clear();	15✔
274	volCommunity.resize(o, 0.0);	15✔
275	zeta.parallelForEntries([&](node u, index C) { // set volume for all communities	15✔
276	if (C != none) {	28,781✔
277	edgeweight volN = volNode[u];	28,780✔
278	#pragma omp atomic	28,939✔
279	volCommunity[C] += volN;	28,780✔
280	}
281	});	28,781✔
282	// second move phase
283	timer.start();	15✔
284
285	movePhase();	15✔
286
287	timer.stop();	15✔
288	timing["refine"].push_back(timer.elapsedMilliseconds());	15✔
289	}
290	}	29✔
291	result = std::move(zeta);	37✔
292	hasRun = true;	37✔
293	}	37✔
294
295	std::pair<Graph, std::vector<node>> PLM::coarsen(const Graph &G, const Partition &zeta) {	29✔
296	ParallelPartitionCoarsening parCoarsening(G, zeta);	29✔
297	parCoarsening.run();	29✔
298	return {parCoarsening.getCoarseGraph(), parCoarsening.getFineToCoarseNodeMapping()};	58✔
299	}	29✔
300
301	Partition PLM::prolong(const Graph &, const Partition &zetaCoarse, const Graph &Gfine,	29✔
302	std::vector<node> nodeToMetaNode) {
303	Partition zetaFine(Gfine.upperNodeIdBound());	29✔
304	zetaFine.setUpperBound(zetaCoarse.upperBound());	29✔
305
306	Gfine.forNodes([&](node v) {	29✔
307	node mv = nodeToMetaNode[v];	57,190✔
308	index cv = zetaCoarse[mv];	57,190✔
309	zetaFine[v] = cv;	57,190✔
310	});	57,190✔
311
312	return zetaFine;	29✔
313	}	×
314
315	const std::map<std::string, std::vector<count>> &PLM::getTiming() const {	29✔
316	assureFinished();	29✔
317	return timing;	29✔
318	}
319
320	} /* namespace NetworKit */

networkit / networkit / 22892510196

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous