FileGraph.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_FILEGRAPH_H
#define GALOIS_GRAPHS_FILEGRAPH_H

#include <cstring>
#include <deque>
#include <type_traits>
#include <vector>

#include <boost/iterator/counting_iterator.hpp>
#include <boost/iterator/transform_iterator.hpp>

#include "galois/config.h"
#include "galois/Endian.h"
#include "galois/MethodFlags.h"
#include "galois/LargeArray.h"
#include "galois/graphs/Details.h"
#include "galois/graphs/GraphHelpers.h"
#include "galois/runtime/Context.h"
#include "galois/substrate/CacheLineStorage.h"
#include "galois/substrate/CompilerSpecific.h"
#include "galois/substrate/NumaMem.h"
#include "galois/Reduction.h"

namespace galois {
namespace graphs {

// XXX(ddn): Refactor to eliminate OCFileGraph

class FileGraph {
public:
  using GraphNode = uint64_t;

private:
  struct Convert32 : public std::unary_function<uint32_t, uint32_t> {
    uint32_t operator()(uint32_t x) const { return convert_le32toh(x); }
  };

  struct Convert64 : public std::unary_function<uint64_t, uint64_t> {
    uint64_t operator()(uint64_t x) const { return convert_le64toh(x); }
  };

  struct mapping {
    void* ptr;
    size_t len;
  };

  std::deque<mapping> mappings;
  std::deque<int> fds;

  uint64_t sizeofEdge;
  uint64_t numNodes;
  uint64_t numEdges;

  uint64_t* outIdx;
  void* outs;
  char* edgeData;

  int graphVersion;

  uint64_t nodeOffset;
  uint64_t edgeOffset;

  // graph reading speed variables
  galois::GAccumulator<uint64_t> numBytesReadIndex, numBytesReadEdgeDst,
      numBytesReadEdgeData;

  void move_assign(FileGraph&&);
  uint64_t getEdgeIdx(GraphNode src, GraphNode dst);

  void* raw_neighbor_begin(GraphNode N);
  void* raw_neighbor_end(GraphNode N);

  void fromMem(void* m, uint64_t nodeOffset, uint64_t edgeOffset, uint64_t);

  void* fromGraph(FileGraph& g, size_t sizeofEdgeData);

  size_t findIndex(size_t nodeSize, size_t edgeSize, size_t targetSize,
                   size_t lb, size_t ub);

  void fromFileInterleaved(const std::string& filename, size_t sizeofEdgeData);

  void pageInByNode(size_t id, size_t total, size_t sizeofEdgeData);

protected:
  void* fromArrays(uint64_t* outIdx, uint64_t numNodes, void* outs,
                   uint64_t numEdges, char* edgeData, size_t sizeofEdgeData,
                   uint64_t nodeOffset, uint64_t edgeOffset, bool converted,
                   int oGraphVersion = 1);

public:
  void reset_byte_counters() {
    numBytesReadEdgeDst.reset();
    numBytesReadIndex.reset();
    numBytesReadEdgeData.reset();
  }

  uint64_t num_bytes_read() {
    return numBytesReadEdgeDst.reduce() + numBytesReadEdgeData.reduce() +
           numBytesReadIndex.reduce();
  }

  // Node Handling

  bool containsNode(const GraphNode n) const {
    return n + nodeOffset < numNodes;
  }

  // Edge Handling

  template <typename EdgeTy>
  EdgeTy& getEdgeData(GraphNode src, GraphNode dst) {
    assert(sizeofEdge == sizeof(EdgeTy));
    numBytesReadEdgeData += sizeof(EdgeTy);
    return reinterpret_cast<EdgeTy*>(edgeData)[getEdgeIdx(src, dst)];
  }

  using edge_iterator = boost::counting_iterator<uint64_t>;

  edge_iterator edge_begin(GraphNode N);
  edge_iterator edge_end(GraphNode N);

  runtime::iterable<NoDerefIterator<edge_iterator>> edges(GraphNode N) {
    return internal::make_no_deref_range(edge_begin(N), edge_end(N));
  }

  runtime::iterable<NoDerefIterator<edge_iterator>> out_edges(GraphNode N) {
    return edges(N);
  }

