Code to construct a complete graph
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&lt;T&gt; 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&lt;T&gt;
{
    T node1;
    T node2;
    Double d;
}

public void addEdges(Iterable&lt;Edge&gt; 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&lt;T, Double&gt;());
    HashMap&lt;T, Double&gt; map = graph.get(node1);
    if (map.containsKey(node2))
        throw new DuplicateEdgeException("Duplicate " + node1 + " to " + node2);
    map.put(node2, value);
}


Your Set&lt;T&gt; 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&lt;T&gt;
    {
        T node1;
        T node2;
        Double d;
    }

    private final Map&lt;T, HashMap&lt;T, Double&gt;&gt; graph;

    public Graph(Iterable&lt;Edge&gt; allEdges) {
        graph = new HashMap&lt;T, HashMap&lt;T, Double&gt;&gt;();
        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&lt;T, Double&gt;());
        HashMap&lt;T, Double&gt; 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&lt;T, Double&gt; map : graph.values())
            if (count != (map.size() + 1))
                return false;
        return true;
    }

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