21357890104

Committed 26 Jan 2026 12:36PM UTC coverage: 79.449% (+0.02%) from 79.431%

Build # 21357890104

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #1390 from domischweisgut/feature/python-implicit-conversion

Allow implicit conversion from int to float for NodeAttributes - Issue #1221

Run Details

2 of 2 new or added lines in 1 file covered. (100.0%)

4 existing lines in 1 file now uncovered.

29517 of 37152 relevant lines covered (79.45%)

2284855.43 hits per line

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

93.9

/networkit/cpp/distance/AlgebraicDistance.cpp

/*
 * AlgebraicDistance.cpp
 *
 *  Created on: 03.11.2015
 *      Author: Henning Meyerhenke, Christian Staudt, Michael Hamann
 */

#include <omp.h>

#include <networkit/auxiliary/Timer.hpp>
#include <networkit/distance/AlgebraicDistance.hpp>

namespace NetworKit {

AlgebraicDistance::AlgebraicDistance(const Graph &G, count numberSystems, count numberIterations,
                                     double omega, index norm, bool withEdgeScores)
    : NodeDistance(G), numSystems(numberSystems), numIters(numberIterations), omega(omega),
      norm(norm), withEdgeScores(withEdgeScores) {
    if ((omega < 0.0) || (omega > 1.0))
        throw std::invalid_argument("omega must be in [0,1]");
    if (withEdgeScores && !G.hasEdgeIds()) {
        throw std::runtime_error("edges have not been indexed - call indexEdges first");
    }
    if (G.isDirected()) {
        throw std::invalid_argument("Graph must be undirected");
    }
}

void AlgebraicDistance::randomInit() {
    // allocate space for loads
    loads.resize(numSystems * G->upperNodeIdBound());

#pragma omp parallel for
    for (omp_index i = 0; i < static_cast<omp_index>(loads.size()); ++i) {
        loads[i] = Aux::Random::real();
    }
}

void AlgebraicDistance::preprocess() {
    Aux::Timer running1;
    running1.start();
    // random init
    randomInit();

    // main loop

    {
        std::vector<double> oldLoads(loads.size());

        for (index iter = 0; iter < numIters; ++iter) {
            // store previous iteration
            loads.swap(oldLoads);

            G->balancedParallelForNodes([&](node u) {
                std::vector<double> val(numSystems, 0.0);

                double weightedDeg = 0;
                // step 1
                G->forNeighborsOf(u, [&](node v, edgeweight weight) {
                    for (index i = 0; i < numSystems; ++i) {
                        val[i] += weight * oldLoads[v * numSystems + i];
                    }

                    weightedDeg += weight;
                });

                for (index i = 0; i < numSystems; ++i) {
                    val[i] /= weightedDeg;

                    // step 2
                    loads[u * numSystems + i] =
                        (1 - omega) * oldLoads[u * numSystems + i] + omega * val[i];
                }
            });
        }
    }

    // normalization. Compute min/max over all nodes per system (and per thread)
    std::vector<std::vector<double>> minPerThread(
        omp_get_max_threads(), std::vector<double>(numSystems, std::numeric_limits<double>::max()));
    std::vector<std::vector<double>> maxPerThread(
        omp_get_max_threads(),
        std::vector<double>(numSystems, std::numeric_limits<double>::lowest()));
    G->parallelForNodes([&](node u) {
        auto tid = omp_get_thread_num();
        const index startId = u * numSystems;
        for (index sys = 0; sys < numSystems; ++sys) {
            minPerThread[tid][sys] = std::min(minPerThread[tid][sys], loads[startId + sys]);
            maxPerThread[tid][sys] = std::max(maxPerThread[tid][sys], loads[startId + sys]);
        }
    });

    std::vector<double> minPerSystem = std::move(minPerThread[0]);
    std::vector<double> maxPerSystem = std::move(maxPerThread[0]);
    for (index i = 1; i < minPerThread.size(); ++i) {
        for (index sys = 0; sys < numSystems; ++sys) {
            minPerSystem[sys] = std::min(minPerSystem[sys], minPerThread[i][sys]);
            maxPerSystem[sys] = std::max(maxPerSystem[sys], maxPerThread[i][sys]);
        }
    }

    // set normalized values: new = (min - old) / (min - max)
    // normalization is per system
    G->parallelForNodes([&](node u) {
        const index startId = u * numSystems;
        for (index sys = 0; sys < numSystems; ++sys) {
            loads[startId + sys] = (minPerSystem[sys] - loads[startId + sys])
                                   / (minPerSystem[sys] - maxPerSystem[sys]);
        }
    });

    // calculate edge scores

    if (withEdgeScores) {
        edgeScores.resize(G->upperEdgeIdBound(), std::numeric_limits<edgeweight>::max());

        G->parallelForEdges([&](node u, node v, edgeid eid) { edgeScores[eid] = distance(u, v); });
    }

    running1.stop();
    INFO("elapsed millisecs for AD preprocessing: ", running1.elapsedMilliseconds(), "\n");
}

double AlgebraicDistance::distance(node u, node v) {
    if (loads.empty()) {
        throw std::runtime_error("Call preprocess() first.");
    }
    double result = 0.0;

    if (norm == MAX_NORM) {
        for (index sys = 0; sys < numSystems; ++sys) {
            double absDiff = std::fabs(loads[u * numSystems + sys] - loads[v * numSystems + sys]);
            if (absDiff > result) {
                result = absDiff;
            }
        }
    } else {
        for (index sys = 0; sys < numSystems; ++sys) {
            double absDiff = std::fabs(loads[u * numSystems + sys] - loads[v * numSystems + sys]);
            result += std::pow(absDiff, norm);
        }
        result = std::pow(result, 1.0 / (double)norm);
    }

    return std::isnan(result) ? 0 : result;
}

const std::vector<double> &AlgebraicDistance::getEdgeScores() const {
    if (!withEdgeScores)
        throw std::runtime_error("set constructor parameter 'withEdgeScores' to true");
    return edgeScores;
}

} /* namespace NetworKit */

