1 // This file is part of libigl, a simple c++ geometry processing library.
2 //
3 // Copyright (C) 2013 Alec Jacobson <alecjacobson@gmail.com>
4 //
5 // This Source Code Form is subject to the terms of the Mozilla Public License
6 // v. 2.0. If a copy of the MPL was not distributed with this file, You can
7 // obtain one at http://mozilla.org/MPL/2.0/.
8 #include "vertex_components.h"
9 #include "adjacency_matrix.h"
10 #include <queue>
11 #include <vector>
12
13 template <typename AScalar, typename DerivedC, typename Derivedcounts>
vertex_components(const Eigen::SparseMatrix<AScalar> & A,Eigen::PlainObjectBase<DerivedC> & C,Eigen::PlainObjectBase<Derivedcounts> & counts)14 IGL_INLINE void igl::vertex_components(
15 const Eigen::SparseMatrix<AScalar> & A,
16 Eigen::PlainObjectBase<DerivedC> & C,
17 Eigen::PlainObjectBase<Derivedcounts> & counts)
18 {
19 using namespace Eigen;
20 using namespace std;
21 assert(A.rows() == A.cols() && "A should be square.");
22 const size_t n = A.rows();
23 Array<bool,Dynamic,1> seen = Array<bool,Dynamic,1>::Zero(n,1);
24 C.resize(n,1);
25 typename DerivedC::Scalar id = 0;
26 vector<typename Derivedcounts::Scalar> vcounts;
27 // breadth first search
28 for(int k=0; k<A.outerSize(); ++k)
29 {
30 if(seen(k))
31 {
32 continue;
33 }
34 queue<int> Q;
35 Q.push(k);
36 vcounts.push_back(0);
37 while(!Q.empty())
38 {
39 const int f = Q.front();
40 Q.pop();
41 if(seen(f))
42 {
43 continue;
44 }
45 seen(f) = true;
46 C(f,0) = id;
47 vcounts[id]++;
48 // Iterate over inside
49 for(typename SparseMatrix<AScalar>::InnerIterator it (A,f); it; ++it)
50 {
51 const int g = it.index();
52 if(!seen(g) && it.value())
53 {
54 Q.push(g);
55 }
56 }
57 }
58 id++;
59 }
60 assert((size_t) id == vcounts.size());
61 const size_t ncc = vcounts.size();
62 assert((size_t)C.maxCoeff()+1 == ncc);
63 counts.resize(ncc,1);
64 for(size_t i = 0;i<ncc;i++)
65 {
66 counts(i) = vcounts[i];
67 }
68 }
69
70 template <typename AScalar, typename DerivedC>
vertex_components(const Eigen::SparseMatrix<AScalar> & A,Eigen::PlainObjectBase<DerivedC> & C)71 IGL_INLINE void igl::vertex_components(
72 const Eigen::SparseMatrix<AScalar> & A,
73 Eigen::PlainObjectBase<DerivedC> & C)
74 {
75 Eigen::VectorXi counts;
76 return vertex_components(A,C,counts);
77 }
78
79 template <typename DerivedF, typename DerivedC>
vertex_components(const Eigen::MatrixBase<DerivedF> & F,Eigen::PlainObjectBase<DerivedC> & C)80 IGL_INLINE void igl::vertex_components(
81 const Eigen::MatrixBase<DerivedF> & F,
82 Eigen::PlainObjectBase<DerivedC> & C)
83 {
84 Eigen::SparseMatrix<typename DerivedC::Scalar> A;
85 adjacency_matrix(F,A);
86 return vertex_components(A,C);
87 }
88
89 #ifdef IGL_STATIC_LIBRARY
90 // Explicit template instantiation
91 // generated by autoexplicit.sh
92 template void igl::vertex_components<bool, Eigen::Array<int, -1, 1, 0, -1, 1> >(Eigen::SparseMatrix<bool, 0, int> const&, Eigen::PlainObjectBase<Eigen::Array<int, -1, 1, 0, -1, 1> >&);
93 template void igl::vertex_components<Eigen::Matrix<int, -1, -1, 0, -1, -1>, Eigen::Matrix<int, -1, 1, 0, -1, 1> >(Eigen::MatrixBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> >&);
94 template void igl::vertex_components<int, Eigen::Matrix<int, -1, 1, 0, -1, 1> >(Eigen::SparseMatrix<int, 0, int> const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> >&);
95 template void igl::vertex_components<int, Eigen::Matrix<int, -1, -1, 0, -1, -1> >(Eigen::SparseMatrix<int, 0, int> const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> >&);
96 template void igl::vertex_components<double, Eigen::Matrix<int, -1, -1, 0, -1, -1>, Eigen::Matrix<int, -1, -1, 0, -1, -1> >(Eigen::SparseMatrix<double, 0, int> const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> >&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> >&);
97 template void igl::vertex_components<Eigen::Matrix<int, -1, -1, 0, -1, -1>, Eigen::Matrix<int, -1, -1, 0, -1, -1> >(Eigen::MatrixBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> >&);
98 #endif
99