# GraphDistance error when Graph vertices are Associations

Bug introduced in 10.0 or earlier and fixed in 12.0
Note: Associations are new in 10.0

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
{"ft_lang_label":"__label__en","ft_lang_prob":0.8758898,"math_prob":0.6989682,"size":885,"snap":"2020-45-2020-50","text_gpt3_token_len":277,"char_repetition_ratio":0.18728717,"word_repetition_ratio":0.04347826,"special_character_ratio":0.3559322,"punctuation_ratio":0.18125,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9572218,"pos_list":[0,1,2,3,4],"im_url_duplicate_count":[null,5,null,5,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-10-27T18:39:43Z\",\"WARC-Record-ID\":\"<urn:uuid:4136f405-f62e-4014-92ca-e03129641c67>\",\"Content-Length\":\"164551\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b5dbf5e4-0f6b-4d16-a507-0d66d3b29eba>\",\"WARC-Concurrent-To\":\"<urn:uuid:79910f19-609f-4a72-b090-531c7270fc33>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://mathematica.stackexchange.com/questions/183665/graphdistance-error-when-graph-vertices-are-associations\",\"WARC-Payload-Digest\":\"sha1:SPE7TC2NYK4R2ET6KF2IE2LMWQPSR7XL\",\"WARC-Block-Digest\":\"sha1:VRCNVDF5VZREEXGAC3COESD2MQECAYHO\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-45/CC-MAIN-2020-45_segments_1603107894426.63_warc_CC-MAIN-20201027170516-20201027200516-00133.warc.gz\"}"}