↰ Return to documentation for file (include/networkit/graph/Graph.hpp)
/*
* Graph.hpp
*
* Created on: 01.06.2014
* Author: Christian Staudt
* Klara Reichard <klara.reichard@gmail.com>
* Marvin Ritter <marvin.ritter@gmail.com>
*/
#ifndef NETWORKIT_GRAPH_GRAPH_HPP_
#define NETWORKIT_GRAPH_GRAPH_HPP_
#include <algorithm>
#include <fstream>
#include <functional>
#include <iostream>
#include <memory>
#include <numeric>
#include <omp.h>
#include <queue>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <typeindex>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <networkit/Globals.hpp>
#include <networkit/auxiliary/ArrayTools.hpp>
#include <networkit/auxiliary/FunctionTraits.hpp>
#include <networkit/auxiliary/Log.hpp>
#include <networkit/auxiliary/Random.hpp>
#include <networkit/graph/Attributes.hpp>
#include <networkit/graph/EdgeIterators.hpp>
#include <networkit/graph/NeighborIterators.hpp>
#include <networkit/graph/NodeIterators.hpp>
#include <tlx/define/deprecated.hpp>
namespace NetworKit {
struct Edge {
node u, v;
Edge() : u(none), v(none) {}
Edge(node _u, node _v, bool sorted = false) {
u = sorted ? std::min(_u, _v) : _u;
v = sorted ? std::max(_u, _v) : _v;
}
};
struct WeightedEdge : Edge {
edgeweight weight;
// Needed by cython
WeightedEdge() : Edge(), weight(std::numeric_limits<edgeweight>::max()) {}
WeightedEdge(node u, node v, edgeweight w) : Edge(u, v), weight(w) {}
};
struct WeightedEdgeWithId : WeightedEdge {
edgeid eid;
WeightedEdgeWithId(node u, node v, edgeweight w, edgeid eid)
: WeightedEdge(u, v, w), eid(eid) {}
};
inline bool operator==(const Edge &e1, const Edge &e2) {
return e1.u == e2.u && e1.v == e2.v;
}
inline bool operator<(const WeightedEdge &e1, const WeightedEdge &e2) {
return e1.weight < e2.weight;
}
struct Unsafe {};
static constexpr Unsafe unsafe{};
} // namespace NetworKit
namespace std {
template <>
struct hash<NetworKit::Edge> {
size_t operator()(const NetworKit::Edge &e) const { return hash_node(e.u) ^ hash_node(e.v); }
hash<NetworKit::node> hash_node;
};
} // namespace std
namespace NetworKit {
// forward declaration to randomization/CurveballImpl.hpp
namespace CurveballDetails {
class CurveballMaterialization;
}
class Graph final {
// graph attributes
count n;
count m;
count storedNumberOfSelfLoops;
node z;
edgeid omega;
count t;
bool weighted;
bool directed;
bool edgesIndexed;
bool maintainCompactEdges = false;
bool maintainSortedEdges = false;
edgeid deletedID;
// per node data
std::vector<bool> exists;
std::vector<std::vector<node>> inEdges;
std::vector<std::vector<node>> outEdges;
std::vector<std::vector<edgeweight>> inEdgeWeights;
std::vector<std::vector<edgeweight>> outEdgeWeights;
std::vector<std::vector<edgeid>> inEdgeIds;
std::vector<std::vector<edgeid>> outEdgeIds;
private:
AttributeMap<PerNode, Graph> nodeAttributeMap;
AttributeMap<PerEdge, Graph> edgeAttributeMap;
public:
auto &nodeAttributes() noexcept { return nodeAttributeMap; }
const auto &nodeAttributes() const noexcept { return nodeAttributeMap; }
auto &edgeAttributes() noexcept { return edgeAttributeMap; }
const auto &edgeAttributes() const noexcept { return edgeAttributeMap; }
// wrap up some typed attributes for the cython interface:
//
auto attachNodeIntAttribute(const std::string &name) {
nodeAttributes().theGraph = this;
return nodeAttributes().attach<int>(name);
}
auto attachEdgeIntAttribute(const std::string &name) {
edgeAttributes().theGraph = this;
return edgeAttributes().attach<int>(name);
}
auto attachNodeDoubleAttribute(const std::string &name) {
nodeAttributes().theGraph = this;
return nodeAttributes().attach<double>(name);
}
auto attachEdgeDoubleAttribute(const std::string &name) {
edgeAttributes().theGraph = this;
return edgeAttributes().attach<double>(name);
}
auto attachNodeStringAttribute(const std::string &name) {
nodeAttributes().theGraph = this;
return nodeAttributes().attach<std::string>(name);
}
auto attachEdgeStringAttribute(const std::string &name) {
edgeAttributes().theGraph = this;
return edgeAttributes().attach<std::string>(name);
}
auto getNodeIntAttribute(const std::string &name) {
nodeAttributes().theGraph = this;
return nodeAttributes().get<int>(name);
}
auto getEdgeIntAttribute(const std::string &name) {
edgeAttributes().theGraph = this;
return edgeAttributes().get<int>(name);
}
auto getNodeDoubleAttribute(const std::string &name) {
nodeAttributes().theGraph = this;
return nodeAttributes().get<double>(name);
}
auto getEdgeDoubleAttribute(const std::string &name) {
edgeAttributes().theGraph = this;
return edgeAttributes().get<double>(name);
}
auto getNodeStringAttribute(const std::string &name) {
nodeAttributes().theGraph = this;
return nodeAttributes().get<std::string>(name);
}
auto getEdgeStringAttribute(const std::string &name) {
edgeAttributes().theGraph = this;
return edgeAttributes().get<std::string>(name);
}
void detachNodeAttribute(std::string const &name) {
nodeAttributes().theGraph = this;
nodeAttributes().detach(name);
}
void detachEdgeAttribute(std::string const &name) {
edgeAttributes().theGraph = this;
edgeAttributes().detach(name);
}
using NodeIntAttribute = Attribute<PerNode, Graph, int, false>;
using NodeDoubleAttribute = Attribute<PerNode, Graph, double, false>;
using NodeStringAttribute = Attribute<PerNode, Graph, std::string, false>;
using EdgeIntAttribute = Attribute<PerEdge, Graph, int, false>;
using EdgeDoubleAttribute = Attribute<PerEdge, Graph, double, false>;
using EdgeStringAttribute = Attribute<PerEdge, Graph, std::string, false>;
private:
index indexInInEdgeArray(node v, node u) const;
index indexInOutEdgeArray(node u, node v) const;
edgeweight computeWeightedDegree(node u, bool inDegree = false,
bool countSelfLoopsTwice = false) const;
template <bool hasWeights>
inline edgeweight getOutEdgeWeight(node u, index i) const;
template <bool hasWeights>
inline edgeweight getInEdgeWeight(node u, index i) const;
template <bool graphHasEdgeIds>
inline edgeid getOutEdgeId(node u, index i) const;
template <bool graphHasEdgeIds>
inline edgeid getInEdgeId(node u, index i) const;
template <bool graphIsDirected>
inline bool useEdgeInIteration(node u, node v) const;
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
inline void forOutEdgesOfImpl(node u, L handle) const;
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
inline void forInEdgesOfImpl(node u, L handle) const;
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
inline void forEdgeImpl(L handle) const;
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
inline void parallelForEdgesImpl(L handle) const;
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
inline double parallelSumForEdgesImpl(L handle) const;
/*
* In the following definition, Aux::FunctionTraits is used in order to only
* execute lambda functions with the appropriate parameters. The
* decltype-return type is used for determining the return type of the
* lambda (needed for summation) but also determines if the lambda accepts
* the correct number of parameters. Otherwise the return type declaration
* fails and the function is excluded from overload resolution. Then there
* are multiple possible lambdas with three (third parameter id or weight)
* and two (second parameter can be second node id or edge weight for
* neighbor iterators). This is checked using Aux::FunctionTraits and
* std::enable_if. std::enable_if only defines the type member when the
* given bool is true, this bool comes from std::is_same which compares two
* types. The function traits give either the parameter type or if it is out
* of bounds they define type as void.
*/
template <class F, void * = (void *)0>
typename Aux::FunctionTraits<F>::result_type edgeLambda(F &, ...) const {
// the strange condition is used in order to delay the evaluation of the
// static assert to the moment when this function is actually used
static_assert(!std::is_same<F, F>::value,
"Your lambda does not support the required parameters or the "
"parameters have the wrong type.");
return std::declval<typename Aux::FunctionTraits<F>::result_type>(); // use the correct
// return type (this
// won't compile)
}
template <class F,
typename std::enable_if<
(Aux::FunctionTraits<F>::arity >= 3)
&& std::is_same<edgeweight,
typename Aux::FunctionTraits<F>::template arg<2>::type>::value
&& std::is_same<edgeid, typename Aux::FunctionTraits<F>::template arg<3>::type>::
value>::type * = (void *)0>
auto edgeLambda(F &f, node u, node v, edgeweight ew, edgeid id) const
-> decltype(f(u, v, ew, id)) {
return f(u, v, ew, id);
}
template <
class F,
typename std::enable_if<
(Aux::FunctionTraits<F>::arity >= 2)
&& std::is_same<edgeid, typename Aux::FunctionTraits<F>::template arg<2>::type>::value
&& std::is_same<node, typename Aux::FunctionTraits<F>::template arg<1>::type>::
value /* prevent f(v, weight, eid)
*/
>::type * = (void *)0>
auto edgeLambda(F &f, node u, node v, edgeweight, edgeid id) const -> decltype(f(u, v, id)) {
return f(u, v, id);
}
template <class F,
typename std::enable_if<
(Aux::FunctionTraits<F>::arity >= 2)
&& std::is_same<edgeweight, typename Aux::FunctionTraits<F>::template arg<
2>::type>::value>::type * = (void *)0>
auto edgeLambda(F &f, node u, node v, edgeweight ew, edgeid /*id*/) const
-> decltype(f(u, v, ew)) {
return f(u, v, ew);
}
template <class F, typename std::enable_if<
(Aux::FunctionTraits<F>::arity >= 1)
&& std::is_same<node, typename Aux::FunctionTraits<F>::template arg<
1>::type>::value>::type * = (void *)0>
auto edgeLambda(F &f, node u, node v, edgeweight /*ew*/, edgeid /*id*/) const
-> decltype(f(u, v)) {
return f(u, v);
}
template <class F,
typename std::enable_if<
(Aux::FunctionTraits<F>::arity >= 1)
&& std::is_same<edgeweight, typename Aux::FunctionTraits<F>::template arg<
1>::type>::value>::type * = (void *)0>
auto edgeLambda(F &f, node, node v, edgeweight ew, edgeid /*id*/) const -> decltype(f(v, ew)) {
return f(v, ew);
}
template <class F, void * = (void *)0>
auto edgeLambda(F &f, node, node v, edgeweight, edgeid) const -> decltype(f(v)) {
return f(v);
}
template <class F>
auto callBFSHandle(F &f, node u, count dist) const -> decltype(f(u, dist)) {
return f(u, dist);
}
template <class F>
auto callBFSHandle(F &f, node u, count) const -> decltype(f(u)) {
return f(u);
}
public:
// For support of API: NetworKit::Graph::NodeIterator
using NodeIterator = NodeIteratorBase<Graph>;
// For support of API: NetworKit::Graph::NodeRange
using NodeRange = NodeRangeBase<Graph>;
// For support of API: NetworKit::Graph:EdgeIterator
using EdgeIterator = EdgeTypeIterator<Graph, Edge>;
// For support of API: NetworKit::Graph:EdgeWeightIterator
using EdgeWeightIterator = EdgeTypeIterator<Graph, WeightedEdge>;
// For support of API: NetworKit::Graph:EdgeRange
using EdgeRange = EdgeTypeRange<Graph, Edge>;
// For support of API: NetworKit::Graph:EdgeWeightRange
using EdgeWeightRange = EdgeTypeRange<Graph, WeightedEdge>;
// For support of API: NetworKit::Graph::NeighborIterator;
using NeighborIterator = NeighborIteratorBase<std::vector<node>>;
// For support of API: NetworKit::Graph::NeighborIterator;
using NeighborWeightIterator =
NeighborWeightIteratorBase<std::vector<node>, std::vector<edgeweight>>;
template <bool InEdges = false>
class NeighborRange {
const Graph *G;
node u;
public:
NeighborRange(const Graph &G, node u) : G(&G), u(u) { assert(G.hasNode(u)); };
NeighborRange() : G(nullptr){};
NeighborIterator begin() const {
assert(G);
return InEdges ? NeighborIterator(G->inEdges[u].begin())
: NeighborIterator(G->outEdges[u].begin());
}
NeighborIterator end() const {
assert(G);
return InEdges ? NeighborIterator(G->inEdges[u].end())
: NeighborIterator(G->outEdges[u].end());
}
};
using OutNeighborRange = NeighborRange<false>;
using InNeighborRange = NeighborRange<true>;
template <bool InEdges = false>
class NeighborWeightRange {
const Graph *G;
node u;
public:
NeighborWeightRange(const Graph &G, node u) : G(&G), u(u) { assert(G.hasNode(u)); };
NeighborWeightRange() : G(nullptr){};
NeighborWeightIterator begin() const {
assert(G);
return InEdges
? NeighborWeightIterator(G->inEdges[u].begin(), G->inEdgeWeights[u].begin())
: NeighborWeightIterator(G->outEdges[u].begin(),
G->outEdgeWeights[u].begin());
}
NeighborWeightIterator end() const {
assert(G);
return InEdges
? NeighborWeightIterator(G->inEdges[u].end(), G->inEdgeWeights[u].end())
: NeighborWeightIterator(G->outEdges[u].end(), G->outEdgeWeights[u].end());
}
};
using OutNeighborWeightRange = NeighborWeightRange<false>;
using InNeighborWeightRange = NeighborWeightRange<true>;
Graph(count n = 0, bool weighted = false, bool directed = false, bool edgesIndexed = false);
template <class EdgeMerger = std::plus<edgeweight>>
Graph(const Graph &G, bool weighted, bool directed, bool edgesIndexed = false,
EdgeMerger edgeMerger = std::plus<edgeweight>())
: n(G.n), m(G.m), storedNumberOfSelfLoops(G.storedNumberOfSelfLoops), z(G.z),
omega(edgesIndexed ? G.omega : 0), t(G.t), weighted(weighted), directed(directed),
edgesIndexed(edgesIndexed), // edges are not indexed by default
exists(G.exists),
// let the following be empty for the start, we fill them later
inEdges(0), outEdges(0), inEdgeWeights(0), outEdgeWeights(0), inEdgeIds(0), outEdgeIds(0),
// copy node attribute map
nodeAttributeMap(G.nodeAttributeMap, this),
// fill this later
edgeAttributeMap(this) {
if (G.isDirected() == directed) {
// G.inEdges might be empty (if G is undirected), but
// that's fine
inEdges = G.inEdges;
outEdges = G.outEdges;
edgeAttributeMap = AttributeMap(G.edgeAttributeMap, this);
// copy weights if needed
if (weighted) {
if (G.isWeighted()) {
// just copy from G, again either both graphs are directed or both are
// undirected
inEdgeWeights = G.inEdgeWeights;
outEdgeWeights = G.outEdgeWeights;
} else {
// G has no weights, set defaultEdgeWeight for all edges
if (directed) {
inEdgeWeights.resize(z);
for (node u = 0; u < z; u++) {
inEdgeWeights[u].resize(G.inEdges[u].size(), defaultEdgeWeight);
}
}
outEdgeWeights.resize(z);
for (node u = 0; u < z; u++) {
outEdgeWeights[u].resize(outEdges[u].size(), defaultEdgeWeight);
}
}
}
if (G.hasEdgeIds() && edgesIndexed) {
inEdgeIds = G.inEdgeIds;
outEdgeIds = G.outEdgeIds;
}
} else if (G.isDirected()) {
// G is directed, but we want an undirected graph
// so we need to combine the out and in stuff for every node
// for edge attributes, it is not well defined how they should be comined - we will skip
// that step and warn the user
WARN("Edge attributes are not preserved when converting from directed to undirected "
"graphs. The resulting graph will have empty edge attributes.");
outEdges.resize(z);
if (weighted)
outEdgeWeights.resize(z);
if (G.hasEdgeIds() && edgesIndexed)
outEdgeIds.resize(z);
G.balancedParallelForNodes([&](node u) {
// copy both out and in edges into our new outEdges
outEdges[u].reserve(G.outEdges[u].size() + G.inEdges[u].size());
outEdges[u].insert(outEdges[u].end(), G.outEdges[u].begin(), G.outEdges[u].end());
if (weighted) {
if (G.isWeighted()) {
// same for weights
outEdgeWeights[u].reserve(G.outEdgeWeights[u].size()
+ G.inEdgeWeights[u].size());
outEdgeWeights[u].insert(outEdgeWeights[u].end(),
G.outEdgeWeights[u].begin(),
G.outEdgeWeights[u].end());
} else {
// we are undirected, so no need to write anything into inEdgeWeights
outEdgeWeights[u].resize(outEdges[u].size(), defaultEdgeWeight);
}
}
if (G.hasEdgeIds() && edgesIndexed) {
// copy both out and in edges ids into our new outEdgesIds
outEdgeIds[u].reserve(G.outEdgeIds[u].size() + G.inEdgeIds[u].size());
outEdgeIds[u].insert(outEdgeIds[u].end(), G.outEdgeIds[u].begin(),
G.outEdgeIds[u].end());
}
});
G.balancedParallelForNodes([&](node u) {
// this is necessary to avoid multi edges, because both u -> v and v -> u can exist
// in G
count edgeSurplus = 0;
for (count i = 0; i < G.inEdges[u].size(); ++i) {
node v = G.inEdges[u][i];
bool alreadyPresent = false;
for (count j = 0; j < G.outEdges[u].size(); ++j) {
if (v != G.outEdges[u][j])
continue; // the edge already exists as an out edge
alreadyPresent = true;
if (u != v) {
++edgeSurplus;
if (weighted) // we need combine those edges weights when making it a
// single edge
outEdgeWeights[u][j] =
G.isWeighted()
? edgeMerger(G.inEdgeWeights[u][i], G.outEdgeWeights[u][j])
: edgeMerger(defaultEdgeWeight, defaultEdgeWeight);
if (G.hasEdgeIds() && edgesIndexed)
outEdgeIds[u][j] = std::min(G.inEdgeIds[u][i], G.outEdgeIds[u][j]);
}
break;
}
if (!alreadyPresent) { // an equivalent out edge wasn't present so we add it
outEdges[u].push_back(v);
if (weighted)
outEdgeWeights[u].push_back(G.isWeighted() ? G.inEdgeWeights[u][i]
: defaultEdgeWeight);
if (G.hasEdgeIds() && edgesIndexed)
outEdgeIds[u].push_back(G.inEdgeIds[u][i]);
}
}
#pragma omp atomic
m -= edgeSurplus;
});
} else {
// G is not directed, but this copy should be
// generally we can can copy G.out stuff into our in stuff
// for edge attributes, we currently do not have a way to iterate them for duplication
WARN("Edge attributes are currently not preserved when converting from undirected to "
"directed graphs.");
inEdges = G.outEdges;
outEdges = G.outEdges;
if (weighted) {
if (G.isWeighted()) {
inEdgeWeights = G.outEdgeWeights;
outEdgeWeights = G.outEdgeWeights;
} else {
// initialize both inEdgeWeights and outEdgeWeights with the
// defaultEdgeWeight
inEdgeWeights.resize(z);
for (node u = 0; u < z; ++u) {
inEdgeWeights[u].resize(inEdges[u].size(), defaultEdgeWeight);
}
outEdgeWeights.resize(z);
for (node u = 0; u < z; ++u) {
outEdgeWeights[u].resize(outEdges[u].size(), defaultEdgeWeight);
}
}
}
if (G.hasEdgeIds() && edgesIndexed) {
inEdgeIds = G.outEdgeIds;
outEdgeIds = G.outEdgeIds;
}
}
if (!G.edgesIndexed && edgesIndexed)
indexEdges();
}
Graph(std::initializer_list<WeightedEdge> edges);
Graph(const Graph &other)
: n(other.n), m(other.m), storedNumberOfSelfLoops(other.storedNumberOfSelfLoops),
z(other.z), omega(other.omega), t(other.t), weighted(other.weighted),
directed(other.directed), edgesIndexed(other.edgesIndexed), exists(other.exists),
inEdges(other.inEdges), outEdges(other.outEdges), inEdgeWeights(other.inEdgeWeights),
outEdgeWeights(other.outEdgeWeights), inEdgeIds(other.inEdgeIds),
outEdgeIds(other.outEdgeIds),
// call special constructors to copy attribute maps
nodeAttributeMap(other.nodeAttributeMap, this),
edgeAttributeMap(other.edgeAttributeMap, this){};
Graph(Graph &&other) noexcept
: n(other.n), m(other.m), storedNumberOfSelfLoops(other.storedNumberOfSelfLoops),
z(other.z), omega(other.omega), t(other.t), weighted(other.weighted),
directed(other.directed), edgesIndexed(other.edgesIndexed),
exists(std::move(other.exists)), inEdges(std::move(other.inEdges)),
outEdges(std::move(other.outEdges)), inEdgeWeights(std::move(other.inEdgeWeights)),
outEdgeWeights(std::move(other.outEdgeWeights)), inEdgeIds(std::move(other.inEdgeIds)),
outEdgeIds(std::move(other.outEdgeIds)),
nodeAttributeMap(std::move(other.nodeAttributeMap)),
edgeAttributeMap(std::move(other.edgeAttributeMap)) {
// attributes: set graph pointer to this new graph
nodeAttributeMap.theGraph = this;
edgeAttributeMap.theGraph = this;
};
~Graph() = default;
Graph &operator=(Graph &&other) noexcept {
std::swap(n, other.n);
std::swap(m, other.m);
std::swap(storedNumberOfSelfLoops, other.storedNumberOfSelfLoops);
std::swap(z, other.z);
std::swap(omega, other.omega);
std::swap(t, other.t);
std::swap(weighted, other.weighted);
std::swap(directed, other.directed);
std::swap(edgesIndexed, other.edgesIndexed);
std::swap(exists, other.exists);
std::swap(inEdges, other.inEdges);
std::swap(outEdges, other.outEdges);
std::swap(inEdgeWeights, other.inEdgeWeights);
std::swap(outEdgeWeights, other.outEdgeWeights);
std::swap(inEdgeIds, other.inEdgeIds);
std::swap(outEdgeIds, other.outEdgeIds);
// attributes: set graph pointer to this new graph
std::swap(nodeAttributeMap, other.nodeAttributeMap);
std::swap(edgeAttributeMap, other.edgeAttributeMap);
nodeAttributeMap.theGraph = this;
edgeAttributeMap.theGraph = this;
return *this;
};
Graph &operator=(const Graph &other) {
n = other.n;
m = other.m;
storedNumberOfSelfLoops = other.storedNumberOfSelfLoops;
z = other.z;
omega = other.omega;
t = other.t;
weighted = other.weighted;
directed = other.directed;
edgesIndexed = other.edgesIndexed;
exists = other.exists;
inEdges = other.inEdges;
outEdges = other.outEdges;
inEdgeWeights = other.inEdgeWeights;
outEdgeWeights = other.outEdgeWeights;
inEdgeIds = other.inEdgeIds;
outEdgeIds = other.outEdgeIds;
// call special constructors to copy attribute maps
nodeAttributeMap = AttributeMap(other.nodeAttributeMap, this);
edgeAttributeMap = AttributeMap(other.edgeAttributeMap, this);
return *this;
};
void preallocateUndirected(node u, size_t size);
void preallocateDirected(node u, size_t outSize, size_t inSize);
void preallocateDirectedOutEdges(node u, size_t outSize);
void preallocateDirectedInEdges(node u, size_t inSize);
void indexEdges(bool force = false);
bool hasEdgeIds() const noexcept { return edgesIndexed; }
edgeid edgeId(node u, node v) const;
std::pair<node, node> edgeById(index id) const {
std::pair<node, node> result{none, none};
bool found = false;
forNodesWhile([&] { return !found; },
[&](node u) {
forNeighborsOf(u, [&](node v) {
if (!this->isDirected() && v < u)
return;
auto uvId = edgeId(u, v);
if (uvId == id) {
found = true;
result = std::make_pair(u, v);
}
});
});
return result;
}
index upperEdgeIdBound() const noexcept { return omega; }
void shrinkToFit();
void TLX_DEPRECATED(compactEdges());
void sortEdges();
template <class Lambda>
void sortEdges(Lambda lambda);
void setEdgeCount(Unsafe, count edges) { m = edges; }
void setUpperEdgeIdBound(Unsafe, edgeid newBound) { omega = newBound; }
void setNumberOfSelfLoops(Unsafe, count loops) { storedNumberOfSelfLoops = loops; }
/* NODE MODIFIERS */
node addNode();
node addNodes(count numberOfNewNodes);
void removeNode(node v);
void removePartialOutEdges(Unsafe, node u) {
assert(hasNode(u));
outEdges[u].clear();
if (isWeighted()) {
outEdgeWeights[u].clear();
}
if (hasEdgeIds()) {
outEdgeIds[u].clear();
}
}
void removePartialInEdges(Unsafe, node u) {
assert(hasNode(u));
inEdges[u].clear();
if (isWeighted()) {
inEdgeWeights[u].clear();
}
if (hasEdgeIds()) {
inEdgeIds[u].clear();
}
}
bool hasNode(node v) const noexcept { return (v < z) && this->exists[v]; }
void restoreNode(node v);
count degree(node v) const {
assert(hasNode(v));
return outEdges[v].size();
}
count degreeIn(node v) const {
assert(hasNode(v));
return directed ? inEdges[v].size() : outEdges[v].size();
}
count degreeOut(node v) const { return degree(v); }
bool isIsolated(node v) const {
if (!exists[v])
throw std::runtime_error("Error, the node does not exist!");
return outEdges[v].empty() && (!directed || inEdges[v].empty());
}
edgeweight weightedDegree(node u, bool countSelfLoopsTwice = false) const;
edgeweight weightedDegreeIn(node u, bool countSelfLoopsTwice = false) const;
/* EDGE MODIFIERS */
bool addEdge(node u, node v, edgeweight ew = defaultEdgeWeight, bool checkMultiEdge = false);
bool addPartialEdge(Unsafe, node u, node v, edgeweight ew = defaultEdgeWeight,
uint64_t index = 0, bool checkForMultiEdges = false);
bool addPartialInEdge(Unsafe, node u, node v, edgeweight ew = defaultEdgeWeight,
uint64_t index = 0, bool checkForMultiEdges = false);
bool addPartialOutEdge(Unsafe, node u, node v, edgeweight ew = defaultEdgeWeight,
uint64_t index = 0, bool checkForMultiEdges = false);
void setKeepEdgesSorted(bool sorted = true) { maintainSortedEdges = sorted; }
void setMaintainCompactEdges(bool compact = true) { maintainCompactEdges = compact; }
bool getKeepEdgesSorted() const noexcept { return maintainSortedEdges; }
/*
* Returns true if edges are currently being compacted when removeEdge() is called.
*/
bool getMaintainCompactEdges() const noexcept { return maintainCompactEdges; }
void removeEdge(node u, node v);
void removeAllEdges();
template <typename Condition>
std::pair<count, count> removeAdjacentEdges(node u, Condition condition, bool edgesIn = false);
void removeSelfLoops();
void removeMultiEdges();
void swapEdge(node s1, node t1, node s2, node t2);
bool hasEdge(node u, node v) const noexcept;
/* GLOBAL PROPERTIES */
bool isWeighted() const noexcept { return weighted; }
bool isDirected() const noexcept { return directed; }
bool isEmpty() const noexcept { return !n; }
count numberOfNodes() const noexcept { return n; }
count numberOfEdges() const noexcept { return m; }
count numberOfSelfLoops() const noexcept { return storedNumberOfSelfLoops; }
index upperNodeIdBound() const noexcept { return z; }
bool checkConsistency() const;
/* DYNAMICS */
void timeStep() {
WARN("Graph::timeStep should not be used and will be deprecated in the future.");
t++;
}
count time() {
WARN("Graph::time should not be used and will be deprecated in the future.");
return t;
}
edgeweight weight(node u, node v) const;
void setWeight(node u, node v, edgeweight ew);
void setWeightAtIthNeighbor(Unsafe, node u, index i, edgeweight ew);
void setWeightAtIthInNeighbor(Unsafe, node u, index i, edgeweight ew);
void increaseWeight(node u, node v, edgeweight ew);
/* SUMS */
edgeweight totalEdgeWeight() const noexcept;
node getIthNeighbor(Unsafe, node u, index i) const { return outEdges[u][i]; }
edgeweight getIthNeighborWeight(Unsafe, node u, index i) const {
return isWeighted() ? outEdgeWeights[u][i] : defaultEdgeWeight;
}
NodeRange nodeRange() const noexcept { return NodeRange(*this); }
EdgeRange edgeRange() const noexcept { return EdgeRange(*this); }
EdgeWeightRange edgeWeightRange() const noexcept { return EdgeWeightRange(*this); }
NeighborRange<false> neighborRange(node u) const {
assert(exists[u]);
return NeighborRange<false>(*this, u);
}
NeighborWeightRange<false> weightNeighborRange(node u) const {
assert(isWeighted());
assert(exists[u]);
return NeighborWeightRange<false>(*this, u);
}
NeighborRange<true> inNeighborRange(node u) const {
assert(isDirected());
assert(exists[u]);
return NeighborRange<true>(*this, u);
}
NeighborWeightRange<true> weightInNeighborRange(node u) const {
assert(isDirected() && isWeighted());
assert(exists[u]);
return NeighborWeightRange<true>(*this, u);
}
index indexOfNeighbor(node u, node v) const { return indexInOutEdgeArray(u, v); }
node getIthNeighbor(node u, index i) const {
if (!hasNode(u) || i >= outEdges[u].size())
return none;
return outEdges[u][i];
}
node getIthInNeighbor(node u, index i) const {
if (!hasNode(u) || i >= inEdges[u].size())
return none;
return inEdges[u][i];
}
edgeweight getIthNeighborWeight(node u, index i) const {
if (!hasNode(u) || i >= outEdges[u].size())
return nullWeight;
return isWeighted() ? outEdgeWeights[u][i] : defaultEdgeWeight;
}
std::pair<node, edgeweight> getIthNeighborWithWeight(node u, index i) const {
if (!hasNode(u) || i >= outEdges[u].size())
return {none, none};
return getIthNeighborWithWeight(unsafe, u, i);
}
std::pair<node, edgeweight> getIthNeighborWithWeight(Unsafe, node u, index i) const {
if (!isWeighted())
return {outEdges[u][i], defaultEdgeWeight};
return {outEdges[u][i], outEdgeWeights[u][i]};
}
std::pair<node, edgeid> getIthNeighborWithId(node u, index i) const {
assert(hasEdgeIds());
if (!hasNode(u) || i >= outEdges[u].size())
return {none, none};
return {outEdges[u][i], outEdgeIds[u][i]};
}
/* NODE ITERATORS */
template <typename L>
void forNodes(L handle) const;
template <typename L>
void parallelForNodes(L handle) const;
template <typename C, typename L>
void forNodesWhile(C condition, L handle) const;
template <typename L>
void forNodesInRandomOrder(L handle) const;
template <typename L>
void balancedParallelForNodes(L handle) const;
template <typename L>
void forNodePairs(L handle) const;
template <typename L>
void parallelForNodePairs(L handle) const;
/* EDGE ITERATORS */
template <typename L>
void forEdges(L handle) const;
template <typename L>
void parallelForEdges(L handle) const;
/* NEIGHBORHOOD ITERATORS */
template <typename L>
void forNeighborsOf(node u, L handle) const;
template <typename L>
void forEdgesOf(node u, L handle) const;
template <typename L>
void forInNeighborsOf(node u, L handle) const;
template <typename L>
void forInEdgesOf(node u, L handle) const;
/* REDUCTION ITERATORS */
template <typename L>
double parallelSumForNodes(L handle) const;
template <typename L>
double parallelSumForEdges(L handle) const;
};
/* NODE ITERATORS */
template <typename L>
void Graph::forNodes(L handle) const {
for (node v = 0; v < z; ++v) {
if (exists[v]) {
handle(v);
}
}
}
template <typename L>
void Graph::parallelForNodes(L handle) const {
#pragma omp parallel for
for (omp_index v = 0; v < static_cast<omp_index>(z); ++v) {
if (exists[v]) {
handle(v);
}
}
}
template <typename C, typename L>
void Graph::forNodesWhile(C condition, L handle) const {
for (node v = 0; v < z; ++v) {
if (exists[v]) {
if (!condition()) {
break;
}
handle(v);
}
}
}
template <typename L>
void Graph::forNodesInRandomOrder(L handle) const {
std::vector<node> randVec;
randVec.reserve(numberOfNodes());
forNodes([&](node u) { randVec.push_back(u); });
std::shuffle(randVec.begin(), randVec.end(), Aux::Random::getURNG());
for (node v : randVec) {
handle(v);
}
}
template <typename L>
void Graph::balancedParallelForNodes(L handle) const {
// TODO: define min block size (and test it!)
#pragma omp parallel for schedule(guided)
for (omp_index v = 0; v < static_cast<omp_index>(z); ++v) {
if (exists[v]) {
handle(v);
}
}
}
template <typename L>
void Graph::forNodePairs(L handle) const {
for (node u = 0; u < z; ++u) {
if (exists[u]) {
for (node v = u + 1; v < z; ++v) {
if (exists[v]) {
handle(u, v);
}
}
}
}
}
template <typename L>
void Graph::parallelForNodePairs(L handle) const {
#pragma omp parallel for schedule(guided)
for (omp_index u = 0; u < static_cast<omp_index>(z); ++u) {
if (exists[u]) {
for (node v = u + 1; v < z; ++v) {
if (exists[v]) {
handle(u, v);
}
}
}
}
}
/* EDGE ITERATORS */
/* HELPERS */
template <typename T>
void erase(node u, index idx, std::vector<std::vector<T>> &vec);
// implementation for weighted == true
template <bool hasWeights>
inline edgeweight Graph::getOutEdgeWeight(node u, index i) const {
return outEdgeWeights[u][i];
}
// implementation for weighted == false
template <>
inline edgeweight Graph::getOutEdgeWeight<false>(node, index) const {
return defaultEdgeWeight;
}
// implementation for weighted == true
template <bool hasWeights>
inline edgeweight Graph::getInEdgeWeight(node u, index i) const {
return inEdgeWeights[u][i];
}
// implementation for weighted == false
template <>
inline edgeweight Graph::getInEdgeWeight<false>(node, index) const {
return defaultEdgeWeight;
}
// implementation for hasEdgeIds == true
template <bool graphHasEdgeIds>
inline edgeid Graph::getOutEdgeId(node u, index i) const {
return outEdgeIds[u][i];
}
// implementation for hasEdgeIds == false
template <>
inline edgeid Graph::getOutEdgeId<false>(node, index) const {
return none;
}
// implementation for hasEdgeIds == true
template <bool graphHasEdgeIds>
inline edgeid Graph::getInEdgeId(node u, index i) const {
return inEdgeIds[u][i];
}
// implementation for hasEdgeIds == false
template <>
inline edgeid Graph::getInEdgeId<false>(node, index) const {
return none;
}
// implementation for graphIsDirected == true
template <bool graphIsDirected>
inline bool Graph::useEdgeInIteration(node /* u */, node /* v */) const {
return true;
}
// implementation for graphIsDirected == false
template <>
inline bool Graph::useEdgeInIteration<false>(node u, node v) const {
return u >= v;
}
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
inline void Graph::forOutEdgesOfImpl(node u, L handle) const {
for (index i = 0; i < outEdges[u].size(); ++i) {
node v = outEdges[u][i];
if (useEdgeInIteration<graphIsDirected>(u, v)) {
edgeLambda<L>(handle, u, v, getOutEdgeWeight<hasWeights>(u, i),
getOutEdgeId<graphHasEdgeIds>(u, i));
}
}
}
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
inline void Graph::forInEdgesOfImpl(node u, L handle) const {
if (graphIsDirected) {
for (index i = 0; i < inEdges[u].size(); i++) {
node v = inEdges[u][i];
if (useEdgeInIteration<true>(u, v)) {
edgeLambda<L>(handle, u, v, getInEdgeWeight<hasWeights>(u, i),
getInEdgeId<graphHasEdgeIds>(u, i));
}
}
} else {
for (index i = 0; i < outEdges[u].size(); ++i) {
node v = outEdges[u][i];
if (useEdgeInIteration<true>(u, v)) {
edgeLambda<L>(handle, u, v, getOutEdgeWeight<hasWeights>(u, i),
getOutEdgeId<graphHasEdgeIds>(u, i));
}
}
}
}
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
inline void Graph::forEdgeImpl(L handle) const {
for (node u = 0; u < z; ++u) {
forOutEdgesOfImpl<graphIsDirected, hasWeights, graphHasEdgeIds, L>(u, handle);
}
}
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
inline void Graph::parallelForEdgesImpl(L handle) const {
#pragma omp parallel for schedule(guided)
for (omp_index u = 0; u < static_cast<omp_index>(z); ++u) {
forOutEdgesOfImpl<graphIsDirected, hasWeights, graphHasEdgeIds, L>(u, handle);
}
}
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
inline double Graph::parallelSumForEdgesImpl(L handle) const {
double sum = 0.0;
#pragma omp parallel for reduction(+ : sum)
for (omp_index u = 0; u < static_cast<omp_index>(z); ++u) {
for (index i = 0; i < outEdges[u].size(); ++i) {
node v = outEdges[u][i];
// undirected, do not iterate over edges twice
// {u, v} instead of (u, v); if v == none, u > v is not fulfilled
if (useEdgeInIteration<graphIsDirected>(u, v)) {
sum += edgeLambda<L>(handle, u, v, getOutEdgeWeight<hasWeights>(u, i),
getOutEdgeId<graphHasEdgeIds>(u, i));
}
}
}
return sum;
}
template <typename L>
void Graph::forEdges(L handle) const {
switch (weighted + 2 * directed + 4 * edgesIndexed) {
case 0: // unweighted, undirected, no edgeIds
forEdgeImpl<false, false, false, L>(handle);
break;
case 1: // weighted, undirected, no edgeIds
forEdgeImpl<false, true, false, L>(handle);
break;
case 2: // unweighted, directed, no edgeIds
forEdgeImpl<true, false, false, L>(handle);
break;
case 3: // weighted, directed, no edgeIds
forEdgeImpl<true, true, false, L>(handle);
break;
case 4: // unweighted, undirected, with edgeIds
forEdgeImpl<false, false, true, L>(handle);
break;
case 5: // weighted, undirected, with edgeIds
forEdgeImpl<false, true, true, L>(handle);
break;
case 6: // unweighted, directed, with edgeIds
forEdgeImpl<true, false, true, L>(handle);
break;
case 7: // weighted, directed, with edgeIds
forEdgeImpl<true, true, true, L>(handle);
break;
}
}
template <typename L>
void Graph::parallelForEdges(L handle) const {
switch (weighted + 2 * directed + 4 * edgesIndexed) {
case 0: // unweighted, undirected, no edgeIds
parallelForEdgesImpl<false, false, false, L>(handle);
break;
case 1: // weighted, undirected, no edgeIds
parallelForEdgesImpl<false, true, false, L>(handle);
break;
case 2: // unweighted, directed, no edgeIds
parallelForEdgesImpl<true, false, false, L>(handle);
break;
case 3: // weighted, directed, no edgeIds
parallelForEdgesImpl<true, true, false, L>(handle);
break;
case 4: // unweighted, undirected, with edgeIds
parallelForEdgesImpl<false, false, true, L>(handle);
break;
case 5: // weighted, undirected, with edgeIds
parallelForEdgesImpl<false, true, true, L>(handle);
break;
case 6: // unweighted, directed, with edgeIds
parallelForEdgesImpl<true, false, true, L>(handle);
break;
case 7: // weighted, directed, with edgeIds
parallelForEdgesImpl<true, true, true, L>(handle);
break;
}
}
/* NEIGHBORHOOD ITERATORS */
template <typename L>
void Graph::forNeighborsOf(node u, L handle) const {
forEdgesOf(u, handle);
}
template <typename L>
void Graph::forEdgesOf(node u, L handle) const {
switch (weighted + 2 * edgesIndexed) {
case 0: // not weighted, no edge ids
forOutEdgesOfImpl<true, false, false, L>(u, handle);
break;
case 1: // weighted, no edge ids
forOutEdgesOfImpl<true, true, false, L>(u, handle);
break;
case 2: // not weighted, with edge ids
forOutEdgesOfImpl<true, false, true, L>(u, handle);
break;
case 3: // weighted, with edge ids
forOutEdgesOfImpl<true, true, true, L>(u, handle);
break;
}
}
template <typename L>
void Graph::forInNeighborsOf(node u, L handle) const {
forInEdgesOf(u, handle);
}
template <typename L>
void Graph::forInEdgesOf(node u, L handle) const {
switch (weighted + 2 * directed + 4 * edgesIndexed) {
case 0: // unweighted, undirected, no edge ids
forInEdgesOfImpl<false, false, false, L>(u, handle);
break;
case 1: // weighted, undirected, no edge ids
forInEdgesOfImpl<false, true, false, L>(u, handle);
break;
case 2: // unweighted, directed, no edge ids
forInEdgesOfImpl<true, false, false, L>(u, handle);
break;
case 3: // weighted, directed, no edge ids
forInEdgesOfImpl<true, true, false, L>(u, handle);
break;
case 4: // unweighted, undirected, with edge ids
forInEdgesOfImpl<false, false, true, L>(u, handle);
break;
case 5: // weighted, undirected, with edge ids
forInEdgesOfImpl<false, true, true, L>(u, handle);
break;
case 6: // unweighted, directed, with edge ids
forInEdgesOfImpl<true, false, true, L>(u, handle);
break;
case 7: // weighted, directed, with edge ids
forInEdgesOfImpl<true, true, true, L>(u, handle);
break;
}
}
/* REDUCTION ITERATORS */
template <typename L>
double Graph::parallelSumForNodes(L handle) const {
double sum = 0.0;
#pragma omp parallel for reduction(+ : sum)
for (omp_index v = 0; v < static_cast<omp_index>(z); ++v) {
if (exists[v]) {
sum += handle(v);
}
}
return sum;
}
template <typename L>
double Graph::parallelSumForEdges(L handle) const {
double sum = 0.0;
switch (weighted + 2 * directed + 4 * edgesIndexed) {
case 0: // unweighted, undirected, no edge ids
sum = parallelSumForEdgesImpl<false, false, false, L>(handle);
break;
case 1: // weighted, undirected, no edge ids
sum = parallelSumForEdgesImpl<false, true, false, L>(handle);
break;
case 2: // unweighted, directed, no edge ids
sum = parallelSumForEdgesImpl<true, false, false, L>(handle);
break;
case 3: // weighted, directed, no edge ids
sum = parallelSumForEdgesImpl<true, true, false, L>(handle);
break;
case 4: // unweighted, undirected, with edge ids
sum = parallelSumForEdgesImpl<false, false, true, L>(handle);
break;
case 5: // weighted, undirected, with edge ids
sum = parallelSumForEdgesImpl<false, true, true, L>(handle);
break;
case 6: // unweighted, directed, with edge ids
sum = parallelSumForEdgesImpl<true, false, true, L>(handle);
break;
case 7: // weighted, directed, with edge ids
sum = parallelSumForEdgesImpl<true, true, true, L>(handle);
break;
}
return sum;
}
/* EDGE MODIFIERS */
template <typename Condition>
std::pair<count, count> Graph::removeAdjacentEdges(node u, Condition condition, bool edgesIn) {
count removedEdges = 0;
count removedSelfLoops = 0;
// For directed graphs, this function is supposed to be called twice: one to remove out-edges,
// and one to remove in-edges.
auto &edges_ = edgesIn ? inEdges[u] : outEdges[u];
for (index vi = 0; vi < edges_.size();) {
if (condition(edges_[vi])) {
const auto isSelfLoop = (edges_[vi] == u);
removedSelfLoops += isSelfLoop;
removedEdges += !isSelfLoop;
edges_[vi] = edges_.back();
edges_.pop_back();
if (isWeighted()) {
auto &weights_ = edgesIn ? inEdgeWeights[u] : outEdgeWeights[u];
weights_[vi] = weights_.back();
weights_.pop_back();
}
if (hasEdgeIds()) {
auto &edgeIds_ = edgesIn ? inEdgeIds[u] : outEdgeIds[u];
edgeIds_[vi] = edgeIds_.back();
edgeIds_.pop_back();
}
} else {
++vi;
}
}
return {removedEdges, removedSelfLoops};
}
template <class Lambda>
void Graph::sortEdges(Lambda lambda) {
std::vector<std::vector<index>> indicesGlobal(omp_get_max_threads());
const auto sortAdjacencyArrays = [&](node u, std::vector<node> &adjList,
std::vector<edgeweight> &weights,
std::vector<edgeid> &edgeIds) -> void {
auto &indices = indicesGlobal[omp_get_thread_num()];
if (adjList.size() > indices.size())
indices.resize(adjList.size());
const auto indicesEnd =
indices.begin()
+ static_cast<
std::iterator_traits<std::vector<index>::const_iterator>::difference_type>(
adjList.size());
std::iota(indices.begin(), indicesEnd, 0);
if (isWeighted()) {
if (hasEdgeIds())
std::sort(indices.begin(), indicesEnd, [&](auto a, auto b) -> bool {
return lambda(WeightedEdgeWithId{u, adjList[a], weights[a], edgeIds[a]},
WeightedEdgeWithId{u, adjList[b], weights[b], edgeIds[b]});
});
else
std::sort(indices.begin(), indicesEnd, [&](auto a, auto b) -> bool {
return lambda(WeightedEdgeWithId{u, adjList[a], weights[a], 0},
WeightedEdgeWithId{u, adjList[b], weights[b], 0});
});
} else if (hasEdgeIds())
std::sort(indices.begin(), indicesEnd, [&](auto a, auto b) -> bool {
return lambda(WeightedEdgeWithId{u, adjList[a], defaultEdgeWeight, edgeIds[a]},
WeightedEdgeWithId{u, adjList[b], defaultEdgeWeight, edgeIds[b]});
});
else
std::sort(indices.begin(), indicesEnd, [&](auto a, auto b) -> bool {
return lambda(WeightedEdgeWithId{u, adjList[a], defaultEdgeWeight, 0},
WeightedEdgeWithId{u, adjList[b], defaultEdgeWeight, 0});
});
Aux::ArrayTools::applyPermutation(adjList.begin(), adjList.end(), indices.begin());
if (isWeighted())
Aux::ArrayTools::applyPermutation(weights.begin(), weights.end(), indices.begin());
if (hasEdgeIds())
Aux::ArrayTools::applyPermutation(edgeIds.begin(), edgeIds.end(), indices.begin());
};
balancedParallelForNodes([&](const node u) {
if (degree(u) < 2)
return;
std::vector<edgeweight> dummyEdgeWeights;
std::vector<edgeid> dummyEdgeIds;
sortAdjacencyArrays(u, outEdges[u], isWeighted() ? outEdgeWeights[u] : dummyEdgeWeights,
hasEdgeIds() ? outEdgeIds[u] : dummyEdgeIds);
if (isDirected())
sortAdjacencyArrays(u, inEdges[u], isWeighted() ? inEdgeWeights[u] : dummyEdgeWeights,
hasEdgeIds() ? inEdgeIds[u] : dummyEdgeIds);
});
}
} /* namespace NetworKit */
#endif // NETWORKIT_GRAPH_GRAPH_HPP_