2
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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);
    }
    ...
\$\endgroup\$
  • \$\begingroup\$ That's kind of funny, but I was told in the previous iteration to compute the connected component from a node in the constructor. \$\endgroup\$ – coderodde Nov 22 '15 at 6:24
  • \$\begingroup\$ So what do you think yourself? The main reasons for me are that you are stuck to the initial implementation which i've faced when trying to optimieze your code. And that you are doing work on a probably unexpected moment. Your performance check misses this time as well. There are more pro's and contra's. As always it depends.. \$\endgroup\$ – Sam Segers Nov 22 '15 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.