Galois
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
LC_InlineEdge_Graph.h
Go to the documentation of this file.
1 /*
2  * This file belongs to the Galois project, a C++ library for exploiting
3  * parallelism. The code is being released under the terms of the 3-Clause BSD
4  * License (a copy is located in LICENSE.txt at the top-level directory).
5  *
6  * Copyright (C) 2018, The University of Texas at Austin. All rights reserved.
7  * UNIVERSITY EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES CONCERNING THIS
8  * SOFTWARE AND DOCUMENTATION, INCLUDING ANY WARRANTIES OF MERCHANTABILITY,
9  * FITNESS FOR ANY PARTICULAR PURPOSE, NON-INFRINGEMENT AND WARRANTIES OF
10  * PERFORMANCE, AND ANY WARRANTY THAT MIGHT OTHERWISE ARISE FROM COURSE OF
11  * DEALING OR USAGE OF TRADE. NO WARRANTY IS EITHER EXPRESS OR IMPLIED WITH
12  * RESPECT TO THE USE OF THE SOFTWARE OR DOCUMENTATION. Under no circumstances
13  * shall University be liable for incidental, special, indirect, direct or
14  * consequential damages or loss of profits, interruption of business, or
15  * related expenses which may arise from use of Software or Documentation,
16  * including but not limited to those resulting from defects in Software and/or
17  * Documentation, or loss or inaccuracy of data of any kind.
18  */
19 
20 #ifndef GALOIS_GRAPHS_LC_INLINEEDGE_GRAPH_H
21 #define GALOIS_GRAPHS_LC_INLINEEDGE_GRAPH_H
22 
23 #include <type_traits>
24 
25 #include "galois/config.h"
26 #include "galois/LargeArray.h"
28 #include "galois/graphs/Details.h"
29 
30 namespace galois {
31 namespace graphs {
32 
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 &&
48  !HasNoLockable> {
49  template <typename Graph>
50  friend class LC_InOut_Graph;
51 
52 public:
53  template <bool _has_id>
54  struct with_id {
56  };
57 
58  template <typename _node_data>
59  struct with_node_data {
60  typedef LC_InlineEdge_Graph<_node_data, EdgeTy, HasNoLockable, UseNumaAlloc,
61  HasOutOfLineLockable, HasCompressedNodePtr,
62  FileEdgeTy>
64  };
65 
66  template <typename _edge_data>
67  struct with_edge_data {
68  typedef LC_InlineEdge_Graph<NodeTy, _edge_data, HasNoLockable, UseNumaAlloc,
69  HasOutOfLineLockable, HasCompressedNodePtr,
70  FileEdgeTy>
72  };
73 
74  template <typename _file_edge_data>
76  typedef LC_InlineEdge_Graph<NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc,
77  HasOutOfLineLockable, HasCompressedNodePtr,
78  _file_edge_data>
80  };
81 
82  template <bool _has_no_lockable>
84  typedef LC_InlineEdge_Graph<NodeTy, EdgeTy, _has_no_lockable, UseNumaAlloc,
85  HasOutOfLineLockable, HasCompressedNodePtr,
86  FileEdgeTy>
88  };
89 
90  template <bool _use_numa_alloc>
91  struct with_numa_alloc {
92  typedef LC_InlineEdge_Graph<NodeTy, EdgeTy, HasNoLockable, _use_numa_alloc,
93  HasOutOfLineLockable, HasCompressedNodePtr,
94  FileEdgeTy>
96  };
97 
98  template <bool _has_out_of_line_lockable>
100  typedef LC_InlineEdge_Graph<NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc,
101  _has_out_of_line_lockable, HasCompressedNodePtr,
102  FileEdgeTy>
104  };
105 
110  template <bool _has_compressed_node_ptr>
112  typedef LC_InlineEdge_Graph<NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc,
113  HasOutOfLineLockable, _has_compressed_node_ptr,
114  FileEdgeTy>
116  };
117 
119 
120 protected:
121  class NodeInfo;
122  typedef internal::EdgeInfoBase<
123  typename std::conditional<HasCompressedNodePtr, uint32_t,
124  NodeInfo*>::type,
125  EdgeTy>
126  EdgeInfo;
129  typedef internal::NodeInfoBaseTypes<NodeTy,
130  !HasNoLockable && !HasOutOfLineLockable>
132 
133  class NodeInfo
134  : public internal::NodeInfoBase<NodeTy,
135  !HasNoLockable && !HasOutOfLineLockable> {
136  EdgeInfo* m_edgeBegin;
137  EdgeInfo* m_edgeEnd;
138 
139  public:
140  EdgeInfo*& edgeBegin() { return m_edgeBegin; }
141  EdgeInfo*& edgeEnd() { return m_edgeEnd; }
142  };
143 
144 public:
145  typedef NodeInfo* GraphNode;
146  typedef EdgeTy edge_data_type;
147  typedef FileEdgeTy file_edge_data_type;
148  typedef NodeTy node_data_type;
150  typedef typename NodeInfoTypes::reference node_data_reference;
156 
157 protected:
160  uint64_t numNodes;
161  uint64_t numEdges;
162 
163  template <bool C_b = HasCompressedNodePtr>
165  typename std::enable_if<C_b>::type* = 0) const {
166  return const_cast<NodeInfo*>(&nodeData[ii->dst]);
167  }
168 
169  template <bool C_b = HasCompressedNodePtr>
171  typename std::enable_if<!C_b>::type* = 0) const {
172  return ii->dst;
173  }
174 
175  template <typename Container, typename Index, bool C_b = HasCompressedNodePtr>
176  void setEdgeDst(Container&, edge_iterator edge, Index idx,
177  typename std::enable_if<C_b>::type* = 0) {
178  edge->dst = idx;
179  }
180 
181  template <typename Container, typename Index, bool C_b = HasCompressedNodePtr>
182  void setEdgeDst(Container& c, edge_iterator edge, Index idx,
183  typename std::enable_if<!C_b>::type* = 0) {
184  edge->dst = &c[idx];
185  }
186 
187  template <bool _A1 = HasNoLockable, bool _A2 = HasOutOfLineLockable>
189  typename std::enable_if<!_A1 && !_A2>::type* = 0) {
190  galois::runtime::acquire(N, mflag);
191  }
192 
193  template <bool _A1 = HasOutOfLineLockable, bool _A2 = HasNoLockable>
195  typename std::enable_if<_A1 && !_A2>::type* = 0) {
196  this->outOfLineAcquire(getId(N), mflag);
197  }
198 
199  template <bool _A1 = HasOutOfLineLockable, bool _A2 = HasNoLockable>
201  typename std::enable_if<_A2>::type* = 0) {}
202 
204  return nodeData[getId(N)].edgeBegin();
205  }
206 
207  edge_iterator raw_end(GraphNode N) { return nodeData[getId(N)].edgeEnd(); }
208 
209  template <bool _A1 = EdgeInfo::has_value,
212  typename FileGraph::edge_iterator nn, EdgeInfo* edge,
213  typename std::enable_if<!_A1 || _A2>::type* = 0) {
214  typedef LargeArray<FileEdgeTy> FED;
215  if (EdgeInfo::has_value)
216  edge->construct(graph.getEdgeData<typename FED::value_type>(nn));
217  }
218 
219  template <bool _A1 = EdgeInfo::has_value,
222  EdgeInfo* edge,
223  typename std::enable_if<_A1 && !_A2>::type* = 0) {
224  edge->construct();
225  }
226 
227  size_t getId(GraphNode N) { return std::distance(this->nodeData.data(), N); }
228 
229  GraphNode getNode(size_t n) { return &nodeData[n]; }
230 
231 public:
233  if (!EdgeInfo::has_value)
234  return;
235  if (numNodes == 0)
236  return;
237 
238  for (edge_iterator ii = nodeData[0].edgeBegin(),
239  ei = nodeData[numNodes - 1].edgeEnd();
240  ii != ei; ++ii) {
241  ii->destroy();
242  }
243  }
244 
246  MethodFlag mflag = MethodFlag::WRITE) {
247  // galois::runtime::checkWrite(mflag, false);
248  acquireNode(N, mflag);
249  return N->getData();
250  }
251 
254  MethodFlag GALOIS_UNUSED(mflag) = MethodFlag::UNPROTECTED) const {
255  // galois::runtime::checkWrite(mflag, false);
256  return ni->get();
257  }
258 
259  GraphNode getEdgeDst(edge_iterator ni) const { return getDst(ni); }
260 
261  size_t size() const { return numNodes; }
262  size_t sizeEdges() const { return numEdges; }
263 
267  iterator end() { return iterator(nodeData.end()); }
268 
270  return local_iterator(&nodeData[this->localBegin(numNodes)]);
271  }
273  return local_iterator(&nodeData[this->localEnd(numNodes)]);
274  }
276  return const_local_iterator(&nodeData[this->localBegin(numNodes)]);
277  }
279  return const_local_iterator(&nodeData[this->localEnd(numNodes)]);
280  }
281 
283  acquireNode(N, mflag);
284  if (galois::runtime::shouldLock(mflag)) {
285  for (edge_iterator ii = N->edgeBegin(), ee = N->edgeEnd(); ii != ee;
286  ++ii) {
287  acquireNode(getDst(ii), mflag);
288  }
289  }
290  return N->edgeBegin();
291  }
292 
294  acquireNode(N, mflag);
295  return N->edgeEnd();
296  }
297 
300  return internal::make_no_deref_range(edge_begin(N, mflag),
301  edge_end(N, mflag));
302  }
303 
306  return edges(N, mflag);
307  }
308 
309 #if 0
310 
313  template<typename CompTy>
314  void sortEdgesByEdgeData(GraphNode N, const CompTy& comp = std::less<EdgeTy>(), MethodFlag mflag = MethodFlag::WRITE) {
315  galois::runtime::acquire(N, mflag);
316  std::sort(edge_sort_begin(N), edge_sort_end(N), EdgeSortCompWrapper<EdgeSortValue<GraphNode,EdgeTy>,CompTy>(comp));
317  }
318 
322  template<typename CompTy>
323  void sortEdges(GraphNode N, const CompTy& comp, MethodFlag mflag = MethodFlag::WRITE) {
324  galois::runtime::acquire(N, mflag);
325  std::sort(edge_sort_begin(N), edge_sort_end(N), comp);
326  }
327 #endif
328 
329  void allocateFrom(FileGraph& graph) {
330  numNodes = graph.size();
331  numEdges = graph.sizeEdges();
332 
333  if (UseNumaAlloc) {
336  this->outOfLineAllocateBlocked(numNodes);
337  } else {
340  this->outOfLineAllocateInterleaved(numNodes);
341  }
342  }
343 
344  void constructFrom(FileGraph& graph, unsigned tid, unsigned total) {
345  auto r =
346  graph
347  .divideByNode(NodeData::size_of::value +
348  LC_InlineEdge_Graph::size_of_out_of_line::value,
349  EdgeData::size_of::value, tid, total)
350  .first;
351 
352  EdgeInfo* curEdge = edgeData.data() + *graph.edge_begin(*r.first);
353 
354  this->setLocalRange(*r.first, *r.second);
355 
356  for (FileGraph::iterator ii = r.first, ei = r.second; ii != ei; ++ii) {
357  nodeData.constructAt(*ii);
358  this->outOfLineConstructAt(*ii);
359  nodeData[*ii].edgeBegin() = curEdge;
360  for (FileGraph::edge_iterator nn = graph.edge_begin(*ii),
361  en = graph.edge_end(*ii);
362  nn != en; ++nn) {
363  constructEdgeValue(graph, nn, curEdge);
364  setEdgeDst(nodeData, curEdge, graph.getEdgeDst(nn));
365  ++curEdge;
366  }
367  nodeData[*ii].edgeEnd() = curEdge;
368  }
369  }
370 };
371 
372 } // namespace graphs
373 } // namespace galois
374 
375 #endif
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&#39;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
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&#39;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
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