3
$\begingroup$

It appears that GraphDistance, GraphDistanceMatrix, FindShortestPath, etc. all work with Machine Precision. I don't see an option for WorkingPrecision. Please tell me that's not the case!

The overview introduction to Graphs & Networks says

Graphs are first-class citizens in the Wolfram Language; they can be used as input and output and they are deeply integrated into the rest of the Wolfram Language.

Has arbitrary precision been omitted from this deep integration? Or have I just missed something?

Example: Inputs have explicit precision 80

m = GraphDistanceMatrix[
      CompleteGraph[3, DirectedEdges -> True, 
      EdgeWeight -> {0.0084166399999999995384936113396179280243813991546630859375`80., 
                  0.0003397469999999999982175091783886955454363487660884857177734375`80.,
                  0.005964065999999999638514491806517980876378715038299560546875`80.,
                  0.000114147000000000003344137466942953551551909185945987701416015625`80.,
                  0.0086472479999999997402060358808739692904055118560791015625`80.,
                  0.0037996010000000001068098942624828850966878235340118408203125`80.},
      EdgeLabels -> "EdgeWeight", 
      VertexLabels -> "Name"
     ]
    ]

Outputs look like machine precision numbers:

{{0., 0.00413935, 0.000339747}, 
 {0.00596407, 0., 0.000114147}, 
 {0.00864725, 0.0037996, 0.}}

GraphDistance only involves comparisons and additions. It seems to me that incorporating arbitrary precision would be a small step with great value.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ I am no expert in Mathematica's graph functionality but, if I had to guess, I'd say that this might be a limitation of whatever external library is used under the hood to implement this functionality. $\endgroup$
    – MarcoB
    Commented Dec 17, 2021 at 3:55
  • $\begingroup$ Some graph metrics can use exact numbers and arbitrary precision numbers, some cannot. As you yourself show, this is not the case for shortest paths. While it could be implemented, it does not seem to be (note that if it were, it would come with a performance impact; in order to retain the current performance, they'd possibly need to keep two separate implementations, a fast machine precision one and a slow exact one). $\endgroup$
    – Szabolcs
    Commented Dec 17, 2021 at 16:30
  • 1
    $\begingroup$ I am just curious: what is the application for which you need shortest paths with higher than machine precision? $\endgroup$
    – Szabolcs
    Commented Dec 17, 2021 at 16:31
  • 1
    $\begingroup$ Szabolcs, yes, I understand the tradeoff between speed and precision (and memory). That balance is managed so nicely in tools like NDSolve and Minimize. I'm trying to solve a Brownian drift control problem. Proving optimality of the solution requires high precision -- often WorkingPrecision greater than 100. To construct the functions proving optimality requires Column Generation: Maximize (an LP) yields dual variables that translate to edge weights for ShortestPath that identifies new columns to add to the optimization. NDSolve was brilliant in getting the solution. Now I need the proof. $\endgroup$
    – user46831
    Commented Dec 18, 2021 at 14:20

1 Answer 1

Reset to default
2
$\begingroup$

This will do for my purposes. It employs the precision of the weights themselves. Basic, but fast enough.

graphDistanceMatrix[graph_]:=
  Module[{distances},
      With[{edges = EdgeList[graph],
            vertices = VertexList[graph]}, 
          With[{weights = Thread[edges->PropertyValue[graph,EdgeWeight]],
                n = Length[vertices]},
                (* Initialize the distances between vertices *)
                distances = Array[(#1\[DirectedEdge]#2/.weights/.i_[DirectedEdge]j_:>If[i==j,0,\[Infinity]])&, {Length[vertices],Length[vertices]}];
                Do[If[distances[[i]][[j]] > distances[[i]][[k]]+distances[[k]][[j]],
                   distances[[i]][[j]] = distances[[i]][[k]]+distances[[k]][[j]]],{k,1, n}, {i, 1, n}, {j, 1, n}];
                distances]]]
Improve this answer
$\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.