Graph radius in Java - follow-up

Question

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?

Answer 1

Don't do a lot of work in the constructor

This 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 iterations

If 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); } ...