Graph.h

Go to the documentation of this file.

#ifndef GALOIS_GRAPHS_GRAPH_H
#define GALOIS_GRAPHS_GRAPH_H

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

#include "Galois/ConflictFlags.h"
#include "Galois/Runtime/Support.h"
#include "Galois/Runtime/Context.h"
#include "Galois/Runtime/InsBag.h"
//#include "Galois/Runtime/MemRegionPool.h"
#include "LLVM/SmallVector.h"

using namespace GaloisRuntime;

namespace Galois {
namespace Graph {


template<typename T>
struct VoidWrapper {
  typedef T type;
  typedef T& ref_type;
  typedef const T& const_ref_type;
};

template<>
struct VoidWrapper<void> {
  struct unit { 
    bool operator<(const unit& a) {
      return true;
    }
  };
  typedef unit type;
  typedef unit ref_type;
  typedef const unit const_ref_type;
};

typedef VoidWrapper<void>::unit GraphUnit;

template<typename NTy>
struct NodeItem {
  NTy N;
  NodeItem(typename VoidWrapper<NTy>::const_ref_type n) : N(n) { }
  inline typename VoidWrapper<NTy>::ref_type getData() {
    return N;
  }
};

template<>
struct NodeItem<void> {
  NodeItem(VoidWrapper<void>::const_ref_type n) { }
  inline VoidWrapper<void>::ref_type getData() {
    return VoidWrapper<void>::ref_type();
  }
};

template<typename NTy, typename ETy>
struct EdgeItem {
  NTy N;
  ETy E;
  inline NTy getNeighbor() {
    return N;
  }
  inline ETy& getData() {
    return E;
  }
  inline EdgeItem(NTy& n) : N(n) {
  }
  inline EdgeItem(NTy& n, ETy e) : N(n), E(e) {
  }

  inline EdgeItem(){ }
};

template<typename NTy>
struct EdgeItem<NTy, void> {
  NTy N;
  inline NTy getNeighbor() {
    return N;
  }
  inline typename VoidWrapper<void>::ref_type getData() {
    return VoidWrapper<void>::ref_type();
  }
  inline EdgeItem(NTy& n) : N(n) {
  }
};


template<typename NodeTy, typename EdgeTy, bool Directional>
class FirstGraph {
public:
  typedef typename VoidWrapper<EdgeTy>::ref_type edge_reference;
  typedef typename VoidWrapper<EdgeTy>::const_ref_type const_edge_reference;
  typedef typename VoidWrapper<NodeTy>::ref_type node_reference;
  typedef typename VoidWrapper<NodeTy>::const_ref_type const_node_reference;

private:
  struct gNode: public GaloisRuntime::Lockable {
    typedef EdgeItem<gNode*, EdgeTy> EITy;
    typedef NodeItem<NodeTy> NITy;

    typedef llvm::SmallVector<EITy, 3> EdgesTy;
    typedef typename EdgesTy::iterator iterator;

    EdgesTy edges;
    NITy data;
    bool active;

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

    struct getNeigh : public std::unary_function<EITy, gNode*> {
      gNode* operator()(EITy& e) const { return e.getNeighbor(); }
    };

    typedef typename boost::transform_iterator<getNeigh, iterator> neighbor_iterator;

    neighbor_iterator neighbor_begin() {
      return boost::make_transform_iterator(begin(), getNeigh());
    }
    neighbor_iterator neighbor_end() {
      return boost::make_transform_iterator(end(), getNeigh());
    }

    gNode(const_node_reference d, bool a) :
      data(d), active(a) {
    }

    void prefetch_neighbors() {
      for (iterator ii = begin(), ee = end(); ii != ee; ++ii)
        if (ii->getNeighbor())
          __builtin_prefetch(ii->getNeighbor());
    }

    void eraseEdge(gNode* N) {
      for (iterator ii = begin(), ee = end(); ii != ee; ++ii) {
        if (ii->getNeighbor() == N) {
          edges.erase(ii);
          return;
        }
      }
    }

    edge_reference getEdgeData(gNode* N) {
      for (iterator ii = begin(), ee = end(); ii != ee; ++ii)
        if (ii->getNeighbor() == N)
          return ii->getData();
      assert(0 && "Edge doesn't exist");
      abort();
    }

    edge_reference getEdgeData(iterator ii) {
      return ii->getData();
    }

    edge_reference getOrCreateEdge(gNode* N) {
      for (iterator ii = begin(), ee = end(); ii != ee; ++ii)
        if (ii->getNeighbor() == N)
          return ii->getData();
      edges.push_back(EITy(N));
      return edges.back().getData();
    }

    edge_reference getOrCreateEdge(gNode* N,  const_edge_reference data) {
        for (iterator ii = begin(), ee = end(); ii != ee; ++ii)
                if (ii->getNeighbor() == N)
                        return ii->getData();

        edges.push_back(EITy(N, data));
        return edges.back().getData();
    }

    bool isActive() {
      return active;
    }

