Bug with SparseArray selector in Pick

Question

Bug introduced in version 8 or earlier and fixed in 10.0

---

I have created a notebook with two cells. This is the content of the first:

g = Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 1 \[UndirectedEdge] 3, 1 \[UndirectedEdge] 4, 4 \[UndirectedEdge] 5, 4 \[UndirectedEdge] 6}]

And this is the content of the second:

g
listDegree = VertexDegree[g]
vl = VertexList[g]
nodeMaxDegree = Pick[vl, listDegree, Max[VertexDegree[g]]][[1]]
aM = AdjacencyMatrix[g];
vLM = aM[[VertexIndex[g, nodeMaxDegree]]];
nN = Pick[vl, vLM, 0]

If I evaluate the second cell (after processing the first) for a second time:

1. the first time no problem, the results are correct;
2. the second time the vertex list of g is inexplicably wrong but the graph remain correct!!

I don't understand the cause because the graph g is never touched.

Thanks in advance

Answer 1

This is a bug in Pick caused by SparseArray, has nothing to do with Graph. Minimal example (SparseArray object is the fullform version of your vLM):

x = {1, 2, 3, 4, 5, 6};
Pick[x, SparseArray[Automatic, {6}, 0, {1, {{0, 3}, {{2}, {3}, {4}}}, {1, 1, 1}}], 0];
FullForm@x

{1, System`Private`InternSequence[], System`Private`InternSequence[], 
    System`Private`InternSequence[], 5, 6}

As you can observe, the value of x gets updated though no assignment is done: those members are replaced in x which are listed in the SparseArray (2, 3 and 4).

One obvious solution for your case is to wrap the AdjacencyMatrix into Normal so its result won't be a SparseArray.

Answer 2

This looks like a bug to me. Here is a slightly more minimal example.

ue = UndirectedEdge;
g = Graph[ue @@@ {{1, 2}, {2, 3}, {1, 3}, {1, 4}, {4, 5}, {4, 6}}];
vl = VertexList[g]
aM = AdjacencyMatrix[g];
vLM = aM[[VertexIndex[g, 1]]];
Pick[vl, vLM, 0];
VertexList[g]

Output

{1, 2, 3, 4, 5, 6}  
{1, 5, 6}

You can solve the error by making a copy of the vertexlist yourself. This can be done by using Append and Delete as follows

ue = UndirectedEdge;
g = Graph[ue @@@ {{1, 2}, {2, 3}, {1, 3}, {1, 4}, {4, 5}, {4, 6}}]
vl = Delete[Append[VertexList[g], 0], -1]
aM = AdjacencyMatrix[g];
vLM = aM[[VertexIndex[g, 1]]];
Pick[vl, vLM, 0];
v1 = VertexList[g]

Output

{1, 2, 3, 4, 5, 6}  
{1, 2, 3, 4, 5, 6}

So in your case you could do

copy[list_] := Delete[Append[list, 0], -1];

g
listDegree = VertexDegree[g]

Block[
 {punchingBag},
 punchingBag = copy[VertexList[g]]; 
 nodeMaxDegree = 
  Pick[punchingBag, listDegree, Max[VertexDegree[g]]][[1]]; 
 aM = AdjacencyMatrix[g]; vLM = aM[[VertexIndex[g, nodeMaxDegree]]]; 
 nN = Pick[punchingBag, vLM, 0];
 ]
vl = VertexList[g]

Another (probably better) solution would be to use Developer`ToPackedArray on VertexList[g], this avoids the strange behaviour from occurring altogether.