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
|
/*
* Copyright 2008-2009 NVIDIA Corporation
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include <stack>
#include <cusp/exception.h>
#include <thrust/fill.h>
namespace cusp
{
namespace graph
{
namespace detail
{
namespace host
{
template<typename MatrixType, typename ArrayType>
size_t connected_components(const MatrixType& G, ArrayType& components)
{
typedef typename MatrixType::index_type VertexId;
VertexId num_nodes = G.num_rows;
thrust::fill(components.begin(), components.begin() + num_nodes, -1);
std::stack<VertexId> DFS;
VertexId component = 0;
for(VertexId i = 0; i < num_nodes; i++)
{
if(components[i] == -1)
{
DFS.push(i);
components[i] = component;
while (!DFS.empty())
{
VertexId top = DFS.top();
DFS.pop();
for(VertexId jj = G.row_offsets[top]; jj < G.row_offsets[top + 1]; jj++){
const VertexId j = G.column_indices[jj];
if(components[j] == -1){
DFS.push(j);
components[j] = component;
}
}
}
component++;
}
}
return component;
}
} // end namespace host
} // end namespace detail
} // end namespace graph
} // end namespace cusp
|
