|PREV NEXT||FRAMES NO FRAMES|
|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
|com.phoenixst.plexus.examples||Contains a number of example
|com.phoenixst.plexus.operations||Contains operations on
|com.phoenixst.plexus.traversals||Contains basic traversals that can be used upon
|com.phoenixst.plexus.util||Contains utilities useful for creating
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.
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:
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.
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
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
is used to distinguish nodes, a particular
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
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.
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
creates a new graph with the same elements as its argument.
|PREV NEXT||FRAMES NO FRAMES|