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]

graph with associations as vertices

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

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

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

enter image description here

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 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 at 10:15
  • 1
    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 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 2 days ago

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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