Graph design in Java

[andrey_zh]

Hi, there!

I need to implement a general purpose graph and I've stuck with OOP design.

The graph is very general, just vertices and edges. Also I'll need to iterate through vertices and edges. Both must allow to store some info on them.

So what is the proper design of a class hierarchy in my case?

What is a better way to store information on vertices and edges: inheritance or a field?

Does it make any sense to use inner classes (hope this is a proper name) like this:

class Graph
{
    public class Vertex { ... }
    public class Edge { ... }
}

?

Thanks in advance!

[Xeel]

Probably the most adequate solution in this case would be http://jgrapht.sourceforge.net/

Examples taken from the JGraphT:

private static DirectedGraph<URL, DefaultEdge> createHrefGraph()
    {
        DirectedGraph<URL, DefaultEdge> g =
            new DefaultDirectedGraph<URL, DefaultEdge>(DefaultEdge.class);

        try {
            URL amazon = new URL("http://www.amazon.com");
            URL yahoo = new URL("http://www.yahoo.com");
            URL **** = new URL("http://www.****.com");

            // add the vertices
            g.addVertex(amazon);
            g.addVertex(yahoo);
            g.addVertex(****);

            // add edges to create linking structure
            g.addEdge(yahoo, amazon);
            g.addEdge(yahoo, ****);
        } catch (MalformedURLException e) {
            e.printStackTrace();
        }

        return g;
    } 

private static UndirectedGraph<String, DefaultEdge> createStringGraph()
    {
        UndirectedGraph<String, DefaultEdge> g =
            new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

        String v1 = "v1";
        String v2 = "v2";
        String v3 = "v3";
        String v4 = "v4";

        // add the vertices
        g.addVertex(v1);
        g.addVertex(v2);
        g.addVertex(v3);
        g.addVertex(v4);

        // add edges to create a circuit
        g.addEdge(v1, v2);
        g.addEdge(v2, v3);
        g.addEdge(v3, v4);
        g.addEdge(v4, v1);

        return g;
    } 

And if you still don't want to implement it just use hashmaps for lists and beans for the actual objects.