(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.
GraphRadiusFinder.java:
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)
*/
public class GraphRadiusFinder {
private Deque<UnweightedGraphNode> queue;
private Map<UnweightedGraphNode, Integer> distanceMap;
public GraphRadiusFinder() {}
private GraphRadiusFinder(boolean dummy) {
this.queue = new ArrayDeque<>();
this.distanceMap = new HashMap<>();
}
public int compute(UnweightedGraphNode connectedComponentRepresentative) {
Objects.requireNonNull(connectedComponentRepresentative,
"The graph component representative is null.");
GraphRadiusFinder finderState = new GraphRadiusFinder(false);
List<UnweightedGraphNode> connectedComponent =
finderState.expand(connectedComponentRepresentative);
int radius = Integer.MAX_VALUE;
for (UnweightedGraphNode node : connectedComponent) {
int tentativeRadius = finderState.getMaximumDistanceFrom(node);
if (radius > tentativeRadius) {
radius = tentativeRadius;
}
}
return radius;
}
private int getMaximumDistanceFrom(UnweightedGraphNode node) {
queue.clear();
distanceMap.clear();
queue.addLast(node);
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);
queue.addLast(child);
if (maximumDistance < distance) {
maximumDistance = distance;
}
}
}
}
return maximumDistance;
}
private List<UnweightedGraphNode> expand(UnweightedGraphNode node) {
queue.add(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);
queue.addLast(child);
}
}
}
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 void addNeighbor(UnweightedGraphNode neighbor) {
this.neighbors.add(neighbor);
neighbor.neighbors.add(this);
}
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;
import net.coderodde.graph.radius.GraphRadiusFinder;
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();
int radius = new GraphRadiusFinder().compute(graph.get(0));
long endTime = System.nanoTime();
System.out.printf("Time elapsed: %.2f milliseconds, radius: %d.\n",
1.0 * (endTime - startTime) / 1e6,
radius);
}
private static List<UnweightedGraphNode> buildRandomGraph(int nodes,
int edges,
Random random) {
List<UnweightedGraphNode> nodeList = new ArrayList<>(nodes);
for (int i = 0; i < nodes; ++i) {
nodeList.add(new UnweightedGraphNode("" + i));
}
for (int i = 0; i < edges; ++i) {
choose(nodeList, random).addNeighbor(choose(nodeList, random));
}
return nodeList;
}
private static <T> T choose(List<T> list, Random random) {
return list.get(random.nextInt(list.size()));
}
}
GraphRadiusFinderTest.java:
package net.coderodde.graph.radius;
import net.coderodde.graph.UnweightedGraphNode;
import org.junit.Test;
import static org.junit.Assert.*;
public class GraphRadiusFinderTest {
private final GraphRadiusFinder finder = new GraphRadiusFinder();
@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");
a.addNeighbor(b);
a.addNeighbor(c);
a.addNeighbor(d);
assertEquals(1, finder.compute(a));
assertEquals(1, finder.compute(b));
assertEquals(1, finder.compute(c));
assertEquals(1, finder.compute(d));
c.addNeighbor(d);
assertEquals(1, finder.compute(a));
assertEquals(1, finder.compute(b));
assertEquals(1, finder.compute(c));
assertEquals(1, finder.compute(d));
c.addNeighbor(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));
e.addNeighbor(f);
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));
f.addNeighbor(g);
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));
g.addNeighbor(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(f));
assertEquals(2, finder.compute(g));
}
}
So, how can I improve this one?
