pseudo_diameter

graph_tool.topology.pseudo_diameter(g, source=None, weights=None)

Compute the pseudo-diameter of the graph.

Parameters:

gGraph

Graph to be used.

sourceVertex (optional, default: None)

Source vertex of the search. If not supplied, the first vertex in the graph will be chosen.

weightsEdgePropertyMap (optional, default: None)

The edge weights.

Returns:

pseudo_diameterint

The pseudo-diameter of the graph.

end_pointspair of Vertex

The two vertices which correspond to the pseudo-diameter found.

Notes

The pseudo-diameter is an approximate graph diameter. It is obtained by starting from a vertex source, and finds a vertex target that is farthest away from source. This process is repeated by treating target as the new starting vertex, and ends when the graph distance no longer increases. A vertex from the last level set that has the smallest degree is chosen as the final starting vertex u, and a traversal is done to see if the graph distance can be increased. This graph distance is taken to be the pseudo-diameter.

The paths are computed with a breadth-first search (BFS) or Dijkstra’s algorithm [dijkstra], if weights are given.

The algorithm runs in \(O(V + E)\) time, or \(O(V \log V)\) if weights are given.

References

[pseudo-diameter]

http://en.wikipedia.org/wiki/Distance_%28graph_theory%29

[dijkstra]

E. Dijkstra, “A note on two problems in connexion with graphs.” Numerische Mathematik, 1:269-271, 1959.

Examples

>>> from numpy.random import poisson
>>> g = gt.random_graph(300, lambda: (poisson(3), poisson(3)))
>>> dist, ends = gt.pseudo_diameter(g)
>>> print(dist)
8.0
>>> print(int(ends[0]), int(ends[1]))
0 157