Code to construct a complete graph

Question

I have tried to design a class for a complete graph.

Needless to say, disadvantages of my current solution are very visible:

• dependent inputs have led to verification headaches.

  In this code we rely on 2 inputs set of nodes and edge map. This creates the need to add a special verification function called addEdgeVerification to ensure both these data structures are in sync.how to avoid this complexity of inter-parameter dependency at the same not burdening the client with headache of providing a complex data structure as input to our code ?

• forces illegal states when some functions are invoked out of sequence.

  This code returns illegal state if getAdj is called before complete graph has been constructed. How can this illegal state issues be avoided, without the need to force user to provide a complete graph ? Note the name of code is CompleteGraphConstructor. This means users will make use of our code to construct a complete graph. We dont users to take any effort to construct graph themselves. We want them to provide tiny inputs such as edges and nodes, and we should take the pain to join pieces.

But alternatives are also not free from handicaps:

• dumping everything in constructor would make it a god constructor

  A constructor can help us reduce/eliminate illegal state. But it would result in god constructors. It does not look like a good option, either.

I am looking for recommendations on code architecture.

public class CompleteGraphConstructor<T> {

    private final Map<T, HashMap<T, Double>> graph;
    private Set<T> nodes;

    public CompleteGraphConstructor() {
        graph = new HashMap<T, HashMap<T, Double>>();
    }

    /**
    * Add the nodes needed to be part of a graph.
    * 
    * @param nodes     the set nodes to add in the graph.
    * @return           true if nodes list is set, and false if it is not.
    */
    public boolean addNodes (Set<T> nodes) {
        // prevent overriting the nodes.
        if (this.nodes != null) {
            /**
            * Should exception check be performed inside or outside?
            */
            if (nodes == null) throw new NullPointerException("The node cannot be null.");
            if (nodes.size() == 0) throw new NullPointerException("The size of node cannot be zero.");
            this.nodes = nodes;
            return true;
        }
        return false;
    }

    /**
    * Add all edges of the graph.
    * 
    * @param nodeId  if nodeId is not null. 
    * @param allEdges   all the edges of input node
    */
    public void addEdges (T nodeId, Map<T, Double> allEdges) {

        addEdgeVerification(nodeId, allEdges);

        graph.put(nodeId, (HashMap<T, Double>) allEdges);
    }


    private void addEdgeVerification(T nodeId, Map<T, Double> allEdges) {
        if (!nodes.contains(nodeId)) throw new NoSuchElementException("The source node: " + nodeId + " does not exist.");

        // making sure that edges include nodes provided in the node Set.
        for (T node : allEdges.keySet()) {
            if (!nodes.contains(node)) throw new NoSuchElementException("The target node: " + nodeId + "  not exist.");
        }

        // make sure that all the nodes in the edge set are included in allEdges
        for (T node : nodes) {
            if (node != nodeId) {
                if (!allEdges.containsKey(nodeId)) throw new IllegalArgumentException("The input map does not contain all edges. ");
                }
            }
        }

    public Map<T, Double> getAdj (T nodeId) {
        if (!nodes.contains(nodeId)) throw new NoSuchElementException("The node " + nodeId + " does not exist.");
        if (!graph.containsKey(nodeId)) throw new IllegalStateException("The graph is not populated with " + nodeId);

        return graph.get(nodeId);
    }
}

Answer 1

I think you expect addNodes to be called exactly once, and expect it to be called before any other method.

Therefore, remove the addNodes method, and move the Set<T> nodes parameter to the constructor.

The next thing you want to do is define all edges. To do that you expect the user to call addEdges repeatedly (one for each node).

A simpler way to do that might be to pass in a list of all edges. If you do the following then you only need to call the method once (because the List can contain all edges for all nodes):

public class Edge<T>
{
    T node1;
    T node2;
    Double d;
}

public void addEdges(Iterable<Edge> allEdges) {
    for (Edge edge : allEdges) {
        addEdge(edge.node1, edge.node2, edge.value);
        addEdge(edge.node2, edge.node1, edge.value);
    }
}

private void addEdge(T node1, T node2, Double value) {
    if (!graph.containsKey(node1))
        graph.put(node1, new HashMap<T, Double>());
    HashMap<T, Double> map = graph.get(node1);
    if (map.containsKey(node2))
        throw new DuplicateEdgeException("Duplicate " + node1 + " to " + node2);
    map.put(node2, value);
}

Your Set<T> nodes is only used for assertions. I'm not sure how useful that is.

Also I don't understand your comment about a "god constructor". A constructor initializes the object using input data: that is something to love.

In summary, perhaps a class like the following. This constructs an arbitrary graph, using only a collection of edges as its input; it supports an isComplete method to test whether the resulting graph is complete (which, you could call as an assertion in the constructor):

class Graph
{
    public class Edge<T>
    {
        T node1;
        T node2;
        Double d;
    }

    private final Map<T, HashMap<T, Double>> graph;

    public Graph(Iterable<Edge> allEdges) {
        graph = new HashMap<T, HashMap<T, Double>>();
        for (Edge edge : allEdges) {
            addEdge(edge.node1, edge.node2, edge.value);
            addEdge(edge.node2, edge.node1, edge.value);
        }
    }

    private void addEdge(T node1, T node2, Double value) {
        if (!graph.containsKey(node1))
            graph.put(node1, new HashMap<T, Double>());
        HashMap<T, Double> map = graph.get(node1);
        if (map.containsKey(node2))
            throw new DuplicateEdgeException("Duplicate " + node1 + " to " + node2);
        map.put(node2, value);
    }

    public bool isComplete()
    {
        int count = graph.size();
        for (HashMap<T, Double> map : graph.values())
            if (count != (map.size() + 1))
                return false;
        return true;
    }

    public Map<T, Double> getAdj (T nodeId) {
        if (!graph.containsKey(nodeId)) throw new IllegalStateException("The graph is not populated with " + nodeId);    
        return graph.get(nodeId);
    }
}