Labeled graph representation in Java

Suppose we have a directed labeled graph, i.e. a graph where the edges from a vertex to another are labeled with a value. How can we model this in Java? (or in an object oriented language in general?)

My current solution is to have a class Vertex which has a Collection<Edge> outgoingEdges and a Collection<Edge>开发者_Python百科 incomingEdges, where Edge is a class that has three fields:

• label which is the label of the edge
• predecessor which is the source Vertex
• successor which is the destination Vertex

Other solutions?

I wouldn't say you need to separate out the outgoing and incoming edges, you can just check whether the vertex is the source or target and have a utility method that gives you outgoing and incoming. I notice a lot of implementations code directed and undirected graphs differently, there really is no reason to.

Looks OK. It's analogous to the standard technique of modelling a many-to-many relationship in a database with an auxillary table to hold info about the relationship.

Do you also have a collection of root vertices?

Depending on what traversals you need to do, you may not need incoming edges - e.g. if you only ever start from the roots.

Strictly speaking you don't even need Vertex objects, if that hasn't got any other information attached, you can just number the vertices and put the numbers in predecessor and successor for each edge. That may be going a bit far, however :)

I think what you did was right. And you can add a Graph class which have list of vertex and list of edge as the members.

You have represented all the entities as object, so that looks okay to me.