LC_CSR_CSC_Graph.h

Go to the documentation of this file.

/*
 * This file belongs to the Galois project, a C++ library for exploiting
 * parallelism. The code is being released under the terms of the 3-Clause BSD
 * License (a copy is located in LICENSE.txt at the top-level directory).
 *
 * Copyright (C) 2018, The University of Texas at Austin. All rights reserved.
 * UNIVERSITY EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES CONCERNING THIS
 * SOFTWARE AND DOCUMENTATION, INCLUDING ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR ANY PARTICULAR PURPOSE, NON-INFRINGEMENT AND WARRANTIES OF
 * PERFORMANCE, AND ANY WARRANTY THAT MIGHT OTHERWISE ARISE FROM COURSE OF
 * DEALING OR USAGE OF TRADE.  NO WARRANTY IS EITHER EXPRESS OR IMPLIED WITH
 * RESPECT TO THE USE OF THE SOFTWARE OR DOCUMENTATION. Under no circumstances
 * shall University be liable for incidental, special, indirect, direct or
 * consequential damages or loss of profits, interruption of business, or
 * related expenses which may arise from use of Software or Documentation,
 * including but not limited to those resulting from defects in Software and/or
 * Documentation, or loss or inaccuracy of data of any kind.
 */

#ifndef GALOIS_GRAPHS_LC_CSR_CSC_GRAPH_H
#define GALOIS_GRAPHS_LC_CSR_CSC_GRAPH_H

#include "galois/config.h"

#include "galois/graphs/LC_CSR_Graph.h"