    bool hasNeighbor(gNode* N) {
      for (iterator ii = begin(), ee = end(); ii != ee; ++ii)
        if (ii->getNeighbor() == N)
          return true;
      return false;
    }
  };

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

  //GaloisRuntime::MemRegionPool<gNode> NodePool;

  //deal with the Node redirction
  node_reference getData(gNode* ID, Galois::MethodFlag mflag = ALL) {
    assert(ID);
    acquire(ID, mflag);
    return ID->data.getData();
  }

public:
  class GraphNode {
    friend class FirstGraph;
    FirstGraph* Parent;
    gNode* ID;

    explicit GraphNode(FirstGraph* p, gNode* id) :
      Parent(p), ID(id) {
    }

  public:
    GraphNode() :
      Parent(0), ID(0) {
    }

    void prefetch_all() {
      if (ID)
        ID->prefetch_neighbors();
    }

    node_reference getData(Galois::MethodFlag mflag = ALL) const {
      return Parent->getData(ID, mflag);
    }

    FirstGraph* getGraph() const {
      return Parent;
    }

    bool isNull() const {
      return !Parent;
    }

    bool operator!=(const GraphNode& rhs) const {
      return Parent != rhs.Parent || ID != rhs.ID;
    }

    bool operator==(const GraphNode& rhs) const {
      return Parent == rhs.Parent && ID == rhs.ID;
    }

    bool operator<(const GraphNode& rhs) const {
      return Parent < rhs.Parent || (Parent == rhs.Parent && ID < rhs.ID);
    }

    bool operator>(const GraphNode& rhs) const {
      return Parent > rhs.Parent || (Parent == rhs.Parent && ID > rhs.ID);
    }

    bool hasNeighbor(const GraphNode& N) const {
      return ID->hasNeighbor(N.ID);
    }
  };

private:
  // Helpers for the iterator classes
  class makeGraphNode: public std::unary_function<gNode, GraphNode> {
    FirstGraph* G;
  public:
    makeGraphNode(FirstGraph* g = 0) :
      G(g) {
    }
    GraphNode operator()(gNode& data) const {
      return GraphNode(G, &data);
    }
  };

  class makeGraphNodePtr: public std::unary_function<gNode*, GraphNode> {
    FirstGraph* G;
  public:
    makeGraphNodePtr(FirstGraph* g = 0) :
      G(g) {
    }
    GraphNode operator()(gNode* data) const {
      return GraphNode(G, data);
    }
  };

public:
  typedef EdgeTy EdgeDataTy;
  typedef NodeTy NodeDataTy;

  
  GraphNode createNode(const_node_reference n) {
    gNode N(n, false);
    return GraphNode(this, &(nodes.push(N)));
  }

  bool addNode(const GraphNode& n, Galois::MethodFlag mflag = ALL) {
    assert(n.ID);
    acquire(n.ID, mflag);
    bool oldActive = n.ID->active;
    if (!oldActive) {
      n.ID->active = true;
      //__sync_add_and_fetch(&numActive, 1);
    }
    return !oldActive;
  }

  //add a node and reserve the space for edges
  bool addNode(const GraphNode& n, int maxDegree, MethodFlag mflag = ALL) {
          assert(n.ID);
          acquire(n.ID, mflag);
          bool oldActive = n.ID->active;
          if (!oldActive) {
                  n.ID->active = true;
                  //__sync_add_and_fetch(&numActive, 1);
          }
          n.ID->edges.reserve(maxDegree);
          return !oldActive;
  }

  node_reference getData(const GraphNode& n, Galois::MethodFlag mflag = ALL) const {
    assert(n.ID);
    acquire(n.ID, mflag);
    return n.ID->data.getData();
  }

  bool containsNode(const GraphNode& n) const {
    return n.ID && (n.Parent == this) && n.ID->active;
  }

  // FIXME: incoming edges aren't handled here for directed graphs
  bool removeNode(GraphNode n, Galois::MethodFlag mflag = ALL) {
    assert(n.ID);
    acquire(n.ID, mflag);
    gNode* N = n.ID;
    bool wasActive = N->active;
    if (wasActive) {
      //__sync_sub_and_fetch(&numActive, 1);
      N->active = false;
      //erase the in-edges first
      for (unsigned int i = 0; i < N->edges.size(); ++i) {
        if (N->edges[i].getNeighbor() != N) // don't handle loops yet
          N->edges[i].getNeighbor()->eraseEdge(N);
      }
      N->edges.clear();
    }
    return wasActive;
  }


  void addEdge(GraphNode src, GraphNode dst,
               const_edge_reference data, 
               Galois::MethodFlag mflag = ALL) {
    assert(src.ID);
    assert(dst.ID);
    acquire(src.ID, mflag);

    if (Directional) {
      src.ID->getOrCreateEdge(dst.ID) = data;
    } else {
      acquire(dst.ID, mflag);
      EdgeTy& E1 = src.ID->getOrCreateEdge(dst.ID);
      EdgeTy& E2 = dst.ID->getOrCreateEdge(src.ID);
      if (src < dst)
        E1 = data;
      else
        E2 = data;
    }
  }

