2
$\begingroup$

Assuming you have a connected graph (in my case also undirected and equal/no edge weights), how could you see all the vertex pairs whose shortest length path is equal to the graph's diameter?

An implementation of Floyd–Warshall algorithm would work, and it sounds like there are slightly faster implementations to the problem. As of now I'm just looping over every pair and running FindShortestPath.

Maybe you can somehow get access to the pair(s) used to output the longest minimum path with the built-in Diameter function?

$\endgroup$
1
  • 3
    $\begingroup$ how about diameterPairs[g_?ConnectedGraphQ] := Module[{dm = GraphDistanceMatrix[g]}, Position[dm, Max[dm]]] or diameterPairs2[g_?ConnectedGraphQ] := Position[GraphDistanceMatrix[g], GraphDiameter[g]]? $\endgroup$
    – kglr
    Jun 7, 2021 at 5:09

1 Answer 1

2
$\begingroup$

You can use IGFindDiameter from IGraph/M. It will return the path corresponding to the diameter. You can take the first/last elements as the endpoints.

$\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.