00001
00025 #ifndef GALOIS_GRAPH_OCGRAPH_H
00026 #define GALOIS_GRAPH_OCGRAPH_H
00027
00028 #include "Galois/config.h"
00029 #include "Galois/optional.h"
00030 #include "Galois/LazyObject.h"
00031 #include "Galois/LargeArray.h"
00032 #include "Galois/Graph/Details.h"
00033 #include "Galois/Runtime/MethodFlags.h"
00034
00035 #include <boost/iterator/counting_iterator.hpp>
00036 #include <boost/utility.hpp>
00037
00038 #include GALOIS_CXX11_STD_HEADER(type_traits)
00039 #include <string>
00040
00041 namespace Galois {
00042 namespace Graph {
00043
00048 template<typename Graph>
00049 class BindSegmentGraph: private boost::noncopyable {
00050 typedef typename Graph::segment_type segment_type;
00051
00052 Graph& graph;
00053 segment_type segment;
00054
00055 public:
00056 explicit BindSegmentGraph(Graph& g): graph(g) { }
00057 BindSegmentGraph(Graph& g, segment_type s): graph(g), segment(s) { }
00058
00059 void setSegment(const segment_type& s) {
00060 segment = s;
00061 }
00062
00063 typedef typename Graph::GraphNode GraphNode;
00064 typedef typename Graph::edge_data_type edge_data_type;
00065 typedef typename Graph::node_data_type node_data_type;
00066 typedef typename Graph::edge_data_reference edge_data_reference;
00067 typedef typename Graph::node_data_reference node_data_reference;
00068 typedef typename Graph::edge_iterator edge_iterator;
00069 typedef typename Graph::in_edge_iterator in_edge_iterator;
00070 typedef typename Graph::iterator iterator;
00071 typedef typename Graph::const_iterator const_iterator;
00072 typedef typename Graph::local_iterator local_iterator;
00073 typedef typename Graph::const_local_iterator const_local_iterator;
00074
00075 node_data_reference getData(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00076 return graph.getData(N, mflag);
00077 }
00078
00079 edge_data_reference getEdgeData(edge_iterator ni, MethodFlag mflag = MethodFlag::NONE) {
00080 return graph.getEdgeData(segment, ni, mflag);
00081 }
00082
00083 GraphNode getEdgeDst(edge_iterator ni) {
00084 return graph.getEdgeDst(segment, ni);
00085 }
00086
00087 uint64_t size() const { return graph.size(); }
00088 uint64_t sizeEdges() const { return graph.sizeEdges(); }
00089
00090 iterator begin() const { return graph.begin(); }
00091 iterator end() const { return graph.end(); }
00092
00093 local_iterator local_begin() const { return graph.local_begin(); }
00094 local_iterator local_end() const { return graph.local_end(); }
00095
00096 edge_iterator edge_begin(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00097 return graph.edge_begin(segment, N, mflag);
00098 }
00099
00100 edge_iterator edge_end(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00101 return graph.edge_end(segment, N, mflag);
00102 }
00103
00104 detail::EdgesIterator<BindSegmentGraph> out_edges(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00105 return detail::EdgesIterator<BindSegmentGraph>(*this, N, mflag);
00106 }
00107
00108 edge_data_reference getInEdgeData(edge_iterator ni, MethodFlag mflag = MethodFlag::NONE) {
00109 return graph.getInEdgeData(segment, ni, mflag);
00110 }
00111
00112 GraphNode getInEdgeDst(in_edge_iterator ni) {
00113 return graph.getInEdgeDst(segment, ni);
00114 }
00115
00116 in_edge_iterator in_edge_begin(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00117 return graph.in_edge_begin(segment, N, mflag);
00118 }
00119
00120 in_edge_iterator in_edge_end(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00121 return graph.in_edge_end(segment, N, mflag);
00122 }
00123
00124 detail::InEdgesIterator<BindSegmentGraph> in_edges(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00125 return detail::InEdgesIterator<BindSegmentGraph>(*this, N, mflag);
00126 }
00127
00128 size_t idFromNode(GraphNode N) {
00129 return graph.idFromNode(N);
00130 }
00131
00132 GraphNode nodeFromId(size_t N) {
00133 return graph.nodeFromId(N);
00134 }
00135 };
00136
00138 class OCFileGraph: private boost::noncopyable {
00139 public:
00140 typedef uint32_t GraphNode;
00141 typedef boost::counting_iterator<uint32_t> iterator;
00142 typedef boost::counting_iterator<uint64_t> edge_iterator;
00143 typedef uint64_t* edge_offset_iterator;
00144
00145 template<typename EdgeTy>
00146 struct EdgeReference {
00147 typedef typename LazyObject<EdgeTy>::reference type;
00148 };
00149
00150 private:
00151 class Block {
00152 friend class OCFileGraph;
00153 void* m_mapping;
00154 size_t m_length;
00155 char* m_data;
00156 size_t m_begin;
00157 size_t m_sizeof_data;
00158
00159 void unload();
00160 void load(int fd, off64_t offset, size_t begin, size_t len, size_t sizeof_data);
00161
00162 public:
00163 Block(): m_mapping(0) { }
00164
00165 char* get(size_t index) const {
00166 char* p = m_data + (m_sizeof_data * (index - m_begin));
00167 assert(p < reinterpret_cast<char*>(m_mapping) + m_length);
00168 assert(m_mapping <= p);
00169 return p;
00170 }
00171 };
00172
00173 struct Segment {
00174 Block outs;
00175 Block edgeData;
00176 bool loaded;
00177
00178 Segment(): loaded(false) { }
00179
00180 void unload() {
00181 outs.unload();
00182 edgeData.unload();
00183 loaded = false;
00184 }
00185 };
00186
00187 void* masterMapping;
00188 int masterFD;
00189 size_t masterLength;
00190 uint64_t numEdges;
00191 uint64_t numNodes;
00192 uint64_t* outIdx;
00193
00194 public:
00195 typedef Segment segment_type;
00196
00197 OCFileGraph(): masterMapping(0), masterFD(-1), numEdges(0), numNodes(0), outIdx(0) { }
00198 ~OCFileGraph();
00199
00200 iterator begin() const { return iterator(0); }
00201 iterator end() const { return iterator(numNodes); }
00202 uint64_t size() const { return numNodes; }
00203 uint64_t sizeEdges() const { return numEdges; }
00204 edge_iterator edge_begin(GraphNode n) const { return edge_iterator(n == 0 ? 0 : outIdx[n-1]); }
00205 edge_iterator edge_end(GraphNode n) const { return edge_iterator(outIdx[n]); }
00206 edge_offset_iterator edge_offset_begin() const { return outIdx; }
00207 edge_offset_iterator edge_offset_end() const { return outIdx + numNodes; }
00208
00209 template<typename EdgeTy>
00210 typename EdgeReference<EdgeTy>::type getEdgeData(const segment_type& s, edge_iterator it, typename std::enable_if<!std::is_same<void,EdgeTy>::value>::type* = 0) {
00211 EdgeTy* p = reinterpret_cast<EdgeTy*>(s.edgeData.get(*it));
00212 return *p;
00213 }
00214
00215 template<typename EdgeTy>
00216 typename EdgeReference<EdgeTy>::type getEdgeData(const segment_type& s, edge_iterator it, typename std::enable_if<std::is_same<void,EdgeTy>::value>::type* = 0) {
00217 return 0;
00218 }
00219
00220 GraphNode getEdgeDst(const segment_type& s, edge_iterator it) {
00221 uint32_t* p = reinterpret_cast<uint32_t*>(s.outs.get(*it));
00222 return *p;
00223 }
00224
00225 void unload(segment_type& s) {
00226 if (!s.loaded)
00227 return;
00228
00229 s.outs.unload();
00230 s.edgeData.unload();
00231 s.loaded = false;
00232 }
00233
00234 void load(segment_type& s, edge_iterator begin, edge_iterator end, size_t sizeof_data);
00235
00236 void structureFromFile(const std::string& fname);
00237 };
00238
00239 struct read_oc_immutable_edge_graph_tag { };
00240
00241 template<typename NodeTy, typename EdgeTy,
00242 bool HasNoLockable=false,
00243
00244 bool HasOutOfLineLockable=false>
00245 class OCImmutableEdgeGraph:
00246 private detail::LocalIteratorFeature<false>,
00247 private detail::OutOfLineLockableFeature<HasOutOfLineLockable && !HasNoLockable> {
00248 public:
00249 template<bool _has_id>
00250 struct with_id {
00251 typedef OCImmutableEdgeGraph type;
00252 };
00253
00254 template<typename _node_data>
00255 struct with_node_data {
00256 typedef OCImmutableEdgeGraph<_node_data,EdgeTy,HasNoLockable,HasOutOfLineLockable> type;
00257 };
00258
00259 template<bool _has_no_lockable>
00260 struct with_no_lockable {
00261 typedef OCImmutableEdgeGraph<NodeTy,EdgeTy,_has_no_lockable,HasOutOfLineLockable> type;
00262 };
00263
00264 template<bool _use_numa_alloc>
00265 struct with_numa_alloc {
00266 typedef OCImmutableEdgeGraph type;
00267 };
00268
00269 template<bool _has_out_of_line_lockable>
00270 struct with_out_of_line_lockable {
00271 typedef OCImmutableEdgeGraph<NodeTy,EdgeTy,HasNoLockable,_has_out_of_line_lockable> type;
00272 };
00273
00274 typedef read_oc_immutable_edge_graph_tag read_tag;
00275
00276 private:
00277 typedef detail::NodeInfoBase<NodeTy,!HasNoLockable && !HasOutOfLineLockable> NodeInfo;
00278 typedef LargeArray<NodeInfo> NodeData;
00279
00280 NodeData nodeData;
00281 OCFileGraph outGraph;
00282 OCFileGraph inGraphStorage;
00283 OCFileGraph* inGraph;
00284
00285 uint64_t numNodes;
00286 uint64_t numEdges;
00287
00288 public:
00289 typedef int tt_is_segmented;
00290
00291 typedef typename OCFileGraph::GraphNode GraphNode;
00292 typedef EdgeTy edge_data_type;
00293 typedef NodeTy node_data_type;
00294 typedef typename OCFileGraph::template EdgeReference<EdgeTy>::type edge_data_reference;
00295 typedef typename NodeInfo::reference node_data_reference;
00296 typedef typename OCFileGraph::edge_iterator edge_iterator;
00297 typedef edge_iterator in_edge_iterator;
00298 typedef typename OCFileGraph::iterator iterator;
00299 typedef iterator const_iterator;
00300 typedef boost::counting_iterator<GraphNode> local_iterator;
00301 typedef local_iterator const_local_iterator;
00302
00303 class segment_type {
00304 template<typename,typename,bool,bool> friend class OCImmutableEdgeGraph;
00305 OCFileGraph::segment_type out;
00306 OCFileGraph::segment_type in;
00307 iterator nodeBegin;
00308 iterator nodeEnd;
00309 public:
00311 bool loaded() const { return out.loaded; }
00313 explicit operator bool() { return nodeBegin != nodeEnd; }
00314 size_t size() const { return std::distance(nodeBegin, nodeEnd); }
00315 bool containsNode(size_t n) const {
00316 return *nodeBegin <= n && n < *nodeEnd;
00317 }
00318 };
00319
00320 private:
00321 Galois::optional<segment_type> memorySegment;
00322
00323 segment_type computeSegment(size_t startNode, size_t numEdges) {
00324 typedef typename OCFileGraph::edge_offset_iterator edge_offset_iterator;
00325
00326 segment_type ret;
00327
00328 edge_offset_iterator outStart = outGraph.edge_offset_begin();
00329 edge_offset_iterator outEnd = outGraph.edge_offset_end();
00330 std::advance(outStart, startNode);
00331 if (outStart == outEnd) {
00332 ret.nodeBegin = ret.nodeEnd = iterator(0);
00333 return ret;
00334 }
00335 edge_offset_iterator outNext = std::lower_bound(outStart + 1, outEnd, *outStart + numEdges);
00336 ptrdiff_t outNodes = std::distance(outStart, outNext);
00337
00338 edge_offset_iterator inStart = inGraph->edge_offset_begin();
00339 edge_offset_iterator inEnd = inGraph->edge_offset_end();
00340 std::advance(inStart, startNode);
00341 edge_offset_iterator inNext = std::lower_bound(inStart + 1, inEnd, *inStart + numEdges);
00342 ptrdiff_t inNodes = std::distance(inStart, inNext);
00343
00344 ptrdiff_t nodes = std::min(outNodes, inNodes);
00345
00346 ret.nodeBegin = iterator(startNode);
00347 ret.nodeEnd = iterator(startNode + nodes);
00348 return ret;
00349 }
00350
00351 void load(segment_type& seg, size_t sizeof_data) {
00352 outGraph.load(seg.out, outGraph.edge_begin(*seg.nodeBegin), outGraph.edge_end(seg.nodeEnd[-1]), sizeof_data);
00353 if (inGraph != &outGraph)
00354 inGraph->load(seg.in, inGraph->edge_begin(*seg.nodeBegin), inGraph->edge_end(seg.nodeEnd[-1]), sizeof_data);
00355 else
00356 seg.in = seg.out;
00357 }
00358
00359 template<bool _A1 = HasNoLockable, bool _A2 = HasOutOfLineLockable>
00360 void acquireNode(GraphNode N, MethodFlag mflag, typename std::enable_if<!_A1 && !_A2>::type* = 0) {
00361 Galois::Runtime::acquire(&nodeData[N], mflag);
00362 }
00363
00364 template<bool _A1 = HasOutOfLineLockable, bool _A2 = HasNoLockable>
00365 void acquireNode(GraphNode N, MethodFlag mflag, typename std::enable_if<_A1 && !_A2>::type* = 0) {
00366 this->outOfLineAcquire(idFromNode(N), mflag);
00367 }
00368
00369 template<bool _A1 = HasOutOfLineLockable, bool _A2 = HasNoLockable>
00370 void acquireNode(GraphNode N, MethodFlag mflag, typename std::enable_if<_A2>::type* = 0) { }
00371
00372 public:
00373 ~OCImmutableEdgeGraph() {
00374 if (memorySegment) {
00375 outGraph.unload(memorySegment->out);
00376 if (inGraph != &outGraph)
00377 inGraph->unload(memorySegment->in);
00378 }
00379 }
00380
00381 void keepInMemory() {
00382 memorySegment = Galois::optional<segment_type>(computeSegment(0, numEdges));
00383 load(*memorySegment, LazyObject<EdgeTy>::size_of::value);
00384 }
00385
00391 segment_type nextSegment(size_t edges) {
00392 if (memorySegment)
00393 return *memorySegment;
00394 else
00395 return computeSegment(0, edges);
00396 }
00397
00401 segment_type nextSegment(const segment_type& cur, size_t edges) {
00402 return computeSegment(*cur.nodeEnd, edges);
00403 }
00404
00405 void load(segment_type& seg) {
00406 if (memorySegment)
00407 return;
00408
00409 load(seg, LazyObject<EdgeTy>::size_of::value);
00410 }
00411
00412 void unload(segment_type& seg) {
00413 if (memorySegment)
00414 return;
00415
00416 outGraph.unload(seg.out);
00417 if (inGraph != &outGraph)
00418 inGraph->unload(seg.in);
00419 }
00420
00421 iterator begin(const segment_type& cur) { return cur.nodeBegin; }
00422 iterator end(const segment_type& cur) { return cur.nodeEnd; }
00423
00424 node_data_reference getData(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00425 Galois::Runtime::checkWrite(mflag, false);
00426 NodeInfo& NI = nodeData[N];
00427 acquireNode(N, mflag);
00428 return NI.getData();
00429 }
00430
00431 edge_data_reference getEdgeData(const segment_type& segment, edge_iterator ni, MethodFlag mflag = MethodFlag::NONE) {
00432 Galois::Runtime::checkWrite(mflag, false);
00433 return outGraph.getEdgeData<EdgeTy>(segment.out, ni);
00434 }
00435
00436 GraphNode getEdgeDst(const segment_type& segment, edge_iterator ni) {
00437 return outGraph.getEdgeDst(segment.out, ni);
00438 }
00439
00440 uint64_t size() const { return numNodes; }
00441 uint64_t sizeEdges() const { return numEdges; }
00442
00443 iterator begin() const { return outGraph.begin(); }
00444 iterator end() const { return outGraph.end(); }
00445
00446 const_local_iterator local_begin() const { return const_local_iterator(this->localBegin(numNodes)); }
00447 const_local_iterator local_end() const { return const_local_iterator(this->localEnd(numNodes)); }
00448 local_iterator local_begin() { return local_iterator(this->localBegin(numNodes)); }
00449 local_iterator local_end() { return local_iterator(this->localEnd(numNodes)); }
00450
00451 edge_iterator edge_begin(const segment_type& segment, GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00452 acquireNode(N, mflag);
00453 if (Galois::Runtime::shouldLock(mflag)) {
00454 for (edge_iterator ii = outGraph.edge_begin(N), ee = outGraph.edge_end(N); ii != ee; ++ii) {
00455 acquireNode(outGraph.getEdgeDst(segment.out, *ii), mflag);
00456 }
00457 }
00458 return outGraph.edge_begin(N);
00459 }
00460
00461 edge_iterator edge_end(const segment_type& segment, GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00462 acquireNode(N, mflag);
00463 return outGraph.edge_end(N);
00464 }
00465
00466 edge_data_reference getInEdgeData(const segment_type& segment, edge_iterator ni, MethodFlag mflag = MethodFlag::NONE) {
00467 Galois::Runtime::checkWrite(mflag, false);
00468 return inGraph->getEdgeData<EdgeTy>(segment.in, ni);
00469 }
00470
00471 GraphNode getInEdgeDst(const segment_type& segment, in_edge_iterator ni) {
00472 return inGraph->getEdgeDst(segment.in, ni);
00473 }
00474
00475 in_edge_iterator in_edge_begin(const segment_type& segment, GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00476 acquireNode(N, mflag);
00477 if (Galois::Runtime::shouldLock(mflag)) {
00478 for (in_edge_iterator ii = inGraph->edge_begin(N), ee = inGraph->edge_end(N); ii != ee; ++ii) {
00479 acquireNode(inGraph->getEdgeDst(segment.in, ii), mflag);
00480 }
00481 }
00482 return inGraph->edge_begin(N);
00483 }
00484
00485 in_edge_iterator in_edge_end(const segment_type& segment, GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00486 acquireNode(N, mflag);
00487 return inGraph->edge_end(N);
00488 }
00489
00490 size_t idFromNode(GraphNode N) {
00491 return N;
00492 }
00493
00494 GraphNode nodeFromId(size_t N) {
00495 return N;
00496 }
00497
00499 void createFrom(const std::string& fname) {
00500 outGraph.structureFromFile(fname);
00501 numNodes = outGraph.size();
00502 numEdges = outGraph.sizeEdges();
00503 nodeData.create(numNodes);
00504 inGraph = &outGraph;
00505 this->outOfLineAllocateInterleaved(numNodes);
00506 for (size_t i = 0; i < numNodes; ++i)
00507 this->outOfLineConstructAt(i);
00508 }
00509
00510 void createFrom(const std::string& fname, const std::string& transpose) {
00511 outGraph.structureFromFile(fname);
00512 inGraphStorage.structureFromFile(transpose);
00513 numNodes = outGraph.size();
00514 if (numNodes != inGraphStorage.size())
00515 GALOIS_DIE("graph does not have the same number of nodes as its transpose");
00516 numEdges = outGraph.sizeEdges();
00517 nodeData.create(numNodes);
00518 inGraph = &inGraphStorage;
00519 this->outOfLineAllocateInterleaved(numNodes);
00520 for (size_t i = 0; i < numNodes; ++i)
00521 this->outOfLineConstructAt(i);
00522 }
00523 };
00524
00525 template<typename GraphTy,typename... Args>
00526 void readGraphDispatch(GraphTy& graph, read_oc_immutable_edge_graph_tag, Args&&... args) {
00527 graph.createFrom(std::forward<Args>(args)...);
00528 }
00529
00530
00531 }
00532 }
00533
00534 #endif