  void addEdge(GraphNode src, GraphNode dst, Galois::MethodFlag mflag = ALL) {
    assert(src.ID);
    assert(dst.ID);
    acquire(src.ID, mflag);
    if (Directional) {
      src.ID->getOrCreateEdge(dst.ID);
    } else {
      acquire(dst.ID, mflag);
      src.ID->getOrCreateEdge(dst.ID);
      dst.ID->getOrCreateEdge(src.ID);
    }
  }

  void removeEdge(GraphNode src, GraphNode dst, Galois::MethodFlag mflag = ALL) {
    assert(src.ID);
    assert(dst.ID);
    acquire(src.ID, mflag);
    if (Directional) {
      src.ID->eraseEdge(dst.ID);
    } else {
      acquire(dst.ID, mflag);
      src.ID->eraseEdge(dst.ID);
      dst.ID->eraseEdge(src.ID);
    }
  }

  edge_reference getEdgeData(GraphNode src, GraphNode dst,
      Galois::MethodFlag mflag = ALL) const {
    assert(src.ID);
    assert(dst.ID);

    //yes, fault on null (no edge)
    acquire(src.ID, mflag);

    if (Directional) {
      return src.ID->getEdgeData(dst.ID);
    } else {
      acquire(dst.ID, mflag);
      if (src < dst)
        return src.ID->getEdgeData(dst.ID);
      else
        return dst.ID->getEdgeData(src.ID);
    }
  }

   edge_reference getOrCreateEdge(GraphNode src, GraphNode dst,
                   const_edge_reference data, Galois::MethodFlag mflag = ALL) const {
     assert(src.ID);
     assert(dst.ID);

     acquire(src.ID, mflag);

     if (Directional) {
       return src.ID->getOrCreateEdge(dst.ID, data);
     } else {
       acquire(dst.ID, mflag);

       if (src < dst){
           dst.ID->getOrCreateEdge(src.ID, data);
           return src.ID->getOrCreateEdge(dst.ID, data);
       }
       else{
           src.ID->getOrCreateEdge(dst.ID, data);
           return dst.ID->getOrCreateEdge(src.ID, data);

       }
     }
   }


  int neighborsSize(GraphNode N, Galois::MethodFlag mflag = ALL) const {
    assert(N.ID);
    acquire(N.ID, mflag);
    return N.ID->edges.size();
  }

  typedef typename boost::transform_iterator<makeGraphNodePtr,
                                             typename gNode::neighbor_iterator>
                                               neighbor_iterator;

  neighbor_iterator neighbor_begin(GraphNode N, Galois::MethodFlag mflag = ALL) {
    assert(N.ID);
    acquire(N.ID, mflag);
    //    if (shouldLock(mflag)) {
    //Trust the compliler to remove this loop if the body disappears from the right mflag
    for (typename gNode::neighbor_iterator ii = N.ID->neighbor_begin(), ee =
           N.ID->neighbor_end(); ii != ee; ++ii) {
      //__builtin_prefetch(*ii);
      //if (shouldLock(mflag))
      acquire(*ii, mflag);
    }
    //}
    return boost::make_transform_iterator(N.ID->neighbor_begin(),
                                          makeGraphNodePtr(this));
  }

  neighbor_iterator neighbor_end(GraphNode N, Galois::MethodFlag mflag = ALL) {
    assert(N.ID);
    // Probably not necessary (no valid use for an end pointer should ever
    // require it)
    //if (shouldLock(mflag))
    //  acquire(N.ID);
    return boost::make_transform_iterator(N.ID->neighbor_end(),
                                          makeGraphNodePtr(this));
  }

  edge_reference getEdgeData(GraphNode src, neighbor_iterator dst,
      Galois::MethodFlag mflag = ALL) {
    assert(src.ID);

    //yes, fault on null (no edge)
    acquire(src.ID, mflag);

    if (Directional) {
      return src.ID->getEdgeData(dst.base().base());
    } else {
      if (src.ID < dst.base().base()->getNeighbor())
        return src.ID->getEdgeData(dst.base().base()->getNeighbor());
      else
        return dst.base().base()->getNeighbor()->getEdgeData(src.ID);
    }
  }

  //These are not thread safe!!
  typedef boost::transform_iterator<makeGraphNode,
            boost::filter_iterator<std::mem_fun_ref_t<bool, gNode>,
              typename NodeListTy::iterator> > active_iterator;

  active_iterator active_begin() {
    return boost::make_transform_iterator(
        boost::make_filter_iterator(
          std::mem_fun_ref(&gNode::isActive), nodes.begin(), nodes.end()),
        makeGraphNode(this));
  }

  active_iterator active_end() {
    return boost::make_transform_iterator(
        boost::make_filter_iterator(
          std::mem_fun_ref(&gNode::isActive), nodes.end(), nodes.end()), 
        makeGraphNode(this));
  }

  unsigned int size() {
    return std::distance(active_begin(), active_end());
  }

  FirstGraph() {
    reportStatSum("NodeSize", sizeof(gNode));
  }
};

}
}
#endif

---