Program Listing for File 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;

    std::vector<std::vector<node>>
        outEdges;
    std::vector<std::vector<edgeweight>>
        outEdgeWeights;

    std::vector<std::vector<node>> inEdges;
    std::vector<std::vector<edgeweight>>
        inEdgeWeights;

    index indexInOutEdgeArray(node u, node v) const;

    index indexInInEdgeArray(node u, node v) const;

public:
    GraphBuilder(count n = 0, bool weighted = false, bool directed = 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) {
        addHalfOutEdge(u, v, ew);
    }
    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(bool parallel);

    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;

private:
    void toGraphSequential(Graph &G);
    void toGraphParallel(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_