FileGraph.h

Go to the documentation of this file.

#ifndef GALOIS_GRAPH_FILEGRAPH_H
#define GALOIS_GRAPH_FILEGRAPH_H

#include "Galois/Endian.h"
#include "Galois/MethodFlags.h"
#include "Galois/LargeArray.h"
#include "Galois/Graph/Details.h"
#include "Galois/Runtime/Context.h"
#include "Galois/Runtime/ll/CacheLineStorage.h"
#include "Galois/Runtime/ll/CompilerSpecific.h"

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

#include GALOIS_CXX11_STD_HEADER(type_traits)
//#include <fstream>

#include <string.h>

namespace Galois {
namespace Graph {

class FileGraph: private boost::noncopyable {
  friend class FileGraphAllocator;
public:
  typedef uint32_t GraphNode;

protected:
  void* volatile masterMapping;
  size_t masterLength;
  uint64_t sizeofEdge;
  int masterFD;

  uint64_t* outIdx;
  uint32_t* outs;

  char* edgeData;

  uint64_t numEdges;
  uint64_t numNodes;

  uint64_t getEdgeIdx(GraphNode src, GraphNode dst) const;
  uint32_t* raw_neighbor_begin(GraphNode N) const;
  uint32_t* raw_neighbor_end(GraphNode N) const;

  struct Convert32: public std::unary_function<uint32_t, uint32_t> {
    uint32_t operator()(uint32_t x) const {
      return convert_le32(x);
    }
  };
  
  struct Convert64: public std::unary_function<uint64_t,uint64_t> {
    uint64_t operator()(uint64_t x) const {
      return convert_le64(x);
    }
  };

  void parse(void* m);

  void structureFromMem(void* mem, size_t len, bool clone);

  void* structureFromArrays(uint64_t* outIdxs, uint64_t numNodes,
      uint32_t* outs, uint64_t numEdges, size_t sizeofEdgeData);

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

  size_t findIndex(size_t nodeSize, size_t edgeSize, size_t targetSize, size_t lb, size_t ub);
  
public:
  // Node Handling

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

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

  // Iterators
  typedef boost::counting_iterator<uint64_t> edge_iterator;
  edge_iterator edge_begin(GraphNode N) const;
  edge_iterator edge_end(GraphNode N) const;

  detail::EdgesWithNoFlagIterator<FileGraph> out_edges(GraphNode N) {
    return detail::EdgesWithNoFlagIterator<FileGraph>(*this, N);
  }

  template<typename EdgeTy, typename CompTy>
  void sortEdgesByEdgeData(GraphNode N, const CompTy& comp = std::less<EdgeTy>()) {
    typedef LargeArray<GraphNode> EdgeDst;
    typedef LargeArray<EdgeTy> EdgeData;
    typedef detail::EdgeSortIterator<GraphNode,uint64_t,EdgeDst,EdgeData> edge_sort_iterator;

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

    edge_sort_iterator begin(std::distance(outs, raw_neighbor_begin(N)), &edgeDst, &ed);
    edge_sort_iterator end(std::distance(outs, raw_neighbor_end(N)), &edgeDst, &ed);

    std::sort(begin, end, detail::EdgeSortCompWrapper<EdgeSortValue<GraphNode,EdgeTy>,CompTy>(comp));
  }

  template<typename EdgeTy, typename CompTy>
  void sortEdges(GraphNode N, const CompTy& comp) {
    typedef LargeArray<GraphNode> EdgeDst;
    typedef LargeArray<EdgeTy> EdgeData;
    typedef detail::EdgeSortIterator<GraphNode,uint64_t,EdgeDst,EdgeData> edge_sort_iterator;

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

    edge_sort_iterator begin(std::distance(outs, raw_neighbor_begin(N)), &edgeDst, &ed);
    edge_sort_iterator end(std::distance(outs, raw_neighbor_end(N)), &edgeDst, &ed);

    std::sort(begin, end, comp);
  }

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

  GraphNode getEdgeDst(edge_iterator it) const;

  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) const {
    return boost::make_transform_iterator(raw_neighbor_begin(N), Convert32());
  }

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

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

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

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

