00001
00026 #ifndef GALOIS_GRAPH_LC_INLINEEDGE_GRAPH_H
00027 #define GALOIS_GRAPH_LC_INLINEEDGE_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 HasCompressedNodePtr=false>
00054 class LC_InlineEdge_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_InlineEdge_Graph type; };
00063
00064 template<typename _node_data>
00065 struct with_node_data { typedef LC_InlineEdge_Graph<_node_data,EdgeTy,HasNoLockable,UseNumaAlloc,HasOutOfLineLockable,HasCompressedNodePtr> type; };
00066
00067 template<bool _has_no_lockable>
00068 struct with_no_lockable { typedef LC_InlineEdge_Graph<NodeTy,EdgeTy,_has_no_lockable,UseNumaAlloc,HasOutOfLineLockable,HasCompressedNodePtr> type; };
00069
00070 template<bool _use_numa_alloc>
00071 struct with_numa_alloc { typedef LC_InlineEdge_Graph<NodeTy,EdgeTy,HasNoLockable,_use_numa_alloc,HasOutOfLineLockable,HasCompressedNodePtr> type; };
00072
00073 template<bool _has_out_of_line_lockable>
00074 struct with_out_of_line_lockable { typedef LC_InlineEdge_Graph<NodeTy,EdgeTy,HasNoLockable,UseNumaAlloc,_has_out_of_line_lockable,HasCompressedNodePtr> type; };
00075
00080 template<bool _has_compressed_node_ptr>
00081 struct with_compressed_node_ptr { typedef LC_InlineEdge_Graph<NodeTy,EdgeTy,HasNoLockable,UseNumaAlloc,HasOutOfLineLockable,_has_compressed_node_ptr> type; };
00082
00083 typedef read_default_graph_tag read_tag;
00084
00085 protected:
00086 class NodeInfo;
00087 typedef detail::EdgeInfoBase<typename boost::mpl::if_c<HasCompressedNodePtr,uint32_t,NodeInfo*>::type,EdgeTy> EdgeInfo;
00088 typedef LargeArray<EdgeInfo> EdgeData;
00089 typedef LargeArray<NodeInfo> NodeData;
00090 typedef detail::NodeInfoBaseTypes<NodeTy,!HasNoLockable && !HasOutOfLineLockable> NodeInfoTypes;
00091
00092 class NodeInfo: public detail::NodeInfoBase<NodeTy,!HasNoLockable && !HasOutOfLineLockable> {
00093 EdgeInfo* m_edgeBegin;
00094 EdgeInfo* m_edgeEnd;
00095 public:
00096 EdgeInfo*& edgeBegin() { return m_edgeBegin; }
00097 EdgeInfo*& edgeEnd() { return m_edgeEnd; }
00098 };
00099
00100 public:
00101 typedef NodeInfo* GraphNode;
00102 typedef EdgeTy edge_data_type;
00103 typedef NodeTy node_data_type;
00104 typedef typename EdgeInfo::reference edge_data_reference;
00105 typedef typename NodeInfoTypes::reference node_data_reference;
00106 typedef EdgeInfo* edge_iterator;
00107 typedef Galois::NoDerefIterator<NodeInfo*> iterator;
00108 typedef Galois::NoDerefIterator<const NodeInfo*> const_iterator;
00109 typedef iterator local_iterator;
00110 typedef const_iterator const_local_iterator;
00111
00112 protected:
00113 NodeData nodeData;
00114 EdgeData edgeData;
00115 uint64_t numNodes;
00116 uint64_t numEdges;
00117
00118 template<bool _C = HasCompressedNodePtr>
00119 NodeInfo* getDst(edge_iterator ii, typename std::enable_if<_C>::type* x = 0) const {
00120 return const_cast<NodeInfo*>(&nodeData[ii->dst]);
00121 }
00122
00123 template<bool _C = HasCompressedNodePtr>
00124 NodeInfo* getDst(edge_iterator ii, typename std::enable_if<!_C>::type* x = 0) const {
00125 return ii->dst;
00126 }
00127
00128 template<typename Container,typename Index, bool _C = HasCompressedNodePtr>
00129 void setEdgeDst(Container& c, edge_iterator edge, Index idx, typename std::enable_if<_C>::type* = 0) {
00130 edge->dst = idx;
00131 }
00132
00133 template<typename Container,typename Index, bool _C = HasCompressedNodePtr>
00134 void setEdgeDst(Container& c, edge_iterator edge, Index idx, typename std::enable_if<!_C>::type* = 0) {
00135 edge->dst = &c[idx];
00136 }
00137
00138 template<bool _A1 = HasNoLockable, bool _A2 = HasOutOfLineLockable>
00139 void acquireNode(GraphNode N, MethodFlag mflag, typename std::enable_if<!_A1 && !_A2>::type* = 0) {
00140 Galois::Runtime::acquire(N, mflag);
00141 }
00142
00143 template<bool _A1 = HasOutOfLineLockable, bool _A2 = HasNoLockable>
00144 void acquireNode(GraphNode N, MethodFlag mflag, typename std::enable_if<_A1 && !_A2>::type* = 0) {
00145 this->outOfLineAcquire(getId(N), mflag);
00146 }
00147
00148 template<bool _A1 = HasOutOfLineLockable, bool _A2 = HasNoLockable>
00149 void acquireNode(GraphNode N, MethodFlag mflag, typename std::enable_if<_A2>::type* = 0) { }
00150
00151 edge_iterator raw_begin(GraphNode N) {
00152 return nodeData[getId(N)].edgeBegin();
00153 }
00154
00155 edge_iterator raw_end(GraphNode N) {
00156 return nodeData[getId(N)].edgeEnd();
00157 }
00158
00159 size_t getId(GraphNode N) {
00160 return std::distance(this->nodeData.data(), N);
00161 }
00162
00163 GraphNode getNode(size_t n) {
00164 return &nodeData[n];
00165 }
00166
00167 public:
00168 ~LC_InlineEdge_Graph() {
00169 if (!EdgeInfo::has_value) return;
00170 if (numNodes == 0) return;
00171
00172 for (edge_iterator ii = nodeData[0].edgeBegin(), ei = nodeData[numNodes-1].edgeEnd(); ii != ei; ++ii) {
00173 ii->destroy();
00174 }
00175 }
00176
00177 node_data_reference getData(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00178 Galois::Runtime::checkWrite(mflag, false);
00179 acquireNode(N, mflag);
00180 return N->getData();
00181 }
00182
00183 edge_data_reference getEdgeData(edge_iterator ni, MethodFlag mflag = MethodFlag::NONE) const {
00184 Galois::Runtime::checkWrite(mflag, false);
00185 return ni->get();
00186 }
00187
00188 GraphNode getEdgeDst(edge_iterator ni) const {
00189 return getDst(ni);
00190 }
00191
00192 uint64_t size() const { return numNodes; }
00193 uint64_t sizeEdges() const { return numEdges; }
00194
00195 const_iterator begin() const { return const_iterator(nodeData.begin()); }
00196 const_iterator end() const { return const_iterator(nodeData.end()); }
00197 iterator begin() { return iterator(nodeData.data()); }
00198 iterator end() { return iterator(nodeData.end()); }
00199
00200 local_iterator local_begin() { return local_iterator(&nodeData[this->localBegin(numNodes)]); }
00201 local_iterator local_end() { return local_iterator(&nodeData[this->localEnd(numNodes)]); }
00202 const_local_iterator local_begin() const { return const_local_iterator(&nodeData[this->localBegin(numNodes)]); }
00203 const_local_iterator local_end() const { return const_local_iterator(&nodeData[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(getDst(ii), 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_InlineEdge_Graph> out_edges(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00221 return detail::EdgesIterator<LC_InlineEdge_Graph>(*this, N, mflag);
00222 }
00223
00224 #if 0
00225
00228 template<typename CompTy>
00229 void sortEdgesByEdgeData(GraphNode N, const CompTy& comp = std::less<EdgeTy>(), MethodFlag mflag = MethodFlag::ALL) {
00230 Galois::Runtime::acquire(N, mflag);
00231 std::sort(edge_sort_begin(N), edge_sort_end(N), EdgeSortCompWrapper<EdgeSortValue<GraphNode,EdgeTy>,CompTy>(comp));
00232 }
00233
00237 template<typename CompTy>
00238 void sortEdges(GraphNode N, const CompTy& comp, MethodFlag mflag = MethodFlag::ALL) {
00239 Galois::Runtime::acquire(N, mflag);
00240 std::sort(edge_sort_begin(N), edge_sort_end(N), comp);
00241 }
00242 #endif
00243
00244 void allocateFrom(FileGraph& graph) {
00245 numNodes = graph.size();
00246 numEdges = graph.sizeEdges();
00247
00248 if (UseNumaAlloc) {
00249 nodeData.allocateLocal(numNodes, false);
00250 edgeData.allocateLocal(numEdges, false);
00251 this->outOfLineAllocateLocal(numNodes, false);
00252 } else {
00253 nodeData.allocateInterleaved(numNodes);
00254 edgeData.allocateInterleaved(numEdges);
00255 this->outOfLineAllocateInterleaved(numNodes);
00256 }
00257 }
00258
00259 void constructFrom(FileGraph& graph, unsigned tid, unsigned total) {
00260 typedef typename EdgeInfo::value_type EDV;
00261 auto r = graph.divideBy(
00262 NodeData::size_of::value + LC_InlineEdge_Graph::size_of_out_of_line::value,
00263 EdgeData::size_of::value,
00264 tid, total);
00265
00266 EdgeInfo* curEdge = edgeData.data() + *graph.edge_begin(*r.first);
00267
00268 this->setLocalRange(*r.first, *r.second);
00269
00270 for (FileGraph::iterator ii = r.first, ei = r.second; ii != ei; ++ii) {
00271 nodeData.constructAt(*ii);
00272 this->outOfLineConstructAt(*ii);
00273 nodeData[*ii].edgeBegin() = curEdge;
00274 for (FileGraph::edge_iterator nn = graph.edge_begin(*ii), en = graph.edge_end(*ii); nn != en; ++nn) {
00275 if (EdgeInfo::has_value)
00276 curEdge->construct(graph.getEdgeData<EDV>(nn));
00277 setEdgeDst(nodeData, curEdge, graph.getEdgeDst(nn));
00278 ++curEdge;
00279 }
00280 nodeData[*ii].edgeEnd() = curEdge;
00281 }
00282 }
00283 };
00284
00285 }
00286 }
00287
00288 #endif
