5
$\begingroup$

Does anyone know what the complexity of Mathematica's GraphDiameter algorithm is? I have a family of very large (and very regular and very sparse) graphs, and if Mathematica uses something like the Johnson algorithm, it is feasible, but $O(V^3)$ algorithms are right out - $V$ is in the several million range.

$\endgroup$
5
  • 1
    $\begingroup$ Are your graphs weighted? $\endgroup$
    – Szabolcs
    Commented Jul 21, 2016 at 6:57
  • $\begingroup$ No, they are not (some of them may be directed, though...) $\endgroup$
    – Igor Rivin
    Commented Jul 21, 2016 at 16:08
  • $\begingroup$ Then you won't run into the performance problem with igraph. In fact it is usually slightly faster than Mathematica for undirected (occasionally slightly slower). Most importantly it'll spare you the memory problem. There are also functions for counting how many shortest paths are there of each length, again without the need to keep the full distance matrix in memory. This is what I specifically needed for my own work. $\endgroup$
    – Szabolcs
    Commented Jul 21, 2016 at 16:23
  • $\begingroup$ @Szabolcs any progress on this? With bated breath... $\endgroup$
    – Igor Rivin
    Commented Aug 17, 2016 at 0:20
  • $\begingroup$ I just sent you an email. If you didn't get it, please email me. $\endgroup$
    – Szabolcs
    Commented Aug 17, 2016 at 8:42

2 Answers 2

10
$\begingroup$

If you need to compute diameters for large graphs, you should be aware that GraphDiameter tends to use an unreasonable amount of memory (up to gigabytes). Based on its memory use, I believe that it computes the complete GraphDistanceMatrix first, and then just takes the largest element.

I have reported this to WRI on Feb 13 this year, and support confirmed the problem.

Because of this problem, I exposed igraph's diameter calculation function in IGraph/M. How it compares in performance to Mathematica's builtin depends on the problem (the performance tends to be similar). But I simply wasn't able to do the calculation for large graphs with GraphDiameter because it ran out of memory.


The methods available for the builtin are documented:

{"Dijkstra", "FloydWarshall", "Johnson", "PseudoDiameter"}

I am not familiar with all of these so I cannot tell you about their complexity. "PseudoDiameter" does an approximation only.

Here is a test for a sparse graph, both weighted and unweighted versions. igraph is supposed to use Dijkstra for weighted graphs.

SeedRandom[42];

g = 
  First@ConnectedGraphComponents@
    RandomGraph[BernoulliGraphDistribution[4000, 0.001]];

wg = 
  SetProperty[g, EdgeWeight -> RandomReal[1, EdgeCount[g]]];

Unweighted:

Table[
 {m, AbsoluteTiming@GraphDiameter[g, Method -> m]},
 {m, {"Dijkstra", "FloydWarshall", "Johnson", "PseudoDiameter"}}
 ]

(* {{"Dijkstra", {1.64515, 13.}}, {"FloydWarshall", {48.7639, 13.}}, 
    {"Johnson", {1.77069, 13.}}, {"PseudoDiameter", {0.000592, 13}}} *)

Weighted:

Table[
 {m, AbsoluteTiming@GraphDiameter[wg, Method -> m]},
 {m, {"Dijkstra", "FloydWarshall", "Johnson", "PseudoDiameter"}}
 ]

(*
{{"Dijkstra", {2.54546, 6.07364}}, {"FloydWarshall", {51.3041, 6.07364}},
 {"Johnson", {2.68918, 6.07364}}, {"PseudoDiameter", {2.70202, 6.07364}}}
*)

IGraph/M unweighted:

 << IGraphM`

IGDiameter[g] // AbsoluteTiming
(* {0.613409, 13} *)

Weighted:

IGDiameter[wg] // AbsoluteTiming
(* {34.0476, 6.07364} *)

Here's some more benchmarking for the weighted one with IGraph/M:

IGDistanceMatrix[wg, Method -> "Johnson"] // Max // AbsoluteTiming
(* {4.46778, 6.07364} *)

IGDistanceMatrix[wg, Method -> "BellmanFord"] // Max // AbsoluteTiming
(* {3.95098, 6.07364} *)

IGDistanceMatrix[wg, Method -> "Dijkstra"] // Max // AbsoluteTiming
(* {4.43047, 6.07364} *)

I will have to look into what is going on and why this is so much faster than IGDiameter. The underlying C layer of igraph has the habit of overriding the user's method choice. I am simply exposing this C layer to Mathematica.


Update: I reported the performance problem with igraph's diameter calculation function. It has been fixed. IGraph/M version 0.3.0 will include the fix. New timing is 3.2 s instead of 34 s.

$\endgroup$
6
  • $\begingroup$ Does IGraph/M export something like Mathematica's VertexEccentricity[]? I could not find it in the documentation.... (I have some vertex transitive graphs, so this would be way faster than diameter...) Thanks! $\endgroup$
    – Igor Rivin
    Commented Aug 9, 2016 at 1:34
  • $\begingroup$ @IgorRivin No, not without calculating the full distance matrix. But I made a note to add this in the next version. It will be in 0.3.0, if I ever get the time to finish it ... $\endgroup$
    – Szabolcs
    Commented Aug 9, 2016 at 8:54
  • $\begingroup$ Thanks, Szabolcs! Maybe I will just go to igraph in the meantime (for large graph, Mathematica bombs out of space [no surprise there...]) $\endgroup$
    – Igor Rivin
    Commented Aug 9, 2016 at 12:50
  • $\begingroup$ @IgorRivin What operating system do you usually use? $\endgroup$
    – Szabolcs
    Commented Aug 9, 2016 at 12:58
  • $\begingroup$ Usually OS X, but also Linux... $\endgroup$
    – Igor Rivin
    Commented Aug 9, 2016 at 17:59
5
$\begingroup$

Hiding behind Details and Options on the documentation page is

Method  Automatic  Method to use

and

Possible Method Settings include "Dijkstra", "FloydWarshall", "Johnson", and "PseudoDiameter".
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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