  std::pair<iterator,iterator> divideBy(size_t nodeSize, size_t edgeSize, unsigned id, unsigned 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;

  template<typename EdgeTy>
  EdgeTy& getEdgeData(neighbor_iterator it) {
    return reinterpret_cast<EdgeTy*>(edgeData)[std::distance(outs, it.base())];
  }

  bool hasNeighbor(GraphNode N1, GraphNode N2) const;

  unsigned int size() const { return numNodes; }

  unsigned int sizeEdges() const { return numEdges; }

  size_t edgeSize() const { return sizeofEdge; }

  FileGraph();
  ~FileGraph();

  void structureFromFile(const std::string& filename, bool preFault = true);

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

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

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

  template<typename T>
  T* structureFromArrays(uint64_t* outIdxs, uint64_t numNodes,
      uint32_t* outs, uint64_t numEdges) {
    return reinterpret_cast<T*>(structureFromArrays(outIdx, numNodes, outs, numEdges, sizeof(T)));
  }

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

  void structureToFile(const std::string& file);

  void swap(FileGraph& other);

  void cloneFrom(FileGraph& other);
};

class FileGraphWriter: public FileGraph {
  uint64_t *outIdx; // outIdxs
  uint32_t *starts;
  uint32_t *outs; // outs
  size_t sizeofEdgeData;

public:
  FileGraphWriter(): outIdx(0), starts(0), outs(0), sizeofEdgeData(0) { }

  ~FileGraphWriter() { 
    if (outIdx)
      delete [] outIdx;
    if (starts)
      delete [] starts;
    if (outs)
      delete [] outs;
  }

  void setNumNodes(uint64_t n) { this->numNodes = n; }
  void setNumEdges(uint64_t n) { this->numEdges = n; }
  void setSizeofEdgeData(size_t n) { sizeofEdgeData = n; }
  
  void phase1() { 
    assert(!outIdx);
    outIdx = new uint64_t[this->numNodes];
    memset(outIdx, 0, sizeof(*outIdx) * this->numNodes);
  }

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

  void phase2() {
    if (this->numNodes == 0)
      return;

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

    starts = new uint32_t[this->numNodes];
    memset(starts, 0, sizeof(*starts) * this->numNodes);

    outs = new uint32_t[this->numEdges];
  }

  size_t addNeighbor(size_t src, size_t dst) {
    size_t base = src ? outIdx[src-1] : 0;
    size_t idx = base + starts[src]++;
    assert(idx < outIdx[src]);
    outs[idx] = dst;
    return idx;
  }

  template<typename T>
  T* finish() { 
    void* ret = structureFromArrays(outIdx, this->numNodes, outs, this->numEdges, sizeofEdgeData);
    delete [] outIdx;
    outIdx = 0;
    delete [] starts;
    starts = 0;
    delete [] outs;
    outs = 0;
    return reinterpret_cast<T*>(ret);
  }
};

template<typename EdgeTy>
void makeSymmetric(FileGraph& in, 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.sizeEdges() * 2;
  g.setNumNodes(in.size());
  g.setNumEdges(numEdges);
  g.setSizeofEdgeData(EdgeData::has_value ? sizeof(edge_value_type) : 0);

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

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

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

  out.swap(g);
}

template<typename EdgeTy,typename PTy>
void permute(FileGraph& in, 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.sizeEdges();
  g.setNumNodes(in.size());
  g.setNumEdges(numEdges);
  g.setSizeofEdgeData(EdgeData::has_value ? sizeof(edge_value_type) : 0);

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

  g.phase2();
  edgeData.create(numEdges);
  for (FileGraph::iterator ii = in.begin(), ei = in.end(); ii != ei; ++ii) {
    GNode src = *ii;
    for (FileGraph::edge_iterator jj = in.edge_begin(src), ej = in.edge_end(src); jj != ej; ++jj) {
      GNode dst = in.getEdgeDst(jj);
      if (EdgeData::has_value) {
        edge_value_type& data = in.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::copy(edgeData.begin(), edgeData.end(), rawEdgeData);

  out.swap(g);
}

template<typename GraphTy,typename... Args>
GALOIS_ATTRIBUTE_DEPRECATED
void structureFromFile(GraphTy& g, const std::string& fname, Args&&... args) {
  FileGraph graph;
  graph.structureFromFile(fname);
  g.structureFromGraph(graph, std::forward<Args>(args)...);
}

}
}
#endif

---