See the previous and initial iteration.TerminologyGiven 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 conceptWhat 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 newThe 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\$.PerformanceI get the following figures:Seed: 70678049304775GraphRadiusFinder - time elapsed: 12449.61 milliseconds, radius: 4.PruningGraphRadiusFinder - time elapsed: 1709.66 milliseconds, radius: 4.CodeAbstractGraphRadiusFinder.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?
Graph radius in Java - follow-up
java;algorithm;graph;breadth first search
Don't do a lot of work in the constructorThis is a bad programming practice in general. Because just creating instances can already take a lot of time. I would prefer an init() method instead. Or put the work you are doing in the constructor, in the findRadius() method. Which can call a findRadiusImpl() or something.Prune entire BFS iterationsIf you hold a maximum radius for each node while visiting. You can determine at start that a certain node will not decrease the radius. When it is already visited with a higher or equal radius.public class PruningGraphRadiusFinderExtended extends AbstractGraphRadiusFinder {    protected final Map<UndirectedGraphNode, Integer> allDistanceMap;    public PruningGraphRadiusFinderExtended(UndirectedGraphNode connectedComponentRepresentative) {        super(connectedComponentRepresentative);        allDistanceMap = new HashMap<>();    }    @Override    public int findRadiusImpl() {        int smallestRadius = Integer.MAX_VALUE;        for (UndirectedGraphNode node : connectedComponent) {            int tentativeRadius = getMaximumDistanceFrom(node, smallestRadius);            if (smallestRadius > tentativeRadius) {                smallestRadius = tentativeRadius;            }        }        return smallestRadius;    }    private void setMax(UndirectedGraphNode node, int radius){        if(!allDistanceMap.containsKey(node)){            allDistanceMap.put(node, radius);        }else{            int prev = allDistanceMap.put(node, radius);            if(prev > radius){                allDistanceMap.put(node, prev);            }        }    }    private int getMaximumDistanceFrom(UndirectedGraphNode node, int smallestRadius) {        if(allDistanceMap.containsKey(node)                && allDistanceMap.get(node) >= smallestRadius){            return allDistanceMap.get(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;                    setMax(child, distance);                    if (distance == smallestRadius) {                        return distance;                    }                    distanceMap.put(child, distance);                    queue.addLast(child);                    if (maximumDistance < distance) {                        maximumDistance = distance;                    }                }            }        }        return maximumDistance;    }}Consider using an int id field instead of String name . You are using a lot of hashing, which causes overhead on a String.public class UndirectedGraphNode {    public final int id;    public UndirectedGraphNode(int id) {        this.id = id;    }    @Override    public int hashCode() {        return id;    }    @Override    public boolean equals(Object o) {        if (o == null) {            return false;        }        if (o.getClass() != getClass()) {            return false;        }        return id == (((UndirectedGraphNode) o).id);    }    ...