  template <typename EdgeTy, typename CompTy>
  void sortEdgesByEdgeData(GraphNode N,
                           const CompTy& comp = std::less<EdgeTy>()) {
    if (graphVersion == 1) {
      typedef LargeArray<uint32_t> EdgeDst;
      typedef LargeArray<EdgeTy> EdgeData;

      typedef internal::EdgeSortIterator<GraphNode, uint64_t, EdgeDst, EdgeData,
                                         Convert32>
          edge_sort_iterator;

      EdgeDst edgeDst(outs, numEdges);
      EdgeData ed(edgeData, numEdges);

      edge_sort_iterator begin(
          std::distance((uint32_t*)outs, (uint32_t*)raw_neighbor_begin(N)),
          &edgeDst, &ed);
      edge_sort_iterator end(
          std::distance((uint32_t*)outs, (uint32_t*)raw_neighbor_end(N)),
          &edgeDst, &ed);
      std::sort(begin, end,
                internal::EdgeSortCompWrapper<EdgeSortValue<GraphNode, EdgeTy>,
                                              CompTy>(comp));
    } else if (graphVersion == 2) {
      typedef LargeArray<uint64_t> EdgeDst;
      typedef LargeArray<EdgeTy> EdgeData;

      typedef internal::EdgeSortIterator<GraphNode, uint64_t, EdgeDst, EdgeData,
                                         Convert64>
          edge_sort_iterator;

      EdgeDst edgeDst(outs, numEdges);
      EdgeData ed(edgeData, numEdges);

      edge_sort_iterator begin(
          std::distance((uint64_t*)outs, (uint64_t*)raw_neighbor_begin(N)),
          &edgeDst, &ed);
      edge_sort_iterator end(
          std::distance((uint64_t*)outs, (uint64_t*)raw_neighbor_end(N)),
          &edgeDst, &ed);
      std::sort(begin, end,
                internal::EdgeSortCompWrapper<EdgeSortValue<GraphNode, EdgeTy>,
                                              CompTy>(comp));
    } else {
      GALOIS_DIE("unknown file version: ", graphVersion);
    }
  }

  template <typename EdgeTy, typename CompTy>
  void sortEdges(GraphNode N, const CompTy& comp) {
    if (graphVersion == 1) {
      typedef LargeArray<uint32_t> EdgeDst;
      typedef LargeArray<EdgeTy> EdgeData;
      typedef internal::EdgeSortIterator<GraphNode, uint64_t, EdgeDst, EdgeData,
                                         Convert32>
          edge_sort_iterator;

      EdgeDst edgeDst(outs, numEdges);
      EdgeData ed(edgeData, numEdges);

      edge_sort_iterator begin(
          std::distance((uint32_t*)outs, (uint32_t*)raw_neighbor_begin(N)),
          &edgeDst, &ed);
      edge_sort_iterator end(
          std::distance((uint32_t*)outs, (uint32_t*)raw_neighbor_end(N)),
          &edgeDst, &ed);
      std::sort(begin, end, comp);
    } else if (graphVersion == 2) {
      typedef LargeArray<uint64_t> EdgeDst;
      typedef LargeArray<EdgeTy> EdgeData;
      typedef internal::EdgeSortIterator<GraphNode, uint64_t, EdgeDst, EdgeData,
                                         Convert64>
          edge_sort_iterator;

      EdgeDst edgeDst(outs, numEdges);
      EdgeData ed(edgeData, numEdges);

      edge_sort_iterator begin(
          std::distance((uint64_t*)outs, (uint64_t*)raw_neighbor_begin(N)),
          &edgeDst, &ed);
      edge_sort_iterator end(
          std::distance((uint64_t*)outs, (uint64_t*)raw_neighbor_end(N)),
          &edgeDst, &ed);
      std::sort(begin, end, comp);
    } else {
      GALOIS_DIE("unknown file version: ", graphVersion);
    }
  }

  // template<typename EdgeTy>
  // const EdgeTy& getEdgeData(edge_iterator it) const {
  //  assert(edgeData);
  //  return reinterpret_cast<const EdgeTy*>(edgeData)[*it];
  //}

  template <typename EdgeTy>
  EdgeTy& getEdgeData(edge_iterator it) {
    assert(edgeData);
    numBytesReadEdgeData += sizeof(EdgeTy);
    return reinterpret_cast<EdgeTy*>(edgeData)[*it];
  }

  GraphNode getEdgeDst(edge_iterator it);

  typedef boost::transform_iterator<Convert32, uint32_t*> neighbor_iterator;
  typedef boost::transform_iterator<Convert32, uint32_t*> node_id_iterator;
  typedef boost::transform_iterator<Convert64, uint64_t*> edge_id_iterator;
  typedef boost::counting_iterator<uint64_t> iterator;

  neighbor_iterator neighbor_begin(GraphNode N) {
    return boost::make_transform_iterator((uint32_t*)raw_neighbor_begin(N),
                                          Convert32());
  }

  neighbor_iterator neighbor_end(GraphNode N) {
    return boost::make_transform_iterator((uint32_t*)raw_neighbor_end(N),
                                          Convert32());
  }

  template <typename EdgeTy>
  EdgeTy* edge_data_begin() const {
    assert(edgeData);
    return reinterpret_cast<EdgeTy*>(edgeData);
  }

