20 #ifndef GALOIS_GRAPHS_LC_INLINEEDGE_GRAPH_H
21 #define GALOIS_GRAPHS_LC_INLINEEDGE_GRAPH_H
23 #include <type_traits>
25 #include "galois/config.h"
41 template <
typename NodeTy,
typename EdgeTy,
bool HasNoLockable =
false,
42 bool UseNumaAlloc =
false,
bool HasOutOfLineLockable =
false,
43 bool HasCompressedNodePtr =
false,
typename FileEdgeTy = EdgeTy>
45 :
private boost::noncopyable,
46 private internal::LocalIteratorFeature<UseNumaAlloc>,
47 private internal::OutOfLineLockableFeature<HasOutOfLineLockable &&
49 template <
typename Graph>
53 template <
bool _has_
id>
58 template <
typename _node_data>
61 HasOutOfLineLockable, HasCompressedNodePtr,
66 template <
typename _edge_data>
69 HasOutOfLineLockable, HasCompressedNodePtr,
74 template <
typename _file_edge_data>
77 HasOutOfLineLockable, HasCompressedNodePtr,
82 template <
bool _has_no_lockable>
85 HasOutOfLineLockable, HasCompressedNodePtr,
90 template <
bool _use_numa_alloc>
93 HasOutOfLineLockable, HasCompressedNodePtr,
98 template <
bool _has_out_of_line_lockable>
101 _has_out_of_line_lockable, HasCompressedNodePtr,
110 template <
bool _has_compressed_node_ptr>
113 HasOutOfLineLockable, _has_compressed_node_ptr,
122 typedef internal::EdgeInfoBase<
123 typename std::conditional<HasCompressedNodePtr, uint32_t,
129 typedef internal::NodeInfoBaseTypes<NodeTy,
130 !HasNoLockable && !HasOutOfLineLockable>
134 :
public internal::NodeInfoBase<NodeTy,
135 !HasNoLockable && !HasOutOfLineLockable> {
163 template <
bool C_b = HasCompressedNodePtr>
165 typename std::enable_if<C_b>::type* = 0)
const {
169 template <
bool C_b = HasCompressedNodePtr>
171 typename std::enable_if<!C_b>::type* = 0)
const {
175 template <
typename Container,
typename Index,
bool C_b = HasCompressedNodePtr>
177 typename std::enable_if<C_b>::type* = 0) {
181 template <
typename Container,
typename Index,
bool C_b = HasCompressedNodePtr>
183 typename std::enable_if<!C_b>::type* = 0) {
187 template <
bool _A1 = HasNoLockable,
bool _A2 = HasOutOfLineLockable>
189 typename std::enable_if<!_A1 && !_A2>::type* = 0) {
193 template <
bool _A1 = HasOutOfLineLockable,
bool _A2 = HasNoLockable>
195 typename std::enable_if<_A1 && !_A2>::type* = 0) {
196 this->outOfLineAcquire(
getId(N), mflag);
199 template <
bool _A1 = HasOutOfLineLockable,
bool _A2 = HasNoLockable>
201 typename std::enable_if<_A2>::type* = 0) {}
209 template <
bool _A1 = EdgeInfo::has_value,
213 typename std::enable_if<!_A1 || _A2>::type* = 0) {
215 if (EdgeInfo::has_value)
219 template <
bool _A1 = EdgeInfo::has_value,
223 typename std::enable_if<_A1 && !_A2>::type* = 0) {
233 if (!EdgeInfo::has_value)
300 return internal::make_no_deref_range(
edge_begin(N, mflag),
306 return edges(N, mflag);
313 template<
typename CompTy>
322 template<
typename CompTy>
325 std::sort(edge_sort_begin(N), edge_sort_end(N), comp);
336 this->outOfLineAllocateBlocked(
numNodes);
340 this->outOfLineAllocateInterleaved(
numNodes);
348 LC_InlineEdge_Graph::size_of_out_of_line::value,
349 EdgeData::size_of::value, tid, total)
354 this->setLocalRange(*r.first, *r.second);
358 this->outOfLineConstructAt(*ii);
359 nodeData[*ii].edgeBegin() = curEdge;
NodeTy node_data_type
Definition: LC_InlineEdge_Graph.h:148
void setEdgeDst(Container &, edge_iterator edge, Index idx, typename std::enable_if< C_b >::type *=0)
Definition: LC_InlineEdge_Graph.h:176
EdgeData edgeData
Definition: LC_InlineEdge_Graph.h:159
runtime::iterable< NoDerefIterator< edge_iterator > > out_edges(GraphNode N, MethodFlag mflag=MethodFlag::WRITE)
Definition: LC_InlineEdge_Graph.h:305
LC_InlineEdge_Graph< NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, _has_compressed_node_ptr, FileEdgeTy > type
Definition: LC_InlineEdge_Graph.h:115
const_iterator const_local_iterator
Definition: LC_InlineEdge_Graph.h:155
const_local_iterator local_end() const
Definition: LC_InlineEdge_Graph.h:278
EdgeInfo *& edgeBegin()
Definition: LC_InlineEdge_Graph.h:140
iterator begin()
Definition: LC_InlineEdge_Graph.h:266
edge_iterator edge_begin(GraphNode N)
Returns the index to the beginning of global node N's outgoing edges in the outgoing edges array...
Definition: FileGraph.cpp:641
Contains FileGraph and FileGraphWriter class declarations.
internal::EdgeInfoBase< typename std::conditional< HasCompressedNodePtr, uint32_t, NodeInfo * >::type, EdgeTy > EdgeInfo
Definition: LC_InlineEdge_Graph.h:121
local_iterator local_end()
Definition: LC_InlineEdge_Graph.h:272
size_t size() const
Returns the number of nodes in the (sub)graph.
Definition: FileGraph.h:545
edge_iterator edge_begin(GraphNode N, MethodFlag mflag=MethodFlag::WRITE)
Definition: LC_InlineEdge_Graph.h:282
boost::counting_iterator< uint64_t > iterator
uint64 boost counting iterator
Definition: FileGraph.h:408
NodeInfo * GraphNode
Definition: LC_InlineEdge_Graph.h:145
edge_iterator raw_end(GraphNode N)
Definition: LC_InlineEdge_Graph.h:207
runtime::iterable< NoDerefIterator< edge_iterator > > edges(GraphNode N, MethodFlag mflag=MethodFlag::WRITE)
Definition: LC_InlineEdge_Graph.h:299
EdgeInfo *& edgeEnd()
Definition: LC_InlineEdge_Graph.h:141
~LC_InlineEdge_Graph()
Definition: LC_InlineEdge_Graph.h:232
const_local_iterator local_begin() const
Definition: LC_InlineEdge_Graph.h:275
GraphNode getEdgeDst(edge_iterator it)
Gets the destination of some edge.
Definition: FileGraph.cpp:669
iterator end()
Definition: LC_InlineEdge_Graph.h:267
boost::counting_iterator< uint64_t > edge_iterator
Edge iterators (boost iterator)
Definition: FileGraph.h:248
Definition: Iterable.h:36
LargeArray< EdgeInfo > EdgeData
Definition: LC_InlineEdge_Graph.h:127
FileEdgeTy file_edge_data_type
Definition: LC_InlineEdge_Graph.h:147
NodeInfoTypes::reference node_data_reference
Definition: LC_InlineEdge_Graph.h:150
const_iterator end() const
Definition: LC_InlineEdge_Graph.h:265
EdgeTy edge_data_type
Definition: LC_InlineEdge_Graph.h:146
bool shouldLock(const galois::MethodFlag g)
Helper function to decide if the conflict detection lock should be taken.
Definition: libgalois/include/galois/runtime/Context.h:189
Definition: LC_InlineEdge_Graph.h:59
LC_InlineEdge_Graph< NodeTy, EdgeTy, HasNoLockable, _use_numa_alloc, HasOutOfLineLockable, HasCompressedNodePtr, FileEdgeTy > type
Definition: LC_InlineEdge_Graph.h:95
Definition: LC_InlineEdge_Graph.h:83
Definition: LC_InlineEdge_Graph.h:67
galois::NoDerefIterator< const NodeInfo * > const_iterator
Definition: LC_InlineEdge_Graph.h:153
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
Definition: ParallelSTL.h:247
edge_iterator edge_end(GraphNode N, MethodFlag mflag=MethodFlag::WRITE)
Definition: LC_InlineEdge_Graph.h:293
Modify a LC_Graph to have in and out edges.
Definition: LC_InOut_Graph.h:39
edge_iterator raw_begin(GraphNode N)
Definition: LC_InlineEdge_Graph.h:203
EdgeTy & reference
Definition: LazyObject.h:96
NodeInfo * getDst(edge_iterator ii, typename std::enable_if<!C_b >::type *=0) const
Definition: LC_InlineEdge_Graph.h:170
size_t size() const
Definition: LC_InlineEdge_Graph.h:261
GraphNode getEdgeDst(edge_iterator ni) const
Definition: LC_InlineEdge_Graph.h:259
Modify an iterator so that *it == it.
Definition: NoDerefIterator.h:31
Definition: LC_InlineEdge_Graph.h:99
void allocateInterleaved(size_type n)
[allocatefunctions] Allocates interleaved across NUMA (memory) nodes.
Definition: LargeArray.h:206
LC_InlineEdge_Graph< NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc, _has_out_of_line_lockable, HasCompressedNodePtr, FileEdgeTy > type
Definition: LC_InlineEdge_Graph.h:103
LC_InlineEdge_Graph< NodeTy, EdgeTy, _has_no_lockable, UseNumaAlloc, HasOutOfLineLockable, HasCompressedNodePtr, FileEdgeTy > type
Definition: LC_InlineEdge_Graph.h:87
GraphNode getNode(size_t n)
Definition: LC_InlineEdge_Graph.h:229
void acquireNode(GraphNode N, MethodFlag mflag, typename std::enable_if<!_A1 &&!_A2 >::type *=0)
Definition: LC_InlineEdge_Graph.h:188
LC_InlineEdge_Graph< NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, HasCompressedNodePtr, _file_edge_data > type
Definition: LC_InlineEdge_Graph.h:79
Definition: LC_InlineEdge_Graph.h:133
uint64_t numEdges
Definition: LC_InlineEdge_Graph.h:161
Definition: LC_InlineEdge_Graph.h:91
const_iterator begin() const
Definition: LC_InlineEdge_Graph.h:264
NodeData nodeData
Definition: LC_InlineEdge_Graph.h:158
EdgeInfo::reference edge_data_reference
Definition: LC_InlineEdge_Graph.h:149
Proxy object for internal EdgeSortReference.
Definition: Details.h:56
edge_data_reference getEdgeData(edge_iterator ni, MethodFlag GALOIS_UNUSED(mflag)=MethodFlag::UNPROTECTED) const
Definition: LC_InlineEdge_Graph.h:253
Local computation graph (i.e., graph structure does not change).
Definition: LC_InlineEdge_Graph.h:44
node_data_reference getData(GraphNode N, MethodFlag mflag=MethodFlag::WRITE)
Definition: LC_InlineEdge_Graph.h:245
internal::NodeInfoBaseTypes< NodeTy,!HasNoLockable &&!HasOutOfLineLockable > NodeInfoTypes
Definition: LC_InlineEdge_Graph.h:131
void acquire(Lockable *lockable, galois::MethodFlag m)
Master function which handles conflict detection used to acquire a lockable thing.
Definition: libgalois/include/galois/runtime/Context.h:218
MethodFlag
What should the runtime do when executing a method.
Definition: MethodFlags.h:34
void constructFrom(FileGraph &graph, unsigned tid, unsigned total)
Definition: LC_InlineEdge_Graph.h:344
void acquireNode(GraphNode N, MethodFlag mflag, typename std::enable_if< _A1 &&!_A2 >::type *=0)
Definition: LC_InlineEdge_Graph.h:194
local_iterator local_begin()
Definition: LC_InlineEdge_Graph.h:269
LargeArray< NodeInfo > NodeData
Definition: LC_InlineEdge_Graph.h:128
void allocateFrom(FileGraph &graph)
Definition: LC_InlineEdge_Graph.h:329
LC_InlineEdge_Graph type
Definition: LC_InlineEdge_Graph.h:55
EdgeTy & getEdgeData(GraphNode src, GraphNode dst)
Get edge data of an edge between 2 nodes.
Definition: FileGraph.h:241
void constructAt(size_type n, Args &&...args)
Definition: LargeArray.h:260
GraphRange divideByNode(size_t nodeSize, size_t edgeSize, size_t id, size_t total)
Given a division and a total number of divisions, return a range for that particular division to work...
Definition: FileGraph.cpp:480
edge_iterator edge_end(GraphNode N)
Returns the index to the end of global node N's outgoing edges in the outgoing edges array...
Definition: FileGraph.cpp:655
size_t sizeEdges() const
Returns the number of edges in the (sub)graph.
Definition: FileGraph.h:548
read_default_graph_tag read_tag
Definition: LC_InlineEdge_Graph.h:118
iterator local_iterator
Definition: LC_InlineEdge_Graph.h:154
const_pointer data() const
Definition: LargeArray.h:292
void allocateBlocked(size_type n)
Allocates using blocked memory policy.
Definition: LargeArray.h:213
iterator end()
Definition: LargeArray.h:201
LC_InlineEdge_Graph< _node_data, EdgeTy, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, HasCompressedNodePtr, FileEdgeTy > type
Definition: LC_InlineEdge_Graph.h:63
void setEdgeDst(Container &c, edge_iterator edge, Index idx, typename std::enable_if<!C_b >::type *=0)
Definition: LC_InlineEdge_Graph.h:182
Graph that mmaps Galois gr files for access.
Definition: FileGraph.h:57
size_t getId(GraphNode N)
Definition: LC_InlineEdge_Graph.h:227
NodeInfo * getDst(edge_iterator ii, typename std::enable_if< C_b >::type *=0) const
Definition: LC_InlineEdge_Graph.h:164
galois::NoDerefIterator< NodeInfo * > iterator
Definition: LC_InlineEdge_Graph.h:152
EdgeInfo * edge_iterator
Definition: LC_InlineEdge_Graph.h:151
T value_type
Definition: Executor_ParaMeter.h:111
void construct(Args &&...args)
[allocatefunctions]
Definition: LargeArray.h:254
size_t sizeEdges() const
Definition: LC_InlineEdge_Graph.h:262
Definition: LC_InlineEdge_Graph.h:54
Compress representation of graph at the expense of one level of indirection on accessing neighbors of...
Definition: LC_InlineEdge_Graph.h:111
iterator begin()
Definition: LargeArray.h:199
uint64_t numNodes
Definition: LC_InlineEdge_Graph.h:160
void acquireNode(GraphNode, MethodFlag, typename std::enable_if< _A2 >::type *=0)
Definition: LC_InlineEdge_Graph.h:200
Definition: LC_InlineEdge_Graph.h:75
void constructEdgeValue(FileGraph &graph, typename FileGraph::edge_iterator nn, EdgeInfo *edge, typename std::enable_if<!_A1||_A2 >::type *=0)
Definition: LC_InlineEdge_Graph.h:211
void constructEdgeValue(FileGraph &, typename FileGraph::edge_iterator, EdgeInfo *edge, typename std::enable_if< _A1 &&!_A2 >::type *=0)
Definition: LC_InlineEdge_Graph.h:221
LC_InlineEdge_Graph< NodeTy, _edge_data, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, HasCompressedNodePtr, FileEdgeTy > type
Definition: LC_InlineEdge_Graph.h:71