4
$\begingroup$

Bug introduced in 10.0 and fixed in 12.0
Multigraph support was introduced in 10.0

GraphDistance and GraphDistanceMatrix return incorrect results for the following weighted multigraphs. Is there a workaround?

g = Graph[{1 <-> 2, 1 <-> 3, 2 <-> 1, 2 <-> 3}, EdgeWeight -> {3, 3, 2, 1}, VertexLabels -> "Name"];

enter image description here

There are two edges between vertices 1 and 2. One of these edges has weight 3, the other weight 2.

The shortest path length between 1 and 2 is calculated as:

{GraphDistance[g, 1, 2], GraphDistance[g, 2, 1]} (* {3., 5.} *) 
GraphDistanceMatrix[g] // MatrixForm |0. 3. 3.| |5. 0. 1.| |5. 1. 0.|

The shortest distance between 1 and 2 is not the same as the shortest distance between 2 and 1. Also, the distance matrix is not symmetric. Finally, neither 3, nor 5 is a correct result here. It should be 2.

Is there a workaround for computing shortest paths in weighted multigraphs?

Finally, edge weights are displayed incorrectly in the following:

SetProperty[g, EdgeLabels -> "EdgeWeight"]

enter image description here

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Do not add the bugs tag until your observed behavior has already been confirmed by other users. $\endgroup$ Commented Aug 26, 2015 at 6:07
  • 1
    $\begingroup$ If you're sure those are bugs, please go on and report them to WRI. Otherwise, please ask an answerable question. This site isn't a bug reporting tool ;) $\endgroup$ Commented Aug 26, 2015 at 6:09
  • $\begingroup$ If you want this fixed, please report it to Wolfram. This website is not affiliated with Wolfram. They might not notice that you complained about this here. This website is not for complaints, it's for questions. If they do notice, and they do create a bug report, it might not receive the same weight as if you had reported it yourself. $\endgroup$ Commented Aug 26, 2015 at 8:27
  • 2
    $\begingroup$ I think this is directly related: mathematica.stackexchange.com/questions/92014/… I do think that multigraphs are near-unusable un Mathematica and should not have been introduced in this state. It is in everyone's interest to have these bugs fixed. But for that to happen, you need to talk to Wolfram. I voted to close this post because it is clearly not a question but a complaint and thus unsuitable for this site. I suggest rephrasing it as a question to prevent closing. $\endgroup$ Commented Aug 26, 2015 at 8:30
  • 1
    $\begingroup$ You can use the IGDistanceMatrix function from IGraph/M as a workaround until this gets fixed. $\endgroup$ Commented Apr 17, 2018 at 6:44

1 Answer 1

Reset to default
2
$\begingroup$

One possible workaround is to use IGDistanceMatrix from the IGraph/M package.

IGDistanceMatrix[g] (* {{0., 2., 3.}, {2., 0., 1.}, {3., 1., 0.}} *)

Another workaround is to convert the multi-graph to a simple graph and keep only the smallest weight for parallel edges.

Again IGraph/M has a function for this.

enter image description here

IGWeightedSimpleGraph[g, Min]

The distance matrix:

GraphDistanceMatrix@IGWeightedSimpleGraph[g, Min] (* {{0., 2., 3.}, {2., 0., 1.}, {3., 1., 0.}} *)

Finally, we could do the same without IGraph/M, though the performance won't be nearly as good.

weightedSimpleEdges = Min /@ GroupBy[ Transpose@{Sort /@ EdgeList[g], PropertyValue[g, EdgeWeight]}, First -> Last ] (* <|1 \[UndirectedEdge] 2 -> 2, 1 \[UndirectedEdge] 3 -> 3, 2 \[UndirectedEdge] 3 -> 1|> *) GraphDistanceMatrix@Graph[ VertexList[g], Keys[weightedSimpleEdges], EdgeWeight -> Values[weightedSimpleEdges] ] (* {{0., 2., 3.}, {2., 0., 1.}, {3., 1., 0.}} *)
Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.