↰ 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 <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:
// base class for all node (and edge) attribute
// storages with attribute type info
// independent of the attribute type, holds bookkeeping info only:
// - attribute name
// - type info of derived (real storage holding) classes
// - which indices are valid
// - number of valid indices
// - the associated graph (who knows, which nodes/edges exist)
// - the validity of the whole storage (initially true, false after detach)
// all indexed accesses by NetworKit::index: synonym both for node and edgeid
class PerNode {
public:
static constexpr bool edges = false;
};
class PerEdge {
public:
static constexpr bool edges = true;
};
template <typename NodeOrEdge>
class AttributeStorageBase { // alias ASB
public:
AttributeStorageBase(const Graph *graph, std::string name, std::type_index type)
: name{std::move(name)}, type{type}, theGraph{graph}, validStorage{true} {
checkPremise(); // node for PerNode, theGraph.hasEdgeIds() for PerEdges
}
void invalidateStorage() { validStorage = false; }
const std::string &getName() const noexcept { return name; }
std::type_index getType() const noexcept { return type; }
bool isValid(index n) const noexcept { return n < valid.size() && valid[n]; }
// Called by Graph when node/edgeid n is deleted.
void invalidate(index n) {
if (isValid(n)) {
valid[n] = false;
--validElements;
}
}
protected:
void markValid(index n) {
indexOK(n); // specialized for node/edgeid
if (n >= valid.size())
valid.resize(n + 1);
if (!valid[n]) {
valid[n] = true;
++validElements;
}
}
void checkIndex(index n) const {
indexOK(n);
if (!isValid(n)) {
throw std::runtime_error("Invalid attribute value");
}
}
private:
std::string name;
std::type_index type;
std::vector<bool> valid; // For each node/edgeid: whether attribute is set or not.
protected:
void indexOK(index n) const;
void checkPremise() const;
index validElements = 0;
const Graph *theGraph;
bool validStorage; // Validity of the whole storage
}; // class AttributeStorageBase
template <typename NodeOrEdge>
using ASB = AttributeStorageBase<NodeOrEdge>;
template <typename NodeOrEdge, typename T, bool isConst>
class Attribute;
template <typename NodeOrEdge, template <typename> class Base, typename T>
class AttributeStorage : public Base<NodeOrEdge> {
public:
AttributeStorage(const Graph *theGraph, std::string name)
: Base<NodeOrEdge>{theGraph, std::move(name), typeid(T)} {}
void resize(index i) {
if (i >= values.size())
values.resize(i + 1);
}
auto size() const noexcept { return this->validElements; }
void set(index i, T &&v) {
this->markValid(i);
resize(i);
values[i] = std::move(v);
}
// instead of returning an std::optional (C++17) we provide these
// C++14 options
// (1) throw an exception when invalid:
T get(index i) const { // may throw
this->checkIndex(i);
return values[i];
}
// (2) give default value when invalid:
T get(index i, T defaultT) const noexcept {
if (i >= values.size() || !this->isValid(i))
return defaultT;
return values[i];
}
friend Attribute<NodeOrEdge, T, true>;
friend Attribute<NodeOrEdge, T, false>;
private:
using Base<NodeOrEdge>::theGraph;
std::vector<T> values; // the real attribute storage
}; // class AttributeStorage<NodeOrEdge, Base, T>
template <typename NodeOrEdge, typename T, bool isConst>
class Attribute {
public:
using AttributeStorage_type =
std::conditional_t<isConst, const AttributeStorage<NodeOrEdge, ASB, T>,
AttributeStorage<NodeOrEdge, ASB, T>>;
class Iterator {
public:
// The value type of the attribute. Returned by
// operator*().
using value_type = T;
// Reference to the value_type, required by STL.
using reference = std::conditional_t<isConst, const value_type &, value_type &>;
// Pointer to the value_type, required by STL.
using pointer = std::conditional_t<isConst, const value_type *, value_type *>;
// STL iterator category.
using iterator_category = std::forward_iterator_tag;
// Signed integer type of the result of subtracting two pointers,
// required by STL.
using difference_type = ptrdiff_t;
Iterator() : storage{nullptr}, idx{0} {}
Iterator(AttributeStorage_type *storage) : storage{storage}, idx{0} {
if (storage) {
nextValid();
}
}
Iterator &nextValid() {
while (storage && !storage->isValid(idx)) {
if (idx >= storage->values.size()) {
storage = nullptr;
return *this;
}
++idx;
}
return *this;
}
Iterator &operator++() {
if (!storage) {
throw std::runtime_error("Invalid attribute iterator");
}
++idx;
return nextValid();
}
auto operator*() const {
if (!storage) {
throw std::runtime_error("Invalid attribute iterator");
}
return std::make_pair(idx, storage->values[idx]);
}
bool operator==(Iterator const &iter) const noexcept {
if (storage == nullptr && iter.storage == nullptr) {
return true;
}
return storage == iter.storage && idx == iter.idx;
}
bool operator!=(Iterator const &iter) const noexcept { return !(*this == iter); }
private:
AttributeStorage_type *storage;
index idx;
}; // class Iterator
private:
class IndexProxy {
// a helper class for distinguished read and write on an indexed
// attribute
// operator[] on an attribute yields an IndexProxy holding
// location and index of access
// - casting an IndexProxy to the attribute type reads the value
// - assigning to it (operator=) writes the value
public:
IndexProxy(AttributeStorage_type *storage, index idx) : storage{storage}, idx{idx} {}
// reading at idx
operator T() const {
storage->checkIndex(idx);
return storage->values[idx];
}
// writing at idx
template <bool ic = isConst>
std::enable_if_t<!ic, T> &operator=(T &&other) {
storage->set(idx, std::move(other));
return storage->values[idx];
}
private:
AttributeStorage_type *storage;
index idx;
}; // class IndexProxy
public:
explicit Attribute(std::shared_ptr<AttributeStorage_type> ownedStorage = nullptr)
: ownedStorage{ownedStorage}, valid{ownedStorage != nullptr} {}
Attribute(Attribute const &other) : ownedStorage{other.ownedStorage}, valid{other.valid} {}
template <bool ic = isConst, std::enable_if_t<ic, int> = 0>
Attribute(Attribute<NodeOrEdge, T, false> const &other)
: ownedStorage{other.ownedStorage}, valid{other.valid} {}
Attribute &operator=(Attribute other) {
this->swap(other);
return *this;
}
void swap(Attribute &other) {
std::swap(ownedStorage, other.ownedStorage);
std::swap(valid, other.valid);
}
Attribute(Attribute &&other) noexcept
: ownedStorage{std::move(other.ownedStorage)}, valid{other.valid} {
other.valid = false;
}
template <bool ic = isConst, std::enable_if_t<ic, int> = 0>
Attribute(Attribute<NodeOrEdge, T, false> &&other) noexcept
: ownedStorage{std::move(other.ownedStorage)}, valid{other.valid} {
other.valid = false;
}
auto begin() const {
checkAttribute();
return Iterator(ownedStorage.get()).nextValid();
}
auto end() const { return Iterator(nullptr); }
auto size() const noexcept { return ownedStorage->size(); }
template <bool ic = isConst>
std::enable_if_t<!ic> set(index i, T v) {
checkAttribute();
ownedStorage->set(i, std::move(v));
}
template <bool ic = isConst>
std::enable_if_t<!ic> set2(node u, node v, T t) {
static_assert(NodeOrEdge::edges, "attribute(u,v) for edges only");
set(ownedStorage->theGraph->edgeId(u, v), t);
}
auto get(index i) const {
checkAttribute();
return ownedStorage->get(i);
}
auto get2(node u, node v) const {
static_assert(NodeOrEdge::edges, "attribute(u,v) for edges only");
return get(ownedStorage->theGraph->edgeId(u, v));
}
auto get(index i, T defaultT) const {
checkAttribute();
return ownedStorage->get(i, defaultT);
}
auto get2(node u, node v, T defaultT) const {
static_assert(NodeOrEdge::edges, "attribute(u,v) for edges only");
return get(ownedStorage->theGraph->edgeId(u, v), defaultT);
}
IndexProxy operator[](index i) const {
checkAttribute();
return IndexProxy(ownedStorage.get(), i);
}
IndexProxy operator()(node u, node v) const {
static_assert(NodeOrEdge::edges, "attribute(u,v) for edges only");
checkAttribute();
return IndexProxy(ownedStorage.get(), ownedStorage->theGraph->edgeId(u, v));
}
void checkAttribute() const {
if (!ownedStorage->validStorage)
throw std::runtime_error("Invalid attribute");
}
auto getName() const {
checkAttribute();
return ownedStorage->getName();
}
void write(std::string const &filename) const {
std::ofstream out(filename);
if (!out)
ERROR("cannot open ", filename, " for writing");
for (auto it = begin(); it != end(); ++it) {
auto pair = *it;
auto n = pair.first; // node/edgeid
auto v = pair.second; // value
out << n << "\t" << v << "\n";
}
out.close();
}
template <bool ic = isConst>
std::enable_if_t<!ic> read(const std::string &filename) {
std::ifstream in(filename);
if (!in) {
ERROR("cannot open ", filename, " for reading");
}
index n; // node/edgeid
T v; // value
std::string line;
while (std::getline(in, line)) {
std::istringstream istring(line);
istring >> n >> v;
set(n, v);
}
}
private:
std::shared_ptr<AttributeStorage_type> ownedStorage;
bool valid;
}; // class Attribute
template <typename NodeOrEdge>
class AttributeMap {
friend Graph;
const Graph *theGraph;
public:
std::unordered_map<std::string, std::shared_ptr<ASB<NodeOrEdge>>> attrMap;
AttributeMap(const Graph *g) : theGraph{g} {}
auto find(std::string const &name) {
auto it = attrMap.find(name);
if (it == attrMap.end()) {
throw std::runtime_error("No such attribute");
}
return it;
}
auto find(std::string const &name) const {
auto it = attrMap.find(name);
if (it == attrMap.end()) {
throw std::runtime_error("No such attribute");
}
return it;
}
template <typename T>
auto attach(const std::string &name) {
auto ownedPtr =
std::make_shared<AttributeStorage<NodeOrEdge, ASB, T>>(theGraph, std::string{name});
auto insertResult = attrMap.emplace(ownedPtr->getName(), ownedPtr);
auto success = insertResult.second;
if (!success) {
throw std::runtime_error("Attribute with same name already exists");
}
return Attribute<NodeOrEdge, T, false>{ownedPtr};
}
void detach(const std::string &name) {
auto it = find(name);
auto storage = it->second.get();
storage->invalidateStorage();
it->second.reset();
attrMap.erase(name);
}
template <typename T>
auto get(const std::string &name) {
auto it = find(name);
if (it->second.get()->getType() != typeid(T))
throw std::runtime_error("Type mismatch in Attributes().get()");
return Attribute<NodeOrEdge, T, false>{
std::static_pointer_cast<AttributeStorage<NodeOrEdge, ASB, T>>(it->second)};
}
template <typename T>
auto get(const std::string &name) const {
auto it = find(name);
if (it->second.get()->getType() != typeid(T))
throw std::runtime_error("Type mismatch in Attributes().get()");
return Attribute<NodeOrEdge, T, true>{
std::static_pointer_cast<const AttributeStorage<NodeOrEdge, ASB, T>>(it->second)};
}
}; // class AttributeMap
AttributeMap<PerNode> nodeAttributeMap;
AttributeMap<PerEdge> 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, int, false>;
using NodeDoubleAttribute = Attribute<PerNode, double, false>;
using NodeStringAttribute = Attribute<PerNode, std::string, false>;
using EdgeIntAttribute = Attribute<PerEdge, int, false>;
using EdgeDoubleAttribute = Attribute<PerEdge, double, false>;
using EdgeStringAttribute = Attribute<PerEdge, 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:
class NodeIterator {
const Graph *G;
node u;
public:
// The value type of the nodes (i.e. nodes). Returned by
// operator*().
using value_type = node;
// Reference to the value_type, required by STL.
using reference = value_type &;
// Pointer to the value_type, required by STL.
using pointer = value_type *;
// STL iterator category.
using iterator_category = std::forward_iterator_tag;
// Signed integer type of the result of subtracting two pointers,
// required by STL.
using difference_type = ptrdiff_t;
// Own type.
using self = NodeIterator;
NodeIterator(const Graph *G, node u) : G(G), u(u) {
if (!G->hasNode(u) && u < G->upperNodeIdBound()) {
++(*this);
}
}
NodeIterator() : G(nullptr) {}
~NodeIterator() = default;
NodeIterator &operator++() {
assert(u < G->upperNodeIdBound());
do {
++u;
} while (!(G->hasNode(u) || u >= G->upperNodeIdBound()));
return *this;
}
NodeIterator operator++(int) {
const auto tmp = *this;
++(*this);
return tmp;
}
NodeIterator operator--() {
assert(u);
do {
--u;
} while (!G->hasNode(u));
return *this;
}
NodeIterator operator--(int) {
const auto tmp = *this;
--(*this);
return tmp;
}
bool operator==(const NodeIterator &rhs) const noexcept { return u == rhs.u; }
bool operator!=(const NodeIterator &rhs) const noexcept { return !(*this == rhs); }
node operator*() const noexcept {
assert(u < G->upperNodeIdBound());
return u;
}
};
class NodeRange {
const Graph *G;
public:
NodeRange(const Graph &G) : G(&G) {}
NodeRange() : G(nullptr) {};
~NodeRange() = default;
NodeIterator begin() const noexcept {
assert(G);
return NodeIterator(G, node{0});
}
NodeIterator end() const noexcept {
assert(G);
return NodeIterator(G, G->upperNodeIdBound());
}
};
// Necessary for friendship with EdgeIteratorBase.
class EdgeIterator;
class EdgeWeightIterator;
class EdgeIteratorBase {
friend class EdgeIterator;
friend class EdgeWeightIterator;
const Graph *G;
NodeIterator nodeIter;
index i;
bool validEdge() const noexcept {
return G->isDirected() || (*nodeIter <= G->outEdges[*nodeIter][i]);
}
void nextEdge() {
do {
if (++i >= G->degree(*nodeIter)) {
i = 0;
do {
assert(nodeIter != G->nodeRange().end());
++nodeIter;
if (nodeIter == G->nodeRange().end()) {
return;
}
} while (!G->degree(*nodeIter));
}
} while (!validEdge());
}
void prevEdge() {
do {
if (!i) {
do {
assert(nodeIter != G->nodeRange().begin());
--nodeIter;
} while (!G->degree(*nodeIter));
i = G->degree(*nodeIter);
}
--i;
} while (!validEdge());
}
EdgeIteratorBase(const Graph *G, NodeIterator nodeIter)
: G(G), nodeIter(nodeIter), i(index{0}) {
if (nodeIter != G->nodeRange().end() && !G->degree(*nodeIter)) {
nextEdge();
}
}
EdgeIteratorBase() : G(nullptr) {}
virtual ~EdgeIteratorBase() = default;
bool operator==(const EdgeIteratorBase &rhs) const noexcept {
return nodeIter == rhs.nodeIter && i == rhs.i;
}
bool operator!=(const EdgeIteratorBase &rhs) const noexcept { return !(*this == rhs); }
};
class EdgeIterator : public EdgeIteratorBase {
public:
// The value type of the edges (i.e. a pair). Returned by operator*().
using value_type = Edge;
// Reference to the value_type, required by STL.
using reference = value_type &;
// Pointer to the value_type, required by STL.
using pointer = value_type *;
// STL iterator category.
using iterator_category = std::forward_iterator_tag;
// Signed integer type of the result of subtracting two pointers,
// required by STL.
using difference_type = ptrdiff_t;
// Own type.
using self = EdgeIterator;
EdgeIterator(const Graph *G, NodeIterator nodeIter) : EdgeIteratorBase(G, nodeIter) {}
EdgeIterator() : EdgeIteratorBase() {}
bool operator==(const EdgeIterator &rhs) const noexcept {
return this->EdgeIteratorBase::operator==(static_cast<EdgeIteratorBase>(rhs));
}
bool operator!=(const EdgeIterator &rhs) const noexcept { return !(*this == rhs); }
Edge operator*() const noexcept {
assert(nodeIter != G->nodeRange().end());
return Edge(*nodeIter, G->outEdges[*nodeIter][i]);
}
EdgeIterator &operator++() {
nextEdge();
return *this;
}
EdgeIterator operator++(int) {
const auto tmp = *this;
++(*this);
return tmp;
}
EdgeIterator operator--() {
prevEdge();
return *this;
}
EdgeIterator operator--(int) {
const auto tmp = *this;
--(*this);
return tmp;
}
};
class EdgeWeightIterator : public EdgeIteratorBase {
public:
// The value type of the edges and their weights (i.e. WeightedEdge). Returned by
// operator*().
using value_type = WeightedEdge;
// Reference to the value_type, required by STL.
using reference = value_type &;
// Pointer to the value_type, required by STL.
using pointer = value_type *;
// STL iterator category.
using iterator_category = std::forward_iterator_tag;
// Signed integer type of the result of subtracting two pointers,
// required by STL.
using difference_type = ptrdiff_t;
// Own type.
using self = EdgeWeightIterator;
EdgeWeightIterator(const Graph *G, NodeIterator nodeIter) : EdgeIteratorBase(G, nodeIter) {}
EdgeWeightIterator() : EdgeIteratorBase() {}
bool operator==(const EdgeWeightIterator &rhs) const noexcept {
return this->EdgeIteratorBase::operator==(static_cast<EdgeIteratorBase>(rhs));
}
bool operator!=(const EdgeWeightIterator &rhs) const noexcept { return !(*this == rhs); }
EdgeWeightIterator &operator++() {
nextEdge();
return *this;
}
EdgeWeightIterator operator++(int) {
const auto tmp = *this;
++(*this);
return tmp;
}
EdgeWeightIterator operator--() {
prevEdge();
return *this;
}
EdgeWeightIterator operator--(int) {
const auto tmp = *this;
--(*this);
return tmp;
}
WeightedEdge operator*() const noexcept {
assert(nodeIter != G->nodeRange().end());
return WeightedEdge(*nodeIter, G->outEdges[*nodeIter][i],
G->isWeighted() ? G->outEdgeWeights[*nodeIter][i] : 1);
}
};
class EdgeRange {
const Graph *G;
public:
EdgeRange(const Graph &G) : G(&G) {}
EdgeRange() : G(nullptr) {};
~EdgeRange() = default;
EdgeIterator begin() const {
assert(G);
return EdgeIterator(G, G->nodeRange().begin());
}
EdgeIterator end() const {
assert(G);
return EdgeIterator(G, G->nodeRange().end());
}
};
class EdgeWeightRange {
const Graph *G;
public:
EdgeWeightRange(const Graph &G) : G(&G) {}
EdgeWeightRange() : G(nullptr) {};
~EdgeWeightRange() = default;
EdgeWeightIterator begin() const {
assert(G);
return EdgeWeightIterator(G, G->nodeRange().begin());
}
EdgeWeightIterator end() const {
assert(G);
return EdgeWeightIterator(G, G->nodeRange().end());
}
};
class NeighborIterator {
std::vector<node>::const_iterator nIter;
public:
// The value type of the neighbors (i.e. nodes). Returned by
// operator*().
using value_type = node;
// Reference to the value_type, required by STL.
using reference = value_type &;
// Pointer to the value_type, required by STL.
using pointer = value_type *;
// STL iterator category.
using iterator_category = std::forward_iterator_tag;
// Signed integer type of the result of subtracting two pointers,
// required by STL.
using difference_type = ptrdiff_t;
// Own type.
using self = NeighborIterator;
NeighborIterator(std::vector<node>::const_iterator nodesIter) : nIter(nodesIter) {}
NeighborIterator() {}
NeighborIterator &operator++() {
++nIter;
return *this;
}
NeighborIterator operator++(int) {
const auto tmp = *this;
++nIter;
return tmp;
}
NeighborIterator operator--() {
const auto tmp = *this;
--nIter;
return tmp;
}
NeighborIterator operator--(int) {
--nIter;
return *this;
}
bool operator==(const NeighborIterator &rhs) const { return nIter == rhs.nIter; }
bool operator!=(const NeighborIterator &rhs) const { return !(nIter == rhs.nIter); }
node operator*() const { return *nIter; }
};
class NeighborWeightIterator {
std::vector<node>::const_iterator nIter;
std::vector<edgeweight>::const_iterator wIter;
public:
// The value type of the neighbors (i.e. nodes). Returned by
// operator*().
using value_type = std::pair<node, edgeweight>;
// Reference to the value_type, required by STL.
using reference = value_type &;
// Pointer to the value_type, required by STL.
using pointer = value_type *;
// STL iterator category.
using iterator_category = std::forward_iterator_tag;
// Signed integer type of the result of subtracting two pointers,
// required by STL.
using difference_type = ptrdiff_t;
// Own type.
using self = NeighborWeightIterator;
NeighborWeightIterator(std::vector<node>::const_iterator nodesIter,
std::vector<edgeweight>::const_iterator weightIter)
: nIter(nodesIter), wIter(weightIter) {}
NeighborWeightIterator() {}
NeighborWeightIterator &operator++() {
++nIter;
++wIter;
return *this;
}
NeighborWeightIterator operator++(int) {
const auto tmp = *this;
++(*this);
return tmp;
}
NeighborWeightIterator operator--() {
--nIter;
--wIter;
return *this;
}
NeighborWeightIterator operator--(int) {
const auto tmp = *this;
--(*this);
return tmp;
}
bool operator==(const NeighborWeightIterator &rhs) const {
return nIter == rhs.nIter && wIter == rhs.wIter;
}
bool operator!=(const NeighborWeightIterator &rhs) const { return !(*this == rhs); }
std::pair<node, edgeweight> operator*() const { return std::make_pair(*nIter, *wIter); }
};
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),
// empty node attribute map as last member for this graph
nodeAttributeMap(this), 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;
// 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
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
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) = default;
Graph(Graph &&other) noexcept = default;
~Graph() = default;
Graph &operator=(Graph &&other) noexcept = default;
Graph &operator=(const Graph &other) = default;
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;
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_