  template <typename EdgeTy>
  EdgeTy* edge_data_end() const {
    assert(edgeData);
    assert(sizeof(EdgeTy) == sizeofEdge);
    EdgeTy* r = reinterpret_cast<EdgeTy*>(edgeData);
    return &r[numEdges];
  }

  iterator begin() const;
  iterator end() const;

  typedef std::pair<iterator, iterator> NodeRange;
  typedef std::pair<edge_iterator, edge_iterator> EdgeRange;
  typedef std::pair<NodeRange, EdgeRange> GraphRange;

  GraphRange divideByNode(size_t nodeSize, size_t edgeSize, size_t id,
                          size_t total);

  GraphRange divideByEdge(size_t nodeSize, size_t edgeSize, size_t id,
                          size_t total);
  node_id_iterator node_id_begin() const;
  node_id_iterator node_id_end() const;
  edge_id_iterator edge_id_begin() const;
  edge_id_iterator edge_id_end() const;

  bool hasNeighbor(GraphNode N1, GraphNode N2);

  size_t size() const { return numNodes; }

  size_t sizeEdges() const { return numEdges; }

  size_t edgeSize() const { return sizeofEdge; }

  FileGraph();

  FileGraph(const FileGraph&);
  FileGraph& operator=(const FileGraph&);
  FileGraph(FileGraph&&);
  FileGraph& operator=(FileGraph&&);
  ~FileGraph();

  void fromFile(const std::string& filename);

  void partFromFile(const std::string& filename, NodeRange nrange,
                    EdgeRange erange, bool numaMap = false);

  template <typename EdgeTy>
  void fromFileInterleaved(
      const std::string& filename,
      typename std::enable_if<!std::is_void<EdgeTy>::value>::type* = 0) {
    fromFileInterleaved(filename, sizeof(EdgeTy));
  }

  template <typename EdgeTy>
  void fromFileInterleaved(
      const std::string& filename,
      typename std::enable_if<std::is_void<EdgeTy>::value>::type* = 0) {
    fromFileInterleaved(filename, 0);
  }

  template <typename T>
  T* fromGraph(FileGraph& g) {
    return reinterpret_cast<T*>(fromGraph(g, sizeof(T)));
  }

  void toFile(const std::string& file);
};

class FileGraphWriter : public FileGraph {
  std::vector<uint64_t> outIdx;
  std::vector<uint32_t> starts;
  std::vector<uint32_t> outs;
  std::vector<uint64_t> starts64;
  std::vector<uint64_t> outs64;

  size_t sizeofEdgeData;
  size_t numNodes;
  size_t numEdges;

public:
  FileGraphWriter() : sizeofEdgeData(0), numNodes(0), numEdges(0) {}

  void setNumNodes(size_t n) { numNodes = n; }
  void setNumEdges(size_t n) { numEdges = n; }
  void setSizeofEdgeData(size_t n) { sizeofEdgeData = n; }

  void phase1() { outIdx.resize(numNodes); }

  void incrementDegree(size_t id, int delta = 1) {
    assert(id < numNodes);
    outIdx[id] += delta;
  }

  void phase2() {
    if (numNodes == 0)
      return;

    // Turn counts into partial sums
    auto prev = outIdx.begin();
    for (auto ii = outIdx.begin() + 1, ei = outIdx.end(); ii != ei;
         ++ii, ++prev) {
      *ii += *prev;
    }
    assert(outIdx[numNodes - 1] == numEdges);

    if (numNodes <= std::numeric_limits<uint32_t>::max()) {
      // version 1
      starts.resize(numNodes);
      outs.resize(numEdges);
    } else {
      // version 2
      starts64.resize(numNodes);
      outs64.resize(numEdges);
    }
  }

  size_t addNeighbor(size_t src, size_t dst) {
    size_t base = src ? outIdx[src - 1] : 0;

    if (numNodes <= std::numeric_limits<uint32_t>::max()) {
      // version 1
      size_t idx = base + starts[src]++;
      assert(idx < outIdx[src]);
      outs[idx] = dst;
      return idx;
    } else {
      // version 2
      size_t idx = base + (starts64)[src]++;
      assert(idx < outIdx[src]);
      outs64[idx] = dst;
      return idx;
    }
  }

