↰ Return to documentation for file (include/networkit/graph/DHBGraph.hpp)
#ifndef NETWORKIT_GRAPH_DHB_GRAPH_HPP_
#define NETWORKIT_GRAPH_DHB_GRAPH_HPP_
#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/NodeIterators.hpp>
#include <omp.h>
#include <dhb/dynamic_hashed_blocks.h>
#include <tlx/define/deprecated.hpp>
#include <algorithm>
#include <fstream>
#include <functional>
#include <iostream>
#include <memory>
#include <numeric>
#include <queue>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <thread>
#include <typeindex>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
namespace NetworKit {
class DHBGraph final {
// DHBGraph properties
bool weighted;
bool directed;
// Edge properties
count m;
count storedNumberOfSelfLoops;
edgeid omega;
bool edgesIndexed;
struct EdgeData {
edgeweight weight;
edgeid id;
};
private:
bool addEdge(node u, node v, edgeweight ew, edgeid id, bool do_update = true);
AttributeMap<PerNode, DHBGraph> nodeAttributeMap;
AttributeMap<PerEdge, DHBGraph> edgeAttributeMap;
dhb::Matrix<EdgeData> m_dhb_graph;
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, DHBGraph, int, false>;
using NodeDoubleAttribute = Attribute<PerNode, DHBGraph, double, false>;
using NodeStringAttribute = Attribute<PerNode, DHBGraph, std::string, false>;
using EdgeIntAttribute = Attribute<PerEdge, DHBGraph, int, false>;
using EdgeDoubleAttribute = Attribute<PerEdge, DHBGraph, double, false>;
using EdgeStringAttribute = Attribute<PerEdge, DHBGraph, std::string, false>;
private:
edgeweight computeWeightedDegree(node u, bool inDegree = false,
bool countSelfLoopsTwice = false) const;
bool ithNeighborExists(node u, index i) const {
assert(u < upperNodeIdBound());
return i < m_dhb_graph.neighbors(u).degree();
}
void removePartialOutEdges(Unsafe, node u) {
assert(u < upperNodeIdBound());
m_dhb_graph.neighbors(u).clear();
}
void removePartialInEdges(Unsafe, node v) {
assert(v < upperNodeIdBound());
auto remove_edge = [&](dhb::Vertex const u) {
if (m_dhb_graph.neighbors(u).exists(v)) {
removeEdge(u, v);
}
};
m_dhb_graph.for_nodes(std::move(remove_edge));
}
template <bool graphIsDirected>
inline bool useEdgeInIteration(node u, node v) const;
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
void forOutEdgesOfImpl(node u, L handle) const;
template <bool hasWeights, bool graphHasEdgeIds>
std::tuple<edgeweight, edgeid> getDHBEdgeData(node u, node v) const;
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
void forOutEdgesOfImplParallel(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 forInEdgesOfImplParallel(node u, L handle) const;
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
void forEdgeImpl(L handle) const;
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
void forEdgesImplParallel(L handle) const;
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
inline double parallelSumForEdgesImpl(L handle) const;
template <typename L>
void balancedParallelForNodes(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::DHBGraph::NodeIterator
using NodeIterator = NodeIteratorBase<DHBGraph, node, edgeweight>;
// For support of API: NetworKit::DHBGraph::NodeRange
using NodeRange = NodeRangeBase<DHBGraph, node, edgeweight>;
// For support of API: NetworKit::DHBGraph:EdgeIterator
using EdgeIterator = EdgeWeightTIterator<DHBGraph, node, edgeweight, EdgeT<node>>;
// For support of API: NetworKit::DHBGraph:EdgeWeightIterator
using EdgeWeightIterator =
EdgeWeightTIterator<DHBGraph, node, edgeweight, WeightedEdgeT<node, edgeweight>>;
// For support of API: NetworKit::DHBGraph:EdgeRange
using EdgeRange = EdgeWeightTRange<DHBGraph, node, edgeweight, EdgeT<node>>;
// For support of API: NetworKit::DHBGraph:EdgeWeightRange
using EdgeWeightRange =
EdgeWeightTRange<DHBGraph, node, edgeweight, WeightedEdgeT<node, edgeweight>>;
class NeighborIterator {
using IteratorType = dhb::BlockState<EdgeData>::const_iterator;
IteratorType it;
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(IteratorType it) : it(it) {}
NeighborIterator() {}
NeighborIterator &operator++() {
++it;
return *this;
}
NeighborIterator operator++(int) {
auto const tmp = *this;
++(*this);
return tmp;
}
NeighborIterator operator--() {
--it;
return *this;
}
NeighborIterator operator--(int) {
auto const tmp = *this;
--(*this);
return tmp;
}
bool operator==(NeighborIterator const &rhs) const { return it == rhs.it; }
bool operator!=(NeighborIterator const &rhs) const { return !(it == rhs.it); }
node operator*() const { return it->vertex(); }
};
class NeighborWeightIterator {
using IteratorType = dhb::BlockState<EdgeData>::const_iterator;
IteratorType it;
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(IteratorType it) : it(it) {}
NeighborWeightIterator() {}
NeighborWeightIterator &operator++() {
++it;
return *this;
}
NeighborWeightIterator operator++(int) {
auto const tmp = *this;
++(*this);
return tmp;
}
NeighborWeightIterator operator--() {
--it;
return *this;
}
NeighborWeightIterator operator--(int) {
auto const tmp = *this;
--(*this);
return tmp;
}
bool operator==(NeighborWeightIterator const &rhs) const { return it == rhs.it; }
bool operator!=(NeighborWeightIterator const &rhs) const { return !(it == rhs.it); }
std::pair<node, edgeweight> operator*() const {
return std::make_pair(it->vertex(), it->data().weight);
}
};
template <bool InEdges = false>
class NeighborRange {
DHBGraph const *G;
node u;
public:
NeighborRange(DHBGraph const &G, node u) : G(&G), u(u) { assert(G.hasNode(u)); };
NeighborRange() : G(nullptr) {};
NeighborIterator begin() const {
assert(G);
// in DHB we don't support iterator over InEdges = true;
static_assert(!InEdges);
return NeighborIterator(G->m_dhb_graph.neighbors(u).begin());
}
NeighborIterator end() const {
// in DHB we don't support iterator over InEdges = true;
static_assert(!InEdges);
return NeighborIterator(G->m_dhb_graph.neighbors(u).end());
}
};
using OutNeighborRange = NeighborRange<false>;
template <bool InEdges = false>
class NeighborWeightRange {
const DHBGraph *G;
node u;
public:
NeighborWeightRange(const DHBGraph &G, node u) : G(&G), u(u) { assert(G.hasNode(u)); };
NeighborWeightRange() : G(nullptr) {};
NeighborWeightIterator begin() const {
assert(G);
// in DHB we don't support iterator over InEdges = true;
static_assert(!InEdges);
return NeighborWeightIterator(G->m_dhb_graph.neighbors(u).begin());
}
NeighborWeightIterator end() const {
assert(G);
// in DHB we don't support iterator over InEdges = true;
static_assert(!InEdges);
return NeighborWeightIterator(G->m_dhb_graph.neighbors(u).end());
}
};
using OutNeighborWeightRange = NeighborWeightRange<false>;
using InNeighborWeightRange = NeighborWeightRange<true>;
DHBGraph(count n = 0, bool weighted = false, bool directed = false, bool edgesIndexed = false);
template <class EdgeMerger = std::plus<edgeweight>>
DHBGraph(DHBGraph const &G, bool weighted, bool directed, bool edgesIndexed = false)
: weighted(weighted), directed(directed), m(G.m),
storedNumberOfSelfLoops(G.storedNumberOfSelfLoops), omega(edgesIndexed ? G.omega : 0),
edgesIndexed(edgesIndexed), nodeAttributeMap(G.nodeAttributeMap, this),
edgeAttributeMap(G.edgeAttributeMap, this), m_dhb_graph(G.m_dhb_graph) {
bool const copy_weighted_graph_to_unweighted = G.isWeighted() && !weighted;
bool const copy_directed_graph_to_undirected = G.isDirected() && !directed;
if (copy_weighted_graph_to_unweighted) {
#pragma omp parallel for schedule(guided)
for (omp_index u = 0; u < static_cast<omp_index>(m_dhb_graph.vertices_count()); ++u) {
dhb::Matrix<EdgeData>::NeighborView n = m_dhb_graph.neighbors(u);
for (auto v = n.begin(); v != n.end(); ++v) {
v->data().weight = defaultEdgeWeight;
}
}
}
if (copy_directed_graph_to_undirected) {
// insert bidirectional edges if they don't exist
removeAllEdges();
G.forEdges([&](node u, node v, edgeweight ew, edgeid id) { addEdge(u, v, ew, id); });
}
}
DHBGraph(std::initializer_list<WeightedEdge> edges);
DHBGraph(const DHBGraph &other)
: weighted(other.weighted), directed(other.directed), m(other.m),
storedNumberOfSelfLoops(other.storedNumberOfSelfLoops), omega(other.omega),
edgesIndexed(other.edgesIndexed), nodeAttributeMap(other.nodeAttributeMap, this),
edgeAttributeMap(other.edgeAttributeMap, this), m_dhb_graph(other.m_dhb_graph) {};
DHBGraph(DHBGraph &&other) noexcept
: weighted(other.weighted), directed(other.directed), m(other.m),
storedNumberOfSelfLoops(other.storedNumberOfSelfLoops), omega(other.omega),
edgesIndexed(other.edgesIndexed), nodeAttributeMap(std::move(other.nodeAttributeMap)),
edgeAttributeMap(std::move(other.edgeAttributeMap)), m_dhb_graph(other.m_dhb_graph) {
// attributes: set graph pointer to this new graph
nodeAttributeMap.theGraph = this;
edgeAttributeMap.theGraph = this;
};
~DHBGraph() = default;
DHBGraph &operator=(DHBGraph &&other) noexcept {
std::swap(weighted, other.weighted);
std::swap(directed, other.directed);
std::swap(m, other.m);
std::swap(storedNumberOfSelfLoops, other.storedNumberOfSelfLoops);
std::swap(omega, other.omega);
std::swap(edgesIndexed, other.edgesIndexed);
// attributes: set graph pointer to this new graph
std::swap(nodeAttributeMap, other.nodeAttributeMap);
std::swap(edgeAttributeMap, other.edgeAttributeMap);
nodeAttributeMap.theGraph = this;
edgeAttributeMap.theGraph = this;
std::swap(m_dhb_graph, other.m_dhb_graph);
return *this;
};
DHBGraph &operator=(const DHBGraph &other) {
weighted = other.weighted;
directed = other.directed;
m = other.m;
storedNumberOfSelfLoops = other.storedNumberOfSelfLoops;
omega = other.omega;
edgesIndexed = other.edgesIndexed;
// call special constructors to copy attribute maps
nodeAttributeMap = AttributeMap(other.nodeAttributeMap, this);
edgeAttributeMap = AttributeMap(other.edgeAttributeMap, this);
m_dhb_graph = other.m_dhb_graph;
return *this;
};
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) {
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 sortEdges() {
return sortEdges([](node a_vertex, edgeweight, edgeid, node b_vertex, edgeweight, edgeid) {
return a_vertex < b_vertex;
});
}
template <typename Lambda>
void sortEdges(Lambda &&lambda) {
auto l = std::forward<Lambda>(lambda);
for (node v = 0; v < m_dhb_graph.vertices_count(); ++v) {
m_dhb_graph.sort(v, [&l](dhb::BlockState<EdgeData>::Entry &a,
dhb::BlockState<EdgeData>::Entry &b) {
return l(a.vertex, a.data.weight, a.data.id, b.vertex, b.data.weight, b.data.id);
});
}
}
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);
bool hasNode(node v) const noexcept;
count degree(node v) const;
count degreeIn(node v) const;
count degreeOut(node v) const { return degree(v); }
bool isIsolated(node v) const;
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 do_update = true);
void addEdges(std::vector<WeightedEdge> &&edges, bool do_update);
void addEdges(std::vector<Edge> &&edges, bool do_update);
bool 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 swapEdge(node source_a, node target_a, node source_b, node target_b);
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 0u == m_dhb_graph.vertices_count(); }
count numberOfNodes() const noexcept;
count numberOfEdges() const noexcept;
count numberOfSelfLoops() const noexcept { return storedNumberOfSelfLoops; }
index upperNodeIdBound() const noexcept;
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 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(u < upperNodeIdBound());
return NeighborRange<false>(*this, u);
}
NeighborWeightRange<false> weightNeighborRange(node u) const {
assert(isWeighted());
assert(u < upperNodeIdBound());
return NeighborWeightRange<false>(*this, u);
}
index indexOfNeighbor(node u, node v) const;
node getIthNeighbor(node u, index i) const;
node getIthNeighbor(Unsafe, node u, index i) const;
edgeweight getIthNeighborWeight(node u, index i) const;
edgeweight getIthNeighborWeight(Unsafe, node u, index i) const;
std::pair<node, edgeweight> getIthNeighborWithWeight(node u, index i) const;
std::pair<node, edgeweight> getIthNeighborWithWeight(Unsafe, node u, index i) const;
std::pair<node, edgeid> getIthNeighborWithId(node u, index i) const;
/* 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 forNodePairs(L handle) const;
template <typename L>
void forNodePairsParallel(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 forNeighborsOfParallel(node u, L handle) const;
template <typename L>
void forEdgesOf(node u, L handle) const;
template <typename L>
void forEdgesOfParallel(node u, L handle) const;
template <typename L>
void forInNeighborsOf(node u, L handle) const;
template <typename L>
void forInNeighborsOfParallel(node u, L handle) const;
template <typename L>
void forInEdgesOf(node u, L handle) const;
template <typename L>
void forInEdgesOfParallel(node u, L handle) const;
/* REDUCTION ITERATORS */
template <typename L>
double sumForNodesParallel(L handle) const;
template <typename L>
double sumForEdgesParallel(L handle) const;
};
/* NODE ITERATORS */
template <typename L>
void DHBGraph::forNodes(L handle) const {
for (node v = 0; v < m_dhb_graph.vertices_count(); ++v) {
handle(v);
}
}
template <typename L>
void DHBGraph::parallelForNodes(L handle) const {
#pragma omp parallel for schedule(guided)
for (omp_index v = 0; v < static_cast<omp_index>(m_dhb_graph.vertices_count()); ++v) {
handle(static_cast<node>(v));
}
}
template <typename C, typename L>
void DHBGraph::forNodesWhile(C condition, L handle) const {
for (dhb::Vertex v = 0; v < m_dhb_graph.vertices_count(); ++v) {
if (!condition()) {
break;
}
handle(v);
}
}
template <typename L>
void DHBGraph::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 DHBGraph::balancedParallelForNodes(L handle) const {
#pragma omp parallel for schedule(guided)
for (omp_index v = 0; v < static_cast<omp_index>(m_dhb_graph.vertices_count()); ++v) {
handle(v);
}
}
template <typename L>
void DHBGraph::forNodePairs(L handle) const {
for (node u = 0; u < m_dhb_graph.vertices_count(); ++u) {
for (node v = u + 1; v < m_dhb_graph.vertices_count(); ++v) {
handle(u, v);
}
}
}
template <typename L>
void DHBGraph::forNodePairsParallel(L handle) const {
#pragma omp parallel for schedule(guided)
for (omp_index u = 0; u < static_cast<omp_index>(m_dhb_graph.vertices_count()); ++u) {
auto neighborhood = m_dhb_graph.neighbors(u);
for (auto target = neighborhood.begin(); target != neighborhood.end(); ++target) {
handle(u, target->vertex());
}
}
}
/* EDGE ITERATORS */
// /* HELPERS */
// implementation for graphIsDirected == true
template <bool graphIsDirected>
inline bool DHBGraph::useEdgeInIteration(node /* u */, node /* v */) const {
return true;
}
template <bool hasWeights, bool graphHasEdgeIds>
std::tuple<edgeweight, edgeid> DHBGraph::getDHBEdgeData(node u, node v) const {
auto const w = hasWeights ? weight(u, v) : defaultEdgeWeight;
auto const id = graphHasEdgeIds ? edgeId(u, v) : none;
return std::make_tuple(w, id);
}
// implementation for graphIsDirected == false
template <>
inline bool DHBGraph::useEdgeInIteration<false>(node u, node v) const {
return u >= v;
}
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
void DHBGraph::forOutEdgesOfImpl(node u, L handle) const {
assert(u < upperNodeIdBound());
auto neighbors = m_dhb_graph.neighbors(u);
for (size_t i = 0; i < neighbors.degree(); ++i) {
dhb::Vertex const v = neighbors[i].vertex();
auto const [w, id] = getDHBEdgeData<hasWeights, graphHasEdgeIds>(u, v);
edgeLambda<L>(handle, u, v, w, id);
}
}
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
void DHBGraph::forOutEdgesOfImplParallel(node u, L handle) const {
assert(u < upperNodeIdBound());
auto neighbors = m_dhb_graph.neighbors(u);
#pragma omp parallel for schedule(guided)
for (omp_index i = 0; i < static_cast<omp_index>(neighbors.degree()); ++i) {
dhb::Vertex const v = neighbors[i].vertex();
auto const [w, id] = getDHBEdgeData<hasWeights, graphHasEdgeIds>(u, v);
edgeLambda<L>(handle, u, v, w, id);
}
}
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
void DHBGraph::forInEdgesOfImpl(node u, L handle) const {
assert(u < upperNodeIdBound());
if (graphIsDirected) {
for (dhb::Vertex from = 0; from < m_dhb_graph.vertices_count(); ++from) {
for (auto it = neighborRange(from).begin(); it != neighborRange(from).end(); ++it) {
dhb::Vertex const to = *it;
if (u == to) {
auto const [w, id] = getDHBEdgeData<hasWeights, graphHasEdgeIds>(from, to);
edgeLambda<L>(handle, to, from, w, id);
}
}
}
} else {
forNeighborsOf(u, handle);
}
}
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
inline void DHBGraph::forInEdgesOfImplParallel(node u, L handle) const {
assert(u < upperNodeIdBound());
if (graphIsDirected) {
#pragma omp parallel for schedule(guided)
for (omp_index from = 0; from < static_cast<omp_index>(m_dhb_graph.vertices_count());
++from) {
for (auto it = neighborRange(from).begin(); it != neighborRange(from).end(); ++it) {
dhb::Vertex const to = *it;
if (u == to) {
auto const [w, id] = getDHBEdgeData<hasWeights, graphHasEdgeIds>(from, to);
edgeLambda<L>(handle, to, from, w, id);
}
}
}
} else {
forNeighborsOfParallel(u, handle);
}
}
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
void DHBGraph::forEdgeImpl(L handle) const {
for (dhb::Vertex u = 0; u < m_dhb_graph.vertices_count(); ++u) {
auto neighbors = m_dhb_graph.neighbors(u);
for (auto it = neighbors.begin(); it != neighbors.end(); ++it) {
dhb::Vertex const v = it->vertex();
// If the graph is undirected, this function only call the handle on edges where u > v.
// This avoids processing each edge twice (once for each direction).
// However, in some cases, we might want to iterate over all edges
// in the undirected graph, regardless of direction.
if (useEdgeInIteration<graphIsDirected>(u, v)) {
auto const [w, id] = getDHBEdgeData<hasWeights, graphHasEdgeIds>(u, v);
edgeLambda<L>(handle, u, v, w, id);
}
}
}
}
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
void DHBGraph::forEdgesImplParallel(L handle) const {
#pragma omp parallel for schedule(guided)
for (omp_index u = 0; u < static_cast<omp_index>(m_dhb_graph.vertices_count()); ++u) {
auto neighbors = m_dhb_graph.neighbors(u);
for (auto it = neighbors.begin(); it != neighbors.end(); ++it) {
dhb::Vertex const v = it->vertex();
// if the graph is not directed, only call the handle on edges that u > v.
// So we don't want to use this sometimes, when we want to iterate all edges in an
// undirected graph
if (useEdgeInIteration<graphIsDirected>(u, v)) {
auto const [w, id] = getDHBEdgeData<hasWeights, graphHasEdgeIds>(u, v);
edgeLambda<L>(handle, u, v, w, id);
}
}
}
}
template <bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
double DHBGraph::parallelSumForEdgesImpl(L handle) const {
double total_sum = 0.0;
#pragma omp parallel for schedule(guided) reduction(+ : total_sum)
for (omp_index u = 0; u < static_cast<omp_index>(m_dhb_graph.vertices_count()); ++u) {
auto neighbors = m_dhb_graph.neighbors(u);
for (auto it = neighbors.begin(); it != neighbors.end(); ++it) {
dhb::Vertex const v = it->vertex();
auto const [w, id] = getDHBEdgeData<hasWeights, graphHasEdgeIds>(u, v);
if (u == v && !directed) {
total_sum += 2 * edgeLambda<L>(handle, u, v, w, id);
} else {
total_sum += edgeLambda<L>(handle, u, v, w, id);
}
}
}
if (!directed) {
total_sum /= 2;
}
return total_sum;
}
template <typename L>
void DHBGraph::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 DHBGraph::parallelForEdges(L handle) const {
switch (weighted + 2 * directed + 4 * edgesIndexed) {
case 0: // unweighted, undirected, no edgeIds
forEdgesImplParallel<false, false, false, L>(handle);
break;
case 1: // weighted, undirected, no edgeIds
forEdgesImplParallel<false, true, false, L>(handle);
break;
case 2: // unweighted, directed, no edgeIds
forEdgesImplParallel<true, false, false, L>(handle);
break;
case 3: // weighted, directed, no edgeIds
forEdgesImplParallel<true, true, false, L>(handle);
break;
case 4: // unweighted, undirected, with edgeIds
forEdgesImplParallel<false, false, true, L>(handle);
break;
case 5: // weighted, undirected, with edgeIds
forEdgesImplParallel<false, true, true, L>(handle);
break;
case 6: // unweighted, directed, with edgeIds
forEdgesImplParallel<true, false, true, L>(handle);
break;
case 7: // weighted, directed, with edgeIds
forEdgesImplParallel<true, true, true, L>(handle);
break;
}
}
/* NEIGHBORHOOD ITERATORS */
template <typename L>
void DHBGraph::forNeighborsOf(node u, L handle) const {
forEdgesOf(u, handle);
}
template <typename L>
void DHBGraph::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 DHBGraph::forNeighborsOfParallel(node u, L handle) const {
forEdgesOfParallel(u, handle);
}
template <typename L>
void DHBGraph::forEdgesOfParallel(node u, L handle) const {
switch (weighted + 2 * edgesIndexed) {
case 0: // not weighted, no edge ids
forOutEdgesOfImplParallel<true, false, false, L>(u, handle);
break;
case 1: // weighted, no edge ids
forOutEdgesOfImplParallel<true, true, false, L>(u, handle);
break;
case 2: // not weighted, with edge ids
forOutEdgesOfImplParallel<true, false, true, L>(u, handle);
break;
case 3: // weighted, with edge ids
forOutEdgesOfImplParallel<true, true, true, L>(u, handle);
break;
}
}
template <typename L>
void DHBGraph::forInNeighborsOf(node u, L handle) const {
forInEdgesOf(u, handle);
}
template <typename L>
void DHBGraph::forInNeighborsOfParallel(node u, L handle) const {
forInEdgesOfParallel(u, handle);
}
template <typename L>
void DHBGraph::forInEdgesOfParallel(node u, L handle) const {
switch (weighted + 2 * directed + 4 * edgesIndexed) {
case 0: // unweighted, undirected, no edge ids
forInEdgesOfImplParallel<false, false, false, L>(u, handle);
break;
case 1: // weighted, undirected, no edge ids
forInEdgesOfImplParallel<false, true, false, L>(u, handle);
break;
case 2: // unweighted, directed, no edge ids
forInEdgesOfImplParallel<true, false, false, L>(u, handle);
break;
case 3: // weighted, directed, no edge ids
forInEdgesOfImplParallel<true, true, false, L>(u, handle);
break;
case 4: // unweighted, undirected, with edge ids
forInEdgesOfImplParallel<false, false, true, L>(u, handle);
break;
case 5: // weighted, undirected, with edge ids
forInEdgesOfImplParallel<false, true, true, L>(u, handle);
break;
case 6: // unweighted, directed, with edge ids
forInEdgesOfImplParallel<true, false, true, L>(u, handle);
break;
case 7: // weighted, directed, with edge ids
forInEdgesOfImplParallel<true, true, true, L>(u, handle);
break;
}
}
template <typename L>
void DHBGraph::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 DHBGraph::sumForNodesParallel(L handle) const {
double sum = 0.0;
#pragma omp parallel for schedule(guided) reduction(+ : sum)
for (omp_index v = 0; v < static_cast<omp_index>(m_dhb_graph.vertices_count()); ++v) {
sum += handle(v);
}
return sum;
}
template <typename L>
double DHBGraph::sumForEdgesParallel(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> DHBGraph::removeAdjacentEdges(node u, Condition condition, bool edgesIn) {
std::vector<std::pair<dhb::Vertex, dhb::Vertex>> edgesToRemove;
count removedEdges = 0;
count removedSelfLoops = 0;
if (!edgesIn) {
forNeighborsOf(u, [&](node v) {
if (condition(v)) {
edgesToRemove.emplace_back(u, v);
}
});
} else {
forInNeighborsOf(u, [&](node v) {
if (condition(v)) {
edgesToRemove.emplace_back(v, u);
}
});
}
// actual removal
for (auto const &edge : edgesToRemove) {
bool const remove_success = removeEdge(edge.first, edge.second);
bool const is_loop = edge.first == edge.second;
if (remove_success) {
removedSelfLoops += is_loop;
removedEdges += !is_loop;
}
}
if (!isDirected()) {
return {removedEdges >> 1, removedSelfLoops};
}
return {removedEdges, removedSelfLoops};
}
} /* namespace NetworKit */
#endif // NETWORKIT_GRAPH_DHB_GRAPH_HPP_