Is it possible to use a function for EdgeWeight in a Graph?

Question

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.

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!

Answer 1

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}
 ]

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]]}
]