debugjavaMinor

Code to construct a complete graph

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

codeconstructcompletegraph

Problem

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 {

private final Map> graph;
private Set nodes;

public CompleteGraphConstructor() {
graph = new HashMap>();
}

/**
* 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 nodes) {
// prevent overriting the nodes.
if (this.nodes != null) {
/**
* Sho

Solution

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 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 node1;
    T node2;
    Double d;
}

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

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

    private final Map> graph;

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

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

Code Snippets

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

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

Context

StackExchange Code Review Q#39064, answer score: 4

Revisions (0)

No revisions yet.