Digraph Code in Java

Question

This is used to create a directed graph of type T. The directed graph has edges and vertices with values but is directional such that nodes can loop unto themselves or only go a single direction even though 2 vertices are connected.

Things I am looking to get out of this review are:

• My use of a hashMap instead of an ArrayList in the Digraph<T> class itself. I was wondering if I could just use an ArrayList and an index but then I would have to test whether something did not exist at a certain id value so it seemed a HashMap was better for this function.

• My copy method for Generics. I implemented a copy method for copying a generic type which seems like a lot of overkill to just copy a value but I don't see a better way to do this copy in Java.

• My exception handling. I would like my Exception handling to be reviewed of how I am creating my own exceptions and handling them. In C++ I would be able to just rethrow the exception after being caught and have the rethrown exception not caught to ensure the program would fail after an exception was hit and not continue. In this way I would have a stack of where the exception occurred and the program terminate. I am not sure if I can rethrow an unhandled exception or what is the best way to do this in Java, maybe just rethrow a runtime exception packaging the exception message?

• Any other overall feedback is helpful.

import java.lang.reflect.*;
import java.util.*;

class MissingDigraphNodeException extends Exception 
{
    private static final long serialVersionUID = 1000L;
    public MissingDigraphNodeException(String message)
    {
        super(message);
    }
}

class CopyException extends Exception 
{
    private static final long serialVersionUID = 2000L;
    public CopyException(String message)
    {
        super(message);
    }
}

class DigraphNode<T>  
{
    Integer id;
    T data;
    ArrayList<DigraphNode<T> > links;

    public DigraphNode(Integer i) 
    {
        id = i; 
        links = new ArrayList<DigraphNode<T> >();
    }
    public DigraphNode(Integer i, T d) 
    { 
        id = i; data = d; 
        links = new ArrayList<DigraphNode<T> >();
    }

    public DigraphNode(DigraphNode<T> other)
    {
        try
        {
            this.data = copy(other.data);
        }
        catch (CopyException e)
        {
            e.printStackTrace();
        }
        this.links=other.getLinks();
        this.id = new Integer(other.id);
    }

    // is there a better way to copy a generic?
    @SuppressWarnings("unchecked")
    public T copy( T source ) throws CopyException
    {
        Class<?> clzz = source.getClass();
        Method meth;
        Object dupl = null;
        try {
            meth = clzz.getMethod("clone", new Class[0]);
            dupl = meth.invoke(source, new Object[0]);
        } catch (Exception e) 
        {
            e.printStackTrace();
            throw new CopyException("Error: Copying Generic of T");
        }   
        return (T) dupl;
    }

    public void setData (T d ) { data =  d; }
    public void addLink (DigraphNode<T> n) { links.add(n); }
    public void addLinks (ArrayList<DigraphNode<T> > ns) { links.addAll(ns); }

    public ArrayList<DigraphNode<T> > getLinks()
    {
        // return a new copy of the list
        ArrayList<DigraphNode<T> > l = new ArrayList<DigraphNode<T> >(); 
        for ( DigraphNode<T> i : links )
        {
            i.links.add(new DigraphNode<T>(i)); // use copy constructor
        }
        return l;
    }

    public void printNode()
    {
        System.out.print("Id: " + id + " links: ");
        for ( DigraphNode<T> i : links )
        {
            System.out.print(i.id + " ");
        }
        System.out.println();
    }
}

public class Digraph<T>  
{
    private HashMap<Integer,DigraphNode<T> > nodes;

    Digraph() 
    {
        nodes = new HashMap<Integer,DigraphNode<T> >();
    }

    public void printGraph()
    {
        for ( Map.Entry<Integer, DigraphNode<T> > cursor : nodes.entrySet())
        {
            cursor.getValue().printNode();
        }
    }

    public void addNode(Integer id) { nodes.put (id,new DigraphNode<T>(id)); }

    public void addNodes(ArrayList<Integer> ids) 
    { 
        for ( Integer i : ids)
        {
            nodes.put (i,new DigraphNode<T>(i)); 
        }
    }

    public void setData (Integer id, T data ) throws MissingDigraphNodeException 
    { 
        checkNodeExists(id);
        nodes.get(id).setData(data);
    }

    public void addLink (Integer id, Integer linkId ) throws MissingDigraphNodeException 
    { 
        checkNodeExists(id);
        checkNodeExists(linkId);
        nodes.get(id).addLink(nodes.get(linkId));
    }

    public void addLinks (Integer id, ArrayList<Integer> links ) throws MissingDigraphNodeException 
    { 
        checkNodeExists(id);
        for ( Integer i : links )
        {
            checkNodeExists(i);
            nodes.get(id).addLink(nodes.get(i));
        }
    }

    public static void main(String[] args) 
    {
        Digraph<Integer> graph= new Digraph<Integer>();
        graph.addNodes(new ArrayList<Integer>(Arrays.asList(1,2,3,4,5)));

        try 
        {       
            // set the data fields
            for ( int i = 1; i <= 5; ++i)
            {
                graph.setData(i, new Integer(i));
            }

            // now add the links between digraph nodes

            graph.addLinks(1,new ArrayList<Integer>(Arrays.asList(2,3)));
            graph.addLinks(2,new ArrayList<Integer>(Arrays.asList(2,4)));
            graph.addLinks(3,new ArrayList<Integer>(Arrays.asList(1)));
            graph.addLinks(4,new ArrayList<Integer>(Arrays.asList(5)));

            graph.printGraph();
        }
        catch ( MissingDigraphNodeException e)
        {
            System.out.println(e.getMessage());
        }
    }

