0
\$\begingroup\$

(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?

\$\endgroup\$
1
\$\begingroup\$

- One obvious improvement is not to use brute force. A standard approach is to pick a random vertex \$v\$, BFS find the farthest vertex \$u\$, and BFS find the vertex \$w\$ farthest from \$u\$. Notice that \$u\$ and \$w\$ form the diameter.

  • compute is not a very descriptive name. findRadius perhaps?

  • I am not sure I understand the necessity of dummy public constructor. The

    public GraphRadiusFinder(UnweightedGraphNode connectedComponentRepresentative) {
        this.queue = new ArrayDeque<>();
        this.distanceMap = new HashMap<>();
        this.connectedComponent = expand(connectedComponentRepresentative);
    }
    

    looks more direct.

\$\endgroup\$

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.