com.phoenixst.plexus

Interface Graph

public interface Graph

The root interface of the graph hierarchy.

See the Overview Summary for details not included here.

Nodes must contain unique (using Object#equals Object.equals()) user-provided objects. This requirement allows nodes to be referenced unambiguously (when creating edges, for example). The user-defined objects contained in Edge objects, however, are not subject to this requirement in the general case, although Object.equals() will be used for edge comparisons.

Nothing in this interface prohibits a 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 an Graph.Edge as a node has no impact upon the object's existence as a Graph.Edge, and vice versa.

All general-purpose implementations of this interface 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: 1.0

Version: $Revision: 1.43 $

Author: Ray A. Conner

Nested Class Summary
static interfaceGraph.Edge
An interface describing an edge in a Graph.
Method Summary
Graph.EdgeaddEdge(Object object, Object tail, Object head, boolean isDirected)
Adds the specified edge to the Graph (optional operation).
booleanaddNode(Object node)
Adds node to this Graph (optional operation).
CollectionadjacentNodes(Object node, Predicate traverserPredicate)
Returns the nodes adjacent to the specified node for which the specified Predicate is satisfied.
booleancontainsEdge(Graph.Edge edge)
Returns true if this Graph contains the specified Graph.Edge.
booleancontainsNode(Object node)
Returns true if this Graph contains the specified node.
intdegree(Object node)
Returns the degree of node, defined as the number of edges incident on node, with self-loops counted twice.
intdegree(Object node, Predicate traverserPredicate)
Returns the degree of node for which the specified Predicate is satisfied, defined as the number of edges incident on node that pass the predicate, with self-loops counted only once.
Collectionedges(Predicate edgePredicate)
Returns the Graph.Edges from this Graph that satisfy the specified predicate.
ObjectgetAdjacentNode(Object node, Predicate traverserPredicate)
Returns a node adjacent to the specified node for which the specified Predicate is satisfied.
Graph.EdgegetEdge(Predicate edgePredicate)
Returns a Graph.Edge from this Graph that satisfies the specified predicate, or null if no such Graph.Edge exists.
Graph.EdgegetIncidentEdge(Object node, Predicate traverserPredicate)
Returns a Graph.Edge incident on the specified node for which the specified Predicate is satisfied.
ObjectgetNode(Predicate nodePredicate)
Returns a node from this Graph that satisfies the specified predicate, or null if no such node exists.
CollectionincidentEdges(Object node, Predicate traverserPredicate)
Returns the Graph.Edges incident on the specified node for which the specified Predicate is satisfied.
Collectionnodes(Predicate nodePredicate)
Returns the nodes from this Graph that satisfy the specified predicate.
booleanremoveEdge(Graph.Edge edge)
Removes the specified Graph.Edge from this Graph (optional operation).
booleanremoveNode(Object node)
Removes node from this Graph (optional operation).
Traversertraverser(Object node, Predicate traverserPredicate)
Returns a Traverser from node to all adjacent nodes for which the specified Predicate is satisfied.

Method Detail

addEdge

public Graph.Edge addEdge(Object object, Object tail, Object head, boolean isDirected)
Adds the specified edge to the Graph (optional operation). Returns the newly created Graph.Edge if this Graph changed as a result of the call. Returns null if this Graph does not allow duplicate edges and already contains the specified edge.

If a Graph refuses to add a particular edge for any reason other than that it already contains the edge, it must throw an exception (rather than returning null). This preserves the invariant that a Graph always contains the specified edge after this call returns. Graph classes should clearly specify in their documentation any other restrictions on what edges may be added.

Parameters: object the user-defined object to be contained in the new edge. tail the first endpoint of the new edge. head the second endpoint of the new edge. isDirected whether the new edge is directed.

Returns: the newly created Graph.Edge if this Graph changed as a result of the call, null if this Graph does not allow duplicate edges and already contains the specified edge.

Throws: ClassCastException if the class of object, tail, or head is of an inappropriate class for this Graph. IllegalArgumentException if some aspect of object, tail, head, or isDirected is inappropriate for this Graph. IllegalArgumentException if object, tail, or head is null and this Graph does not not permit null edges and/or nodes. NoSuchNodeException if tail or head is not present in this Graph. UnsupportedOperationException if this method is not supported by this Graph.

addNode

public boolean addNode(Object node)
Adds node to this Graph (optional operation). Returns true if this Graph changed as a result of the call. Returns false if this Graph already contains node.

If a Graph refuses to add a particular node for any reason other than that it already contains the node, it must throw an exception (rather than returning false). This preserves the invariant that a Graph always contains the specified node after this call returns. Graph classes should clearly specify in their documentation any other restrictions on what nodes may be added.

Parameters: node the node to be added to this Graph.

Returns: true if this Graph changed as a result of the call, false if this Graph already contains the specified node.

Throws: ClassCastException if the class of node is of an inappropriate class for this Graph. IllegalArgumentException if some aspect of node is inappropriate for this Graph. IllegalArgumentException if node is null and this Graph does not not permit null nodes. UnsupportedOperationException if this method is not supported by this Graph.

adjacentNodes

public Collection adjacentNodes(Object node, Predicate traverserPredicate)
Returns the nodes adjacent to the specified node for which the specified Predicate is satisfied. The argument to the Predicate.evaluate() method is expected to be an OrderedPair. The first element of the OrderedPair is the specified node, the second is the Graph.Edge. It should be noted that removing a node from the returned Collection merely removes one instance of it being adjacent to the specified node. In other words, a connecting Graph.Edge is removed.

Parameters: node return the nodes adjacent to this node for which the specified predicate is satisfied. traverserPredicate the predicate which the returned nodes and the traversed Graph.Edges must satisfy.

Returns: the nodes adjacent to the specified node for which the specified predicate is satisfied.

Throws: ClassCastException if the class of node is of an inappropriate class for this Graph. IllegalArgumentException if some aspect of node is inappropriate for this Graph. IllegalArgumentException if node is null and this Graph does not not permit null nodes. NoSuchNodeException if node is not present in this Graph.

containsEdge

public boolean containsEdge(Graph.Edge edge)
Returns true if this Graph contains the specified Graph.Edge.

Parameters: edge the Graph.Edge whose presence in this Graph is to be tested.

Returns: true if this Graph contains the specified Graph.Edge.

containsNode

public boolean containsNode(Object node)
Returns true if this Graph contains the specified node.

Parameters: node the node whose presence in this Graph is to be tested.

Returns: true if this Graph contains the specified node.

degree

public int degree(Object node)
Returns the degree of node, defined as the number of edges incident on node, with self-loops counted twice. If this node has more than Integer.MAX_VALUE incident edges, returns Integer.MAX_VALUE.

Parameters: node return the degree of this node.

Returns: the degree of node.

Throws: ClassCastException if the class of node is of an inappropriate class for this Graph. IllegalArgumentException if some aspect of node is inappropriate for this Graph. IllegalArgumentException if node is null and this Graph does not not permit null nodes. NoSuchNodeException if node is not present in this Graph.

degree

public int degree(Object node, Predicate traverserPredicate)
Returns the degree of node for which the specified Predicate is satisfied, defined as the number of edges incident on node that pass the predicate, with self-loops counted only once. The argument to the Predicate.evaluate() method is expected to be an OrderedPair. The first element of the OrderedPair is the specified node, the second is the Graph.Edge. If this node has more than Integer.MAX_VALUE such edges, returns Integer.MAX_VALUE.

Parameters: node return the degree of this node for which the specified predicate is satisfied. traverserPredicate the predicate which the counted Graph.Edges must satisfy.

Returns: the degree of node for which the specified predicate is satisfied.

Throws: ClassCastException if the class of node is of an inappropriate class for this Graph. IllegalArgumentException if some aspect of node is inappropriate for this Graph. IllegalArgumentException if node is null and this Graph does not not permit null nodes. NoSuchNodeException if node is not present in this Graph.

edges

public Collection edges(Predicate edgePredicate)
Returns the Graph.Edges from this Graph that satisfy the specified predicate.

Parameters: edgePredicate the predicate which the returned Graph.Edges must satisfy.

Returns: the Graph.Edges from this Graph that satisfy the specified predicate.

getAdjacentNode

public Object getAdjacentNode(Object node, Predicate traverserPredicate)
Returns a node adjacent to the specified node for which the specified Predicate is satisfied. The argument to the Predicate.evaluate() method is expected to be an OrderedPair. The first element of the OrderedPair is the specified node, the second is the Graph.Edge.

Parameters: node traverse to a node adjacent to this node for which the specified predicate is satisfied. traverserPredicate the predicate which the returned node and the traversed Graph.Edge must satisfy.

Returns: a node adjacent to the specified node for which the specified predicate is satisfied.

Throws: ClassCastException if the class of node is of an inappropriate class for this Graph. IllegalArgumentException if some aspect of node is inappropriate for this Graph. IllegalArgumentException if node is null and this Graph does not not permit null nodes. NoSuchNodeException if node is not present in this Graph.

getEdge

public Graph.Edge getEdge(Predicate edgePredicate)
Returns a Graph.Edge from this Graph that satisfies the specified predicate, or null if no such Graph.Edge exists.

Parameters: edgePredicate the predicate which the returned Graph.Edge must satisfy.

Returns: a Graph.Edge from this Graph that satisfies the specified predicate, or null if no such Graph.Edge exists.

getIncidentEdge

public Graph.Edge getIncidentEdge(Object node, Predicate traverserPredicate)
Returns a Graph.Edge incident on the specified node for which the specified Predicate is satisfied. The argument to the Predicate.evaluate() method is expected to be an OrderedPair. The first element of the OrderedPair is the specified node, the second is the Graph.Edge.

Parameters: node traverse to a Graph.Edge incident on this node for which the specified predicate is satisfied. traverserPredicate the predicate which the returned Graph.Edge must satisfy.

Returns: a Graph.Edge incident on the specified node for which the specified predicate is satisfied.

Throws: ClassCastException if the class of node is of an inappropriate class for this Graph. IllegalArgumentException if some aspect of node is inappropriate for this Graph. IllegalArgumentException if node is null and this Graph does not not permit null nodes. NoSuchNodeException if node is not present in this Graph.

getNode

public Object getNode(Predicate nodePredicate)
Returns a node from this Graph that satisfies the specified predicate, or null if no such node exists.

Parameters: nodePredicate the predicate which the returned node must satisfy.

Returns: a node from this Graph that satisfies the specified predicate, or null if no such node exists.

incidentEdges

public Collection incidentEdges(Object node, Predicate traverserPredicate)
Returns the Graph.Edges incident on the specified node for which the specified Predicate is satisfied. The argument to the Predicate.evaluate() method is expected to be an OrderedPair. The first element of the OrderedPair is the specified node, the second is the Graph.Edge.

Parameters: node return the Graph.Edges incident on this node for which the specified predicate is satisfied. traverserPredicate the predicate which the returned Graph.Edges must satisfy.

Returns: the Graph.Edges incident on the specified node for which the specified predicate is satisfied.

Throws: ClassCastException if the class of node is of an inappropriate class for this Graph. IllegalArgumentException if some aspect of node is inappropriate for this Graph. IllegalArgumentException if node is null and this Graph does not not permit null nodes. NoSuchNodeException if node is not present in this Graph.

nodes

public Collection nodes(Predicate nodePredicate)
Returns the nodes from this Graph that satisfy the specified predicate.

Parameters: nodePredicate the predicate which the returned nodes must satisfy.

Returns: the nodes from this Graph that satisfy the specified predicate.

removeEdge

public boolean removeEdge(Graph.Edge edge)
Removes the specified Graph.Edge from this Graph (optional operation).

Parameters: edge the Graph.Edge to be removed from this Graph.

Returns: true if this Graph contained the specified Graph.Edge.

Throws: UnsupportedOperationException if this method is not supported by this Graph.

removeNode

public boolean removeNode(Object node)
Removes node from this Graph (optional operation). This method will also remove all edges incident on node.

Parameters: node the node to be removed from this Graph.

Returns: true if this Graph contained node.

Throws: UnsupportedOperationException if this method is not supported by this Graph.

traverser

public Traverser traverser(Object node, Predicate traverserPredicate)
Returns a Traverser from node to all adjacent nodes for which the specified Predicate is satisfied. The argument to the Predicate.evaluate() method is expected to be an OrderedPair. The first element of the OrderedPair is the specified node, the second is the Graph.Edge. The nodes returned by Traverser are not necessarily distinct. Self-loops are only traversed once. There are no guarantees concerning the order in which the nodes are returned (unless this Graph is an instance of some class that provides a guarantee).

Parameters: node traverse over all nodes adjacent to this node for which the specified predicate is satisfied. traverserPredicate the predicate which the returned nodes and their traversed Graph.Edges must satisfy.

Returns: a Traverser from node to all adjacent nodes for which the specified predicate is satisfied.

Throws: ClassCastException if the class of node is of an inappropriate class for this Graph. IllegalArgumentException if some aspect of node is inappropriate for this Graph. IllegalArgumentException if node is null and this Graph does not not permit null nodes. NoSuchNodeException if node is not present in this Graph.

See the Plexus project home, hosted by SourceForge.
Copyright B) 1994-2006, by Phoenix Software Technologists, Inc. and others. All Rights Reserved. Use is subject to license terms.