Java Class Design - Graphs

Question

Hey there,

I'm fairly new to Java, and I need some help figuring out a good class hierarchy and overall design for an assignment we've been given (i'm studying CS).

The assignment is graph-theory related, so we were asked to create interfaces for 2 types of graphs, simple graphs and multi-graphs (which are allowed to have parallel edges), and the corresponding implementation.

I came up with the following interface hierarchy:

* Element
    - Vertex
    - Edge
        + MultiEdge
* Graph
    - MultiGraph

And their corresponding implementations. Now I really don't want do discuss my actual implementation here, I'm just giving some examples which I had trouble with because of (at least I think so) the way I designed the whole think.

The whole thing worked pretty well until I needed to extend my Graph to have MultiGraph functionality. Here's a code snippet from GraphImpl:

protected final List edges;

public Graph addEdge(Edge e) {
    List newEdges = new ArrayList<Edge>();
    newEdges.addAll(edges);
    newEdges.add(e);
    return new GraphImpl(vertices, newEdges);
}

As you can see, I store the graphs edges in a List<Edge> in my GraphImpl, and therefor, I have lots of those lists all over my implementation. Also, you can see that I return a new GraphImpl from addEdge, as GraphImpl is supposed to be immutable.

With this I ran into a lot of trouble when implementing MultiGraph, because here, I needed to exchange the List<Edge> for a List<MultiEdge>. But when I redefined the "edges" variable in MultiGraph, I think that the methods in GraphImpl were still accessing the list I defined in GraphImpl, so that edges wouldn't get added if I called MultiGraph, until completely rewrote it for MultiGraph. But later I noticed that I would've had to rewrite it anyway, because addEdge in GraphImpl returns (naturally) a GraphImpl, but in MultiGraphImpl, I would've needed a MultiGraphImpl to be created.

What I am trying to understand is, how would you design and implement such a thing. What I have is a bunch of interfaces extending each other, and the same hierarchy of implementations, also extending each other.

The functionality of Graph is just a subset of MultiGraph, so everything that is being done in GraphImpl is mostly also valid for MultiGraphImpl. Right now, I needed to copy lots of code from GraphImpl to MultiGraphImpl, just to overcome type problems (which I, at least somehow, understand, but I wouldn't know how to circumvent them).

I hope you're not too confused by now, because I definitely am ;) If I was unclear in any part, I'll be happy to clarify, just point me towards whats missing.

Answer 1

Could be that you need a Composite Pattern here. It lets you treat single and multi objects in a similar way. Perhaps that can help your design.

Answer 2

Here is some very well-annotated Java source code implementing graph-theoretical objects and algorithms, hopefully relevant to your problem. (You probably want to start reading here.)

Good luck!

Answer 3

The is a very complete datastructures designed by Goodrich/Tamassia for the book Data Structures and Algorithms in Java.

Give it a try it: http://net3.datastructures.net/

And, yes, i does support multi-graph