
Plexus v0.13.1  
PREV NEXT  FRAMES NO FRAMES 
See:
Description
Packages  

com.phoenixst.collections  This package contains additions and/or fixes to the JakartaCommons 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 userdefined 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 selfloops (an edge with both endpoints being the same node). A multigraph is a graph which does not have these restrictions.
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()
) userprovided objects. This requirement allows
nodes to be referenced unambiguously (when creating edges, for
example). The userdefined 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 generalpurpose 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.

Plexus v0.13.1  
PREV NEXT  FRAMES NO FRAMES 