↰ Return to documentation for file (include/networkit/graph/AdjListGraph.hpp)
/*
* AdjListGraph.hpp
*
* Created on: 01.06.2014
* Author: Christian Staudt
* Klara Reichard <klara.reichard@gmail.com>
* Marvin Ritter <marvin.ritter@gmail.com>
*/
#ifndef NETWORKIT_GRAPH_ADJ_LIST_GRAPH_HPP_
#define NETWORKIT_GRAPH_ADJ_LIST_GRAPH_HPP_
#include <algorithm>
#include <atomic>
#include <cassert>
#include <concepts>
#include <functional>
#include <numeric>
#include <omp.h>
#include <ranges>
#include <span>
#include <sstream>
#include <stdexcept>
#include <type_traits>
#include <typeindex>
#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/EdgeUtils.hpp>
#include <networkit/graph/GraphConcepts.hpp>
#include <networkit/graph/NeighborIterators.hpp>
#include <networkit/graph/NodeIterators.hpp>
#include <tlx/define/deprecated.hpp>
namespace NetworKit {
// forward declaration to randomization/CurveballImpl.hpp
namespace CurveballDetails {
class CurveballMaterialization;
}
template <GraphNode NodeType, GraphEdgeWeight EdgeWeightType>
class AdjListGraph final {
public:
using NodeT = NodeType;
using EdgeWeightT = EdgeWeightType;
private:
// graph attributes
count n;
count m;
count storedNumberOfSelfLoops;
NodeT 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<NodeT>> inEdges;
std::vector<std::vector<NodeT>> outEdges;
std::vector<std::vector<EdgeWeightT>> inEdgeWeights;
std::vector<std::vector<EdgeWeightT>> outEdgeWeights;
std::vector<std::vector<edgeid>> inEdgeIds;
std::vector<std::vector<edgeid>> outEdgeIds;
static constexpr NodeT nullNodeId = NullNodeId<NodeT>;
AttributeMap<PerNode, AdjListGraph> nodeAttributeMap;
AttributeMap<PerEdge, AdjListGraph> 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().template attach<int>(name);
}
auto attachEdgeIntAttribute(const std::string &name) {
edgeAttributes().theGraph = this;
return edgeAttributes().template attach<int>(name);
}
auto attachNodeDoubleAttribute(const std::string &name) {
nodeAttributes().theGraph = this;
return nodeAttributes().template attach<double>(name);
}
auto attachEdgeDoubleAttribute(const std::string &name) {
edgeAttributes().theGraph = this;
return edgeAttributes().template attach<double>(name);
}
auto attachNodeStringAttribute(const std::string &name) {
nodeAttributes().theGraph = this;
return nodeAttributes().template attach<std::string>(name);
}
auto attachEdgeStringAttribute(const std::string &name) {
edgeAttributes().theGraph = this;
return edgeAttributes().template attach<std::string>(name);
}
auto getNodeIntAttribute(const std::string &name) {
nodeAttributes().theGraph = this;
return nodeAttributes().template get<int>(name);
}
auto getEdgeIntAttribute(const std::string &name) {
edgeAttributes().theGraph = this;
return edgeAttributes().template get<int>(name);
}
auto getNodeDoubleAttribute(const std::string &name) {
nodeAttributes().theGraph = this;
return nodeAttributes().template get<double>(name);
}
auto getEdgeDoubleAttribute(const std::string &name) {
edgeAttributes().theGraph = this;
return edgeAttributes().template get<double>(name);
}
auto getNodeStringAttribute(const std::string &name) {
nodeAttributes().theGraph = this;
return nodeAttributes().template get<std::string>(name);
}
auto getEdgeStringAttribute(const std::string &name) {
edgeAttributes().theGraph = this;
return edgeAttributes().template 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, AdjListGraph, int, false>;
using NodeDoubleAttribute = Attribute<PerNode, AdjListGraph, double, false>;
using NodeStringAttribute = Attribute<PerNode, AdjListGraph, std::string, false>;
using EdgeIntAttribute = Attribute<PerEdge, AdjListGraph, int, false>;
using EdgeDoubleAttribute = Attribute<PerEdge, AdjListGraph, double, false>;
using EdgeStringAttribute = Attribute<PerEdge, AdjListGraph, std::string, false>;
private:
static constexpr EdgeWeightT defaultEdgeWeightT = EdgeWeightT{1};
index indexInInEdgeArray(NodeT v, NodeT u) const;
index indexInOutEdgeArray(NodeT u, NodeT v) const;
EdgeWeightT computeWeightedDegree(NodeT u, bool inDegree = false,
bool countSelfLoopsTwice = false) const;
template <bool hasWeights>
inline EdgeWeightT getOutEdgeWeight(NodeT u, index i) const {
if constexpr (hasWeights)
return outEdgeWeights[u][i];
else
return defaultEdgeWeightT;
}
template <bool hasWeights>
inline EdgeWeightT getInEdgeWeight(NodeT u, index i) const {
if constexpr (hasWeights)
return inEdgeWeights[u][i];
else
return defaultEdgeWeightT;
}
template <bool graphHasEdgeIds>
inline edgeid getOutEdgeId(NodeT u, index i) const {
if constexpr (graphHasEdgeIds)
return outEdgeIds[u][i];
else
return nullEdgeId;
}
template <bool graphHasEdgeIds>
inline edgeid getInEdgeId(NodeT u, index i) const {
if constexpr (graphHasEdgeIds)
return inEdgeIds[u][i];
else
return nullEdgeId;
}
template <bool graphIsDirected>
inline bool useEdgeInIteration(NodeT u, NodeT v) const {
if constexpr (graphIsDirected)
return true;
else
return u >= v;
}
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
inline void forOutEdgesOfImpl(NodeT u, L handle) const;
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
inline void forInEdgesOfImpl(NodeT 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;
/* Compile-time callable dispatcher.
*
* Aux::FunctionTraits lets us inspect a callable's arity and parameter types
* so we can invoke it with the best matching edge callback signature.
* SafeArg prevents out-of-bounds access to Traits::arg<N> by returning void
* when the callable has fewer than N + 1 parameters.
* ArgType normalizes the inspected type with std::decay_t so comparisons work
* for references, const qualifiers, and other call-compatible forms.
*
* The overload selection below is ordered from most specific to least specific.
* This matters because several lambda signatures overlap, especially when node
* and EdgeWeightT are the same type.
*
* If no branch matches, the static_assert produces a clear compile-time error
* instead of a long substitution failure.
*/
// Return void when the callable does not have an Nth parameter.
template <typename TraitsT, size_t N, bool InRange = (N < TraitsT::arity)>
struct SafeArg {
using type = void;
};
// Enable this specialization only when N is in range.
template <typename TraitsT, size_t N>
struct SafeArg<TraitsT, N, true> {
using type = typename TraitsT::template arg<N>::type;
};
template <typename F, size_t N>
using ArgType = std::decay_t<typename SafeArg<Aux::FunctionTraits<F>, N>::type>;
template <class F>
decltype(auto) edgeLambda(F &f, NodeT u, NodeT v, EdgeWeightT ew, edgeid id) const {
using Traits = Aux::FunctionTraits<F>;
constexpr size_t arity = Traits::arity;
// Most specific signatures first to avoid ambiguity between overlapping
// callable shapes and implicit conversions.
if constexpr (arity >= 3 && std::is_same_v<ArgType<F, 2>, EdgeWeightT>
&& std::is_same_v<ArgType<F, 3>, edgeid>) {
return f(u, v, ew, id);
} else if constexpr (arity >= 2 && std::is_same_v<ArgType<F, 2>, edgeid>
&& std::is_same_v<ArgType<F, 1>, NodeT>) {
return f(u, v, id);
} else if constexpr (arity >= 2 && std::is_same_v<ArgType<F, 2>, EdgeWeightT>) {
return f(u, v, ew);
} else if constexpr (arity >= 1 && std::is_same_v<ArgType<F, 1>, EdgeWeightT>
&& !std::is_same_v<NodeT, EdgeWeightT>) {
// Treat this as a weight-taking callback only when node ids and weights
// are distinct types.
return f(v, ew);
} else if constexpr (arity >= 1 && std::is_same_v<ArgType<F, 1>, NodeT>) {
return f(u, v);
} else if constexpr (arity >= 1 && std::is_same_v<ArgType<F, 1>, EdgeWeightT>) {
return f(v, ew);
} else if constexpr (arity >= 1 && std::is_same_v<ArgType<F, 0>, NodeT>) {
return f(v);
} else {
static_assert(!std::is_same_v<F, F>,
"Your lambda does not support the required parameters or the parameters "
"have the wrong type.");
}
}
template <class F>
auto callBFSHandle(F &f, NodeT u, count dist) const -> decltype(f(u, dist)) {
return f(u, dist);
}
template <class F>
auto callBFSHandle(F &f, NodeT u, count) const -> decltype(f(u)) {
return f(u);
}
public:
// For support of API: NetworKit::AdjListGraph::NodeIterator
using NodeIterator = NodeIteratorBase<AdjListGraph, NodeT, EdgeWeightT>;
// For support of API: NetworKit::AdjListGraph::NodeRange
using NodeRange = NodeRangeBase<AdjListGraph, NodeT, EdgeWeightT>;
// For support of API: NetworKit::AdjListGraph:EdgeIterator
using EdgeIterator = EdgeWeightTIterator<AdjListGraph, NodeT, EdgeWeightT, EdgeT<NodeT>>;
// For support of API: NetworKit::AdjListGraph:EdgeWeightIterator
using EdgeWeightIterator =
EdgeWeightTIterator<AdjListGraph, NodeT, EdgeWeightT, WeightedEdgeT<NodeT, EdgeWeightT>>;
// For support of API: NetworKit::AdjListGraph:EdgeRange
using EdgeRange = EdgeWeightTRange<AdjListGraph, NodeT, EdgeWeightT, EdgeT<NodeT>>;
// For support of API: NetworKit::AdjListGraph:EdgeWeightRange
using EdgeWeightRange =
EdgeWeightTRange<AdjListGraph, NodeT, EdgeWeightT, WeightedEdgeT<NodeT, EdgeWeightT>>;
// For support of API: NetworKit::AdjListGraph::NeighborIterator;
using NeighborIterator = NeighborIteratorBase<std::vector<NodeT>>;
// For support of API: NetworKit::AdjListGraph::NeighborIterator;
using NeighborWeightIterator =
NeighborWeightIteratorBase<std::vector<NodeT>, std::vector<EdgeWeightT>>;
template <bool InEdges = false>
class NeighborRange {
const AdjListGraph *G;
NodeT u{nullNodeId};
public:
NeighborRange(const AdjListGraph &G, NodeT 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 AdjListGraph *G;
NodeT u{nullNodeId};
public:
NeighborWeightRange(const AdjListGraph &G, NodeT 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>;
AdjListGraph(count n = 0, bool weighted = false, bool directed = false,
bool edgesIndexed = false);
template <class EdgeMerger = std::plus<EdgeWeightT>>
AdjListGraph(const AdjListGraph &G, bool weighted, bool directed, bool edgesIndexed = false,
EdgeMerger edgeMerger = std::plus<EdgeWeightT>())
: 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 defaultEdgeWeightT for all edges
if (directed) {
inEdgeWeights.resize(z);
for (NodeT u = 0; u < z; ++u) {
inEdgeWeights[u].resize(G.inEdges[u].size(), defaultEdgeWeightT);
}
}
outEdgeWeights.resize(z);
for (NodeT u = 0; u < z; ++u) {
outEdgeWeights[u].resize(outEdges[u].size(), defaultEdgeWeightT);
}
}
}
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([&](NodeT 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(), defaultEdgeWeightT);
}
}
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([&](NodeT 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) {
NodeT 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(defaultEdgeWeightT, defaultEdgeWeightT);
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]
: defaultEdgeWeightT);
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
// defaultEdgeWeightT
inEdgeWeights.resize(z);
for (NodeT u = 0; u < z; ++u) {
inEdgeWeights[u].resize(inEdges[u].size(), defaultEdgeWeightT);
}
outEdgeWeights.resize(z);
for (NodeT u = 0; u < z; ++u) {
outEdgeWeights[u].resize(outEdges[u].size(), defaultEdgeWeightT);
}
}
}
if (G.hasEdgeIds() && edgesIndexed) {
inEdgeIds = G.outEdgeIds;
outEdgeIds = G.outEdgeIds;
}
}
if (!G.edgesIndexed && edgesIndexed)
indexEdges();
}
AdjListGraph(std::initializer_list<WeightedEdgeT<NodeT, EdgeWeightT>> edges);
AdjListGraph(const AdjListGraph &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), deletedID(other.deletedID),
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) {};
AdjListGraph(AdjListGraph &&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), deletedID(other.deletedID),
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;
};
~AdjListGraph() = default;
AdjListGraph &operator=(AdjListGraph &&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);
std::swap(deletedID, other.deletedID);
// 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;
};
AdjListGraph &operator=(const AdjListGraph &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;
deletedID = other.deletedID;
// call special constructors to copy attribute maps
nodeAttributeMap = AttributeMap(other.nodeAttributeMap, this);
edgeAttributeMap = AttributeMap(other.edgeAttributeMap, this);
return *this;
};
static AdjListGraph fromCSR(std::span<const index> rowIdxView,
std::span<const index> columnIdxView,
std::span<const double> nonZerosView, bool directed = true,
bool isWeighted = false);
static AdjListGraph _fromCSRRaw(const index *rowIdxPtr, std::size_t rowIdxSize,
const index *columnIdxPtr, std::size_t columnIdxSize,
const double *nonZerosPtr, std::size_t nonZerosSize,
bool directed = true, bool isWeighted = false);
void preallocateUndirected(NodeT u, size_t size);
void preallocateDirected(NodeT u, size_t outSize, size_t inSize);
void preallocateDirectedOutEdges(NodeT u, size_t outSize);
void preallocateDirectedInEdges(NodeT u, size_t inSize);
void indexEdges(bool force = false);
bool hasEdgeIds() const noexcept { return edgesIndexed; }
edgeid edgeId(NodeT u, NodeT v) const;
std::pair<NodeT, NodeT> edgeById(index id) const {
std::pair<NodeT, NodeT> result{nullNodeId, nullNodeId};
bool found = false;
forNodesWhile([&] { return !found; },
[&](NodeT u) {
forNeighborsOf(u, [&](NodeT 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());
template <typename Lambda>
void sortNeighbors(NodeT u, Lambda lambda);
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 */
NodeT addNode();
NodeT addNodes(count numberOfNewNodes);
void removeNode(NodeT v);
void removePartialOutEdges(Unsafe, NodeT u) {
assert(hasNode(u));
outEdges[u].clear();
if (isWeighted()) {
outEdgeWeights[u].clear();
}
if (hasEdgeIds()) {
outEdgeIds[u].clear();
}
}
void removePartialInEdges(Unsafe, NodeT u) {
assert(hasNode(u));
inEdges[u].clear();
if (isWeighted()) {
inEdgeWeights[u].clear();
}
if (hasEdgeIds()) {
inEdgeIds[u].clear();
}
}
bool hasNode(NodeT v) const noexcept { return (v < z) && this->exists[v]; }
void restoreNode(NodeT v);
count degree(NodeT v) const {
assert(hasNode(v));
return outEdges[v].size();
}
count degreeIn(NodeT v) const {
assert(hasNode(v));
return directed ? inEdges[v].size() : outEdges[v].size();
}
count degreeOut(NodeT v) const { return degree(v); }
bool isIsolated(NodeT v) const {
if (!exists[v])
throw std::runtime_error("Error, the node does not exist!");
return outEdges[v].empty() && (!directed || inEdges[v].empty());
}
EdgeWeightT weightedDegree(NodeT u, bool countSelfLoopsTwice = false) const;
EdgeWeightT weightedDegreeIn(NodeT u, bool countSelfLoopsTwice = false) const;
/* EDGE MODIFIERS */
bool addEdge(NodeT u, NodeT v, EdgeWeightT ew = defaultEdgeWeightT,
bool checkMultiEdge = false);
bool addPartialEdge(Unsafe, NodeT u, NodeT v, EdgeWeightT ew = defaultEdgeWeightT,
uint64_t index = 0, bool checkForMultiEdges = false);
bool addPartialInEdge(Unsafe, NodeT u, NodeT v, EdgeWeightT ew = defaultEdgeWeightT,
uint64_t index = 0, bool checkForMultiEdges = false);
bool addPartialOutEdge(Unsafe, NodeT u, NodeT v, EdgeWeightT ew = defaultEdgeWeightT,
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(NodeT u, NodeT v);
void removeAllEdges();
template <typename Condition>
std::pair<count, count> removeAdjacentEdges(NodeT u, Condition condition, bool edgesIn = false);
void removeSelfLoops();
void removeMultiEdges();
void swapEdge(NodeT s1, NodeT t1, NodeT s2, NodeT t2);
bool hasEdge(NodeT u, NodeT 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; }
NodeT 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;
}
EdgeWeightT weight(NodeT u, NodeT v) const;
void setWeight(NodeT u, NodeT v, EdgeWeightT ew);
void setWeightAtIthNeighbor(Unsafe, NodeT u, index i, EdgeWeightT ew);
void setWeightAtIthInNeighbor(Unsafe, NodeT u, index i, EdgeWeightT ew);
void increaseWeight(NodeT u, NodeT v, EdgeWeightT ew);
/* SUMS */
EdgeWeightT totalEdgeWeight() const noexcept;
NodeT getIthNeighbor(Unsafe, NodeT u, index i) const { return outEdges[u][i]; }
EdgeWeightT getIthNeighborWeight(Unsafe, NodeT u, index i) const {
return isWeighted() ? outEdgeWeights[u][i] : defaultEdgeWeightT;
}
NodeRange nodeRange() const noexcept { return NodeRange(*this); }
EdgeRange edgeRange() const noexcept { return EdgeRange(*this); }
EdgeWeightRange edgeWeightRange() const noexcept { return EdgeWeightRange(*this); }
NeighborRange<false> neighborRange(NodeT u) const {
assert(exists[u]);
return NeighborRange<false>(*this, u);
}
NeighborWeightRange<false> weightNeighborRange(NodeT u) const {
assert(isWeighted());
assert(exists[u]);
return NeighborWeightRange<false>(*this, u);
}
NeighborRange<true> inNeighborRange(NodeT u) const {
assert(isDirected());
assert(exists[u]);
return NeighborRange<true>(*this, u);
}
NeighborWeightRange<true> weightInNeighborRange(NodeT u) const {
assert(isDirected() && isWeighted());
assert(exists[u]);
return NeighborWeightRange<true>(*this, u);
}
index indexOfNeighbor(NodeT u, NodeT v) const { return indexInOutEdgeArray(u, v); }
NodeT getIthNeighbor(NodeT u, index i) const {
if (!hasNode(u) || i >= outEdges[u].size())
return nullNodeId;
return outEdges[u][i];
}
NodeT getIthInNeighbor(NodeT u, index i) const {
if (!hasNode(u) || i >= inEdges[u].size())
return nullNodeId;
return inEdges[u][i];
}
EdgeWeightT getIthNeighborWeight(NodeT u, index i) const {
if (!hasNode(u) || i >= outEdges[u].size())
return nullWeight;
return isWeighted() ? outEdgeWeights[u][i] : defaultEdgeWeightT;
}
std::pair<NodeT, EdgeWeightT> getIthNeighborWithWeight(NodeT u, index i) const {
if (!hasNode(u) || i >= outEdges[u].size())
return {nullNodeId, EdgeWeightT{0}};
return getIthNeighborWithWeight(unsafe, u, i);
}
std::pair<NodeT, EdgeWeightT> getIthNeighborWithWeight(Unsafe, NodeT u, index i) const {
if (!isWeighted())
return {outEdges[u][i], defaultEdgeWeightT};
return {outEdges[u][i], outEdgeWeights[u][i]};
}
std::pair<NodeT, edgeid> getIthNeighborWithId(NodeT u, index i) const {
assert(hasEdgeIds());
if (!hasNode(u) || i >= outEdges[u].size())
return {nullNodeId, nullEdgeId};
return {outEdges[u][i], outEdgeIds[u][i]};
}
/* NODE ITERATORS */
template <typename L>
void forNodes(L handle) const; // NOLINT(performance-unnecessary-value-param)
template <typename L>
void parallelForNodes(L handle) const; // NOLINT(performance-unnecessary-value-param)
template <typename C, typename L>
void forNodesWhile(C condition, L handle) const; // NOLINT(performance-unnecessary-value-param)
template <typename L>
void forNodesInRandomOrder(L handle) const; // NOLINT(performance-unnecessary-value-param)
template <typename L>
void balancedParallelForNodes(L handle) const; // NOLINT(performance-unnecessary-value-param)
template <typename L>
void forNodePairs(L handle) const; // NOLINT(performance-unnecessary-value-param)
template <typename L>
void parallelForNodePairs(L handle) const; // NOLINT(performance-unnecessary-value-param)
/* 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(NodeT u, L handle) const;
template <typename L>
void forEdgesOf(NodeT u, L handle) const;
template <typename L>
void forInNeighborsOf(NodeT u, L handle) const;
template <typename L>
void forInEdgesOf(NodeT u, L handle) const;
/* REDUCTION ITERATORS */
template <typename L>
double parallelSumForNodes(L handle) const; // NOLINT(performance-unnecessary-value-param)
template <typename L>
double parallelSumForEdges(L handle) const;
};
using Graph = AdjListGraph<node, edgeweight>;
} /* namespace NetworKit */
#include <networkit/graph/AdjListGraphImpl.hpp>
#endif // NETWORKIT_GRAPH_ADJ_LIST_GRAPH_HPP_