GraphDistance error when Graph vertices are Associations

Question

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.)

Answer 1

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]]];
a = AssociationThread[vertexlist, Range[Length[vertexlist]]];

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

Answer 2

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).