    private void checkNodeExists(Integer id) throws MissingDigraphNodeException 
    {
        if ( nodes.isEmpty() || !nodes.containsKey(id) )
        {
            throw new MissingDigraphNodeException("Error: Digraph Node Id: " + id + " not found in Digrpah");
        }
    }
}

Answer 1

Your use of HashMap is fine.

I agree that your copy() method is overkill. Do you really need to clone the data? If not, then your copy constructor can just be

public DigraphNode(DigraphNode<T> other)
{
    this.data = other.data;
    this.links = other.links;
    this.id = other.id;
}

Then you can dispense with the whole copy() method, the reflection, and the CopyException class. (In any case, copy() should not have been public.)

You should change most of your Integers to ints, and let autoboxing / unboxing do its thing. The only difference is that Integer can be null, while int cannot, and you wouldn't want null IDs anyway.

Your exception handling in checkNodeExists() is correct, but unconventional. Exceptions should be for unexpected events. Therefore, your code should abide by the maxim, "Don't ask for permission; ask for forgiveness." The only reason why you would want to call checkNodeExists() is if you want to fetch the node immediately afterwards. With that in mind, you should just go ahead and fetch the node, and throw an exception if that fails.

private DigraphNode<T> getNode(int id) throws MissingDigraphNodeException 
{
    DigraphNode<T> node = nodes.get(id);
    // This assumes that null is not a legitimate value in the map
    if (node == null)
    {
        throw new MissingDigraphNodeException("Error: Digraph Node Id: " + id + " not found in Digraph");
    }
    return node;
}

Then, you can eliminate all calls to checkNodeExists(), and replace all nodes.get(id) with getNode(id).

Finally, the ugliness of

graph.addNodes(new ArrayList<Integer>(Arrays.asList(1,2,3,4,5)))

is a sign that something is wrong — you don't want your method signatures to restrict you to a particular implementation of lists. You should replace all mentions of mentions of ArrayList<DigraphNode<T> > and ArrayList<Integer> with List<DigraphNode<T> > and List<Integer>. Then you can simply say

graph.addNodes(Arrays.asList(1,2,3,4,5));

---

Putting it all together…

import java.util.*;

class MissingDigraphNodeException extends Exception 
{
    private static final long serialVersionUID = 1000L;
    public MissingDigraphNodeException(String message)
    {
        super(message);
    }
}

class DigraphNode<T>  
{
    int id;
    T data;
    ArrayList<DigraphNode<T> > links;

    public DigraphNode(int i) 
    {
        id = i;
        links = new ArrayList<DigraphNode<T> >();
    }
    public DigraphNode(int i, T d) 
    { 
        id = i; data = d;
        links = new ArrayList<DigraphNode<T> >();
    }

    public DigraphNode(DigraphNode<T> other)
    {
        this.data = other.data;
        this.links = other.links;
        this.id = other.id;
    }

    public void setData (T d ) { data =  d; }
    public void addLink (DigraphNode<T> n) { links.add(n); }
    public void addLinks (List<DigraphNode<T> > ns) { links.addAll(ns); }

    public List<DigraphNode<T> > getLinks()
    {
        // return a new copy of the list
        ArrayList<DigraphNode<T> > l = new ArrayList<DigraphNode<T> >(); 
        for ( DigraphNode<T> i : links )
        {
            i.links.add(new DigraphNode<T>(i)); // use copy constructor
        }
        return l;
    }

    public void printNode()
    {
        System.out.print("Id: " + id + " links: ");
        for ( DigraphNode<T> i : links )
        {
            System.out.print(i.id + " ");
        }
        System.out.println();
    }
}

public class Digraph<T>  
{
    private HashMap<Integer,DigraphNode<T> > nodes;

    Digraph() 
    {
        nodes = new HashMap<Integer,DigraphNode<T> >();
    }

    public void printGraph()
    {
        for ( Map.Entry<Integer, DigraphNode<T> > cursor : nodes.entrySet())
        {
            cursor.getValue().printNode();
        }
    }

    public void addNode(int id) { nodes.put (id,new DigraphNode<T>(id)); }

    public void addNodes(List<Integer> ids) 
    { 
        for ( Integer i : ids)
        {
            nodes.put (i,new DigraphNode<T>(i)); 
        }
    }

    public void setData (int id, T data ) throws MissingDigraphNodeException 
    { 
        getNode(id).setData(data);
    }

    public void addLink (int id, int linkId ) throws MissingDigraphNodeException 
    { 
        getNode(id).addLink(getNode(linkId));
    }

    public void addLinks (int id, List<Integer> links ) throws MissingDigraphNodeException 
    { 
        DigraphNode<T> node = getNode(id);
        for ( Integer i : links )
        {
            node.addLink(getNode(i));
        }
    }

    private DigraphNode<T> getNode(int id) throws MissingDigraphNodeException 
    {
        DigraphNode<T> node = nodes.get(id);
        if (node == null)
        {
            throw new MissingDigraphNodeException("Error: Digraph Node Id: " + id + " not found in Digraph");
        }
        return node;
    }

    public static void main(String[] args) 
    {
        Digraph<Integer> graph= new Digraph<Integer>();
        graph.addNodes(Arrays.asList(1,2,3,4,5));

        try 
        {       
            // set the data fields
            for ( int i = 1; i <= 5; ++i)
            {
                graph.setData(i, i);
            }

            // now add the links between digraph nodes

            graph.addLinks(1,Arrays.asList(2,3));
            graph.addLinks(2,Arrays.asList(2,4));
            graph.addLinks(3,Arrays.asList(1));
            graph.addLinks(4,Arrays.asList(5));

            graph.printGraph();
        }
        catch ( MissingDigraphNodeException e)
        {
            System.out.println(e.getMessage());
        }
    }
}