3
$\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

$\endgroup$
  • 1
    $\begingroup$ Do not add the bugs tag until your observed behavior has already been confirmed by other users. $\endgroup$ – J. M. will be back soon Aug 26 '15 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$ – Dr. belisarius Aug 26 '15 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$ – Szabolcs Aug 26 '15 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$ – Szabolcs Aug 26 '15 at 8:30
  • 1
    $\begingroup$ You can use the IGDistanceMatrix function from IGraph/M as a workaround until this gets fixed. $\endgroup$ – Szabolcs Apr 17 '18 at 6:44
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.}} *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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