namespace galois {
namespace graphs {

template <typename NodeTy, typename EdgeTy, bool EdgeDataByValue = false,
          bool HasNoLockable = false, bool UseNumaAlloc = false,
          bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>
class LC_CSR_CSC_Graph
    : public LC_CSR_Graph<NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc,
                          HasOutOfLineLockable, FileEdgeTy> {
  // typedef to make it easier to read
  using BaseGraph = LC_CSR_Graph<NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc,
                                 HasOutOfLineLockable, FileEdgeTy>;
  using ThisGraph =
      LC_CSR_CSC_Graph<NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable,
                       UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy>;

public:
  using GraphNode = uint32_t;

protected:
  // retypedefs of base class
  using EdgeData = LargeArray<EdgeTy>;
  using EdgeDst = LargeArray<uint32_t>;
  using EdgeIndData = LargeArray<uint64_t>;

public:
  using edge_iterator =
      boost::counting_iterator<typename EdgeIndData::value_type>;
  using edge_data_reference = typename EdgeData::reference;

protected:
  EdgeIndData inEdgeIndData;
  EdgeDst inEdgeDst;
  using EdgeDataRep =
      typename std::conditional<EdgeDataByValue, EdgeData, EdgeIndData>::type;
  EdgeDataRep inEdgeData;

  using edge_sort_iterator =
      internal::EdgeSortIterator<GraphNode, typename EdgeIndData::value_type,
                                 EdgeDst, EdgeDataRep>;

  edge_sort_iterator in_edge_sort_begin(GraphNode N) {
    return edge_sort_iterator(*in_raw_begin(N), &inEdgeDst, &inEdgeData);
  }

  edge_sort_iterator in_edge_sort_end(GraphNode N) {
    return edge_sort_iterator(*in_raw_end(N), &inEdgeDst, &inEdgeData);
  }

  template <bool A                            = EdgeDataByValue,
            typename std::enable_if<A>::type* = nullptr>
  void createEdgeData(const uint64_t e_new, const uint64_t e) {
    BaseGraph::edgeDataCopy(inEdgeData, BaseGraph::edgeData, e_new, e);
  }

  template <bool A                             = EdgeDataByValue,
            typename std::enable_if<!A>::type* = nullptr>
  void createEdgeData(const uint64_t e_new, const uint64_t e) {
    if (!std::is_void<EdgeTy>::value) {
      inEdgeData[e_new] = e;
    }
  }

  void determineInEdgeIndices(EdgeIndData& dataBuffer) {
    // counting outgoing edges in the tranpose graph by
    // counting incoming edges in the original graph
    galois::do_all(galois::iterate(UINT64_C(0), BaseGraph::numEdges),
                   [&](uint64_t e) {
                     auto dst = BaseGraph::edgeDst[e];
                     __sync_add_and_fetch(&(dataBuffer[dst]), 1);
                   });

    // prefix sum calculation of the edge index array
    for (uint32_t n = 1; n < BaseGraph::numNodes; ++n) {
      dataBuffer[n] += dataBuffer[n - 1];
    }

    // copy over the new tranposed edge index data
    inEdgeIndData.allocateInterleaved(BaseGraph::numNodes);
    galois::do_all(galois::iterate(UINT64_C(0), BaseGraph::numNodes),
                   [&](uint64_t n) { inEdgeIndData[n] = dataBuffer[n]; });
  }

  void determineInEdgeDestAndData(EdgeIndData& dataBuffer) {
    // after this block dataBuffer[i] will now hold number of edges that all
    // nodes before the ith node have; used to determine where to start
    // saving an edge for a node
    if (BaseGraph::numNodes >= 1) {
      dataBuffer[0] = 0;
      galois::do_all(galois::iterate(UINT64_C(1), BaseGraph::numNodes),
                     [&](uint64_t n) { dataBuffer[n] = inEdgeIndData[n - 1]; });
    }

    // allocate edge dests and data
    inEdgeDst.allocateInterleaved(BaseGraph::numEdges);

    if (!std::is_void<EdgeTy>::value) {
      inEdgeData.allocateInterleaved(BaseGraph::numEdges);
    }

    galois::do_all(
        galois::iterate(UINT64_C(0), BaseGraph::numNodes), [&](uint64_t src) {
          // e = start index into edge array for a particular node
          uint64_t e = (src == 0) ? 0 : BaseGraph::edgeIndData[src - 1];

          // get all outgoing edges of a particular node in the non-transpose
          // and convert to incoming
          while (e < BaseGraph::edgeIndData[src]) {
            // destination nodde
            auto dst = BaseGraph::edgeDst[e];
            // location to save edge
            auto e_new = __sync_fetch_and_add(&(dataBuffer[dst]), 1);
            // save src as destination
            inEdgeDst[e_new] = src;
            // edge data to "new" array
            createEdgeData(e_new, e);
            e++;
          }
        });
  }

public:
  LC_CSR_CSC_Graph() = default;
  LC_CSR_CSC_Graph(LC_CSR_CSC_Graph&& rhs) = default;
  LC_CSR_CSC_Graph& operator=(LC_CSR_CSC_Graph&&) = default;

  // Construction functions

  void constructIncomingEdges() {
    galois::StatTimer incomingEdgeConstructTimer("IncomingEdgeConstruct");
    incomingEdgeConstructTimer.start();

    // initialize the temp array
    EdgeIndData dataBuffer;
    dataBuffer.allocateInterleaved(BaseGraph::numNodes);
    galois::do_all(galois::iterate(UINT64_C(0), BaseGraph::numNodes),
                   [&](uint64_t n) { dataBuffer[n] = 0; });

    determineInEdgeIndices(dataBuffer);
    determineInEdgeDestAndData(dataBuffer);

    incomingEdgeConstructTimer.stop();
  }

  // Access functions

  edge_iterator in_raw_begin(GraphNode N) const {
    return edge_iterator((N == 0) ? 0 : inEdgeIndData[N - 1]);
  }

  edge_iterator in_raw_end(GraphNode N) const {
    return edge_iterator(inEdgeIndData[N]);
  }

  edge_iterator in_edge_begin(GraphNode N,
                              MethodFlag mflag = MethodFlag::WRITE) {
    BaseGraph::acquireNode(N, mflag);
    if (!HasNoLockable && galois::runtime::shouldLock(mflag)) {
      for (edge_iterator ii = in_raw_begin(N), ee = in_raw_end(N); ii != ee;
           ++ii) {
        BaseGraph::acquireNode(inEdgeDst[*ii], mflag);
      }
    }
    return in_raw_begin(N);
  }

  edge_iterator in_edge_end(GraphNode N, MethodFlag mflag = MethodFlag::WRITE) {
    BaseGraph::acquireNode(N, mflag);
    return in_raw_end(N);
  }

  runtime::iterable<NoDerefIterator<edge_iterator>>
  in_edges(GraphNode N, MethodFlag mflag = MethodFlag::WRITE) {
    return internal::make_no_deref_range(in_edge_begin(N, mflag),
                                         in_edge_end(N, mflag));
  }

  GraphNode getInEdgeDst(edge_iterator ni) const { return inEdgeDst[*ni]; }

  template <bool A                            = EdgeDataByValue,
            typename std::enable_if<A>::type* = nullptr>
  edge_data_reference
  getInEdgeData(edge_iterator ni, MethodFlag = MethodFlag::UNPROTECTED) const {
    return inEdgeData[*ni];
  }

  template <bool A                            = EdgeDataByValue,
            typename std::enable_if<A>::type* = nullptr>
  edge_data_reference getInEdgeData(edge_iterator ni,
                                    MethodFlag = MethodFlag::UNPROTECTED) {
    return inEdgeData[*ni];
  }

  template <bool A                             = EdgeDataByValue,
            typename std::enable_if<!A>::type* = nullptr>
  edge_data_reference
  getInEdgeData(edge_iterator ni, MethodFlag = MethodFlag::UNPROTECTED) const {
    return BaseGraph::edgeData[inEdgeData[*ni]];
  }

  template <bool A                             = EdgeDataByValue,
            typename std::enable_if<!A>::type* = nullptr>
  edge_data_reference getInEdgeData(edge_iterator ni,
                                    MethodFlag = MethodFlag::UNPROTECTED) {
    return BaseGraph::edgeData[inEdgeData[*ni]];
  }

  const EdgeIndData& getInEdgePrefixSum() const { return inEdgeIndData; }

  // Utility

  void sortInEdgesByDst(GraphNode N, MethodFlag mflag = MethodFlag::WRITE) {
    BaseGraph::acquireNode(N, mflag);
    // depending on value/ref the type of EdgeSortValue changes
    using EdgeSortVal = EdgeSortValue<
        GraphNode,
        typename std::conditional<EdgeDataByValue, EdgeTy, uint64_t>::type>;

    std::sort(in_edge_sort_begin(N), in_edge_sort_end(N),
              [=](const EdgeSortVal& e1, const EdgeSortVal& e2) {
                return e1.dst < e2.dst;
              });
  }

  void sortAllInEdgesByDst(MethodFlag mflag = MethodFlag::WRITE) {
    galois::do_all(
        galois::iterate((size_t)0, this->size()),
        [=](GraphNode N) { this->sortInEdgesByDst(N, mflag); },
        galois::no_stats(), galois::steal());
  }

  void readAndConstructBiGraphFromGRFile(const std::string& filename) {
    this->readGraphFromGRFile(filename);
    constructIncomingEdges();
  }
};

} // namespace graphs
} // namespace galois
#endif