# GraphDistance error when Graph vertices are Associations

Bug introduced in 10.0 or earlier and persisting through 11.3

Here is a nice graph whose vertices are Associations:

g = Graph[{
<|"n" -> 1|> -> <|"n" -> 2|>,
<|"n" -> 1|> -> <|"n" -> 3|>,
<|"n" -> 2|> -> <|"n" -> 4|>,
<|"n" -> 3|> -> <|"n" -> 4|>},
VertexLabels -> Automatic]


Several graph functions work as expected, e.g., AcyclicGraphQ[g] and AdjacencyMatrix[g].

However, functions that refer explicitly to the vertices don't work:

GraphDistance[g, <|"n" -> 2|>, <|"n" -> 4|>]


"GraphDistance: Unknown option "n" in GraphDistance."

Or:

GraphDistance[g, <|"n" -> 2|>]


"GraphDistance: GraphDistance called with 1 argument; 2 or 3 arguments are expected."

It looks like it's interpreting the Association as a bunch of options to GraphDistance. Is that use of Associations documented somewhere?

(It seems that using non-integer vertices causes problems: link.)

• Actually, I'm pretty confident that this will be fixed in the next version. :-) But do report it anyway. – Szabolcs Oct 12 '18 at 12:00

Sadly, this another one in a long row of issues with noninteger vertices for Graph where things neither work as documented nor as they should. Since GraphDistance is a kernel function, we non-insiders cannot tell why this happens. (But every now and then, associations are interpreted as list of rules; e.g. when used as second argument of ReplaceAll.)

What I can do for you is to provide a way to circumvent that by using integer vertices and the associations as vertex labels. For looking up a vertex from its label, we employ an association a.

edgelist = {<|"n" -> 1|> -> <|"n" -> 2|>, <|"n" -> 1|> -> <|"n" -> 3|>, <|"n" -> 2|> -> <|"n" -> 4|>, <|"n" -> 3|> -> <|"n" -> 4|>};
vertexlist = Sort[DeleteDuplicates[Flatten[List @@@ edgelist]]];


Visuably, we obtain the same graph:

g = Graph[
Map[a, edgelist, {2}],
VertexLabels -> KeyValueMap[{key, val} \[Function] val -> key, a]
]


In calls to Graph-related function that require vertices as argument, we have to insert the lookup function a:

GraphDistance[g, a[<|"n" -> 2|>], a[<|"n" -> 4|>]]


1

• Thank you! And regarding the behavior where an Association as a final argument is interpreted as options, is this known behavior? – ConvexMartian Oct 12 '18 at 9:58
• No, I don't think so. For example, Graphics[Disk[], <|PlotRange -> {-10, 10}|>] produces errors while Graphics[Disk[], Normal@<|PlotRange -> {-10, 10}|>] works as expected. But option processing is not handled consistently, even among built-in functions. An in particular Graph-related functions process their arguments in a very obfuscated and inconsistent way (e.g. flattening out lists so that using lists as vertices causes errors in a similar way). – Henrik Schumacher Oct 12 '18 at 10:15
• I once browsed HighlightGraph and its backend to repair a bug for Szabolcs. (Fortunately, the bug was not completely hidden in the kernel) and it got me the creeps how WRI processes the input. There were at least a dozen of layers of abstraction to unravel before I could find the actual bug (which was in itself not that complicated). But I have to admit that writing computational code is one thing and that writing code for user interaction is an entirely different thing. – Henrik Schumacher Oct 12 '18 at 10:19

This is clearly a bug, and as Henrik said, a fairly common type of bug, unfortunately. When you encounter such problems, please do report them to Wolfram.

As a workaround, you can use IGDistanceMatrix from my IGraph/M package.

<<IGraphM

IGDistanceMatrix[g, {<|"n" -> 2|>}, {<|"n" -> 4|>}]
(* {{1}} *)
`

This function takes only lists of vertices as the 2nd and 3rd argument. It does not take single vertex names. This is a mild inconvenience, but on the upside, it eliminates any ambiguities whether an expression is a vertex list or a single vertex name that happens to be a list (or association or whatever).

• I have reported the bug! Thank you for the information about IGraph/M. – ConvexMartian Oct 12 '18 at 20:02