File: distributed_strong_components_test.cpp

package info (click to toggle)
boost1.55 1.55.0%2Bdfsg-3
  • links: PTS, VCS
  • area: main
  • in suites: jessie, jessie-kfreebsd
  • size: 487,824 kB
  • ctags: 673,349
  • sloc: cpp: 2,098,430; xml: 106,036; ansic: 46,744; python: 32,427; sh: 11,864; cs: 2,121; asm: 1,640; makefile: 984; perl: 714; yacc: 456; php: 132; fortran: 43; sql: 13; csh: 6
file content (175 lines) | stat: -rw-r--r-- 5,404 bytes parent folder | download | duplicates (8)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
// Copyright (C) 2004-2008 The Trustees of Indiana University.

// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Nick Edmonds
//           Douglas Gregor
//           Andrew Lumsdaine

// SCC won't work with CSR currently due to the way the reverse graph 
// is constructed in the SCC algorithm

#include <boost/graph/use_mpi.hpp>

// #define CSR

#ifdef CSR
#  include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
#else
#  include <boost/graph/distributed/adjacency_list.hpp>
#endif

#include <boost/config.hpp>
#include <boost/throw_exception.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/random.hpp>
#include <boost/property_map/parallel/distributed_property_map.hpp>
#include <boost/graph/distributed/mpi_process_group.hpp>
#include <boost/graph/parallel/distribution.hpp>
#include <boost/graph/erdos_renyi_generator.hpp>
#include <boost/test/minimal.hpp>
#include <boost/graph/distributed/graphviz.hpp>
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <boost/random.hpp>
#include <boost/test/minimal.hpp>

#ifdef BOOST_NO_EXCEPTIONS
void
boost::throw_exception(std::exception const& ex)
{
    std::cout << ex.what() << std::endl;
    abort();
}
#endif

typedef double time_type;

inline time_type get_time()
{
  return MPI_Wtime();
}

std::string print_time(time_type t)
{
  std::ostringstream out;
  out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
  return out.str();
}

using namespace boost;
using boost::graph::distributed::mpi_process_group;

void 
test_distributed_strong_components(int n, double _p, bool verify, bool emit_dot_file, int seed)
{
#ifdef CSR
  typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
    distributedS<mpi_process_group> > Graph;
#else
  typedef adjacency_list<listS, 
                         distributedS<mpi_process_group, vecS>,
                         bidirectionalS > Graph;
#endif

  minstd_rand gen;

  gen.seed(seed);

  mpi_process_group pg;
  parallel::variant_distribution<mpi_process_group> distrib 
    = parallel::block(pg, n);

#ifdef CSR
  Graph g(sorted_erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
          sorted_erdos_renyi_iterator<minstd_rand, Graph>(),
          n, pg, distrib);
#else
  Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
          erdos_renyi_iterator<minstd_rand, Graph>(),
          n, pg, distrib);
#endif

  synchronize(g);

  std::vector<int> local_components_vec(num_vertices(g));
  typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> ComponentMap;
  ComponentMap component(local_components_vec.begin(), get(vertex_index, g));

  int num_components = 0;

  time_type start = get_time();
  num_components = strong_components(g, component);
  time_type end = get_time();
  if (process_id(g.process_group()) == 0)
    std::cerr << "Erdos-Reyni graph:\n" << n << " Vertices   " << _p << " Edge probability  " 
              << num_processes(pg) << " Processors\n"
              << "Strong Components time = " << print_time(end - start) << " seconds.\n"
              << num_components << " components identified\n";
  

  if ( verify )
    {
      if ( process_id(g.process_group()) == 0 )
        {
          for (int i = 0; i < n; ++i)
            get(component, vertex(i, g));
          synchronize(component);

          // Check against the sequential version
          typedef adjacency_list<listS, vecS, directedS> Graph2;
          
          gen.seed(seed);
          
          Graph2 g2(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
                    erdos_renyi_iterator<minstd_rand, Graph>(),
                    n);

          std::vector<int> component2(n);
          int seq_num_components = strong_components(g2, make_iterator_property_map(component2.begin(), get(vertex_index, g2)));

          assert(num_components == seq_num_components);

          // Make sure components and component2 match
          std::map<int, int> c2c;
          int i;
          for ( i = 0; i < n; i++ )
            if ( c2c.find( get(component, vertex(i, g)) ) == c2c.end() )
              c2c[get(component, vertex(i, g))] = component2[i];
            else
              if ( c2c[get(component, vertex(i, g))] != component2[i] )
                break;
          
          if ( i < n )
            std::cerr << "Unable to verify SCC result...\n";
          else
            std::cerr << "Passed verification... " << seq_num_components << " strong components\n"; 
        }
      else 
        {
          synchronize(component);
        }
      if ( emit_dot_file )
        write_graphviz("scc.dot", g, paint_by_number(component));
    }
}

int test_main(int argc, char* argv[])
{
  mpi::environment env(argc, argv);

  if (argc == 1)
    test_distributed_strong_components(10000, 0.0005, true, false, 1);
  else if ( argc < 5 )
    std::cerr << "usage: test_distributed_strong_components <int num_vertices> <double p> <bool verify?> <bool emit_dotfile?> [seed]\n";
  else
    test_distributed_strong_components
      (atoi(argv[1]), atof(argv[2]), 
       argv[3]==std::string("true"), argv[4]==std::string("true"),
       argc == 5? 1 : atoi(argv[5]));

  return 0;
}