Java: how to represent graphs?

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

Solution 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.

Solution 3:

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.

Solution 4:

Why not keep things simple and use an adjacency matrix or an adjacency list?

Solution 5:

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/