memScalGraph.h

Go to the documentation of this file.

/*
 * memScalGraph.h
 *
 *  Created on: Mar 4, 2013
 *      Author: nyadav
 */

#ifndef GALOIS_GRAPH_MEMSCALGRAPH_H
#define GALOIS_GRAPH_MEMSCALGRAPH_H

#include "Galois/Bag.h"
#include "Galois/Graph/Details.h"
#include "Galois/Runtime/Context.h"
#include "Galois/Runtime/MethodFlags.h"

#include "Galois/gdeque.h"

#include <boost/functional.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/iterator/filter_iterator.hpp>

#include <algorithm>
#include <map>
#include <set>
#include <vector>

namespace Galois {
namespace Graph {

template<typename NodeTy, typename EdgeTy, bool Directional>
class MemScalGraph : private boost::noncopyable {
  template<typename T>
  struct first_eq_and_valid {
    T N2;
    first_eq_and_valid(T& n) :N2(n) {}
    template <typename T2>
    bool operator()(const T2& ii) const {
      return ii.first() == N2 && ii.first();
    }
  };
  struct first_not_valid {
    template <typename T2>
    bool operator()(const T2& ii) const { return !ii.first();}
  };

  struct gNode: public Galois::Runtime::Lockable {
    typedef GraphImpl::EdgeItem<gNode, EdgeTy, Directional> EITy;


    typedef Galois::gdeque<EITy,32> EdgesTy;
    typedef typename EdgesTy::iterator iterator;

    EdgesTy edges;
    NodeTy data;


    template<typename... Args>
    gNode(Args&&... args): data(std::forward<Args>(args)...) { }

    iterator begin() { return edges.begin(); }
    iterator end()   { return edges.end();  }

    void erase(iterator ii) {
      *ii = edges.back();
      edges.pop_back();
    }

    void erase(gNode* N) {
      iterator ii = find(N);
      if (ii != end())
        edges.erase(ii);
    }

    iterator find(gNode* N) {
      return std::find_if(begin(), end(), first_eq_and_valid<gNode*>(N));
    }


    template<typename... Args>
    iterator createEdge(gNode* N, EdgeTy* v, Args&&... args) {
      edges.push_front(EITy(N, v, std::forward<Args>(args)...));
      return edges.begin();
    }

    template<typename... Args>
    iterator createEdgeWithReuse(gNode* N, EdgeTy* v, Args&&... args) {
      //First check for holes
      iterator ii = std::find_if(begin(), end(), first_not_valid());
      if (ii != end()) {
        *ii = EITy(N, v, std::forward<Args>(args)...);
        return ii;
      }
       edges.push_front(EITy(N, v, std::forward<Args>(args)...));
       return edges.begin();
    }
  };

  //The graph manages the lifetimes of the data in the nodes and edges
  typedef Galois::InsertBag<gNode> NodeListTy;
  NodeListTy nodes;

  GraphImpl::EdgeFactory<EdgeTy> edges;

  //Helpers for iterator classes
  struct is_node : public std::unary_function<gNode&, bool>{
    bool operator() (const gNode& g) const { return true; }
  };
  struct is_edge : public std::unary_function<typename gNode::EITy&, bool> {
    bool operator()(typename gNode::EITy& e) const { return true; }
  };
  struct makeGraphNode: public std::unary_function<gNode&, gNode*> {
    gNode* operator()(gNode& data) const { return &data; }
  };

public:
  typedef gNode* GraphNode;
  typedef EdgeTy edge_type;
  typedef NodeTy node_type;
  typedef typename  gNode::iterator edge_iterator;
  typedef typename gNode::EITy::reference edge_data_reference;
  typedef boost::transform_iterator<makeGraphNode,
          boost::filter_iterator<is_node,
                   typename NodeListTy::iterator> > iterator;

private:
  template<typename... Args>
  edge_iterator createEdgeWithReuse(GraphNode src, GraphNode dst, Galois::MethodFlag mflag, Args&&... args) {
    assert(src);
    assert(dst);
    Galois::Runtime::checkWrite(mflag, true);
    Galois::Runtime::acquire(src, mflag);
    typename gNode::iterator ii = src->find(dst);
    if (ii == src->end()) {
      if (Directional) {
        ii = src->createEdgeWithReuse(dst, 0, std::forward<Args>(args)...);
      } else {
        Galois::Runtime::acquire(dst, mflag);
        EdgeTy* e = edges.mkEdge(std::forward<Args>(args)...);
        ii = dst->createEdgeWithReuse(src, e, std::forward<Args>(args)...);
        ii = src->createEdgeWithReuse(dst, e, std::forward<Args>(args)...);
      }
    }
    //return boost::make_filter_iterator(is_edge(), ii, src->end());
    return ii;
  }

