See the previous and initial iteration.
Terminology
Given an undirected graph \$G = (V, E)\$, the eccentricity of a node \$u \in V\$, \$e(u)\$, is the maximum length (number of edges) of a shortest path from \$u\$ to the furthermost node from \$u\$. The graph radius is the smallest eccentricity over all its nodes, or namely
$$ \min_{u \in V} e(u). $$
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 \in V\$, 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.
What's new
The following snippet demonstrates two brute-force algorithms for computing graph radii. However, I was able to optimize the second radius finder by the following heuristic: keep track of the smallest eccentricity so far (call it, say, \$e\$) and whenever we are running yet another BFS from a node, if we reach a distance at least equal to \$e\$, we terminate search as we are not able to improve \$e\$.
Performance
I get the following figures:
Seed: 70678049304775
GraphRadiusFinder - time elapsed: 12449.61 milliseconds, radius: 4.
PruningGraphRadiusFinder - time elapsed: 1709.66 milliseconds, radius: 4.
Code
AbstractGraphRadiusFinder.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.UndirectedGraphNode;
/**
* This abstract class defines the API for graph radius finder algorithms and
* provides some shared functionality.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Nov 21, 2015)
*/
public abstract class AbstractGraphRadiusFinder {
protected final Deque<UndirectedGraphNode> queue = new ArrayDeque<>();
protected final Map<UndirectedGraphNode,
Integer> distanceMap = new HashMap<>();
protected final List<UndirectedGraphNode> connectedComponent;
public abstract int findRadius();
protected AbstractGraphRadiusFinder(
UndirectedGraphNode connectedComponentRepresentative) {
Objects.requireNonNull(connectedComponentRepresentative,
"The connected component representative node " +
"is null.");
this.connectedComponent = expand(connectedComponentRepresentative);
}
protected List<UndirectedGraphNode> expand(UndirectedGraphNode node) {
queue.add(node);
distanceMap.put(node, 0);
while (!queue.isEmpty()) {
UndirectedGraphNode current = queue.removeFirst();
for (UndirectedGraphNode child : current.children()) {
if (!distanceMap.containsKey(child)) {
distanceMap.put(child, 0);
queue.addLast(child);
}
}
}
return new ArrayList<>(distanceMap.keySet());
}
}
GraphRadiusFinder.java:
package net.coderodde.graph.radius;
import net.coderodde.graph.UndirectedGraphNode;
/**
* 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 extends AbstractGraphRadiusFinder {
public GraphRadiusFinder(
UndirectedGraphNode connectedComponentRepresentative) {
super(connectedComponentRepresentative);
}
@Override
public int findRadius() {
int radius = Integer.MAX_VALUE;
for (UndirectedGraphNode node : connectedComponent) {
int tentativeRadius = getMaximumDistanceFrom(node);
if (radius > tentativeRadius) {
radius = tentativeRadius;
}
}
return radius;
}
private int getMaximumDistanceFrom(UndirectedGraphNode node) {
queue.clear();
distanceMap.clear();
queue.addLast(node);
distanceMap.put(node, 0);
int maximumDistance = 0;
while (!queue.isEmpty()) {
UndirectedGraphNode current = queue.removeFirst();
for (UndirectedGraphNode 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;
}
}
PruningGraphRadiusFinder.java:
package net.coderodde.graph.radius;
import net.coderodde.graph.UndirectedGraphNode;
/**
* 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.
* <p>
* This implementation, however, keeps track of the minimum node eccentricity,
* and prunes all the nodes whose distance from the initial node is equal or
* larger than the cached eccentricity.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Nov 20, 2015)
*/
public class PruningGraphRadiusFinder extends AbstractGraphRadiusFinder {
public PruningGraphRadiusFinder(
UndirectedGraphNode connectedComponentRepresentative) {
super(connectedComponentRepresentative);
}
@Override
public int findRadius() {
int smallestRadius = Integer.MAX_VALUE;
for (UndirectedGraphNode node : connectedComponent) {
int tentativeRadius = getMaximumDistanceFrom(node, smallestRadius);
if (smallestRadius > tentativeRadius) {
smallestRadius = tentativeRadius;
}
}
return smallestRadius;
}
private int getMaximumDistanceFrom(UndirectedGraphNode node,
int smallestRadius) {
queue.clear();
distanceMap.clear();
queue.addLast(node);
distanceMap.put(node, 0);
int maximumDistance = 0;
while (!queue.isEmpty()) {
UndirectedGraphNode current = queue.removeFirst();
for (UndirectedGraphNode child : current.children()) {
if (!distanceMap.containsKey(child)) {
int distance = distanceMap.get(current) + 1;
if (distance == smallestRadius) {
return distance;
}
distanceMap.put(child, distance);
queue.addLast(child);
if (maximumDistance < distance) {
maximumDistance = distance;
}
}
}
}
return maximumDistance;
}
}
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 UndirectedGraphNode {
private final String name;
private final Set<UndirectedGraphNode> neighbors = new HashSet<>();
public UndirectedGraphNode(String name) {
this.name = Objects.requireNonNull(name, "The node name is null.");
}
public void addNeighbor(UndirectedGraphNode neighbor) {
this.neighbors.add(neighbor);
neighbor.neighbors.add(this);
}
public Set<UndirectedGraphNode> 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(((UndirectedGraphNode) o).name);
}
}
PerformanceDemo.java:
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import net.coderodde.graph.UndirectedGraphNode;
import net.coderodde.graph.radius.AbstractGraphRadiusFinder;
import net.coderodde.graph.radius.GraphRadiusFinder;
import net.coderodde.graph.radius.PruningGraphRadiusFinder;
public class PerformanceDemo {
public static void main(String[] args) {
int NODES = 3000;
int EDGES = 25000;
long seed = System.nanoTime();
Random random = new Random(seed);
List<UndirectedGraphNode> graph = buildRandomGraph(NODES,
EDGES,
random);
System.out.println("Seed: " + seed);
profile(new GraphRadiusFinder(graph.get(0)));
profile(new PruningGraphRadiusFinder(graph.get(0)));
}
private static void profile(AbstractGraphRadiusFinder finder) {
long startTime = System.nanoTime();
int radius = finder.findRadius();
long endTime = System.nanoTime();
System.out.printf("%s - time elapsed: " +
"%.2f milliseconds, radius: %d.\n",
finder.getClass().getSimpleName(),
1.0 * (endTime - startTime) / 1e6,
radius);
}
private static List<UndirectedGraphNode> buildRandomGraph(int nodes,
int edges,
Random random) {
List<UndirectedGraphNode> nodeList = new ArrayList<>(nodes);
for (int i = 0; i < nodes; ++i) {
nodeList.add(new UndirectedGraphNode("" + 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()));
}
}
Anything to improve here?
