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?

Improve this question
$\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

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.