# Why does VertexComponent not return all vertices at distance <= 3?

Bug introduced in 10.0 or earlier and fixed in 12.0

Take the following triangle lattice graph (see edges definition below):

g = Graph[edges, DirectedEdges -> False, VertexLabels -> Automatic]


Let us try to find the vertices reachable from vertex 50 in at most 3 steps. My understanding is that we can use VertexComponent for this.

Let's try:

HighlightGraph[g, Subgraph[g, VertexComponent[g, 50, 3]],
GraphHighlightStyle -> "Thick"]


Why are 75, 42 and 69 missed? Their distance is also 3:

GraphDistance[g, 50, #] & /@ {75, 42, 69}
(* {3, 3, 3} *)


What is happening here? Am I misunderstanding something or is this a bug?

edges = {1 -> 12, 2 -> 13, 3 -> 14, 4 -> 15, 5 -> 16, 6 -> 17,
7 -> 18, 8 -> 19, 9 -> 20, 10 -> 21, 11 -> 22, 12 -> 23, 13 -> 24,
14 -> 25, 15 -> 26, 16 -> 27, 17 -> 28, 18 -> 29, 19 -> 30,
20 -> 31, 21 -> 32, 22 -> 33, 23 -> 34, 24 -> 35, 25 -> 36,
26 -> 37, 27 -> 38, 28 -> 39, 29 -> 40, 30 -> 41, 31 -> 42,
32 -> 43, 33 -> 44, 34 -> 45, 35 -> 46, 36 -> 47, 37 -> 48,
38 -> 49, 39 -> 50, 40 -> 51, 41 -> 52, 42 -> 53, 43 -> 54,
44 -> 55, 45 -> 56, 46 -> 57, 47 -> 58, 48 -> 59, 49 -> 60,
50 -> 61, 51 -> 62, 52 -> 63, 53 -> 64, 54 -> 65, 55 -> 66,
56 -> 67, 57 -> 68, 58 -> 69, 59 -> 70, 60 -> 71, 61 -> 72,
62 -> 73, 63 -> 74, 64 -> 75, 65 -> 76, 66 -> 77, 67 -> 78,
68 -> 79, 69 -> 80, 70 -> 81, 71 -> 82, 72 -> 83, 73 -> 84,
74 -> 85, 75 -> 86, 76 -> 87, 77 -> 88, 78 -> 89, 79 -> 90,
80 -> 91, 81 -> 92, 82 -> 93, 83 -> 94, 84 -> 95, 85 -> 96,
86 -> 97, 87 -> 98, 88 -> 99, 89 -> 100, 90 -> 101, 91 -> 102,
92 -> 103, 93 -> 104, 94 -> 105, 95 -> 106, 96 -> 107, 97 -> 108,
98 -> 109, 99 -> 110, 1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5, 5 -> 6,
6 -> 7, 7 -> 8, 8 -> 9, 9 -> 10, 10 -> 11, 12 -> 13, 13 -> 14,
14 -> 15, 15 -> 16, 16 -> 17, 17 -> 18, 18 -> 19, 19 -> 20,
20 -> 21, 21 -> 22, 23 -> 24, 24 -> 25, 25 -> 26, 26 -> 27,
27 -> 28, 28 -> 29, 29 -> 30, 30 -> 31, 31 -> 32, 32 -> 33,
34 -> 35, 35 -> 36, 36 -> 37, 37 -> 38, 38 -> 39, 39 -> 40,
40 -> 41, 41 -> 42, 42 -> 43, 43 -> 44, 45 -> 46, 46 -> 47,
47 -> 48, 48 -> 49, 49 -> 50, 50 -> 51, 51 -> 52, 52 -> 53,
53 -> 54, 54 -> 55, 56 -> 57, 57 -> 58, 58 -> 59, 59 -> 60,
60 -> 61, 61 -> 62, 62 -> 63, 63 -> 64, 64 -> 65, 65 -> 66,
67 -> 68, 68 -> 69, 69 -> 70, 70 -> 71, 71 -> 72, 72 -> 73,
73 -> 74, 74 -> 75, 75 -> 76, 76 -> 77, 78 -> 79, 79 -> 80,
80 -> 81, 81 -> 82, 82 -> 83, 83 -> 84, 84 -> 85, 85 -> 86,
86 -> 87, 87 -> 88, 89 -> 90, 90 -> 91, 91 -> 92, 92 -> 93,
93 -> 94, 94 -> 95, 95 -> 96, 96 -> 97, 97 -> 98, 98 -> 99,
100 -> 101, 101 -> 102, 102 -> 103, 103 -> 104, 104 -> 105,
105 -> 106, 106 -> 107, 107 -> 108, 108 -> 109, 109 -> 110,
2 -> 12, 2 -> 14, 4 -> 14, 4 -> 16, 6 -> 16, 6 -> 18, 8 -> 18,
8 -> 20, 10 -> 20, 10 -> 22, 13 -> 23, 13 -> 25, 15 -> 25,
15 -> 27, 17 -> 27, 17 -> 29, 19 -> 29, 19 -> 31, 21 -> 31,
21 -> 33, 24 -> 34, 24 -> 36, 26 -> 36, 26 -> 38, 28 -> 38,
28 -> 40, 30 -> 40, 30 -> 42, 32 -> 42, 32 -> 44, 35 -> 45,
35 -> 47, 37 -> 47, 37 -> 49, 39 -> 49, 39 -> 51, 41 -> 51,
41 -> 53, 43 -> 53, 43 -> 55, 46 -> 56, 46 -> 58, 48 -> 58,
48 -> 60, 50 -> 60, 50 -> 62, 52 -> 62, 52 -> 64, 54 -> 64,
54 -> 66, 57 -> 67, 57 -> 69, 59 -> 69, 59 -> 71, 61 -> 71,
61 -> 73, 63 -> 73, 63 -> 75, 65 -> 75, 65 -> 77, 68 -> 78,
68 -> 80, 70 -> 80, 70 -> 82, 72 -> 82, 72 -> 84, 74 -> 84,
74 -> 86, 76 -> 86, 76 -> 88, 79 -> 89, 79 -> 91, 81 -> 91,
81 -> 93, 83 -> 93, 83 -> 95, 85 -> 95, 85 -> 97, 87 -> 97,
87 -> 99, 90 -> 100, 90 -> 102, 92 -> 102, 92 -> 104, 94 -> 104,
94 -> 106, 96 -> 106, 96 -> 108, 98 -> 108, 98 -> 110};

• Looks like a bug to me. You could use AdjacencyMatrix instead as a workaround. Apr 25, 2018 at 21:24
• @CarlWoll You mean AdjacencyList, right? It does basically the same thing, except it does not include the original vertex in the list. Apr 25, 2018 at 22:23
• No, I was thinking of something like MatrixPower[AdjacencyMatrix[g], 3] . initialVector or probably better MatrixPower[AdjacencyMatrix[g], 3, initialVector]. Apr 25, 2018 at 22:40

Something seems broken. As a workaround you might do something like:

gg[1] := NeighborhoodGraph[g, 50, 1]

gg[k_] := NeighborhoodGraph[g, gg[k - 1], 1]

HighlightGraph[g, gg[3], GraphHighlightStyle -> "Thick"]


Here's an alternate implementation of VertexComponent using AdjacencyMatrix:

vertexComponent[g_, v_, n___] := Module[{vec = initialVector[g, v, n]},
ivertexComponent[g, v, vec, n] /; vec =!= $Failed ] /; ArgumentCountQ[vertexComponent, Length @ Hold[g, v, n], 2, 3] initialVector[g_, v_, n___] := Module[{vl = VertexList[g]}, Which[ MemberQ[vl, v], Boole[Thread[vl == v]], ListQ[v] && ContainsAll[vl, v], Boole[MemberQ[v, #]& /@ vl], True, Message[vertexComponent::inv, HoldForm[OutputForm @ vertexComponent[g,v,n]], v, "vertex"];$Failed
]
]

ivertexComponent[g_, v_, vec_, n___] := Module[{p, vl = VertexList[g], a},
p = Replace[{n},
{
{i_Integer?NonNegative} :> i,
{} -> Length[vl],
{x_} :> (Message[vertexComponent::inv, HoldForm[OutputForm @ vertexComponent[g,v,n]], x, "parameter"]; $Failed) } ]; ( a = AdjacencyMatrix[g] + IdentityMatrix[Length[vl], SparseArray]; Pick[vl, Unitize @ MatrixPower[a, p, vec], 1] ) /; p =!=$Failed
]


vertexComponent[g, 50, 3]

Complement[vertexComponent[g, 50, 3], VertexComponent[g, 50, 3]]