8
$\begingroup$

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]

Mathematica graphics

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"]

Mathematica graphics

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};
$\endgroup$
  • $\begingroup$ Looks like a bug to me. You could use AdjacencyMatrix instead as a workaround. $\endgroup$ – Carl Woll Apr 25 '18 at 21:24
  • $\begingroup$ @CarlWoll You mean AdjacencyList, right? It does basically the same thing, except it does not include the original vertex in the list. $\endgroup$ – Szabolcs Apr 25 '18 at 22:23
  • $\begingroup$ No, I was thinking of something like MatrixPower[AdjacencyMatrix[g], 3] . initialVector or probably better MatrixPower[AdjacencyMatrix[g], 3, initialVector]. $\endgroup$ – Carl Woll Apr 25 '18 at 22:40
5
$\begingroup$

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"]

enter image description here

$\endgroup$
4
$\begingroup$

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
]

For your example:

vertexComponent[g, 50, 3]

{17, 26, 27, 28, 29, 30, 36, 37, 38, 39, 40, 41, 42, 47, 48, 49, 50, 51, 52, 53, 58, 59, 60, 61, 62, 63, 64, 69, 70, 71, 72, 73, 74, 75, 82, 83, 84}

Comparison:

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

{42, 69, 75}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.