1	/*
2	* AlgebraicDistance.cpp
3	*
4	* Created on: 03.11.2015
5	* Author: Henning Meyerhenke, Christian Staudt, Michael Hamann
6	*/
7
8	#include <omp.h>
9
10	#include <networkit/auxiliary/Timer.hpp>
11	#include <networkit/distance/AlgebraicDistance.hpp>
12
13	namespace NetworKit {
14
15	AlgebraicDistance::AlgebraicDistance(const Graph &G, count numberSystems, count numberIterations,	7✔
16	double omega, index norm, bool withEdgeScores)	7✔
17	: NodeDistance(G), numSystems(numberSystems), numIters(numberIterations), omega(omega),	7✔
18	norm(norm), withEdgeScores(withEdgeScores) {	7✔
19	if ((omega < 0.0) \|\| (omega > 1.0))	7✔
20	throw std::invalid_argument("omega must be in [0,1]");	2✔
21	if (withEdgeScores && !G.hasEdgeIds()) {	5✔
22	throw std::runtime_error("edges have not been indexed - call indexEdges first");	1✔
23	}
24	if (G.isDirected()) {	4✔
25	throw std::invalid_argument("Graph must be undirected");	1✔
26	}
27	}	15✔
28
29	void AlgebraicDistance::randomInit() {	2✔
30	// allocate space for loads
31	loads.resize(numSystems * G->upperNodeIdBound());	2✔
32
33	#pragma omp parallel for	2✔
34	for (omp_index i = 0; i < static_cast<omp_index>(loads.size()); ++i) {
35	loads[i] = Aux::Random::real();
36	}
37	}	2✔
38
39	void AlgebraicDistance::preprocess() {	2✔
40	Aux::Timer running1;	2✔
41	running1.start();	2✔
42	// random init
43	randomInit();	2✔
44
45	// main loop
46
47	{
48	std::vector<double> oldLoads(loads.size());	2✔
49
50	for (index iter = 0; iter < numIters; ++iter) {	62✔
51	// store previous iteration
52	loads.swap(oldLoads);	60✔
53
54	G->balancedParallelForNodes([&](node u) {	60✔
55	std::vector<double> val(numSystems, 0.0);	15,900✔
56
57	double weightedDeg = 0;	15,900✔
58	// step 1
59	G->forNeighborsOf(u, [&](node v, edgeweight weight) {	152,640✔
60	for (index i = 0; i < numSystems; ++i) {	1,504,140✔
61	val[i] += weight * oldLoads[v * numSystems + i];	1,383,300✔
62	}
63
64	weightedDeg += weight;	136,740✔
65	});	136,740✔
66
67	for (index i = 0; i < numSystems; ++i) {	174,900✔
68	val[i] /= weightedDeg;	159,000✔
69
70	// step 2
71	loads[u * numSystems + i] =	159,000✔
72	(1 - omega) * oldLoads[u * numSystems + i] + omega * val[i];	159,000✔
73	}
74	});	15,900✔
75	}
76	}	2✔
77
78	// normalization. Compute min/max over all nodes per system (and per thread)
79	std::vector<std::vector<double>> minPerThread(
80	omp_get_max_threads(), std::vector<double>(numSystems, std::numeric_limits<double>::max()));	2✔
81	std::vector<std::vector<double>> maxPerThread(
82	omp_get_max_threads(),	2✔
83	std::vector<double>(numSystems, std::numeric_limits<double>::lowest()));	4✔
84	G->parallelForNodes([&](node u) {	2✔
85	auto tid = omp_get_thread_num();	530✔
86	const index startId = u * numSystems;	16,960✔
87	for (index sys = 0; sys < numSystems; ++sys) {	5,830✔
88	minPerThread[tid][sys] = std::min(minPerThread[tid][sys], loads[startId + sys]);	5,300✔
89	maxPerThread[tid][sys] = std::max(maxPerThread[tid][sys], loads[startId + sys]);	5,300✔
90	}
91	});	530✔
92
93	std::vector<double> minPerSystem = std::move(minPerThread[0]);	2✔
94	std::vector<double> maxPerSystem = std::move(maxPerThread[0]);	2✔
95	for (index i = 1; i < minPerThread.size(); ++i) {	4✔
96	for (index sys = 0; sys < numSystems; ++sys) {	22✔
97	minPerSystem[sys] = std::min(minPerSystem[sys], minPerThread[i][sys]);	20✔
98	maxPerSystem[sys] = std::max(maxPerSystem[sys], maxPerThread[i][sys]);	20✔
99	}
100	}
101
102	// set normalized values: new = (min - old) / (min - max)
103	// normalization is per system
104	G->parallelForNodes([&](node u) {	2✔
105	const index startId = u * numSystems;	16,960✔
106	for (index sys = 0; sys < numSystems; ++sys) {	5,830✔
107	loads[startId + sys] = (minPerSystem[sys] - loads[startId + sys])	10,600✔
108	/ (minPerSystem[sys] - maxPerSystem[sys]);	5,300✔
109	}
110	});	530✔
111
112	// calculate edge scores
113
114	if (withEdgeScores) {	2✔
115	edgeScores.resize(G->upperEdgeIdBound(), std::numeric_limits<edgeweight>::max());	2✔
116
117	G->parallelForEdges([&](node u, node v, edgeid eid) { edgeScores[eid] = distance(u, v); });	2,281✔
118	}
119
120	running1.stop();	2✔
121	INFO("elapsed millisecs for AD preprocessing: ", running1.elapsedMilliseconds(), "\n");	2✔
122	}	2✔
123
124	double AlgebraicDistance::distance(node u, node v) {	2,282✔
125	if (loads.empty()) {	2,282✔
126	throw std::runtime_error("Call preprocess() first.");	1✔
127	}
128	double result = 0.0;	2,281✔
129
130	if (norm == MAX_NORM) {	2,281✔
131	for (index sys = 0; sys < numSystems; ++sys) {	25,091✔
132	double absDiff = std::fabs(loads[u * numSystems + sys] - loads[v * numSystems + sys]);	22,810✔
133	if (absDiff > result) {	22,810✔
134	result = absDiff;	5,959✔
135	}
136	}
137	} else {
UNCOV 138	for (index sys = 0; sys < numSystems; ++sys) {	×
139	double absDiff = std::fabs(loads[u * numSystems + sys] - loads[v * numSystems + sys]);	×
UNCOV 140	result += std::pow(absDiff, norm);	×
141	}
UNCOV 142	result = std::pow(result, 1.0 / (double)norm);	×
143	}
144
145	return std::isnan(result) ? 0 : result;	2,281✔
146	}
147
148	const std::vector<double> &AlgebraicDistance::getEdgeScores() const {	2✔
149	if (!withEdgeScores)	2✔
UNCOV 150	throw std::runtime_error("set constructor parameter 'withEdgeScores' to true");	×
151	return edgeScores;	2✔
152	}
153
154	} /* namespace NetworKit */

networkit / networkit / 21357890104

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