1 
/* 
2 
* Copyright 20082009 NVIDIA Corporation 
3 
* 
4 
* Licensed under the Apache License, Version 2.0 (the "License"); 
5 
* you may not use this file except in compliance with the License. 
6 
* You may obtain a copy of the License at 
7 
* 
8 
* http://www.apache.org/licenses/LICENSE2.0 
9 
* 
10 
* Unless required by applicable law or agreed to in writing, software 
11 
* distributed under the License is distributed on an "AS IS" BASIS, 
12 
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
13 
* See the License for the specific language governing permissions and 
14 
* limitations under the License. 
15 
*/ 
16 

17 
/*! \file maximal_independent_set.h 
18 
* \brief Maximal independent set of a graph 
19 
*/ 
20 

21 
#pragma once 
22 

23 
#include <cusp/detail/config.h> 
24 

25 
namespace cusp 
26 
{ 
27 
namespace graph 
28 
{ 
29 
/*! \addtogroup algorithms Algorithms 
30 
* \ingroup algorithms 
31 
* \{ 
32 
*/ 
33 

34 
/*! \p maximal_independent_set : computes a maximal independent set (MIS) 
35 
* a graph. The MIS is a set of vertices such that (1) no two vertices 
36 
* are adjacent and (2) it is not possible to add another vertex to thes 
37 
* set without violating the first property. The MIS(k) is a generalization 
38 
* of the MIS with the property that no two vertices in the set are joined 
39 
* by a path of \p k edges or less. The standard MIS is therefore a MIS(1). 
40 
* 
41 
* The MIS(k) is represented by an array of {0,1} values. Specifically, 
42 
* <tt>stencil[i]</tt> is 1 if vertex \p i is a member of the MIS(k) and 
43 
* 0 otherwise. 
44 
* 
45 
* \param A symmetric matrix that represents a graph 
46 
* \param stencil array to hold the MIS(k) 
47 
* \param k radius of independence 
48 
* 
49 
* \tparam Matrix matrix 
50 
* \tparam Array array 
51 
* 
52 
* \see http://en.wikipedia.org/wiki/Maximal_independent_set 
53 
*/ 
54 

55 
template <typename Matrix, typename Array> 
56 
size_t maximal_independent_set(const Matrix& A, Array& stencil, size_t k = 1); 
57 

58 
/*! \} 
59 
*/ 
60 

61 

62 
} // end namespace graph 
63 
} // end namespace cusp 
64 

65 
#include <cusp/graph/detail/maximal_independent_set.inl> 
66 
