GraphStream is hosted by the University of Le Havre. It is initiated and maintained by members of the RI_{2}C research team from the LITIS computer science lab.

In a graph G, if d(u,v) is the shortest length between two nodes u and v (ie
the number of edges of the shortest path) let m(u) be the sum of d(u,v) for
all nodes v of G. Centroid of a graph G is a subgraph induced by vertices u
with minimum m(u).

Requirements

This algorithm needs that APSP algorithm has been computed before its own
computation.

Example

Output will be:

A is not in the centroid
B is not in the centroid
C is not in the centroid
D is in the centroid
E is not in the centroid
F is not in the centroid
G is not in the centroid

Complexity

O(n2)

Reference

F. Harary, Graph Theory. Westview Press, Oct. 1969. [Online].
Available: link