/[escript]/trunk/cusplibrary/performance/graph/maximum_flow.cu
ViewVC logotype

Contents of /trunk/cusplibrary/performance/graph/maximum_flow.cu

Parent Directory Parent Directory | Revision Log Revision Log


Revision 5148 - (show annotations)
Mon Sep 15 01:25:23 2014 UTC (6 years, 4 months ago) by caltinay
File size: 2296 byte(s)
Merging ripley diagonal storage + CUDA support into trunk.
Options file version has been incremented due to new options
'cuda' and 'nvccflags'.

1 #include <cusp/csr_matrix.h>
2 #include <cusp/print.h>
3
4 #include <cusp/gallery/grid.h>
5 #include <cusp/graph/maximum_flow.h>
6 #include <cusp/io/matrix_market.h>
7
8 #include "../timer.h"
9
10 template<typename MemorySpace, typename MatrixType>
11 void MaxFlow(const MatrixType& G)
12 {
13 typedef typename MatrixType::index_type IndexType;
14 typedef typename MatrixType::value_type ValueType;
15 typedef cusp::csr_matrix<IndexType,ValueType,MemorySpace> GraphType;
16
17 GraphType G_flow(G);
18 cusp::array1d<IndexType,MemorySpace> min_cut_edges(G.num_entries);
19 cusp::array1d<ValueType,MemorySpace> flow(G.num_entries);
20
21 IndexType source = 0;
22 IndexType sink = G.num_rows - 1;
23
24 {
25 timer t;
26 ValueType capacity = cusp::graph::maximum_flow(G_flow, flow, source, sink);
27 std::cout << "Max-Flow time : " << t.milliseconds_elapsed() << " (ms), with capacity : " << capacity << std::endl;
28 }
29
30 {
31 timer t;
32 size_t min_cut_size = cusp::graph::max_flow_to_min_cut(G_flow, flow, source, min_cut_edges);
33 std::cout << "\tMin-Cut time : " << t.milliseconds_elapsed() << " (ms), found " << min_cut_size << " edge cuts." << std::endl;
34 }
35 }
36
37 int main(int argc, char*argv[])
38 {
39 srand(time(NULL));
40
41 typedef int IndexType;
42 typedef int ValueType;
43 typedef cusp::host_memory MemorySpace;
44
45 cusp::csr_matrix<IndexType, ValueType, MemorySpace> A;
46 size_t size = 4;
47
48 if (argc == 1)
49 {
50 // no input file was specified, generate an example
51 std::cout << "Generated matrix (2D Grid) ";
52 cusp::gallery::grid2d(A, size, size);
53 }
54 else if (argc == 2)
55 {
56 // an input file was specified, read it from disk
57 cusp::io::read_matrix_market_file(A, argv[1]);
58 std::cout << "Read matrix (" << argv[1] << ") ";
59 }
60
61 std::cout << "with shape (" << A.num_rows << "," << A.num_cols << ") and "
62 << A.num_entries << " entries" << "\n\n";
63
64 // Generate random capacities in range [4,100)
65 for( size_t index = 0; index < A.num_entries; index++ )
66 A.values[index] = (rand() % 100) + 4;
67
68 std::cout << " Device ";
69 MaxFlow<cusp::device_memory>(A);
70
71 std::cout << " Host ";
72 MaxFlow<cusp::host_memory>(A);
73
74 std::cout << std::endl;
75
76 return EXIT_SUCCESS;
77 }
78

  ViewVC Help
Powered by ViewVC 1.1.26