Module algebraic: laplacianMatrix(G) includes deleted nodes

[bernlu]

Given a graph (of size n), adding and then removing a node causes the laplacianMatrix function to return wrong results: The resulting matrix keeps the larger size of n+1 even though the node has been removed. This issue appears in at least two (maybe distinct?) places.

Python

import networkit as nk
G = nk.Graph(4)
G.addEdge(0,1)
G.addEdge(0,2)
G.addEdge(0,3)
G.addEdge(1,2)
nk.algebraic.laplacianMatrix(G).toarray()

[ 3., -1., -1., -1.],
[-1., 2., -1., 0.],
[-1., -1., 2., 0.],
[-1., 0., 0., 1.]

(correct)

newnode = G.addNode()
nk.algebraic.laplacianMatrix(G).toarray()

[ 3., -1., -1., -1., 0.],
[-1., 2., -1., 0., 0.],
[-1., -1., 2., 0., 0.],
[-1., 0., 0., 1., 0.],
[ 0., 0., 0., 0., 0.]

(correct)

G.removeNode(newnode)
nk.algebraic.laplacianMatrix(G).toarray()

[ 3., -1., -1., -1., 0.],
[-1., 2., -1., 0., 0.],
[-1., -1., 2., 0., 0.],
[-1., 0., 0., 1., 0.],
[ 0., 0., 0., 0., 0.]

(wrong) this matrix should be equal to the first.

C++

Graph G(4);
G.addEdge(0, 1);
G.addEdge(0, 2);
G.addEdge(0, 3);
G.addEdge(1, 2);

std::cout << CSRMatrix::laplacianMatrix(G) << std::endl;
node newnode = G.addNode();
std::cout << CSRMatrix::laplacianMatrix(G) << std::endl;
G.removeNode(newnode);
std::cout << CSRMatrix::laplacianMatrix(G) << std::endl;

3, -1, -1, -1
-1, 2, -1, 0
-1, -1, 2, 0
-1, 0, 0, 1

(correct)

3, -1, -1, -1, 0
-1, 2, -1, 0, 0
-1, -1, 2, 0, 0
-1, 0, 0, 1, 0
0, 0, 0, 0, 0

(correct)

3, -1, -1, -1, 0
-1, 2, -1, 0, 0
-1, -1, 2, 0, 0
-1, 0, 0, 1, 0
0, 0, 0, 0, 0

(wrong)