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$
  • 1
    $\begingroup$ Are your graphs weighted? $\endgroup$ – Szabolcs Jul 21 '16 at 6:57
  • $\begingroup$ No, they are not (some of them may be directed, though...) $\endgroup$ – Igor Rivin Jul 21 '16 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 Jul 21 '16 at 16:23
  • $\begingroup$ @Szabolcs any progress on this? With bated breath... $\endgroup$ – Igor Rivin Aug 17 '16 at 0:20
  • $\begingroup$ I just sent you an email. If you didn't get it, please email me. $\endgroup$ – Szabolcs Aug 17 '16 at 8:42
9
$\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$
  • $\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 Aug 9 '16 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 Aug 9 '16 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 Aug 9 '16 at 12:50
  • $\begingroup$ @IgorRivin What operating system do you usually use? $\endgroup$ – Szabolcs Aug 9 '16 at 12:58
  • $\begingroup$ Usually OS X, but also Linux... $\endgroup$ – Igor Rivin Aug 9 '16 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, privacy policy and cookie policy

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