Plexus v0.13.1 API Specification

This document is the API specification for the Plexus Graph Library, a library of generic graph data structures in which vertices and edges may contain user-defined objects.

See:
Description

Packages

com.phoenixst.collections	This package contains additions and/or fixes to the Jakarta-Commons Collections package.
com.phoenixst.plexus	Contains the core interfaces and classes for the Plexus Graph Library.
com.phoenixst.plexus.algorithms	Contains algorithms that can be used upon Graphs.
com.phoenixst.plexus.examples	Contains a number of example Graph implementations for the Plexus Graph Library.
com.phoenixst.plexus.operations	Contains operations on Graph objects for the Plexus Graph Library.
com.phoenixst.plexus.traversals	Contains basic traversals that can be used upon Graphs.
com.phoenixst.plexus.util	Contains utilities useful for creating Graph implementations, but that are unlikely to be relevant for typical users of the Plexus Graph Library.

This document is the API specification for the Plexus Graph Library, a library of generic graph data structures in which vertices and edges may contain user-defined objects.

Formal Definitions and Terminology

A graph is composed of a set of nodes (sometimes also called vertices) and a set of edges, where each edge is a pair of nodes. The nodes comprising an edge are referred to as its endpoints, and we say that the nodes are adjacent. Some sources restrict the term adjacent to apply only to undirected graphs, but we will not do that here. Graphs are usually visualized by assigning points or shapes to each node and drawing a curve for each edge between its endpoints.

An undirected graph is a graph in which an edge's endpoints are unordered. We say that an edge is incident on its endpoints.

A directed graph is a graph in which an edge's endpoints are ordered. The first endpoint is called the edge's tail and the second its head. If (u,v) is an edge (u is the tail and v the head), we may say:

• there is an edge from u to v,
• the edge is incident from or leaves u,
• the edge is incident to or enters v,
• the edge is incident on u and v, and
• u -> v.

A simple graph does not allow more than one edge between any two endpoints (a directed simple graph may still have one edge in each direction) or self-loops (an edge with both endpoints being the same node). A multigraph is a graph which does not have these restrictions.

Implementation Notes, Constraints, and Assumptions

The Graph interface is the primary data structure defined by the Plexus Graph Library. All other classes and interfaces provided here exist to implement and support implementations of this interface. Unlike most examples from graph literature and practice (as well as the short overview above), the interface specification allows a single Graph to contain both directed and undirected edges. Of course, any specific implementation may restrict this behavior.

This package is similar in many ways to the Java Collections Framework. In particular, the details of how graph nodes and edges are implemented are hidden from the user. Nodes (and often edges) serve as containers for objects provided by the user. Although the implementations of both are hidden, they do differ in that there is a Graph.Edge interface presented to the user describing a graph edge.

Nodes must contain unique (using Object.equals()) user-provided objects. This requirement allows nodes to be referenced unambiguously (when creating edges, for example). The user-defined objects contained in Graph.Edge objects, however, are not subject to this requirement in the general case. Because Object.equals() is used to distinguish nodes, a particular Graph implementation may refer to only a single such node encountered. So, for example, the following may occur:

  Object x = new Integer( 0 );
  Object y = new Integer( 1 );
  Object x2 = new Integer( 0 );
  graph.addNode( x );
  graph.addNode( y );
  graph.addEdge( null, x, y, true );
  graph.addNode( x2 );      // returns false, already contains x
  graph.containsNode( x2 ); // returns true
  Graph.Edge edge = graph.getEdge( new DefaultEdgeFilter( x2, y ) );
  // edge.getTail() may be x, not x2, here

Nothing prohibits a Graph.Edge from also being a node in the same Graph. In other words, Graph.Edges can point to other Graph.Edges. If a particular Graph implementation allows this, these two aspects of any particular Graph.Edge are independent. Adding or removing a Graph.Edge as a node has no impact upon the object's existence as an edge, and vice versa.

All general-purpose Graph implementation classes should provide two "standard" constructors: a void (no arguments) constructor, which creates an empty graph, and a constructor with a single argument of type Graph, which creates a new graph with the same elements as its argument.

Since:

Plexus 1.0

Version:

1.0

Author:

Ray A. Conner