00001
00026 #ifndef GALOIS_GRAPH_LC_LINEAR_GRAPH_H
00027 #define GALOIS_GRAPH_LC_LINEAR_GRAPH_H
00028
00029 #include "Galois/config.h"
00030 #include "Galois/LargeArray.h"
00031 #include "Galois/Graph/FileGraph.h"
00032 #include "Galois/Graph/Details.h"
00033 #include "Galois/Runtime/MethodFlags.h"
00034
00035 #include <boost/mpl/if.hpp>
00036 #include GALOIS_CXX11_STD_HEADER(type_traits)
00037
00038 namespace Galois {
00039 namespace Graph {
00040
00049 template<typename NodeTy, typename EdgeTy,
00050 bool HasNoLockable=false,
00051 bool UseNumaAlloc=false,
00052 bool HasOutOfLineLockable=false,
00053 bool HasId=false>
00054 class LC_Linear_Graph:
00055 private boost::noncopyable,
00056 private detail::LocalIteratorFeature<UseNumaAlloc>,
00057 private detail::OutOfLineLockableFeature<HasOutOfLineLockable && !HasNoLockable> {
00058 template<typename Graph> friend class LC_InOut_Graph;
00059
00060 public:
00061 template<bool _has_id>
00062 struct with_id { typedef LC_Linear_Graph<NodeTy,EdgeTy,HasNoLockable,UseNumaAlloc,HasOutOfLineLockable,_has_id> type; };
00063
00064 template<typename _node_data>
00065 struct with_node_data { typedef LC_Linear_Graph<_node_data,EdgeTy,HasNoLockable,UseNumaAlloc,HasOutOfLineLockable,HasId> type; };
00066
00067 template<bool _has_no_lockable>
00068 struct with_no_lockable { typedef LC_Linear_Graph<NodeTy,EdgeTy,_has_no_lockable,UseNumaAlloc,HasOutOfLineLockable,HasId> type; };
00069
00070 template<bool _use_numa_alloc>
00071 struct with_numa_alloc { typedef LC_Linear_Graph<NodeTy,EdgeTy,HasNoLockable,_use_numa_alloc,HasOutOfLineLockable,HasId> type; };
00072
00073 template<bool _has_out_of_line_lockable>
00074 struct with_out_of_line_lockable { typedef LC_Linear_Graph<NodeTy,EdgeTy,HasNoLockable,UseNumaAlloc,_has_out_of_line_lockable,_has_out_of_line_lockable||HasId> type; };
00075
00076 typedef read_with_aux_graph_tag read_tag;
00077
00078 protected:
00079 class NodeInfo;
00080 typedef detail::EdgeInfoBase<NodeInfo*,EdgeTy> EdgeInfo;
00081 typedef LargeArray<NodeInfo*> Nodes;
00082 typedef detail::NodeInfoBaseTypes<NodeTy,!HasNoLockable && !HasOutOfLineLockable> NodeInfoTypes;
00083
00084 class NodeInfo:
00085 public detail::NodeInfoBase<NodeTy,!HasNoLockable && !HasOutOfLineLockable>,
00086 public detail::IntrusiveId<typename boost::mpl::if_c<HasId,uint32_t,void>::type> {
00087 friend class LC_Linear_Graph;
00088 int numEdges;
00089
00090 EdgeInfo* edgeBegin() {
00091 NodeInfo* n = this;
00092 ++n;
00093 return reinterpret_cast<EdgeInfo*>(n);
00094 }
00095
00096 EdgeInfo* edgeEnd() {
00097 EdgeInfo* ei = edgeBegin();
00098 ei += numEdges;
00099 return ei;
00100 }
00101
00102 NodeInfo* next() {
00103 NodeInfo* ni = this;
00104 EdgeInfo* ei = edgeEnd();
00105 while (reinterpret_cast<char*>(ni) < reinterpret_cast<char*>(ei))
00106 ++ni;
00107 return ni;
00108 }
00109 };
00110
00111 public:
00112 typedef NodeInfo* GraphNode;
00113 typedef EdgeTy edge_data_type;
00114 typedef NodeTy node_data_type;
00115 typedef typename NodeInfoTypes::reference node_data_reference;
00116 typedef typename EdgeInfo::reference edge_data_reference;
00117 typedef EdgeInfo* edge_iterator;
00118 typedef NodeInfo** iterator;
00119 typedef NodeInfo*const * const_iterator;
00120 typedef iterator local_iterator;
00121 typedef const_iterator const_local_iterator;
00122 typedef int ReadGraphAuxData;
00123
00124 protected:
00125 LargeArray<char> data;
00126 uint64_t numNodes;
00127 uint64_t numEdges;
00128 Nodes nodes;
00129
00130 template<bool _A1 = HasNoLockable, bool _A2 = HasOutOfLineLockable>
00131 void acquireNode(GraphNode N, MethodFlag mflag, typename std::enable_if<!_A1 && !_A2>::type* = 0) {
00132 Galois::Runtime::acquire(N, mflag);
00133 }
00134
00135 template<bool _A1 = HasOutOfLineLockable, bool _A2 = HasNoLockable>
00136 void acquireNode(GraphNode N, MethodFlag mflag, typename std::enable_if<_A1 && !_A2>::type* = 0) {
00137 this->outOfLineAcquire(getId(N), mflag);
00138 }
00139
00140 template<bool _A1 = HasOutOfLineLockable, bool _A2 = HasNoLockable>
00141 void acquireNode(GraphNode N, MethodFlag mflag, typename std::enable_if<_A2>::type* = 0) { }
00142
00143 edge_iterator raw_begin(GraphNode N) {
00144 return N->edgeBegin();
00145 }
00146
00147 edge_iterator raw_end(GraphNode N) {
00148 return N->edgeEnd();
00149 }
00150
00151 template<bool _Enable = HasId>
00152 size_t getId(GraphNode N, typename std::enable_if<_Enable>::type* = 0) {
00153 return N->getId();
00154 }
00155
00156 template<bool _Enable = HasId>
00157 GraphNode getNode(size_t n, typename std::enable_if<_Enable>::type* = 0) {
00158 return nodes[n];
00159 }
00160
00161 public:
00162 ~LC_Linear_Graph() {
00163 for (typename Nodes::iterator ii = nodes.begin(), ei = nodes.end(); ii != ei; ++ii) {
00164 NodeInfo* n = *ii;
00165 EdgeInfo* edgeBegin = n->edgeBegin();
00166 EdgeInfo* edgeEnd = n->edgeEnd();
00167
00168 if (EdgeInfo::has_value) {
00169 while (edgeBegin != edgeEnd) {
00170 edgeBegin->destroy();
00171 ++edgeBegin;
00172 }
00173 }
00174 n->~NodeInfo();
00175 }
00176 }
00177
00178 node_data_reference getData(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00179 Galois::Runtime::checkWrite(mflag, false);
00180 acquireNode(N, mflag);
00181 return N->getData();
00182 }
00183
00184 edge_data_reference getEdgeData(edge_iterator ni, MethodFlag mflag = MethodFlag::NONE) const {
00185 Galois::Runtime::checkWrite(mflag, false);
00186 return ni->get();
00187 }
00188
00189 GraphNode getEdgeDst(edge_iterator ni) const {
00190 return ni->dst;
00191 }
00192
00193 uint64_t size() const { return numNodes; }
00194 uint64_t sizeEdges() const { return numEdges; }
00195 iterator begin() { return &nodes[0]; }
00196 iterator end() { return &nodes[numNodes]; }
00197 const_iterator begin() const { return &nodes[0]; }
00198 const_iterator end() const { return &nodes[numNodes]; }
00199
00200 local_iterator local_begin() { return &nodes[this->localBegin(numNodes)]; }
00201 local_iterator local_end() { return &nodes[this->localEnd(numNodes)]; }
00202 const_local_iterator local_begin() const { return &nodes[this->localBegin(numNodes)]; }
00203 const_local_iterator local_end() const { return &nodes[this->localEnd(numNodes)]; }
00204
00205 edge_iterator edge_begin(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00206 acquireNode(N, mflag);
00207 if (Galois::Runtime::shouldLock(mflag)) {
00208 for (edge_iterator ii = N->edgeBegin(), ee = N->edgeEnd(); ii != ee; ++ii) {
00209 acquireNode(ii->dst, mflag);
00210 }
00211 }
00212 return N->edgeBegin();
00213 }
00214
00215 edge_iterator edge_end(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00216 acquireNode(N, mflag);
00217 return N->edgeEnd();
00218 }
00219
00220 detail::EdgesIterator<LC_Linear_Graph> out_edges(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00221 return detail::EdgesIterator<LC_Linear_Graph>(*this, N, mflag);
00222 }
00223
00227 template<typename CompTy>
00228 void sortEdgesByEdgeData(GraphNode N, const CompTy& comp = std::less<EdgeTy>(), MethodFlag mflag = MethodFlag::ALL) {
00229 acquireNode(N, mflag);
00230 std::sort(N->edgeBegin(), N->edgeEnd(), detail::EdgeSortCompWrapper<EdgeInfo,CompTy>(comp));
00231 }
00232
00236 template<typename CompTy>
00237 void sortEdges(GraphNode N, const CompTy& comp, MethodFlag mflag = MethodFlag::ALL) {
00238 acquireNode(N, mflag);
00239 std::sort(N->edgeBegin(), N->edgeEnd(), comp);
00240 }
00241
00242 void allocateFrom(FileGraph& graph, const ReadGraphAuxData&) {
00243 numNodes = graph.size();
00244 numEdges = graph.sizeEdges();
00245 if (UseNumaAlloc) {
00246 data.allocateLocal(sizeof(NodeInfo) * numNodes * 2 + sizeof(EdgeInfo) * numEdges, false);
00247 nodes.allocateLocal(numNodes, false);
00248 this->outOfLineAllocateLocal(numNodes, false);
00249 } else {
00250 data.allocateInterleaved(sizeof(NodeInfo) * numNodes * 2 + sizeof(EdgeInfo) * numEdges);
00251 nodes.allocateInterleaved(numNodes);
00252 this->outOfLineAllocateInterleaved(numNodes);
00253 }
00254 }
00255
00256 void constructNodesFrom(FileGraph& graph, unsigned tid, unsigned total, const ReadGraphAuxData&) {
00257 auto r = graph.divideBy(
00258 Nodes::size_of::value + 2 * sizeof(NodeInfo) + LC_Linear_Graph::size_of_out_of_line::value,
00259 sizeof(EdgeInfo),
00260 tid, total);
00261
00262 this->setLocalRange(*r.first, *r.second);
00263 NodeInfo* curNode = reinterpret_cast<NodeInfo*>(data.data());
00264
00265 size_t id = *r.first;
00266 size_t edges = *graph.edge_begin(*r.first);
00267 size_t bytes = edges * sizeof(EdgeInfo) + 2 * (id + 1) * sizeof(NodeInfo);
00268 curNode += bytes / sizeof(NodeInfo);
00269 for (FileGraph::iterator ii = r.first, ei = r.second; ii != ei; ++ii, ++id) {
00270 nodes.constructAt(*ii);
00271 new (curNode) NodeInfo();
00272
00273 curNode->setId(id);
00274 curNode->numEdges = std::distance(graph.edge_begin(*ii), graph.edge_end(*ii));
00275 nodes[*ii] = curNode;
00276 curNode = curNode->next();
00277 }
00278 }
00279
00280 void constructEdgesFrom(FileGraph& graph, unsigned tid, unsigned total, const ReadGraphAuxData&) {
00281 typedef typename EdgeInfo::value_type EDV;
00282 auto r = graph.divideBy(
00283 Nodes::size_of::value + 2 * sizeof(NodeInfo) + LC_Linear_Graph::size_of_out_of_line::value,
00284 sizeof(EdgeInfo),
00285 tid, total);
00286
00287 for (FileGraph::iterator ii = r.first, ei = r.second; ii != ei; ++ii) {
00288 EdgeInfo* edge = nodes[*ii]->edgeBegin();
00289 for (FileGraph::edge_iterator nn = graph.edge_begin(*ii), en = graph.edge_end(*ii); nn != en; ++nn) {
00290 if (EdgeInfo::has_value)
00291 edge->construct(graph.getEdgeData<EDV>(nn));
00292 edge->dst = nodes[graph.getEdgeDst(nn)];
00293 ++edge;
00294 }
00295 }
00296 }
00297 };
00298
00299 }
00300 }
00301
00302 #endif
