↰ Return to documentation for file (include/networkit/graph/GraphTools.hpp)
#ifndef NETWORKIT_GRAPH_GRAPH_TOOLS_HPP_
#define NETWORKIT_GRAPH_GRAPH_TOOLS_HPP_
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include "networkit/graph/TopologicalSort.hpp"
#include <tlx/unused.hpp>
#include <networkit/GlobalState.hpp>
#include <networkit/graph/Graph.hpp>
namespace NetworKit {
namespace GraphTools {
count maxDegree(const Graph &G);
count maxInDegree(const Graph &G);
edgeweight maxWeightedDegree(const Graph &G);
edgeweight maxWeightedInDegree(const Graph &G);
node randomNode(const Graph &G);
std::vector<node> randomNodes(const Graph &G, count n);
node randomNeighbor(const Graph &G, node u);
std::pair<node, node> randomEdge(const Graph &G, bool uniformDistribution = false);
std::vector<std::pair<node, node>> randomEdges(const Graph &G, count nr);
template <class InputIt>
void removeEdgesFromIsolatedSet(Graph &G, InputIt first, InputIt last) {
count removedEdges = 0;
while (first != last) {
const auto u = *first++;
removedEdges += G.degree(u);
G.removePartialOutEdges(unsafe, u);
if (G.isDirected()) {
G.removePartialInEdges(unsafe, u);
}
}
G.setEdgeCount(unsafe, G.numberOfEdges() - (G.isDirected() ? removedEdges : removedEdges / 2));
}
std::pair<node, node> size(const Graph &G) noexcept;
double density(const Graph &G) noexcept;
double volume(const Graph &G);
template <class InputIt>
double volume(const Graph &G, InputIt first, InputIt last) {
double outVolume = 0.0;
// Compute volume of subgraph
for (; first != last; ++first)
outVolume += G.weightedDegree(*first, !G.isDirected());
return outVolume;
}
template <class InputIt>
double inVolume(const Graph &G, InputIt first, InputIt last) {
double inVolume = 0.0;
// Compute volume of subgraph
for (; first != last; ++first)
inVolume += G.weightedDegreeIn(*first, !G.isDirected());
return inVolume;
}
Graph copyNodes(const Graph &G);
Graph subgraphFromNodes(const Graph &G, const std::unordered_set<node> &nodes);
template <class InputIt>
Graph subgraphFromNodes(const Graph &G, InputIt first, InputIt last, bool compact = false) {
count subgraphIdBound = 0;
std::unordered_map<node, node> reverseMapping;
if (compact) {
for (InputIt it = first; it != last; ++it) {
reverseMapping[*it] = subgraphIdBound;
++subgraphIdBound;
}
} else {
subgraphIdBound = G.upperNodeIdBound();
}
Graph S(subgraphIdBound, G.isWeighted(), G.isDirected());
if (compact) {
for (auto nodeIt : reverseMapping) {
node u = nodeIt.first;
node localU = nodeIt.second;
G.forNeighborsOf(u, [&](node v, edgeweight weight) {
if (!G.isDirected() && u > v)
return;
auto vMapping = reverseMapping.find(v);
if (vMapping != reverseMapping.end())
S.addEdge(localU, vMapping->second, weight);
});
}
} else {
// First, delete all nodes
for (node u = 0; u < G.upperNodeIdBound(); ++u) {
S.removeNode(u);
}
// Restore all given nodes
for (InputIt it = first; it != last; ++it) {
S.restoreNode(*it);
}
G.forEdges([&](node u, node v, edgeweight w) {
// only include edges if at least one endpoint is in nodes
if (S.hasNode(u) && S.hasNode(v)) {
S.addEdge(u, v, w);
}
});
}
return S;
}
Graph subgraphAndNeighborsFromNodes(const Graph &G, const std::unordered_set<node> &nodes,
bool includeOutNeighbors = false,
bool includeInNeighbors = false);
Graph toUndirected(const Graph &G);
Graph toUnweighted(const Graph &G);
Graph toWeighted(const Graph &G);
Graph transpose(const Graph &G);
void append(Graph &G, const Graph &G1);
void merge(Graph &G, const Graph &G1);
Graph getCompactedGraph(const Graph &graph, const std::unordered_map<node, node> &nodeIdMap);
std::unordered_map<node, node> getContinuousNodeIds(const Graph &graph);
std::unordered_map<node, node> getRandomContinuousNodeIds(const Graph &graph);
std::vector<node> invertContinuousNodeIds(const std::unordered_map<node, node> &nodeIdMap,
const Graph &G);
Graph restoreGraph(const std::vector<node> &invertedIdMap, const Graph &G);
node augmentGraph(Graph &G);
std::pair<Graph, node> createAugmentedGraph(const Graph &G);
void sortEdgesByWeight(Graph &G, bool decreasing = false);
std::vector<node> topologicalSort(const Graph &G,
const std::unordered_map<node, node> &nodeIdMapping = {},
bool checkMapping = false);
template <class Distribution = std::uniform_real_distribution<edgeweight>>
void randomizeWeights(Graph &G, Distribution distr = std::uniform_real_distribution<edgeweight>{
0, std::nexttoward(1.0, 2.0)}) {
if (!G.isWeighted())
G = toWeighted(G);
#pragma omp parallel
{
std::mt19937 gen;
// each thread is given is own seed
const auto baseSeed =
(GlobalState::getGlobalSeed() != 0 && !GlobalState::getSeedUseThreadId())
? Aux::Random::integer()
: Aux::Random::getSeed();
// static combined with giving each thread its own seed ensures that this process is determinisc
#pragma omp for schedule(static)
for (omp_index u = 0; u < G.upperNodeIdBound(); ++u) {
// we use the hash of the origin node so that the weights are independent
// of processing order
gen.seed(std::hash<node>()(u) + 0x9e3779b9 + (baseSeed << 6) + (baseSeed >> 2));
index j = 0;
G.forEdgesOf(u, [&](node v) {
if (u > v && !G.isDirected()) { // avoid visiting edges twice in undirected graphs
++j;
return;
}
edgeweight ew = distr(gen);
G.setWeightAtIthNeighbor(Unsafe{}, u, j, ew);
++j;
index k = 0;
// we need to set the other direction of the edge to the same weight
if (G.isDirected()) {
G.forInEdgesOf(v, [&](node w) {
if (w == u) {
G.setWeightAtIthInNeighbor(Unsafe{}, v, k, ew);
}
++k;
});
} else if (u != v) {
G.forEdgesOf(v, [&](node w) {
if (w == u) {
G.setWeightAtIthNeighbor(Unsafe{}, v, k, ew);
}
++k;
});
}
});
}
}
}
template <typename UnaryIdMapper, typename SkipEdgePredicate>
Graph getRemappedGraph(const Graph &graph, count numNodes, UnaryIdMapper &&oldIdToNew,
SkipEdgePredicate &&skipNode, bool preallocate = true) {
tlx::unused(preallocate); // TODO: Add perallocate as soon as Graph supports it
#ifndef NDEBUG
graph.forNodes([&](node u) { assert(skipNode(u) || oldIdToNew(u) < numNodes); });
#endif // NDEBUG
const auto directed = graph.isDirected();
Graph Gnew(numNodes, graph.isWeighted(), directed);
graph.forNodes([&](const node u) { // TODO: Make parallel when graph support addHalfEdge
if (skipNode(u))
return;
const node mapped_u = oldIdToNew(u);
graph.forNeighborsOf(u, [&](node, node v, edgeweight ew) {
if (!directed && v < u)
return;
if (skipNode(v))
return;
const node mapped_v = oldIdToNew(v);
Gnew.addEdge(mapped_u, mapped_v, ew);
});
});
return Gnew;
}
template <typename UnaryIdMapper>
Graph getRemappedGraph(const Graph &graph, count numNodes, UnaryIdMapper &&oldIdToNew,
bool preallocate = true) {
return getRemappedGraph(
graph, numNodes, std::forward<UnaryIdMapper>(oldIdToNew), [](node) { return false; },
preallocate);
}
} // namespace GraphTools
} // namespace NetworKit
#endif // NETWORKIT_GRAPH_GRAPH_TOOLS_HPP_