Skip to content

Commit 3fe9b06

Browse files
jmeidowjmeidow
committed
proper reduction of non-square incidence matrices
1 parent cd7d432 commit 3fe9b06

File tree

3 files changed

+50
-53
lines changed

3 files changed

+50
-53
lines changed

‎src/matrix.cpp‎

Lines changed: 37 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -18,29 +18,22 @@
1818

1919
#include "matrix.h"
2020

21-
#include <QDataStream>
22-
#include <QtCompilerDetection>
23-
#include <qassert.h>
24-
2521
#include <Eigen/Core>
2622
#include <Eigen/SparseCore>
2723

24+
#include <cassert>
2825
#include <vector>
2926

3027

31-
using Eigen::Index;
32-
using VectorXidx = Eigen::Vector<Index,Eigen::Dynamic>;
33-
34-
3528
namespace Graph {
3629

30+
using Eigen::Index;
31+
3732

3833
//! check if coeff(r,c)==1
3934
bool IncidenceMatrix::isSet( const Index r, const Index c) const
4035
{
41-
Q_ASSERT_X( r>=0 && r<rows(), Q_FUNC_INFO, "row index out of range" );
42-
Q_ASSERT_X( c>=0 && c<cols(), Q_FUNC_INFO, "column index out of range" );
43-
Q_ASSERT( coeff(r,c)<2 );
36+
assert( coeff(r,c)<2 );
4437
return coeff(r,c)==1;
4538
}
4639

@@ -57,8 +50,7 @@ bool IncidenceMatrix::isSet( const last_t /*unused*/, const Index c) const
5750
}
5851

5952