  template<typename... Args>
  edge_iterator createEdge(GraphNode src, GraphNode dst, Galois::MethodFlag mflag, Args&&... args) {
    assert(src);
    assert(dst);
    Galois::Runtime::checkWrite(mflag, true);
    Galois::Runtime::acquire(src, mflag);
    typename gNode::iterator ii = src->end();
    if (ii == src->end()) {
      if (Directional) {
        ii = src->createEdge(dst, 0, std::forward<Args>(args)...);
      } else {
        Galois::Runtime::acquire(dst, mflag);
        EdgeTy* e = edges.mkEdge(std::forward<Args>(args)...);
        ii = dst->createEdge(src, e, std::forward<Args>(args)...);
        ii = src->createEdge(dst, e, std::forward<Args>(args)...);
      }
    }
    return ii;
  }

public:
  template<typename... Args>
  GraphNode createNode(Args&&... args) {
    gNode* N = &(nodes.emplace(std::forward<Args>(args)...));
    return GraphNode(N);
  }

  void addNode(const GraphNode& n, Galois::MethodFlag mflag = MethodFlag::ALL) {
    Galois::Runtime::checkWrite(mflag, true);
    Galois::Runtime::acquire(n, mflag);
  }

  NodeTy& getData(const GraphNode& n, Galois::MethodFlag mflag = MethodFlag::ALL) const {
    assert(n);
    Galois::Runtime::checkWrite(mflag, false);
    Galois::Runtime::acquire(n, mflag);
    return n->data;
  }

  bool containsNode(const GraphNode& n, Galois::MethodFlag mflag = MethodFlag::ALL) const {
    assert(n);
    Galois::Runtime::acquire(n, mflag);
  }



  edge_iterator addEdge(GraphNode src, GraphNode dst, Galois::MethodFlag mflag = MethodFlag::ALL) {
    return createEdgeWithReuse(src, dst, mflag);
  }

  template<typename... Args>
  edge_iterator addMultiEdge(GraphNode src, GraphNode dst, Galois::MethodFlag mflag, Args&&... args) {
    return createEdge(src, dst, mflag, std::forward<Args>(args)...);
  }


  edge_iterator findEdge(GraphNode src, GraphNode dst, Galois::MethodFlag mflag = MethodFlag::ALL) {
    assert(src);
    assert(dst);
    Galois::Runtime::acquire(src, mflag);
    /*return boost::make_filter_iterator(is_edge(), src->find(dst), src->end());*/
    return src->find(dst);
  }

  edge_data_reference getEdgeData(edge_iterator ii, Galois::MethodFlag mflag = MethodFlag::NONE) const {

    Galois::Runtime::checkWrite(mflag, false);
    Galois::Runtime::acquire(ii->first(), mflag);
    return *ii->second();
  }

  GraphNode getEdgeDst(edge_iterator ii) {

    return GraphNode(ii->first());
  }


  edge_iterator edge_begin(GraphNode N, Galois::MethodFlag mflag = MethodFlag::ALL) {
    assert(N);
    Galois::Runtime::acquire(N, mflag);

    if (Galois::Runtime::shouldLock(mflag)) {
      for (typename gNode::iterator ii = N->begin(), ee = N->end(); ii != ee; ++ii) {

          Galois::Runtime::acquire(ii->first(), mflag);
      }
    }
    return N->begin();
  }

  edge_iterator edge_end(GraphNode N, Galois::MethodFlag mflag = MethodFlag::ALL) {
    assert(N);
    // Not necessary; no valid use for an end pointer should ever require it
    //if (shouldLock(mflag))
    //  acquire(N);
    return N->end();
  }

  detail::EdgesIterator<MemScalGraph> out_edges(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
    return detail::EdgesIterator<MemScalGraph>(*this, N, mflag);
  }

  iterator begin() {
    return boost::make_transform_iterator(nodes.begin(),makeGraphNode());
  }

  iterator end() {
    return boost::make_transform_iterator(nodes.end(),makeGraphNode());
  }

  typedef iterator local_iterator;

  local_iterator local_begin() {
          return boost::make_transform_iterator(nodes.local_begin(),makeGraphNode());
  }

  local_iterator local_end() {
  return boost::make_transform_iterator(nodes.local_end(),makeGraphNode());

  }

  unsigned int size() {
    return std::distance(begin(), end());
  }

  size_t sizeOfEdgeData() const {
    return gNode::EITy::sizeOfSecond();
  }

  MemScalGraph() { }
};

}
}


#endif

---