6
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Why was this code marked negative ? I am looking for suggestions is this out of place ? \$\endgroup\$ – JavaDeveloper Jan 12 '14 at 1:39
  • 1
    \$\begingroup\$ Maybe is because you are asking "for recommendations on code architecture.". If you take a look in the help center, you will realize that your question is off-topic. \$\endgroup\$ – Alfredo Cavalcanti Jan 12 '14 at 4:30
  • \$\begingroup\$ apologies and agreed \$\endgroup\$ – JavaDeveloper Jan 12 '14 at 6:18
  • \$\begingroup\$ Just for the record, I did not down voted your question. You don't need to apologize. ;-) \$\endgroup\$ – Alfredo Cavalcanti Jan 12 '14 at 6:23
  • 1
    \$\begingroup\$ I downvoted it because I didn't understand the question: I didn't understand what the program was supposed to do, until I realized that "complete graph" is a technical term with a precise meaning (after which I added a hyperlink to a definition of "complete graph", and reversed my downvote). \$\endgroup\$ – ChrisW Jan 12 '14 at 12:50
4
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • \$\begingroup\$ maybe god constructor was a wrong term to refer to but here is the article I was referring to - stackoverflow.com/questions/18049710/constructor-best-practices \$\endgroup\$ – JavaDeveloper Jan 12 '14 at 23:13
  • \$\begingroup\$ @JavaDeveloper I see. In my opinion, both those answers are wrong, and I don't understand their reasoning. I think that an API should be easy to use, as simple as possible, and difficult to use incorrectly: therefore having a single constructor is better than 'multi-stage' construction, which would requires the user/client to make several methods calls in the right sequence in order to 'construct' the final object. \$\endgroup\$ – ChrisW Jan 12 '14 at 23:20

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.