source: trunk/test/test_adjacency_iteration.cpp @ 4089

Revision 4089, 15.7 KB checked in by gemacke, 2 weeks ago (diff)

This checkin addresses a bunch of issues. A single random number generation scheme is used throughout the codebase (#3934). Subgraph isomorphism is working again (#4225). Simplified vertex_partition_iterator in connected_components.hpp (#4226). Added correct assignemnt and copy construction for vertex and edge property maps and bundles (#4227). Parallelized shiloach_vishkin() using new iteration macros (#4228). Fixed a bug where subgraphs induced using a vertex mask were incorrect (#4229). Updated transpose_adapter to use vertex and edge property maps and bundles and be parallelized using new iteration macros (#4230).

Line 
1/*  _________________________________________________________________________
2 *
3 *  MTGL: The MultiThreaded Graph Library
4 *  Copyright (c) 2008 Sandia Corporation.
5 *  This software is distributed under the BSD License.
6 *  Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
7 *  the U.S. Government retains certain rights in this software.
8 *  For more information, see the COPYING file in the top MTGL directory.
9 *  _________________________________________________________________________
10 */
11
12/****************************************************************************/
13/*! \file test_adjacency_iteration.cpp
14
15    \brief Compares visiting the adjacencies of a graph by accessing a CSR
16           graph structure directly with using the MTGL interface with using
17           the manually load-balanced version of visit_adj().
18
19    \author Jon Berry (jberry@sandia.gov)
20    \author Greg Mackey (gemacke@sandia.gov)
21
22    /date 8/15/2009
23
24    The inlined function test_pred_func() below represents a typical predicate
25    that users may wish to introduce as an algorithmic filter.  Unfortunately,
26    the use of this predicate via a function pointer in the inner loop of the
27    function count_adjacencies_higher_id_func_ptr() prevents the loop-merge
28    necessary for good performance.  The result is a serial inner loop, which
29    has severe consequences when processing power-law data.
30
31    The predicate is easily introduced into the function object
32    test_pred_func_obj.  Using this function object instead of the function
33    pointer restores the loop merge as demonstrated in the function
34    count_adjacencies_higher_id_func_obj().
35*/
36/****************************************************************************/
37
38#include <cstdlib>
39#include <climits>
40
41#include <mtgl/visit_adj.hpp>
42#include <mtgl/compressed_sparse_row_graph.hpp>
43#include <mtgl/mtgl_test.hpp>
44
45using namespace mtgl;
46
47typedef compressed_sparse_row_graph<directedS> Graph;
48typedef graph_traits<Graph>::size_type size_type;
49typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
50typedef graph_traits<Graph>::vertex_iterator vertex_iterator;
51
52/// Counts the number of adjacencies with a higher id than the source using a
53/// pure C traveral.
54template <typename Graph>
55void
56count_adjacencies_higher_id(Graph& g,
57                            typename graph_traits<Graph>::size_type* indeg)
58{
59  typedef typename graph_traits<Graph>::size_type size_type;
60  typedef typename Graph::edge_data edge_data;
61
62  size_type order = g.get_order();
63  size_type* index = g.get_index();
64  edge_data* end_points = g.get_end_points();
65
66  #pragma mta assert noalias *indeg
67  for (size_type i = 0; i < order; ++i)
68  {
69    size_type begin = index[i];
70    size_type end = index[i + 1];
71
72    for (size_type j = begin; j < end; ++j)
73    {
74      if (i < end_points[j].dest) mt_incr(indeg[end_points[j].dest], 1);
75    }
76  }
77}
78
79typedef bool (*pred_t)(size_type, size_type);
80
81#pragma mta inline
82inline bool test_pred_func(size_type i, size_type j)
83{
84  return (i < j);
85}
86
87/// Counts the number of adjacencies with a higher id than the source using a
88/// pure C traveral with a function pointer.
89template <typename Graph>
90void
91count_adjacencies_higher_id_func_ptr(
92    Graph& g, typename graph_traits<Graph>::size_type* indeg, pred_t my_func)
93{
94  typedef typename graph_traits<Graph>::size_type size_type;
95  typedef typename Graph::edge_data edge_data;
96
97  size_type order = g.get_order();
98  size_type* index = g.get_index();
99  edge_data* end_points = g.get_end_points();
100
101  #pragma mta assert noalias *indeg
102  #pragma mta assert parallel
103  for (size_type i = 0; i < order; ++i)
104  {
105    size_type begin = index[i];
106    size_type end = index[i + 1];
107
108    #pragma mta assert parallel
109    for (size_type j = begin; j < end; ++j)
110    {
111      if (my_func(i, end_points[j].dest)) mt_incr(indeg[end_points[j].dest], 1);
112    }
113  }
114}
115
116template <typename Graph>
117class test_pred_func_obj {
118public:
119  typedef typename graph_traits<Graph>::size_type size_type;
120
121  inline bool operator()(size_type i, size_type j) { return (i < j); }
122};
123
124/// Counts the number of adjacencies with a higher id than the source using a
125/// pure C traveral with a function object.
126template <typename Graph, typename pred>
127void
128count_adjacencies_higher_id_func_obj(
129    Graph& g, typename graph_traits<Graph>::size_type* indeg, pred my_func)
130{
131  typedef typename graph_traits<Graph>::size_type size_type;
132  typedef typename Graph::edge_data edge_data;
133
134  size_type order = g.get_order();
135  size_type* index = g.get_index();
136  edge_data* end_points = g.get_end_points();
137
138  #pragma mta assert noalias *indeg
139  for (size_type i = 0; i < order; ++i)
140  {
141    size_type begin = index[i];
142    size_type end = index[i + 1];
143
144    for (size_type j = begin; j < end; ++j)
145    {
146      if (my_func(i, end_points[j].dest)) mt_incr(indeg[end_points[j].dest], 1);
147    }
148  }
149}
150
151/// Counts the number of adjacencies with a higher id than the source using an
152/// MTGL traveral.
153template <typename Graph, typename predicate>
154void count_adjacencies_higher_id_mtgl(
155    Graph& g, typename graph_traits<Graph>::size_type* indeg, predicate f)
156{
157  typedef typename graph_traits<Graph>::size_type size_type;
158  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
159  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
160  typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
161
162  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
163  size_type order = num_vertices(g);
164  vertex_iterator verts = vertices(g);
165
166  #pragma mta assert noalias *indeg
167  for (size_type i = 0; i < order; ++i)
168  {
169    vertex_descriptor u = verts[i];
170    size_type uid = get(vid_map, u);
171    adjacency_iterator adjs = adjacent_vertices(u, g);
172    size_type end = out_degree(u, g);
173
174    for (size_type j = 0; j < end; ++j)
175    {
176      vertex_descriptor v = adjs[j];
177      size_type vid = get(vid_map, v);
178
179      if (f(uid, vid)) mt_incr(indeg[vid], 1);
180    }
181  }
182}
183
184/// A visitor to the load-balanced visit_adj function.
185template <typename Graph, typename predicate>
186class adjacencies_higher_id_computer {
187public:
188  typedef typename graph_traits<Graph>::size_type size_type;
189  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
190
191  adjacencies_higher_id_computer(const vertex_id_map<Graph>& vm, size_type *ind,
192                                 predicate ff) :
193    vid_map(vm), in_degree(ind), f(ff) {}
194
195  inline void operator()(vertex_descriptor src, vertex_descriptor dest)
196  {
197    size_type v1id = get(vid_map, src);
198    size_type v2id = get(vid_map, dest);
199
200    if (f(v1id, v2id)) mt_incr(in_degree[v2id], 1);
201  }
202
203  void post_visit() {}
204
205private:
206  const vertex_id_map<Graph>& vid_map;
207  size_type* in_degree;
208  predicate f;
209};
210
211template <typename Graph, typename visitor>
212void visit_adj_partial(Graph& g, visitor f)
213{
214  typedef typename graph_traits<Graph>::size_type size_type;
215  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
216  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
217  typedef typename Graph::edge_data edge_data;
218
219  const size_type* index = g.get_index();
220  const edge_data* end_points = g.get_end_points();
221  const size_type order = num_vertices(g);
222
223  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
224  vertex_iterator verts = vertices(g);
225
226  #pragma mta assert parallel
227  for (size_type i = 0; i < order; ++i)
228  {
229    vertex_descriptor u = verts[i];
230    size_type begin = index[get(vid_map, u)];
231    size_type end = index[get(vid_map, u) + 1];
232    #pragma mta assert parallel
233    for (size_type j = begin; j < end; ++j)
234    {
235      vertex_descriptor v = verts[end_points[j].dest];
236      f(u, v);
237    }
238  }
239}
240
241template <typename Graph, typename visitor>
242void visit_adj_full(Graph& g, visitor f)
243{
244  typedef typename graph_traits<Graph>::size_type size_type;
245  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
246  typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
247  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
248
249  const size_type *index = g.get_index();
250  const size_type order = num_vertices(g);
251
252  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
253  vertex_iterator verts = vertices(g);
254
255  #pragma mta assert parallel
256  for (size_type i = 0; i < order; ++i)
257  {
258    vertex_descriptor u = verts[i];
259    adjacency_iterator adjs = adjacent_vertices(u, g);
260    size_type end = out_degree(u, g);
261    #pragma mta assert parallel
262    for (size_type j = 0; j < end; ++j)
263    {
264      vertex_descriptor v = adjs[j];
265      f(u, v);
266    }
267  }
268}
269
270template <typename Graph, typename visitor>
271void visit_adj_partial(Graph& g,
272         typename graph_traits<Graph>::vertex_descriptor* to_visit,
273         typename graph_traits<Graph>::size_type num_to_visit,
274         visitor f)
275{
276  typedef typename graph_traits<Graph>::size_type size_type;
277  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
278  typedef typename Graph::edge_data edge_data;
279
280  const size_type *index = g.get_index();
281  const edge_data *end_points = g.get_end_points();
282
283  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
284
285  #pragma mta assert parallel
286  for (size_type i = 0; i < num_to_visit; ++i)
287  {
288    vertex_descriptor u = to_visit[i];
289    size_type begin = index[get(vid_map, u)];
290    size_type end = index[get(vid_map, u) + 1];
291    #pragma mta assert parallel
292    for (size_type j = begin; j < end; ++j)
293    {
294      f(u, end_points[j].dest);
295    }
296  }
297}
298
299template <typename Graph, typename visitor>
300void visit_adj(Graph& g,
301         typename graph_traits<Graph>::vertex_descriptor* to_visit,
302         typename graph_traits<Graph>::size_type num_to_visit,
303         visitor f)
304{
305  typedef typename graph_traits<Graph>::size_type size_type;
306  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
307  typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
308
309  const size_type *index = g.get_index();
310  vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
311
312  #pragma mta assert parallel
313  for (size_type i = 0; i < num_to_visit; ++i)
314  {
315    vertex_descriptor u = to_visit[i];
316    adjacency_iterator adjs = adjacent_vertices(u, g);
317    size_type deg = out_degree(u, g);
318
319    #pragma mta assert parallel
320    for (size_type j = 0; j < deg; ++j)
321    {
322      vertex_descriptor v = adjs[j];
323      f(u, j);
324    }
325  }
326}
327
328void checkError(size_type* indeg, size_type* indeg2, size_type order)
329{
330  size_type error = (std::numeric_limits<size_type>::max)();
331
332  for (size_type i = 0; i < order; ++i)
333  {
334    if (indeg[i] != indeg2[i]) error = i;
335  }
336
337  if (error != (std::numeric_limits<size_type>::max)())
338  {
339    std::cout << "Error in computation: pos " << error << std::endl;
340  }
341}
342
343int main(int argc, char* argv[])
344{
345  init_test(argc, argv);
346
347  Graph g;
348  create_test_graph(g, argc, argv);
349
350  size_type order = num_vertices(g);
351  size_type size = num_edges(g);
352  size_type* indeg = new size_type[order];
353  size_type* indeg2 = new size_type[order];
354
355  test_pred_func_obj<Graph> tpc;
356
357  printf("order: %lu, size: %lu\n", order, size);
358
359  for (size_type i = 0; i < order; ++i) indeg[i] = 0;
360
361  mt_timer timer;
362  int issues, memrefs, concur, streams, traps;
363
364  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
365
366#ifdef __MTA__
367  int phantoms = mta_get_task_counter(RT_PHANTOM);
368  int ready = mta_get_task_counter(RT_READY);
369#endif
370
371  count_adjacencies_higher_id(g, indeg);
372
373  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
374
375#ifdef __MTA__
376  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
377  ready = mta_get_task_counter(RT_READY) - ready;
378#endif
379
380  printf("---------------------------------------------\n");
381  printf("count_adjacencies_higher_id(): \n");
382  printf("---------------------------------------------\n");
383  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
384                     traps);
385#ifdef __MTA__
386  printf("phantoms: %d\n", phantoms);
387  printf("ready: %d\n", ready);
388#endif
389
390  for (size_type i = 0; i < order; ++i) indeg2[i] = 0;
391
392  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
393
394#ifdef __MTA__
395  phantoms = mta_get_task_counter(RT_PHANTOM);
396  ready = mta_get_task_counter(RT_READY);
397#endif
398
399  count_adjacencies_higher_id_func_ptr(g, indeg2, test_pred_func);
400
401  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
402
403#ifdef __MTA__
404  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
405  ready = mta_get_task_counter(RT_READY) - ready;
406#endif
407
408  printf("---------------------------------------------\n");
409  printf("count_adjacencies_higher_id_func_ptr(): \n");
410  printf("---------------------------------------------\n");
411  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
412                     traps);
413
414#ifdef __MTA__
415  printf("phantoms: %d\n", phantoms);
416  printf("ready: %d\n", ready);
417#endif
418
419  checkError(indeg, indeg2, order);
420
421  for (size_type i = 0; i < order; ++i) indeg2[i] = 0;
422
423  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
424
425#ifdef __MTA__
426  phantoms = mta_get_task_counter(RT_PHANTOM);
427  ready = mta_get_task_counter(RT_READY);
428#endif
429
430  count_adjacencies_higher_id_func_obj(g, indeg2, tpc);
431
432  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
433
434#ifdef __MTA__
435  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
436  ready = mta_get_task_counter(RT_READY) - ready;
437#endif
438
439  printf("---------------------------------------------\n");
440  printf("count_adjacencies_higher_id_func_obj(): \n");
441  printf("---------------------------------------------\n");
442  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
443                     traps);
444
445#ifdef __MTA__
446  printf("phantoms: %d\n", phantoms);
447  printf("ready: %d\n", ready);
448#endif
449
450  checkError(indeg, indeg2, order);
451
452  for (size_type i = 0; i < order; ++i) indeg2[i] = 0;
453
454  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
455
456#ifdef __MTA__
457  phantoms = mta_get_task_counter(RT_PHANTOM);
458  ready = mta_get_task_counter(RT_READY);
459#endif
460
461  count_adjacencies_higher_id_mtgl(g, indeg2, tpc);
462
463  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
464
465#ifdef __MTA__
466  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
467  ready = mta_get_task_counter(RT_READY) - ready;
468#endif
469
470  printf("---------------------------------------------\n");
471  printf("count_adjacencies_higher_id_mtgl(): \n");
472  printf("---------------------------------------------\n");
473  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
474                     traps);
475
476#ifdef __MTA__
477  printf("phantoms: %d\n", phantoms);
478  printf("ready: %d\n", ready);
479#endif
480
481  checkError(indeg, indeg2, order);
482
483  for (size_type i = 0; i < order; ++i) indeg2[i] = 0;
484
485  adjacencies_higher_id_computer<Graph, test_pred_func_obj<Graph> >
486    idc(get(_vertex_id_map, g), indeg2, tpc);
487
488  size_type* prefix_counts = 0;
489  size_type* started_nodes = 0;
490  size_type num_threads;
491
492  init_mta_counters(timer, issues, memrefs, concur, streams, traps);
493
494#ifdef __MTA__
495  phantoms = mta_get_task_counter(RT_PHANTOM);
496  ready = mta_get_task_counter(RT_READY);
497#endif
498
499  visit_adj(g, idc, prefix_counts, started_nodes, num_threads);
500  sample_mta_counters(timer, issues, memrefs, concur, streams, traps);
501
502#ifdef __MTA__
503  phantoms = mta_get_task_counter(RT_PHANTOM) - phantoms;
504  ready = mta_get_task_counter(RT_READY) - ready;
505#endif
506
507  printf("---------------------------------------------\n");
508  printf("visit_adj(): \n");
509  printf("---------------------------------------------\n");
510  print_mta_counters(timer, num_edges(g), issues, memrefs, concur, streams,
511                     traps);
512
513  free(prefix_counts);
514  free(started_nodes);
515
516#ifdef __MTA__
517  printf("phantoms: %d\n", phantoms);
518  printf("ready: %d\n", ready);
519#endif
520
521  checkError(indeg, indeg2, order);
522
523  delete [] indeg;
524  delete [] indeg2;
525
526  return 0;
527}
Note: See TracBrowser for help on using the repository browser.