should the adjacency information be stored in the graph object or in the vertex itself?

Question

For purpose of the demonstrating the concept of adjacency list, I would assume that it is easy to represent the list as a list of lists and put the vertices as numbers and put them in an array where we can reference them by index directly in a graph. Once we get the index of a vertex, we can just get the respective list array.

However, for actual objects, where the vertex can't be just referenced by an array index, I would assume a separate vertex object would need to be created. In this case, my question is where should the edge information be implemented.

In OO based programming languages, such as java, I have see implementations of the adjacency list based graph implementation where the adjacency information is stored in the vertex object itself with a data member of some type of data structure, such as arrays, list, and etc. However, I have also seen people implement the adjacency edge information in the graph object itself by maintaining a list of edges.

Is it more of a personal preference as to where the edge information should be stored?

Answer 1

I think it depends on how you want the graph API to look like.

Suppose for example that the graph works with an arbitrary generic type representing a vertex. In this case, instead of defining a vertex wrapper for internal use (and managing adjacency in it), you can simply have an adjacency data structure as a member of the graph class:

public class Graph<V> {
  private Map<V, Set<V>> adjacencies;
  ..
}  

If on the other hand you do wish to expose a Vertex object together with its adjacencies (I don't find a good reason why), then you should be careful about the data consistency. The adjacency data must be read only for the caller (or defensively copied), otherwise the caller may alter an edge in such way that it's not symmetric anymore.

To conclude, the adjacency data maintained by the graph class seems a better option to me. It simplifies the API and the implementation, and it doesn't require special measures to protect the class invariants if you decide to expose the vertex object.