/[escript]/branches/diaplayground/cusplibrary/testing/maximal_independent_set.cu
ViewVC logotype

Contents of /branches/diaplayground/cusplibrary/testing/maximal_independent_set.cu

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4955 - (show annotations)
Tue May 20 04:33:15 2014 UTC (5 years, 4 months ago) by caltinay
File size: 5019 byte(s)
added pristine copy of cusplibrary (apache license) to be used by ripley.

1 #include <unittest/unittest.h>
2
3 #include <cusp/graph/maximal_independent_set.h>
4
5 #include <cusp/array2d.h>
6 #include <cusp/coo_matrix.h>
7 #include <cusp/csr_matrix.h>
8 #include <cusp/dia_matrix.h>
9 #include <cusp/ell_matrix.h>
10 #include <cusp/hyb_matrix.h>
11 #include <cusp/multiply.h>
12 #include <cusp/gallery/poisson.h>
13
14 // check whether the MIS is valid
15 template <typename MatrixType, typename ArrayType>
16 bool is_valid_mis(MatrixType& A, ArrayType& stencil)
17 {
18 typedef typename MatrixType::index_type IndexType;
19 typedef typename MatrixType::value_type ValueType;
20
21 // convert matrix to CSR format on host
22 cusp::csr_matrix<IndexType,ValueType,cusp::host_memory> csr(A);
23
24 // copy mis array to host
25 cusp::array1d<int,cusp::host_memory> mis(stencil);
26
27 for (size_t i = 0; i < csr.num_rows; i++)
28 {
29 size_t num_mis_neighbors = 0;
30
31 for(IndexType jj = csr.row_offsets[i]; jj < csr.row_offsets[i + 1]; jj++)
32 {
33 size_t j = csr.column_indices[jj];
34
35 // XXX if/when MIS code filters explicit zeros we need to do that here too
36
37 if (i != j && mis[j])
38 num_mis_neighbors++;
39 }
40
41 if (mis[i])
42 {
43 if(num_mis_neighbors > 0)
44 {
45 std::cout << "Node " << i << " conflicts with another node" << std::endl;
46 return false;
47 }
48 }
49 else
50 {
51 if (num_mis_neighbors == 0)
52 {
53 std::cout << "Node " << i << " is not in the MIS and has no MIS neighbors" << std::endl;
54 return false;
55 }
56 }
57 }
58
59 return true;
60 }
61
62 template <typename TestMatrix, typename ExampleMatrix>
63 void _TestMaximalIndependentSet(const ExampleMatrix& example_matrix)
64 {
65 typedef typename TestMatrix::memory_space MemorySpace;
66
67 // initialize test matrix
68 TestMatrix test_matrix(example_matrix);
69
70 // allocate storage for MIS result
71 cusp::array1d<int, MemorySpace> stencil(test_matrix.num_rows);
72
73 {
74 // compute MIS(0)
75 size_t num_nodes = cusp::graph::maximal_independent_set(test_matrix, stencil, 0);
76
77 // check MIS(0)
78 ASSERT_EQUAL(thrust::count(stencil.begin(), stencil.end(), 1), num_nodes);
79 ASSERT_EQUAL(num_nodes, test_matrix.num_rows);
80 }
81
82 {
83 // compute MIS(1)
84 size_t num_nodes = cusp::graph::maximal_independent_set(test_matrix, stencil);
85
86 // check MIS for default k=1
87 ASSERT_EQUAL(is_valid_mis(test_matrix, stencil), true);
88 ASSERT_EQUAL(thrust::count(stencil.begin(), stencil.end(), 1), num_nodes);
89 }
90
91 {
92 // compute MIS(2)
93 size_t num_nodes = cusp::graph::maximal_independent_set(test_matrix, stencil, 2);
94
95 // check MIS(2)
96 cusp::coo_matrix<int,float,MemorySpace> A(example_matrix);
97 cusp::coo_matrix<int,float,MemorySpace> A2;
98 cusp::multiply(A, A, A2);
99
100 ASSERT_EQUAL(is_valid_mis(A2, stencil), true);
101 ASSERT_EQUAL(thrust::count(stencil.begin(), stencil.end(), 1), num_nodes);
102 }
103 }
104 template <typename TestMatrix>
105 void TestMaximalIndependentSet(void)
106 {
107 // note: examples should be {0,1} matrices with 1s on the diagonal
108
109 // two components of two nodes
110 cusp::array2d<float,cusp::host_memory> A(4,4);
111 A(0,0) = 1; A(0,1) = 1; A(0,2) = 0; A(0,3) = 0;
112 A(1,0) = 1; A(1,1) = 1; A(1,2) = 0; A(1,3) = 0;
113 A(2,0) = 0; A(2,1) = 0; A(2,2) = 1; A(2,3) = 1;
114 A(3,0) = 0; A(3,1) = 0; A(3,2) = 1; A(3,3) = 1;
115
116 // linear graph
117 cusp::array2d<float,cusp::host_memory> B(4,4);
118 B(0,0) = 1; B(0,1) = 1; B(0,2) = 0; B(0,3) = 0;
119 B(1,0) = 1; B(1,1) = 1; B(1,2) = 1; B(1,3) = 0;
120 B(2,0) = 0; B(2,1) = 1; B(2,2) = 1; B(2,3) = 1;
121 B(3,0) = 0; B(3,1) = 0; B(3,2) = 1; B(3,3) = 1;
122
123 // complete graph
124 cusp::array2d<float,cusp::host_memory> C(6,6,1);
125
126 // empty graph
127 cusp::array2d<float,cusp::host_memory> D(6,6,0);
128
129 cusp::coo_matrix<int,float,cusp::host_memory> E;
130 cusp::gallery::poisson5pt(E, 3, 3);
131 thrust::fill(E.values.begin(), E.values.end(), 1.0f);
132
133 cusp::coo_matrix<int,float,cusp::host_memory> F;
134 cusp::gallery::poisson5pt(F, 13, 17);
135 thrust::fill(F.values.begin(), F.values.end(), 1.0f);
136
137 cusp::coo_matrix<int,float,cusp::host_memory> G;
138 cusp::gallery::poisson5pt(G, 23, 24);
139 thrust::fill(G.values.begin(), G.values.end(), 1.0f);
140
141 cusp::coo_matrix<int,float,cusp::host_memory> H;
142 cusp::gallery::poisson5pt(H, 105, 107);
143 thrust::fill(H.values.begin(), H.values.end(), 1.0f);
144
145 _TestMaximalIndependentSet<TestMatrix>(A);
146 _TestMaximalIndependentSet<TestMatrix>(B);
147 _TestMaximalIndependentSet<TestMatrix>(C);
148 _TestMaximalIndependentSet<TestMatrix>(D);
149 _TestMaximalIndependentSet<TestMatrix>(E);
150 _TestMaximalIndependentSet<TestMatrix>(F);
151 _TestMaximalIndependentSet<TestMatrix>(G);
152 _TestMaximalIndependentSet<TestMatrix>(H);
153 }
154 DECLARE_SPARSE_MATRIX_UNITTEST(TestMaximalIndependentSet);
155

  ViewVC Help
Powered by ViewVC 1.1.26