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

Each node is named uniquely and knows who it is connected to. The List of connections allows for a Node to be connected to an arbitrary number of other nodes.

public class Node {     public String name;     public List<Edge> connections; } 

Each connection is directed, has a start and an end, and is weighted.

public class Edge {     public Node start;     public Node end;     public double weight; } 

A graph is just your collection of nodes. Instead of List<Node> consider Map<String, Node> for fast lookup by name.

public class Graph {     List<Node> nodes; } 

Answer 2

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.