javautils.graph.adt
Interface Graph

All Known Subinterfaces:

AugmentedGraph

All Known Implementing Classes:

AnAugmentedGraph, AugmentedGraphDecorator, BasicGraph, GraphDecorator, UndirectedGraph

public interface Graph

Abstract, adjacency list style, representation of a directed finite graph. The structure allows multiple edges between the same nodes and nodes to have self edges. Each node and edge must be represented by a separate object.

In this library, graphs are generally considered to be immutable - even though immutability may not be strictly enforced. Instead of mutating a graph, one should generally create new graphs.

Note: If you need to get reproducible results from graph algorithms, you must make sure that the hash codes of node and edge objects do not vary between different runs of the same program. Note that if you override the Object.hashCode()-method, you generally also need to override the Object.equals(java.lang.Object)-method.

Design rationale

The basic assumption underlying the design of this interface is that a client of a graph algorithm library already has some representation of graphs. This graph interface is an Adapter, see [Gamma1995], that the client implements in order to allow the graph algorithms implemented by the library to examine the graphs of the client.

The superclass of nodes and edges is simply Object. The rationale for this is that requiring more specific interfaces would require the client to actually implement the interfaces, potentially requiring modifications to client code, or to implement an adapter layer and actually instantiate new node and edge objects.

Method Summary

java.util.List	edgesFrom(java.lang.Object node) List of all edges from the specified source node.
java.util.List	nodes() List of all nodes.
java.lang.Object	sourceOf(java.lang.Object edge) The source node of the edge.
java.lang.Object	targetOf(java.lang.Object edge) The target node of the edge.

Method Detail

nodes

public java.util.List nodes()

List of all nodes.

Important: This method should have O(1) time complexity. This means that you should avoid constructing the list each time this method is called.

Note: The order of nodes in the returned list may have an effect on the results of graph algorithms.

edgesFrom

public java.util.List edgesFrom(java.lang.Object node)

List of all edges from the specified source node.

Important: This method should have O(1) time complexity. This means that you should avoid constructing the list each time this method is called.

Note: The order of edges in the returned list may have an effect on the results of graph algorithms.

sourceOf

public java.lang.Object sourceOf(java.lang.Object edge)

The source node of the edge.

targetOf

public java.lang.Object targetOf(java.lang.Object edge)

The target node of the edge.