  template <typename T>
  T* finish() {
    void* ret;
    if (numNodes <= std::numeric_limits<uint32_t>::max()) {
      // version 1
      ret = fromArrays(&outIdx[0], numNodes, &outs[0], numEdges, nullptr,
                       sizeofEdgeData, 0, 0, false, 1);
      starts.clear();
      outs.clear();
    } else {
      // version 2
      ret = fromArrays(&outIdx[0], numNodes, &outs64[0], numEdges, nullptr,
                       sizeofEdgeData, 0, 0, false, 2);
    }

    outIdx.clear();
    return reinterpret_cast<T*>(ret);
  }
};

template <typename EdgeTy>
void makeSymmetric(FileGraph& in_graph, FileGraph& out) {
  typedef FileGraph::GraphNode GNode;
  typedef LargeArray<EdgeTy> EdgeData;
  typedef typename EdgeData::value_type edge_value_type;

  FileGraphWriter g;
  EdgeData edgeData;

  size_t numEdges = 0;

  for (FileGraph::iterator ii = in_graph.begin(), ei = in_graph.end(); ii != ei;
       ++ii) {
    GNode src = *ii;
    for (FileGraph::edge_iterator jj = in_graph.edge_begin(src),
                                  ej = in_graph.edge_end(src);
         jj != ej; ++jj) {
      GNode dst = in_graph.getEdgeDst(jj);
      numEdges += 1;
      if (src != dst)
        numEdges += 1;
    }
  }

  g.setNumNodes(in_graph.size());
  g.setNumEdges(numEdges);
  g.setSizeofEdgeData(EdgeData::has_value ? sizeof(edge_value_type) : 0);

  g.phase1();
  for (FileGraph::iterator ii = in_graph.begin(), ei = in_graph.end(); ii != ei;
       ++ii) {
    GNode src = *ii;
    for (FileGraph::edge_iterator jj = in_graph.edge_begin(src),
                                  ej = in_graph.edge_end(src);
         jj != ej; ++jj) {
      GNode dst = in_graph.getEdgeDst(jj);
      g.incrementDegree(src);
      if (src != dst)
        g.incrementDegree(dst);
    }
  }

  g.phase2();
  edgeData.create(numEdges);
  for (FileGraph::iterator ii = in_graph.begin(), ei = in_graph.end(); ii != ei;
       ++ii) {
    GNode src = *ii;
    for (FileGraph::edge_iterator jj = in_graph.edge_begin(src),
                                  ej = in_graph.edge_end(src);
         jj != ej; ++jj) {
      GNode dst = in_graph.getEdgeDst(jj);
      if (EdgeData::has_value) {
        edge_value_type& data = in_graph.getEdgeData<edge_value_type>(jj);
        edgeData.set(g.addNeighbor(src, dst), data);
        if (src != dst)
          edgeData.set(g.addNeighbor(dst, src), data);
      } else {
        g.addNeighbor(src, dst);
        if (src != dst)
          g.addNeighbor(dst, src);
      }
    }
  }

  edge_value_type* rawEdgeData = g.finish<edge_value_type>();
  if (EdgeData::has_value)
    std::uninitialized_copy(std::make_move_iterator(edgeData.begin()),
                            std::make_move_iterator(edgeData.end()),
                            rawEdgeData);

  out = std::move(g);
}

template <typename EdgeTy, typename PTy>
void permute(FileGraph& in_graph, const PTy& p, FileGraph& out) {
  typedef FileGraph::GraphNode GNode;
  typedef LargeArray<EdgeTy> EdgeData;
  typedef typename EdgeData::value_type edge_value_type;

  FileGraphWriter g;
  EdgeData edgeData;

  size_t numEdges = in_graph.sizeEdges();
  g.setNumNodes(in_graph.size());
  g.setNumEdges(numEdges);
  g.setSizeofEdgeData(EdgeData::has_value ? sizeof(edge_value_type) : 0);

  g.phase1();
  for (FileGraph::iterator ii = in_graph.begin(), ei = in_graph.end(); ii != ei;
       ++ii) {
    GNode src = *ii;
    for (FileGraph::edge_iterator jj = in_graph.edge_begin(src),
                                  ej = in_graph.edge_end(src);
         jj != ej; ++jj) {
      g.incrementDegree(p[src]);
    }
  }

  g.phase2();
  edgeData.create(numEdges);
  for (FileGraph::iterator ii = in_graph.begin(), ei = in_graph.end(); ii != ei;
       ++ii) {
    GNode src = *ii;
    for (FileGraph::edge_iterator jj = in_graph.edge_begin(src),
                                  ej = in_graph.edge_end(src);
         jj != ej; ++jj) {
      GNode dst = in_graph.getEdgeDst(jj);
      if (EdgeData::has_value) {
        edge_value_type& data = in_graph.getEdgeData<edge_value_type>(jj);
        edgeData.set(g.addNeighbor(p[src], p[dst]), data);
      } else {
        g.addNeighbor(p[src], p[dst]);
      }
    }
  }

  edge_value_type* rawEdgeData = g.finish<edge_value_type>();
  if (EdgeData::has_value)
    std::uninitialized_copy(std::make_move_iterator(edgeData.begin()),
                            std::make_move_iterator(edgeData.end()),
                            rawEdgeData);

  out = std::move(g);
}

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