All pairs shortest paths
in [Mathematica]
|
From: Jon Harrop on 24 Jul 2010 05:08 How do you obtain the all-pairs shortest paths of a graph in Mathematica? i.e. the paths themselves and not just their lengths. -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com
From: Murta on 26 Jul 2010 07:03 Try the Graph Utilities Package. There are some commands that can help. GraphDistance[g,start,end] give the distance from vertex i to vertex j in the graph g GraphPath[g,start,end] find a shortest path between vertices start and end in graph g GraphDistanceMatrix[g] give a matrix in which the (i,j)\[Null]^th entry is the length of a shortest path in g between vertices i and j GraphDistanceMatrix[g,Parent] return a three-dimensional matrix in which the (1,i,j)\[Null]^th entry is the length of a shortest path from i to j and the (2,i,j)\[Null]^th entry is the predecessor of j in a shortest path from i to j. Regards Murta On Jul 24, 6:08 am, "Jon Harrop" <use...(a)ffconsultancy.com> wrote: > How do you obtain the all-pairs shortest paths of a graph in Mathematica? > i.e. the paths themselves and not just their lengths. > > -- > Dr Jon Harrop, Flying Frog Consultancy Ltd.http://www.ffconsultancy.com
From: Jon Harrop on 30 Jul 2010 06:57 "Murta" <rodrigomurtax(a)gmail.com> wrote in message news:i2jq2j$gr8$1(a)smc.vnet.net... > Try the Graph Utilities Package. There are some commands that can > help. > > GraphDistance[g,start,end] give the distance from vertex i to vertex j > in the graph g > GraphPath[g,start,end] find a shortest path between vertices start and > end in graph g > GraphDistanceMatrix[g] give a matrix in which the (i,j)\[Null]^th > entry is the length of a shortest path in g between vertices i and j > GraphDistanceMatrix[g,Parent] return a three-dimensional matrix in > which the (1,i,j)\[Null]^th entry is the length of a shortest path > from i to j and the (2,i,j)\[Null]^th entry is the predecessor of j in > a shortest path from i to j. Sure, but none of those actually implement what I need. The last one returns a data structure that can be used to compose the information I need but I'd have to do the rest of the computation myself and it would run like a dog if written in Mathematica. Does Mathematica really not provide a built-in function to compute all-pairs shortest paths? Cheers, Jon.
From: Jon Harrop on 31 Jul 2010 02:39 "Murta" <rodrigomurtax(a)gmail.com> wrote in message news:i2jq2j$gr8$1(a)smc.vnet.net... > Try the Graph Utilities Package. There are some commands that can > help. > > GraphDistance[g,start,end] give the distance from vertex i to vertex j > in the graph g > GraphPath[g,start,end] find a shortest path between vertices start and > end in graph g > GraphDistanceMatrix[g] give a matrix in which the (i,j)\[Null]^th > entry is the length of a shortest path in g between vertices i and j > GraphDistanceMatrix[g,Parent] return a three-dimensional matrix in > which the (1,i,j)\[Null]^th entry is the length of a shortest path > from i to j and the (2,i,j)\[Null]^th entry is the predecessor of j in > a shortest path from i to j. The documentation for the Graph Utilities package does actually give the following code to compute the all pairs shortest paths from the output of the GraphDistanceMatrix function: Drop[FixedPointList[prd[[i, #]] &, j], -1] // Reverse Although this code works on the trivial example they provide it does not produce useful answers when applied to the more complicated graph given in the previous example because the vertices are referred to via an unknown mapping rather than by name. The best solution seems to be to convert the graph represented as a list of rules into an adjacency matrix before computing the all pairs shortest paths. For a 1005x1005 sparse graph on this 8-core, that takes 12.7s and requires ~1Gb of RAM. Cheers, Jon.
From: Thomas Dowling on 31 Jul 2010 02:40 Hello, I am not an expert here by any means, but there is such a command in the Combinatorica package: Needs["Combinatorica`"] ?AllPairsShortestPath As you are probably aware, the Combinatorica package is poorly documented compared with other parts of Mathematica. However, the function is described in detail in Sriram Pemmaraju & Stephen Skiena "Computational Discrete Mathematics. Combinatorics and Graph Theory with Mathematica", pp 330 - 333. Can you post an example of what you require? Tom Dowling On Fri, Jul 30, 2010 at 11:57 AM, Jon Harrop <usenet(a)ffconsultancy.com>wrote: > "Murta" <rodrigomurtax(a)gmail.com> wrote in message > news:i2jq2j$gr8$1(a)smc.vnet.net... > > Try the Graph Utilities Package. There are some commands that can > > help. > > > > GraphDistance[g,start,end] give the distance from vertex i to vertex j > > in the graph g > > GraphPath[g,start,end] find a shortest path between vertices start and > > end in graph g > > GraphDistanceMatrix[g] give a matrix in which the (i,j)\[Null]^th > > entry is the length of a shortest path in g between vertices i and j > > GraphDistanceMatrix[g,Parent] return a three-dimensional matrix in > > which the (1,i,j)\[Null]^th entry is the length of a shortest path > > from i to j and the (2,i,j)\[Null]^th entry is the predecessor of j in > > a shortest path from i to j. > > Sure, but none of those actually implement what I need. The last one > returns > a data structure that can be used to compose the information I need but I'd > have to do the rest of the computation myself and it would run like a dog > if > written in Mathematica. > > Does Mathematica really not provide a built-in function to compute > all-pairs > shortest paths? > > Cheers, > Jon. > > >
|
Pages: 1 Prev: Convert PNG image to PDF CMYK? Next: Strange use of time... |