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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
// This file is part of libigl, a simple c++ geometry processing library.
//
// Copyright (C) 2013 Alec Jacobson <alecjacobson@gmail.com>
//
// This Source Code Form is subject to the terms of the Mozilla Public License
// v. 2.0. If a copy of the MPL was not distributed with this file, You can
// obtain one at http://mozilla.org/MPL/2.0/.
#include "components.h"
#include "adjacency_matrix.h"
#include <queue>
#include <vector>
template <typename AScalar, typename DerivedC, typename Derivedcounts>
IGL_INLINE void igl::components(
const Eigen::SparseMatrix<AScalar> & A,
Eigen::PlainObjectBase<DerivedC> & C,
Eigen::PlainObjectBase<Derivedcounts> & counts)
{
using namespace Eigen;
using namespace std;
assert(A.rows() == A.cols() && "A should be square.");
const size_t n = A.rows();
Array<bool,Dynamic,1> seen = Array<bool,Dynamic,1>::Zero(n,1);
C.resize(n,1);
typename DerivedC::Scalar id = 0;
vector<typename Derivedcounts::Scalar> vcounts;
// breadth first search
for(int k=0; k<A.outerSize(); ++k)
{
if(seen(k))
{
continue;
}
queue<int> Q;
Q.push(k);
vcounts.push_back(0);
while(!Q.empty())
{
const int f = Q.front();
Q.pop();
if(seen(f))
{
continue;
}
seen(f) = true;
C(f,0) = id;
vcounts[id]++;
// Iterate over inside
for(typename SparseMatrix<AScalar>::InnerIterator it (A,f); it; ++it)
{
const int g = it.index();
if(!seen(g) && it.value())
{
Q.push(g);
}
}
}
id++;
}
assert((size_t) id == vcounts.size());
const size_t ncc = vcounts.size();
assert((size_t)C.maxCoeff()+1 == ncc);
counts.resize(ncc,1);
for(size_t i = 0;i<ncc;i++)
{
counts(i) = vcounts[i];
}
}
template <typename AScalar, typename DerivedC>
IGL_INLINE void igl::components(
const Eigen::SparseMatrix<AScalar> & A,
Eigen::PlainObjectBase<DerivedC> & C)
{
Eigen::VectorXi counts;
return components(A,C,counts);
}
template <typename DerivedF, typename DerivedC>
IGL_INLINE void igl::components(
const Eigen::MatrixBase<DerivedF> & F,
Eigen::PlainObjectBase<DerivedC> & C)
{
Eigen::SparseMatrix<typename DerivedC::Scalar> A;
adjacency_matrix(F,A);
return components(A,C);
}
#ifdef IGL_STATIC_LIBRARY
// Explicit template instantiation
// generated by autoexplicit.sh
template void igl::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> >&);
template void igl::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> >&);
template void igl::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> >&);
template void igl::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> >&);
template void igl::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> >&);
template void igl::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> >&);
#endif
|
