[Networkit] Getting pair of nodes with shortest path distance equal to the diameter?
michael.hamann at kit.edu
Thu Dec 15 14:50:50 CET 2016
On 15.12.2016 12:39, Matteo Riondato wrote:
> After having computed the diameter or run APSP, is there an easy what to get the pair of nodes whose shortest path distance is equal to the diameter of the graph (or a vector of the pairs or any pair, if there are multiple pairs ) ?
Computing the diameter is not necessarily an APSP computation. The
algorithm we have currently implemented only for unweighted, undirected
graphs  uses a lot of different bounds. Probably, one can find and
keep track of node pairs for the bounds and report the matching one at
the end. If not, one can definitely at least get a node with maximum
eccentricity and run another BFS from it to get the other node.
For all other exact variants we have an APSP implementation where
getting such a node pair is trivial to implement but currently not
More information about the NetworKit