(See the next iteration.)

The following snippet is a brute-force algorithm for computing a graph radius in time $\Theta(V^2 + VE)$ and space $\Theta(V)$ simply by doing $|V|$ breadth-first searches over each node in the graph. The graph radius is a minimum graph eccentricity of any node of the graph, where eccentricity of a node $u$ is the maximum distance from $u$ to any other graph node.

Explanation of the graph radius concept

What happens here is that you iterate over all nodes in the graph, and for each iterated node $u$, you run breadth-first search starting from $u$; your aim here is to find the largest distance from $u$ to any other node in the graph. Record all those distances associated with every iterated node, and finally return the minimum of them.

package net.coderodde.graph.radius;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import net.coderodde.graph.UnweightedGraphNode;

/**
* This class implements a brute-force algorithm for computing the radius of
* an unweighted graph. The graph radius in question is defined as follows:
* for each graph node, run breadth-first search and return the maximum length
* from the source node to any other node. Gather the same number over all of
* the nodes and then pick the smallest of them.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Nov 20, 2015)
*/

private Deque<UnweightedGraphNode> queue;
private Map<UnweightedGraphNode, Integer> distanceMap;

this.queue = new ArrayDeque<>();
this.distanceMap = new HashMap<>();
}

public int compute(UnweightedGraphNode connectedComponentRepresentative) {
Objects.requireNonNull(connectedComponentRepresentative,
"The graph component representative is null.");
List<UnweightedGraphNode> connectedComponent =
finderState.expand(connectedComponentRepresentative);

for (UnweightedGraphNode node : connectedComponent) {

}
}

}

private int getMaximumDistanceFrom(UnweightedGraphNode node) {
queue.clear();
distanceMap.clear();

distanceMap.put(node, 0);

int maximumDistance = 0;

while (!queue.isEmpty()) {
UnweightedGraphNode current = queue.removeFirst();

for (UnweightedGraphNode child : current.children()) {
if (!distanceMap.containsKey(child)) {
int distance = distanceMap.get(current) + 1;
distanceMap.put(child, distance);

if (maximumDistance < distance) {
maximumDistance = distance;
}
}
}
}

return maximumDistance;
}

private List<UnweightedGraphNode> expand(UnweightedGraphNode node) {
distanceMap.put(node, 0);

while (!queue.isEmpty()) {
UnweightedGraphNode current = queue.removeFirst();

for (UnweightedGraphNode child : current.children()) {
if (!distanceMap.containsKey(child)) {
distanceMap.put(child, 0);
}
}
}

return new ArrayList<>(distanceMap.keySet());
}
}


UndirectedGraphNode.java:

package net.coderodde.graph;

import java.util.Collections;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

/**
* This class implements an unweighted graph node.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Nov 20, 2015)
*/
public class UnweightedGraphNode {

private final String name;
private final Set<UnweightedGraphNode> neighbors = new HashSet<>();

public UnweightedGraphNode(String name) {
this.name = Objects.requireNonNull(name, "The node name is null.");
}

}

public Set<UnweightedGraphNode> children() {
return Collections.unmodifiableSet(neighbors);
}

@Override
public int hashCode() {
return name.hashCode();
}

@Override
public boolean equals(Object o) {
if (o == null) {
return false;
}

if (o.getClass() != getClass()) {
return false;
}

return name.equals(((UnweightedGraphNode) o).name);
}
}


PerformanceDemo.java:

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import net.coderodde.graph.UnweightedGraphNode;

public class PerformanceDemo {

public static void main(String[] args) {
int NODES = 2000;
int EDGES = 6000;
long seed = System.nanoTime();
Random random = new Random(seed);
List<UnweightedGraphNode> graph = buildRandomGraph(NODES,
EDGES,
random);
System.out.println("Seed: " + seed);

long startTime = System.nanoTime();
long endTime = System.nanoTime();

System.out.printf("Time elapsed: %.2f milliseconds, radius: %d.\n",
1.0 * (endTime - startTime) / 1e6,
}

private static List<UnweightedGraphNode> buildRandomGraph(int nodes,
int edges,
Random random) {
List<UnweightedGraphNode> nodeList = new ArrayList<>(nodes);

for (int i = 0; i < nodes; ++i) {
}

for (int i = 0; i < edges; ++i) {
}

return nodeList;
}

private static <T> T choose(List<T> list, Random random) {
return list.get(random.nextInt(list.size()));
}
}


package net.coderodde.graph.radius;

import net.coderodde.graph.UnweightedGraphNode;
import org.junit.Test;
import static org.junit.Assert.*;

@Test
public void testCompute() {
UnweightedGraphNode a = new UnweightedGraphNode("A");
UnweightedGraphNode b = new UnweightedGraphNode("B");
UnweightedGraphNode c = new UnweightedGraphNode("C");
UnweightedGraphNode d = new UnweightedGraphNode("D");
UnweightedGraphNode e = new UnweightedGraphNode("E");
UnweightedGraphNode f = new UnweightedGraphNode("F");
UnweightedGraphNode g = new UnweightedGraphNode("G");

assertEquals(1, finder.compute(a));
assertEquals(1, finder.compute(b));
assertEquals(1, finder.compute(c));
assertEquals(1, finder.compute(d));

assertEquals(1, finder.compute(a));
assertEquals(1, finder.compute(b));
assertEquals(1, finder.compute(c));
assertEquals(1, finder.compute(d));

assertEquals(2, finder.compute(a));
assertEquals(2, finder.compute(b));
assertEquals(2, finder.compute(c));
assertEquals(2, finder.compute(d));
assertEquals(2, finder.compute(e));

assertEquals(2, finder.compute(a));
assertEquals(2, finder.compute(b));
assertEquals(2, finder.compute(c));
assertEquals(2, finder.compute(d));
assertEquals(2, finder.compute(e));
assertEquals(2, finder.compute(f));

assertEquals(3, finder.compute(a));
assertEquals(3, finder.compute(b));
assertEquals(3, finder.compute(c));
assertEquals(3, finder.compute(d));
assertEquals(3, finder.compute(e));
assertEquals(3, finder.compute(f));
assertEquals(3, finder.compute(g));

assertEquals(2, finder.compute(a));
assertEquals(2, finder.compute(b));
assertEquals(2, finder.compute(c));
assertEquals(2, finder.compute(d));
assertEquals(2, finder.compute(e));
assertEquals(2, finder.compute(f));
assertEquals(2, finder.compute(g));
}
}


So, how can I improve this one?

- One obvious improvement is not to use brute force. A standard approach is to pick a random vertex $v$, BFS find the farthest vertex $u$, and BFS find the vertex $w$ farthest from $u$. Notice that $u$ and $w$ form the diameter.

• compute is not a very descriptive name. findRadius perhaps?

• I am not sure I understand the necessity of dummy public constructor. The

public GraphRadiusFinder(UnweightedGraphNode connectedComponentRepresentative) {
this.queue = new ArrayDeque<>();
this.distanceMap = new HashMap<>();
this.connectedComponent = expand(connectedComponentRepresentative);
}


looks more direct.