↰ Return to documentation for file (include/networkit/graph/GraphBuilder.hpp)
/*
* GraphBuilder.hpp
*
* Created on: 15.07.2014
* Author: Marvin Ritter (marvin.ritter@gmail.com)
*/
#ifndef NETWORKIT_GRAPH_GRAPH_BUILDER_HPP_
#define NETWORKIT_GRAPH_GRAPH_BUILDER_HPP_
#include <vector>
#include <networkit/Globals.hpp>
#include <networkit/graph/Graph.hpp>
namespace NetworKit {
/*
* The GraphBuilder helps to speed up graph generation by minimizing the number
* of checks on addEdge/setWeight/increaseWeight. Further more it delays the
* construction of some internal data structures of the Graph class until you
* call toGraph(). toGraph() can only be called once. In the Graph class for an
* edge u -> v, v is stored in the adjacent array of u (first half) and u in the
* adjacent array of v (second half). (For directed graphs these might be in and
* out adjacent arrays.). So each edge can be seen as a pair of 2 half edges. To
* allow optimization and mainly parallelization GraphBuilder lets you add both
* half edges yourself. You are responsible for adding both half edges,
* otherwise you might end up with an invalid Graph object. As adding the first
* half edge of an edge u -> v only requires access to the adjacent array of u,
* other threads can add edges a -> b as long as a != u. Some goes for the
* methods setWeight and increaseWeight. Note: If you add the first half edge of
* u -> v, you can change the weight by calling setWeight(u, v, ew) or
* increaseWeight(u, v, ew), but calling setWeight(v, u, ew) or
* increaseWeight(v, u, ew) will add the second half edge. GraphBuilder allows
* you to be lazy and only add one half of each edge. Calling toGraph with
* autoCompleteEdges set to true, will make each half Edge in GraphBuilder to
* one full edge in Graph.
*
* So far I didn't came up with a good parallelization for toGraph, so at some
* point I might omit the parallel parameter for toGraph.
*/
class GraphBuilder {
count n;
count selfloops;
bool weighted;
bool directed;
bool autoCompleteEdges = false;
index indexInOutEdgeArrayPerThread(node u, node v) const;
index indexInInEdgeArrayPerThread(node u, node v) const;
struct HalfEdge {
node source;
node destination;
// HalfEdge(node source, node destination);
HalfEdge(){};
HalfEdge(node source, node destination) : source(source), destination(destination){};
};
std::vector<std::vector<std::vector<HalfEdge>>>
outEdgesPerThread;
std::vector<std::vector<std::vector<edgeweight>>>
outEdgeWeightsPerThread;
std::vector<std::vector<std::vector<HalfEdge>>>
inEdgesPerThread;
std::vector<std::vector<std::vector<edgeweight>>>
inEdgeWeightsPerThread;
public:
GraphBuilder(count n = 0, bool weighted = false, bool directed = false,
bool autoCompleteEdges = false);
void reset(count n = 0);
inline bool isWeighted() const { return weighted; }
inline bool isDirected() const { return directed; }
inline bool isEmpty() const { return n == 0; }
count numberOfNodes() const { return n; }
index upperNodeIdBound() const { return n; }
node addNode();
void addHalfEdge(node u, node v, edgeweight ew = defaultEdgeWeight);
void addHalfOutEdge(node u, node v, edgeweight ew = defaultEdgeWeight);
void addHalfInEdge(node u, node v, edgeweight ew = defaultEdgeWeight);
void swapNeighborhood(node u, std::vector<node> &neighbours, std::vector<edgeweight> &weights,
bool selfloop);
void setWeight(node u, node v, edgeweight ew) { setOutWeight(u, v, ew); }
void setOutWeight(node u, node v, edgeweight ew);
void setInWeight(node u, node v, edgeweight ew);
void increaseWeight(node u, node v, edgeweight ew) { increaseOutWeight(u, v, ew); }
void increaseOutWeight(node u, node v, edgeweight ew);
void increaseInWeight(node u, node v, edgeweight ew);
Graph completeGraph();
Graph TLX_DEPRECATED(completeGraph([[maybe_unused]] bool parallel)) {
WARN("GraphBuilder::completeGraph(bool parallel) is deprecated, use "
"GraphBuilder::completeGraph() instead");
return completeGraph();
}
template <typename L>
void forNodes(L handle) const;
template <typename L>
void parallelForNodes(L handle) const;
template <typename L>
void forNodePairs(L handle) const;
template <typename L>
void parallelForNodePairs(L handle) const;
/*
* If set to true, the graph builder automatically adds the second part of the halfEdge when
* calling <code>addHalfEdge(u,v)</code>. This enables the graph building process to be more
* efficient, while adding the halfEdges takes slightly longer.
*/
void setAutoCompleteEdges(bool completeEdges = false) { autoCompleteEdges = completeEdges; };
private:
void toGraphSequential(Graph &G);
void toGraphParallel(Graph &G);
void addHalfEdgesToGraph(Graph &G);
template <typename T>
static void copyAndClear(std::vector<T> &source, std::vector<T> &target);
count numberOfEdges(const Graph &G);
};
template <typename L>
void GraphBuilder::forNodes(L handle) const {
for (node v = 0; v < n; v++) {
handle(v);
}
}
template <typename L>
void GraphBuilder::parallelForNodes(L handle) const {
#pragma omp parallel for schedule(dynamic, 100)
for (omp_index v = 0; v < static_cast<omp_index>(n); v++) {
handle(v);
}
}
template <typename L>
void GraphBuilder::forNodePairs(L handle) const {
for (node u = 0; u < n; u++) {
for (node v = u + 1; v < n; v++) {
handle(u, v);
}
}
}
template <typename L>
void GraphBuilder::parallelForNodePairs(L handle) const {
#pragma omp parallel for schedule(dynamic, 100)
for (omp_index u = 0; u < static_cast<omp_index>(n); u++) {
for (node v = u + 1; v < n; v++) {
handle(u, v);
}
}
}
template <typename T>
void GraphBuilder::copyAndClear(std::vector<T> &source, std::vector<T> &target) {
std::copy(source.begin(), source.end(), std::back_inserter(target));
source.clear();
}
} /* namespace NetworKit */
#endif // NETWORKIT_GRAPH_GRAPH_BUILDER_HPP_