Class Collaboration Patterns

This page describes some of the patterns we use in defining the structure of JGraphT. Very often, questions come up on the mailing list or forum about how best to accomplish something, or about proposed improvements, and a suggestion is given in terms of one of these patterns. So here's an overview.

Most of the implementation classes which make up the JGraphT library fall into one of these categories:

• Core data structures: in-memory representation for the content of a particular kind of graph (e.g. DefaultDirectedGraph, WeightedMultigraph)
• View data structures: classes which provide a "view" on top of another graph (e.g. an EdgeReversedGraph view can be created on top of any DirectedGraph to simulate the existence of an equivalent graph with the edges reversed)
• Iterators: standard graph iterators (e.g. DepthFirstIterator, ClosestFirstIterator)
• Graph analysis algorithms: algorithms which query a graph for some property or derived structure (e.g. DijkstraShortestPath)
• Graph generators and mutators: algorithms which create or update graphs (e.g. RingGraphGenerator)
• Indexing algorithms: algorithms which compute and store properties of graphs, edges, and vertices for quick retrieval (e.g. NeighborIndex)
• Extenders: classes which extend JGraphT to interoperate with other packages (e.g. JGraphModelAdapter, MatrixExporter)
• Utilities: various generically useful methods With those categories in mind, the sections below explain some of the most common patterns.

Avoid modifying an iterator or algorithm if you can achieve the same effect with a view

For example, we have views AsUndirectedGraph and EdgeReversedGraph. The former allows you to treat a directed graph as an undirected graph. So, if you have a directed tree, but want to perform a breadth-first search on it ignoring direction, just create an AsUndirectedGraph and use that as input to the BreadthFirstIterator. Likewise, if you have a directed acyclic graph and want to perform a reverse-topological sort on it, use an EdgeReversedGraph as input to TopologicalOrderIterator.

Why is this a good idea?

• Separation of concerns. Instead of cluttering up the logic for the iterator with the various cases, we can keep it clean and leave all of that in the views.
• Reusability. Once the view class has been developed, it can be reused to enhance all existing and future iterators.

Keep interfaces minimalist

It is always tempting to edit the core graph interfaces and data structures to add extra methods such as isConnected(v1, v2). Why is this a bad idea?

• The core/view implementations are already quite complicated; from a maintenance point of view, every addition adds a lot of pain and potential for bugs (e.g. due to incorrectly overridden or delegated methods).
• Every addition also adds a burden to developers of new graph implementations. For example, suppose someone writes a graph implementation backed by tables in a relational database. They may not be able to inherit any of the core data structures, so if you add a convenience method such as isConnected to the wrong abstract base class, it will not be of any help to them. And it's not always easy to figure out where a method belongs in the hierarchy or delegation pattern. What should you do instead? Add a new analysis algorithm or utility method for deriving the property of interest (e.g. ConnectivityInspector). If you are worried about the performance of recomputation, create an indexing algorithm (e.g. NeighborIndex).

Use listeners to minimize coupling

For example, NeighborIndex uses a listener to receive notifications of modifications to the graph being indexed. That way, it can maintain the neighbor sets incrementally, without the underlying graph even knowing that the derived properties are being maintained outside.