Galois: FirstGraph.h Source File

00001 
00025 #ifndef GALOIS_GRAPH_FIRSTGRAPH_H
00026 #define GALOIS_GRAPH_FIRSTGRAPH_H
00027 
00028 #include "Galois/Bag.h"
00029 #include "Galois/Graph/Details.h"
00030 #include "Galois/Runtime/MethodFlags.h"
00031 
00032 #include "llvm/ADT/SmallVector.h"
00033 
00034 #include <boost/functional.hpp>
00035 #include <boost/iterator/transform_iterator.hpp>
00036 #include <boost/iterator/filter_iterator.hpp>
00037 
00038 #include <algorithm>
00039 #include <map>
00040 #include <set>
00041 #include <vector>
00042 
00043 namespace Galois {
00045 namespace Graph {
00046 
00047 namespace FirstGraphImpl {
00051 template<typename NTy, typename ETy, bool Directed>
00052 struct UEdgeInfoBase;
00053 
00054 template<typename NTy, typename ETy>
00055 struct UEdgeInfoBase<NTy, ETy, true> {
00056   typedef ETy& reference;
00057 
00058   NTy* N;
00059   ETy Ea;
00060 
00061   inline NTy*&       first()       { assert(N); return N; }
00062   inline NTy* const& first() const { assert(N); return N; }
00063   inline ETy*       second()       { return &Ea; }
00064   inline const ETy* second() const { return &Ea; }
00065 
00066   template<typename... Args>
00067   UEdgeInfoBase(NTy* n, ETy* v, Args&&... args) : N(n), Ea(std::forward<Args>(args)...) {}
00068 
00069   template<typename... Args>
00070   UEdgeInfoBase(ETy* v, Args&&... args) :Ea(std::forward<Args>(args)...) {}
00071   
00072   template<typename... Args>
00073   UEdgeInfoBase(NTy* n, ETy &v, Args&&... args): N(n) { Ea = v; }
00074 
00075   static size_t sizeOfSecond()     { return sizeof(ETy); }
00076 };
00077 
00078 template<typename NTy, typename ETy>
00079 struct UEdgeInfoBase<NTy, ETy, false> {
00080   typedef ETy& reference;
00081   
00082   NTy* N;
00083   ETy* Ea;
00084 
00085   inline NTy*&       first()       { assert(N); return N; }
00086   inline NTy* const& first() const { assert(N); return N; }
00087   inline ETy*       second()       { return Ea; }
00088   inline const ETy* second() const { return Ea; }
00089   template<typename... Args>
00090   UEdgeInfoBase(NTy* n, ETy* v, Args&&... args) : N(n), Ea(v) {}
00091   static size_t sizeOfSecond()     { return sizeof(ETy); }
00092 };
00093 
00094 template<typename NTy>
00095 struct UEdgeInfoBase<NTy, void, true> {
00096   typedef char& reference;
00097 
00098   NTy* N;
00099   inline NTy*&       first()        { return N; }
00100   inline NTy* const& first()  const { return N; }
00101   inline char*       second() const { return static_cast<char*>(NULL); }
00102   inline char*       addr()   const { return second(); }
00103   template<typename... Args>
00104   UEdgeInfoBase(NTy* n, void* v, Args&&... args) : N(n) {}
00105   static size_t sizeOfSecond()      { return 0; }
00106 };
00107 
00108 template<typename NTy>
00109 struct UEdgeInfoBase<NTy, void, false> {
00110   typedef char& reference;
00111 
00112   NTy* N;
00113   inline NTy*&       first()        { return N; }
00114   inline NTy* const& first()  const { return N; }
00115   inline char*       second() const { return static_cast<char*>(NULL); }
00116   inline char*       addr()   const { return second(); }
00117   template<typename... Args>
00118   UEdgeInfoBase(NTy* n, void* v, Args&&... args) : N(n) {}
00119   static size_t sizeOfSecond()      { return 0; }
00120 };
00121 
00122 template<typename ETy>
00123 struct EdgeFactory {
00124   Galois::Runtime::MM::FSBGaloisAllocator<ETy> mem;
00125   template<typename... Args>
00126   ETy* mkEdge(Args&&... args) {
00127     ETy* e = mem.allocate(1);
00128     mem.construct(e, std::forward<Args>(args)...);
00129     return e;
00130   }
00131   void delEdge(ETy* e) {
00132     mem.destroy(e);
00133     mem.deallocate(e, 1);
00134   }
00135   bool mustDel() const { return true; }
00136 };
00137 
00138 template<>
00139 struct EdgeFactory<void> {
00140   void* mkEdge() { return static_cast<void*>(NULL); }
00141   void delEdge(void*) {}
00142   bool mustDel() const { return false; }
00143 };
00144 
00145 } // end namespace impl
00146 
00197 template<typename NodeTy, typename EdgeTy, bool Directional,
00198   bool HasNoLockable=false
00199   >
00200 class FirstGraph : private boost::noncopyable {
00201 public:
00203   template<bool _has_no_lockable>
00204   struct with_no_lockable { typedef FirstGraph<NodeTy,EdgeTy,Directional,_has_no_lockable> type; };
00205 
00206 private:
00207   template<typename T>
00208   struct first_eq_and_valid {
00209     T N2;
00210     first_eq_and_valid(T& n) :N2(n) {}
00211     template <typename T2>
00212     bool operator()(const T2& ii) const { 
00213       return ii.first() == N2 && ii.first() && ii.first()->active;
00214     }
00215   };
00216 
00217   struct first_not_valid {
00218     template <typename T2>
00219     bool operator()(const T2& ii) const { return !ii.first() || !ii.first()->active; }
00220   };
00221   
00222   class gNode;
00223   struct gNodeTypes: public detail::NodeInfoBaseTypes<NodeTy, !HasNoLockable> {
00225     typedef FirstGraphImpl::UEdgeInfoBase<gNode, EdgeTy, Directional> EdgeInfo;
00226     
00228     typedef llvm::SmallVector<EdgeInfo, 3> EdgesTy;
00229     
00230     typedef typename EdgesTy::iterator iterator;
00231   };
00232 
00233   class gNode:
00234     public detail::NodeInfoBase<NodeTy, !HasNoLockable>,
00235     public gNodeTypes
00236   {
00237     friend class FirstGraph;
00238     typedef detail::NodeInfoBase<NodeTy, !HasNoLockable> NodeInfo;
00239     typename gNode::EdgesTy edges;
00240     typedef typename gNode::iterator iterator;
00241     typedef typename gNode::EdgeInfo EdgeInfo;
00242 
00243     bool active;
00244     
00245     iterator begin() { return edges.begin(); }
00246     iterator end() { return edges.end();  }
00247     
00248     void erase(iterator ii) {
00249       *ii = edges.back();
00250       edges.pop_back();
00251     }
00252 
00253     void erase(gNode* N) { 
00254       iterator ii = find(N);
00255       if (ii != end())
00256         edges.erase(ii); 
00257     }
00258 
00259     iterator find(gNode* N) {
00260       return std::find_if(begin(), end(), first_eq_and_valid<gNode*>(N));
00261     }
00262 
00263     void resizeEdges(size_t size) {
00264       edges.resize(size, EdgeInfo(new gNode(), 0));
00265     }
00266 
00267     template<typename... Args>
00268     iterator createEdge(gNode* N, EdgeTy* v, Args&&... args) {
00269       return edges.insert(edges.end(), EdgeInfo(N, v, std::forward<Args>(args)...));
00270     }
00271 
00272     template<typename... Args>
00273     iterator createEdgeWithReuse(gNode* N, EdgeTy* v, Args&&... args) {
00274       //First check for holes
00275       iterator ii = std::find_if(begin(), end(), first_not_valid());
00276       if (ii != end()) {
00277         *ii = EdgeInfo(N, v, std::forward<Args>(args)...);
00278         return ii;
00279       }
00280       return edges.insert(edges.end(), EdgeInfo(N, v, std::forward<Args>(args)...));
00281     }
00282 
00283     template<bool _A1 = HasNoLockable>
00284     void acquire(MethodFlag mflag, typename std::enable_if<!_A1>::type* = 0) {
00285       Galois::Runtime::acquire(this, mflag);
00286     }
00287 
00288     template<bool _A1 = HasNoLockable>
00289     void acquire(MethodFlag mflag, typename std::enable_if<_A1>::type* = 0) { }
00290 
00291   public:
00292     template<typename... Args>
00293     gNode(Args&&... args): NodeInfo(std::forward<Args>(args)...), active(false) { }
00294   };
00295 
00296   //The graph manages the lifetimes of the data in the nodes and edges
00297   typedef Galois::InsertBag<gNode> NodeListTy;
00298   NodeListTy nodes;
00299 
00300   FirstGraphImpl::EdgeFactory<EdgeTy> edges;
00301 
00302   //Helpers for iterator classes
00303   struct is_node : public std::unary_function<gNode&, bool>{
00304     bool operator() (const gNode& g) const { return g.active; }
00305   };
00306   struct is_edge : public std::unary_function<typename gNodeTypes::EdgeInfo&, bool> {
00307     bool operator()(typename gNodeTypes::EdgeInfo& e) const { return e.first()->active; }
00308   };
00309   struct makeGraphNode: public std::unary_function<gNode&, gNode*> {
00310     gNode* operator()(gNode& data) const { return &data; }
00311   };
00312 
00313 public:
00315   typedef gNode* GraphNode;
00317   typedef EdgeTy edge_type;
00319   typedef NodeTy node_type;
00321   typedef typename boost::filter_iterator<is_edge, typename gNodeTypes::iterator> edge_iterator;
00323   typedef typename gNodeTypes::EdgeInfo::reference edge_data_reference;
00325   typedef typename gNodeTypes::reference node_data_reference;
00327   typedef boost::transform_iterator<makeGraphNode,
00328           boost::filter_iterator<is_node,
00329                    typename NodeListTy::iterator> > iterator;
00330 
00331 private:
00332   template<typename... Args>
00333   edge_iterator createEdgeWithReuse(GraphNode src, GraphNode dst, Galois::MethodFlag mflag, Args&&... args) {
00334     assert(src);
00335     assert(dst);
00336     Galois::Runtime::checkWrite(mflag, true);
00337     src->acquire(mflag);
00338     typename gNode::iterator ii = src->find(dst);
00339     if (ii == src->end()) {
00340       if (Directional) {
00341         ii = src->createEdgeWithReuse(dst, 0, std::forward<Args>(args)...);
00342       } else {
00343         dst->acquire(mflag);
00344         EdgeTy* e = edges.mkEdge(std::forward<Args>(args)...);
00345         ii = dst->createEdgeWithReuse(src, e, std::forward<Args>(args)...);
00346         ii = src->createEdgeWithReuse(dst, e, std::forward<Args>(args)...);
00347       }
00348     }
00349     return boost::make_filter_iterator(is_edge(), ii, src->end());
00350   }
00351 
00352   template<typename... Args>
00353   edge_iterator createEdge(GraphNode src, GraphNode dst, Galois::MethodFlag mflag, Args&&... args) {
00354     assert(src);
00355     assert(dst);
00356     Galois::Runtime::checkWrite(mflag, true);
00357     src->acquire(mflag);
00358     typename gNode::iterator ii = src->end();
00359     if (ii == src->end()) {
00360       if (Directional) {
00361         ii = src->createEdge(dst, 0, std::forward<Args>(args)...);
00362       } else {
00363         dst->acquire(mflag);
00364         EdgeTy* e = edges.mkEdge(std::forward<Args>(args)...);
00365         ii = dst->createEdge(src, e, std::forward<Args>(args)...);
00366         ii = src->createEdge(dst, e, std::forward<Args>(args)...);
00367       }
00368     }
00369     return boost::make_filter_iterator(is_edge(), ii, src->end());
00370   }
00371 
00372 public:
00377   template<typename... Args>
00378   GraphNode createNode(Args&&... args) {
00379     gNode* N = &(nodes.emplace(std::forward<Args>(args)...));
00380     N->active = false;
00381     return GraphNode(N);
00382   }
00383 
00387   void addNode(const GraphNode& n, Galois::MethodFlag mflag = MethodFlag::ALL) {
00388     Galois::Runtime::checkWrite(mflag, true);
00389     n->acquire(mflag);
00390     n->active = true;
00391   }
00392 
00394   node_data_reference getData(const GraphNode& n, Galois::MethodFlag mflag = MethodFlag::ALL) const {
00395     assert(n);
00396     Galois::Runtime::checkWrite(mflag, false);
00397     n->acquire(mflag);
00398     return n->getData();
00399   }
00400 
00402   bool containsNode(const GraphNode& n, Galois::MethodFlag mflag = MethodFlag::ALL) const {
00403     assert(n);
00404     n->acquire(mflag);
00405     return n->active;
00406   }
00407 
00412   //FIXME: handle edge memory
00413   void removeNode(GraphNode n, Galois::MethodFlag mflag = MethodFlag::ALL) {
00414     assert(n);
00415     Galois::Runtime::checkWrite(mflag, true);
00416     n->acquire(mflag);
00417     gNode* N = n;
00418     if (N->active) {
00419       N->active = false;
00420       if (!Directional && edges.mustDel())
00421         for (edge_iterator ii = edge_begin(n, MethodFlag::NONE), ee = edge_end(n, MethodFlag::NONE); ii != ee; ++ii)
00422           edges.delEdge(ii->second());
00423       N->edges.clear();
00424     }
00425   }
00426 
00430   void resizeEdges(GraphNode src, size_t size, Galois::MethodFlag mflag = MethodFlag::ALL) {
00431     assert(src);
00432     Galois::Runtime::checkWrite(mflag, false);
00433     src->acquire(mflag);
00434     src->resizeEdges(size);
00435    }
00436 
00444   edge_iterator addEdge(GraphNode src, GraphNode dst, Galois::MethodFlag mflag = MethodFlag::ALL) {
00445     return createEdgeWithReuse(src, dst, mflag);
00446   }
00447 
00449   template<typename... Args>
00450   edge_iterator addMultiEdge(GraphNode src, GraphNode dst, Galois::MethodFlag mflag, Args&&... args) {
00451     return createEdge(src, dst, mflag, std::forward<Args>(args)...);
00452   }
00453 
00455   void removeEdge(GraphNode src, edge_iterator dst, Galois::MethodFlag mflag = MethodFlag::ALL) {
00456     assert(src);
00457     Galois::Runtime::checkWrite(mflag, true);
00458     src->acquire(mflag);
00459     if (Directional) {
00460       src->erase(dst.base());
00461     } else {
00462       dst->first()->acquire(mflag);
00463       EdgeTy* e = dst->second();
00464       edges.delEdge(e);
00465       src->erase(dst.base());
00466       dst->first()->erase(src);
00467     }
00468   }
00469 
00471   edge_iterator findEdge(GraphNode src, GraphNode dst, Galois::MethodFlag mflag = MethodFlag::ALL) {
00472     assert(src);
00473     assert(dst);
00474     src->acquire(mflag);
00475     return boost::make_filter_iterator(is_edge(), src->find(dst), src->end());
00476   }
00477 
00485   edge_data_reference getEdgeData(edge_iterator ii, Galois::MethodFlag mflag = MethodFlag::NONE) const {
00486     assert(ii->first()->active);
00487     Galois::Runtime::checkWrite(mflag, false);
00488     ii->first()->acquire(mflag);
00489     return *ii->second();
00490   }
00491 
00493   GraphNode getEdgeDst(edge_iterator ii) {
00494     assert(ii->first()->active);
00495     return GraphNode(ii->first());
00496   }
00497 
00499 
00501   edge_iterator edge_begin(GraphNode N, Galois::MethodFlag mflag = MethodFlag::ALL) {
00502     assert(N);
00503     N->acquire(mflag);
00504 
00505     if (Galois::Runtime::shouldLock(mflag)) {
00506       for (typename gNode::iterator ii = N->begin(), ee = N->end(); ii != ee; ++ii) {
00507         if (ii->first()->active)
00508           ii->first()->acquire(mflag);
00509       }
00510     }
00511     return boost::make_filter_iterator(is_edge(), N->begin(), N->end());
00512   }
00513 
00515   edge_iterator edge_end(GraphNode N, Galois::MethodFlag mflag = MethodFlag::ALL) {
00516     assert(N);
00517     // Acquiring lock is not necessary: no valid use for an end pointer should
00518     // ever require it
00519     // N->acquire(mflag);
00520     return boost::make_filter_iterator(is_edge(), N->end(), N->end());
00521   }
00522 
00527   detail::EdgesIterator<FirstGraph> out_edges(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00528     return detail::EdgesIterator<FirstGraph>(*this, N, mflag);
00529   }
00530 
00534   iterator begin() {
00535     return boost::make_transform_iterator(
00536            boost::make_filter_iterator(is_node(),
00537                                        nodes.begin(), nodes.end()),
00538            makeGraphNode());
00539   }
00540 
00542   iterator end() {
00543     return boost::make_transform_iterator(
00544            boost::make_filter_iterator(is_node(),
00545                                        nodes.end(), nodes.end()), 
00546            makeGraphNode());
00547   }
00548 
00549   typedef iterator local_iterator;
00550 
00551   local_iterator local_begin() {
00552     return boost::make_transform_iterator(
00553            boost::make_filter_iterator(is_node(),
00554                                        nodes.local_begin(), nodes.local_end()),
00555            makeGraphNode());
00556   }
00557 
00558   local_iterator local_end() {
00559     return boost::make_transform_iterator(
00560            boost::make_filter_iterator(is_node(),
00561                                        nodes.local_end(), nodes.local_end()), 
00562            makeGraphNode());
00563   }
00564 
00568   unsigned int size() {
00569     return std::distance(begin(), end());
00570   }
00571 
00573   size_t sizeOfEdgeData() const {
00574     return gNode::EdgeInfo::sizeOfSecond();
00575   }
00576 };
00577 
00578 }
00579 }
00580 #endif