Java: how to represent graphs?

Question

I'm implementing some algorithms to teach myself about graphs and how to work with them. What would you recommend is the best way to do that in Java? I was thinking something like this:

public class Vertex {

    private ArrayList<Vertex> outnodes; //Adjacency list. if I wanted to support edge weight, this would be a hash map.

    //methods to manipulate outnodes
}

public class Graph {
    private ArrayList<Vertex> nodes;
    //algorithms on graphs
}

But I basically just made this up. Is there a better way?

Also, I want it to be able to support variations on vanilla graphs like digraphs, weighted edges, multigraphs, etc.

Answer 1

If you need weighted edges and multigraphs, you might want to add another class Edge.

I would also recommend using generics to allow specifying which sub-class of Vertex and Edge are currently used. For example:

public class Graph<V extends Vertex> {
List<V> vertices;
...
}

When it comes to implementing graph algorithms, you could also define interfaces for your graph classes on which the algorithms can operate, so that you can play around with different implementations of the actual graph representation. For example, simple graphs that are well-connected might be better implemented by an adjacency matrix, sparser graphs might be represented by adjacency lists - it all depends...

BTW Building such structures efficiently can be quite challenging, so maybe you could give us some more details on what kind of job you would want to use them for? For more complex tasks I would suggest you have a look at the various Java graph libraries, to get some inspiration.

Answer 2

Take a look at the http://jung.sourceforge.net/doc/index.html graph library. You can still practice implementing your own algorithms (maybe breadth-first or depth-first search to start), but you don't need to worry about creating the graph structure.

Answer 3

Time ago I had the same problem and did my own implementation. What I suggest you is to implement another class: Edge. Then, a Vertex will have a List of Edge.

public class Edge {
    private Node a, b;
    private directionEnum direction;     // AB, BA or both
    private int weight;
    ...
}

It worked for me. But maybe is so simple. There is this library that maybe can help you if you look into its code: http://jgrapht.sourceforge.net/

Answer 4

If your goal is use the graphs in any application there are lots of tools available, you could have a look at - http://www.jfree.org/jfreechart/

Answer 5

I'd recommend graphviz highly when you get to the point where you want to render your graphs.

And its companions: take a look at Laszlo Szathmary's GraphViz class, along with notugly.xls.