60-
61-
//! Biadjacency matrix A = [O, B; B',O]
53+
//! Biadjacency matrix B = [O, A; A',O]
6254
SparseMatrix<int> IncidenceMatrix::biadjacency() const
6355
{
6456
const Index C = cols();
@@ -84,62 +76,67 @@ SparseMatrix<int> IncidenceMatrix::biadjacency() const
8476

8577

8678
//! remove column c
87-
void IncidenceMatrix::remove_column( const Index c) {
88-
89-
// qDebug() << Q_FUNC_INFO;
90-
91-
Q_ASSERT( c>=0 && c<cols() );
79+
void IncidenceMatrix::remove_column( const Index c)
80+
{
81+
assert( c>=0 && c<cols() );
9282

9383
const Index C = cols()-1;
9484

95-
SparseMatrix<int> TT(C+1,C);
85+
SparseMatrix<int> RR(C+1,C);
9686
for (Index i=0; i<c; i++) {
97-
TT.insert(i,i) = 1;
87+
RR.insert(i,i) = 1;
9888
}
9989
for (Index i=c; i<C; i++) {
100-
TT.insert(i+1,i) = 1;
90+
RR.insert(i+1,i) = 1;
10191
}
102-
*this = (*this)*TT;
92+
*this = (*this)*RR;
10393
}
10494

10595

10696
//! remove row r
10797
void IncidenceMatrix::remove_row( const Index r)
10898
{
109-
// qDebug() << QString("remove row #%1").arg(r);
110-
111-
Q_ASSERT( r>=0 && r<rows() );
99+
assert( r>=0 && r<rows() );
112100

113101
const Index R = rows()-1;
114102

115-
SparseMatrix<int> SS(R,R+1);
103+
SparseMatrix<int> LL(R,R+1);
116104
for (Index i=0; i<r; i++) {
117-
SS.insert(i,i) = 1; // i.e., true
105+
LL.insert(i,i) = 1;
118106
}
119107
for (Index i=r; i<R; i++) {
120-
SS.insert(i,i+1) = 1;
108+
LL.insert(i,i+1) = 1;
121109
}
122110

123-
*this = SS*(*this);
111+
*this = LL*(*this);
124112
}
125113

126114

127-
//! remove i-th column and i-th row
128-
void IncidenceMatrix::reduce( const Index i)
115+
//! remove r-th column and c-th row
116+
void IncidenceMatrix::reduce( const Index r, const Index c)
129117
{
130-
Q_ASSERT( i>=0 && i<rows() && i<cols() );
131-
// qDebug() << QString("reduce %1").arg(i);
118+
assert( r>=0 && r<rows() );
119+
assert( c>=0 && c<cols() );
120+
121+
// selection matrix LL (left, rows)
122+
SparseMatrix<int> LL( rows()-1,rows());
123+
for ( Index i=0; i<r; i++) {
124+
LL.insert(i,i) = 1;
125+
}
126+
for ( Index i=r; i<LL.rows(); i++) {
127+
LL.insert(i,i+1) = 1;
128+
}
132129

133-
// selection matrix S
134-
SparseMatrix<int> SS( rows()-1,rows());
135-
for ( Index j=0; j<i; j++) {
136-
SS.insert(j,j) = 1;
130+
// selection matrix RR (right, cols)
131+
SparseMatrix<int> RR( cols(),cols()-1);
132+
for ( Index i=0; i<c; i++) {
133+
RR.insert(i,i) = 1;
137134
}
138-
for ( Index j=i; j<SS.rows(); j++) {
139-
SS.insert(j,j+1) = 1;
135+
for ( Index i=c; i<RR.cols(); i++) {
136+
RR.insert(i+1,i) = 1;
140137
}
141138

142-
*this = SS*(*this)*SS.transpose();
139+
*this = LL*(*this)*RR;
143140
}
144141

145142
} // namespace Graph

‎src/matrix.h‎

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -67,23 +67,23 @@ class IncidenceMatrix : public SparseMatrix<int, ColMajor, int>
6767
return {Left*(*this)*Right};
6868
}
6969

70-
[[nodiscard]] bool isSet( Index r, Index c) const; //!< Check if r and c are related
71-
[[nodiscard]] bool isSet( Index r, last_t last) const; //!< Check if r and c are related
72-
[[nodiscard]] bool isSet( last_t last, Index c) const; //!< Check if r and c are related
70+
[[nodiscard]] bool isSet( Index r, Index c) const; //!< A(r,c)==1 ?
71+
[[nodiscard]] bool isSet( Index r, last_t last) const; //!< A(r,end)==1 ?
72+
[[nodiscard]] bool isSet( last_t last, Index c) const; //!< A(end,c)==1 ?
7373

74-
[[nodiscard]] SparseMatrix<int> biadjacency() const; //!< Create biadjacency matrix [O, A; A', O]
74+
[[nodiscard]] SparseMatrix<int> biadjacency() const; //!< Create biadjacency matrix B = [O, A; A', O]
7575

7676
void set( const Index r, const Index c) { coeffRef(r,c) = 1; } //!< Set relation (row r, column c)
77-
void set( const Index r, const last_t /*unused*/) { coeffRef(r,cols()-1) = 1; } //!< Set relation (row r, column c)
78-
void set( const last_t /*unused*/, const Index c) { coeffRef(rows()-1,c) = 1; } //!< Set relation (row r, column c)
77+
void set( const Index r, const last_t /*unused*/) { coeffRef(r,cols()-1) = 1; } //!< Set relation (row r, last column)
78+
void set( const last_t /*unused*/, const Index c) { coeffRef(rows()-1,c) = 1; } //!< Set relation (last row, column c)
7979

8080
void unset( const Index r, const Index c) { coeffRef(r,c) = 0; } //!< Delete relation (row r, column c)
81-
void unset( const Index r, const last_t /*unused*/) { coeffRef(r,cols()-1) = 0; } //!< Delete relation (row r, column c)
82-
void unset( const last_t /*unused*/, const Index c) { coeffRef(rows()-1,c) = 0; } //!< Delete relation (row r, column c)
81+
void unset( const Index r, const last_t /*unused*/) { coeffRef(r,cols()-1) = 0; } //!< Delete relation (row r, last column)
82+
void unset( const last_t /*unused*/, const Index c) { coeffRef(rows()-1,c) = 0; } //!< Delete relation (last row, column c)
8383

8484
void remove_row( Index r ); //!< Remove r-th row
8585
void remove_column( Index c ); //!< Remove c-th column
86-
void reduce( Index i); //!< Remove i-th column and i-th row
86+
void reduce(Index r, Index c); //!< Remove r-th column and c-th row
8787

8888
//! Augment matrix by one row and one column
8989
void augment() { conservativeResize( rows()+1, cols()+1); }

‎src/state.cpp‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -581,12 +581,12 @@ void impl::remove_segment(const Index i)
581581
// qDebug() << Q_FUNC_INFO;
582582

583583
m_segm.removeAt(i);
584-
Adj.reduce(i); // A(i,:)= []; A(:,i)=[]
585-
PP.reduce(i);
584+
Adj.reduce(i,i); // A(i,:)= []; A(:,i)=[]
585+
PP.reduce(i,i);
586586
Rel.remove_row(i); // B(i,:) = [];
587587

588-
x_touches_l.reduce(i);
589-
y_touches_l.reduce(i);
588+
x_touches_l.reduce(i,i);
589+
y_touches_l.reduce(i,i);
590590

591591
m_qStroke.removeAt( i );
592592
m_qUnconstrained.removeAt( i );

0 commit comments

Comments
 (0)