7
$\begingroup$

Why I cannot calculate all edge weights beforehand:

I have many large graphs for which I'd like to find the shortest path between two vertices (FindShortestPath and GraphDistance). The EdgeWeight between two vertices is a function of the two, requiring a URLFetch and therefore takes some (significant ~1s) time to run, which motivates the following.

My desire is to be able to specify a function for EdgeWeight, along the lines of

EdgeWeight -> MyFunction[#1, #2]

with the ultimate goal of speeding up the shortest path finding process.

First a preliminary question:

Is FindShortestPath Intelligent?

By that I mean, will it search exhaustively, or will it stop when no remaining unsearched paths could possibly be shorter? (This obviously requires positive edge weights, as is the case I am considering).

For example in the graphs below, in the first case the shortest route from the green vertex to the red is around the outside, and if we were using a function to calculate the edge weights we would likely need to evaluate it for most edges. However in the second case the increased cost of the 'spokes' means we should never need to evaluate to the weights around the outer rim.

enter image description here

I have tried to observe a timing difference in FindShortestPath by extending the above demonstration to graphs with 50 rings and 20 vertices per ring, and comparing the timing for the case where the shortest path is to go around the outside, to the case where the innermost spokes are prohibitively expensive and the shortest route is the inner ring. However, I see no timing differences.

Is my (big) graph too small, or is the solver exhaustive?

EdgeWeightFunction?

Hopefully the appeal of an edge weight function is now clear. If the solver is intelligent then I wouldn't have to evaluate all the edge costs at the outset, which is time consuming, but rather those that are potentially of interest would be generated by the solver as required. (Also I think an EdgeWeightFunction would be elegant).

Hopefully you guys can as ever point out the flaw in my thoughts!

$\endgroup$
  • $\begingroup$ What would this EdgeWeightFunction take as arguments? What significant advantages do you expect over just setting EdgeWeights explicitly? $\endgroup$ – Szabolcs May 9 '16 at 17:44
  • $\begingroup$ As arguments I would guess, either the vertex name (however this might not be unique), or more likely the vertex index in the graph, as in the order returned by VertexList. The advantage would be saving the time required to calculate many edge weights which need not be calculated if: The shortest path has already bee found. In the graphs above the four outer edge weights need not be calculated in the second case. I hope thats more clear. I admit the situations in which it would be useful are relatively limited. $\endgroup$ – Quantum_Oli May 9 '16 at 20:11
  • $\begingroup$ For example: If I have to generate and find the shortest path across many different graphs with different edge weight functions (so there is no re-use between cases). If we can generate edge weights on-the-fly using an EdgeWeightFunction, and the shortest path solver is intelligent and only then calculates those weights which could be in the shortest path, then we would in the cases of the two graphs presented above, only need to calculate 7 edge weights instead of all 12, saving nearly half the time. $\endgroup$ – Quantum_Oli May 9 '16 at 20:18
  • 1
    $\begingroup$ The problem with the idea to only calculate needed edge weights is that this would involve a kernel callback for each and every edge weight that is needed. Kernel callbacks are slow. A shortest path finder can in principle be implemented purely in a lower lever language and in practice it likely is. Is there a particular example where you are having performance problems? $\endgroup$ – Szabolcs May 9 '16 at 20:28
  • $\begingroup$ Ah ok, I'm beginning to see why an edgeweightfunction is not as simple as I hoped it could be. The performance problem is that I get the edge weights from a URLFetch and the complete network is prohibitively large to acquire all the edge weights. I was hoping an approach along the lines I have described would allow me to expand the network up to the point where I must have the shortest (cheapest) path. $\endgroup$ – Quantum_Oli May 9 '16 at 20:43
7
$\begingroup$

As @Szabolcs suggested I have created my own shortest path finder, based on Dijkstra's algorithm, which allows me to use an EdgeWeightFunction. It's pretty much a translation of the pseudocode on the wiki and I include it below. First I'll demonstrate its use.

Example Use

The code to generate the two graphs, g1 and g2 in my post above:

edges = {1 -> 2, 2 -> 3, 4 -> 3, 1 -> 4, 1 <-> 5, 2 <-> 6, 3 <-> 7, 4 <-> 8, 5 -> 6, 6 -> 7, 8 -> 7, 5 -> 8};
coords = {{-0.5, -0.5}, {0.5, -0.5}, {0.5, 0.5}, {-0.5, 0.5}, {-1., -1.}, {1., -1.}, {1., 1.}, {-1., 1.}};
weights1 = {1, 1, 1, 1, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25};
weights2 = {1, 1, 1, 1, 10, 10, 10, 10, 0.25, 0.25, 0.25, 0.25};


g1 = Graph[edges,
  EdgeLabelStyle -> Directive[Red, 12, Background -> White],
  EdgeLabels -> Thread[edges -> weights],
  VertexCoordinates -> coords,
  VertexLabels -> "Name",
  VertexStyle -> {1 -> Green, 3 -> Red}
 ]

g2 = Graph[edges,
  EdgeLabelStyle -> Directive[Red, 12, Background -> White],
  EdgeLabels -> Thread[edges -> weights],
  VertexCoordinates -> coords,
  VertexLabels -> "Name",
  VertexStyle -> {1 -> Green, 3 -> Red}
 ]

enter image description here

The paths given by the built in FindShortestPath:

FindShortestPath[g1, 1, 3]
FindShortestPath[g2, 1, 3]

{1, 5, 6, 7, 3}

{1, 2, 3}

And MyDijkstra:

MyDijkstra[g1, 1, 3, MyEdgeCost]
MyDijkstra[g2, 1, 3, MyEdgeCost]

{1, 5, 6, 7, 3}

{1, 2, 3}

Where we define the function MyEdgeCost as follows (change g1 to g2):

wam = WeightedAdjacencyMatrix[g1];
vexl = VertexList[g1];
order = Ordering[g1];

wamo = Transpose[Transpose[wam[[order]]][[order]]];

MyEdgeCost[s_, t_] := wamo[[s, t]]

The reordering of the WeightedAdjacencyMatrix is because WeightedAdjacencyMatrix makes a matrix with entries ordered according to the order returned by VertexList.

Performance

Now to the usefulness! Running MyDijkstra on g1 and g2 and counting the number of function calls we get 15 in the first case, and only 7 in the second. This is functionality that I want as I will now be able to calculate a greatly reduced number of edge costs (which are not known in advance and are expensive to compute) in my large (mostly unvisited) graph.

One can also use memoization to further reduce calls in both directions on undirected edges:

MyEdgeCost[s_, t_] := MyEdgeCost[s, t] = MyEdgeCost[t, s] = wamo[[s, t]]

(I have not attempted to optimise the below function as it is still very quick even on large graphs and certainly not a limiting factor in my implementations.)

The Function

A little messy and not fully optimised. Though I have parallelised the edge cost function calls.

MyDijkstra[graph_, source_, target_, EdgeCostFunction_] := 
 Module[{vexl, sourceI, targetI, Q, n, dist, prev, alt, u, v, S},

  vexl = VertexList[graph];

  n = Length[vexl];
  {sourceI, targetI} = Position[vexl, #][[1, 1]] & /@ {source, target};

  Q = Range[n];

  dist = ConstantArray[\[Infinity], n];
  prev = ConstantArray[Indeterminate, n];

  dist[[sourceI]] = 0;

  While[Length[Q] > 0,
   u = Q[[First@Ordering[dist[[#]] & /@ Q, 1]]];
   If[u == targetI, Break[]];
   Q = DeleteCases[Q, u];

   v = Position[vexl, #][[1, 1]] & /@ Rest@VertexOutComponent[graph, vexl[[u]], 1];
   alt = dist[[u]] + ParallelMap[EdgeCostFunction[vexl[[u]], #] &, vexl[[v]]];

   For[i = 1, i <= Length[v], i++,
    If[alt[[i]] < dist[[v[[i]]]],
      dist[[v[[i]]]] = alt[[i]];
      prev[[v[[i]]]] = u;
    ];
   ];

  ];

  (*Reverse iterate shortest path*)
  S = {};
  u = targetI;

  While[NumberQ@prev[[u]],
   PrependTo[S, u];
   u = prev[[u]];
  ];

  PrependTo[S, u];

  {vexl[[S]], dist[[targetI]]}
]
$\endgroup$
  • 1
    $\begingroup$ I was just trying to understand your code for the Dijkstra algorithm and realised that the edge labels method to plot your graphs wasn't working for me. If one replaces the EdgeLabels -> Thread[edges -> weights], with EdgeWeight -> weights, EdgeLabels -> "EdgeWeight", then it works for me at least. I think there is a problem in visualising edge labels when there is a mix of directed and undirected edges. I will post this as a separate question however. $\endgroup$ – Dunlop Mar 6 '17 at 10:50

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.