Docjar: A Java Source and Docuemnt Enginecom.*    java.*    javax.*    org.*    all    new    plug-in

Quick Search    Search Deep
Overview  Package   Class  Use  Deprecated  Index 
Home >> All >> com >> phoenixst >> [ plexus overview ]  PREV CLASS  NEXT CLASS
SUMMARY: JavaDoc of com.phoenixst.plexus.AbstractGraph JAVADOC | Sourc code of com.phoenixst.plexus.AbstractGraph SOURCE | Download com.phoenixst.plexus.AbstractGraph DOWNLOAD | NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

com.phoenixst.plexus
Class AbstractGraph  view AbstractGraph download AbstractGraph.java

java.lang.Object
  extended bycom.phoenixst.plexus.AbstractGraph
All Implemented Interfaces:
Graph
public abstract class AbstractGraph
extends java.lang.Object
implements Graph

This class provides a skeletal implementation of the Graph interface, to minimize the effort required to implement this interface.

Which methods must be implemented by a concrete extension of this class depends upon what kind of graph is being created. The programmer must provide implementations for the following methods (check all categories that apply):

All Graph.nodeIterator() 55
Graph.edgeIterator() 55
Directed outTraverser( node ) 55
inTraverser( node ) 55
Undirected isDirected() 55
traverser( node ) 55
Simple isSimple() 55
removeEdge( Edge ) 55
getEdge( tail, head ) 55
Multi edgeIterator( tail, head ) 55
Modifiable addNode( node ) 55
addEdge( object, tail, head ) 55
Modifying operations of returned iterators

The documentation for each non-abstract method in this class describes its implementation in detail. Each of these methods may be overridden if the graph being implemented admits a more efficient implementation. Note that almost every method implementation here is written in terms of an iterator over the structure of this graph; these methods are all rather inefficient.

NOTE: Because the implemented methods in this class are written in terms of other methods, and sometimes in different ways depending upon whether the graph is simple/multi or directed/undirected, great care must taken when implementing methods in extensions of this class to avoid mutual recursion. For example, when creating a rooted tree class with directed edges from parent to child, you might implement inTraverser( node ) 55 to use inDegree( node ) 55 , since there is at most one edge to traverse and you can use GraphUtils.singletonTraverser( graph, edge, node ) 55 . In this case, you must also override inDegree( node ) since its implementation in this class uses inTraverser( node ).

The programmer should generally provide a void (no argument) and Graph constructor, as per the recommendation in the Graph interface specification.

Since:
1.0
Version:
$Revision: 1.23 $

Nested Class Summary
protected  class AbstractGraph.ChainTraverser
           
 
Nested classes inherited from class com.phoenixst.plexus.Graph
Graph.Edge
 
Constructor Summary
protected AbstractGraph()
          Protected constructor, called implicitly by subclasses.
 
Method Summary
 Graph.Edge addEdge(java.lang.Object object, java.lang.Object tail, java.lang.Object head)
          This implementation throws an UnsupportedOperationException.
 boolean addNode(java.lang.Object node)
          This implementation throws an UnsupportedOperationException.
 void clear()
          This implementation iterates over the nodes in this graph, removing each element using the Iterator.remove()>Iterator.remove() 55 operation.
 boolean containsEdge(Graph.Edge edge)
          This implementation iterates over the edges in this graph with the tail and head of the specified Edge looking for the specified Edge.
 boolean containsNode(java.lang.Object node)
          This implementation iterates over the nodes in this graph looking for the specified element.
 int degree(java.lang.Object node)
          If this graph is directed, this implementation returns outDegree( node ) + inDegree( node ).
 java.util.Iterator edgeIterator(java.lang.Object tail, java.lang.Object head)
          If this graph is simple, this implementation returns a modifiable singleton Iterator using getEdge( tail, head ) 55 if the edge exists.
 int edgeSize()
          This implementation counts the number of elements accessed by this graph's Graph.edgeIterator() 55 method.
 Graph.Edge getEdge(java.lang.Object tail, java.lang.Object head)
          If this graph is not simple, this implementation returns the first Edge returned by edgeIterator( tail, head ) 55 , or null if it the iterator is empty.
 int inDegree(java.lang.Object node)
          This implementation counts the number of elements accessed by this graph's inTraverser( node ) 55 method.
 Traverser inTraverser(java.lang.Object node)
          This implementation throws an UnsupportedOperationException and should be overridden if this graph is directed.
 boolean isDirected()
          This implementation returns true.
 boolean isEmpty()
          This implementation returns edgeSize() == 0.
 boolean isSimple()
          This implementation returns false.
protected static void iteratorClear(java.util.Iterator i)
          Removes all elements accessed by the specified iterator.
protected static boolean iteratorContains(java.util.Iterator i, java.lang.Object obj, boolean useEquals)
          Returns true if the specified iterator accesses the specified object.
protected static int iteratorCount(java.util.Iterator i)
          Returns the number of elements accessed by the specified iterator.
protected static java.lang.Object iteratorRemove(java.util.Iterator i, java.lang.Object obj, boolean useEquals)
          Removes a single instance of the specified object accessed by the specified iterator.
 int nodeSize()
          This implementation counts the number of elements accessed by this graph's Graph.nodeIterator() 55 method.
 int outDegree(java.lang.Object node)
          This implementation counts the number of elements accessed by this graph's outTraverser( node ) 55 method.
 Traverser outTraverser(java.lang.Object node)
          This implementation throws an UnsupportedOperationException and should be overridden if this graph is directed.
 boolean removeEdge(Graph.Edge edge)
          If this graph is not simple, this implementation iterates over the edges in this graph with the tail and head of the specified Edge looking for the specified Edge.
 boolean removeNode(java.lang.Object node)
          This implementation iterates over the nodes in this graph looking for the specified element.
 Traverser traverser(java.lang.Object node)
          If this graph is directed, this implementation chains together the Traversers returned by outTraverser( node ) 55 and inTraverser( node ) 55 .
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface com.phoenixst.plexus.Graph
edgeIterator, nodeIterator
 

Constructor Detail

AbstractGraph

protected AbstractGraph()
Protected constructor, called implicitly by subclasses.

Method Detail

isDirected

public boolean isDirected()

This implementation returns true.

NOTE: If this method is overridden, then you must also override traverser( node ) 55 .

Specified by:
isDirected in interface Graph

isSimple

public boolean isSimple()

This implementation returns false.

NOTE: If this method is overridden, then you must also override removeEdge( Edge ) 55 and getEdge( tail, head ) 55 .

Specified by:
isSimple in interface Graph

isEmpty

public boolean isEmpty()

This implementation returns edgeSize() == 0.

Specified by:
isEmpty in interface Graph

nodeSize

public int nodeSize()

This implementation counts the number of elements accessed by this graph's Graph.nodeIterator() 55 method.

Specified by:
nodeSize in interface Graph

edgeSize

public int edgeSize()

This implementation counts the number of elements accessed by this graph's Graph.edgeIterator() 55 method.

Specified by:
edgeSize in interface Graph

degree

public int degree(java.lang.Object node)

If this graph is directed, this implementation returns outDegree( node ) + inDegree( node ). Otherwise, this implementation counts the number of elements accessed by this graph's traverser( node ) 55 method, counting self-loops twice.

Specified by:
degree in interface Graph

outDegree

public int outDegree(java.lang.Object node)

This implementation counts the number of elements accessed by this graph's outTraverser( node ) 55 method.

Specified by:
outDegree in interface Graph

inDegree

public int inDegree(java.lang.Object node)

This implementation counts the number of elements accessed by this graph's inTraverser( node ) 55 method.

Specified by:
inDegree in interface Graph

addNode

public boolean addNode(java.lang.Object node)

This implementation throws an UnsupportedOperationException.

Specified by:
addNode in interface Graph

removeNode

public boolean removeNode(java.lang.Object node)

This implementation iterates over the nodes in this graph looking for the specified element. If it finds the element, it removes the element using using the Iterator.remove()>Iterator.remove() 55 operation.

Note that this implementation will throw an UnsupportedOperationException if the iterator returned by this graph's Graph.nodeIterator() 55 method does not implement the remove method and this graph contains the specified node.

Specified by:
removeNode in interface Graph

containsNode

public boolean containsNode(java.lang.Object node)

This implementation iterates over the nodes in this graph looking for the specified element.

Specified by:
containsNode in interface Graph

addEdge

public Graph.Edge addEdge(java.lang.Object object,
                          java.lang.Object tail,
                          java.lang.Object head)

This implementation throws an UnsupportedOperationException.

Specified by:
addEdge in interface Graph

removeEdge

public boolean removeEdge(Graph.Edge edge)

If this graph is not simple, this implementation iterates over the edges in this graph with the tail and head of the specified Edge looking for the specified Edge. If it finds the edge, it removes it using using the Iterator.remove()>Iterator.remove() 55 operation.

If this graph is simple, this implementation throws an UnsupportedOperationException and should be overridden. In this case, isSimple() 55 and getEdge( tail, head ) 55 should also be overridden.

Note that this implementation will throw an UnsupportedOperationException if the iterator returned by this graph's edgeIterator( tail, head ) 55 method does not implement the remove method and this graph contains the specified edge.

Specified by:
removeEdge in interface Graph

containsEdge

public boolean containsEdge(Graph.Edge edge)

This implementation iterates over the edges in this graph with the tail and head of the specified Edge looking for the specified Edge.

Specified by:
containsEdge in interface Graph

getEdge

public Graph.Edge getEdge(java.lang.Object tail,
                          java.lang.Object head)

If this graph is not simple, this implementation returns the first Edge returned by edgeIterator( tail, head ) 55 , or null if it the iterator is empty.

If this graph is simple, this implementation throws an UnsupportedOperationException and should be overridden. In this case, isSimple() 55 and removeEdge( Edge ) 55 should also be overridden.

Specified by:
getEdge in interface Graph

clear

public void clear()

This implementation iterates over the nodes in this graph, removing each element using the Iterator.remove()>Iterator.remove() 55 operation.

Note that this implementation will throw an UnsupportedOperationException if the iterator returned by this graph's Graph.nodeIterator() 55 method does not implement the remove method and this graph has nodes.

Specified by:
clear in interface Graph

edgeIterator

public java.util.Iterator edgeIterator(java.lang.Object tail,
                                       java.lang.Object head)

If this graph is simple, this implementation returns a modifiable singleton Iterator using getEdge( tail, head ) 55 if the edge exists. Iterator.remove()>Iterator.remove() 55 calls the removeEdge( Edge ) 55 method. If the edge does not exist, returns an empty Iterator.

If this graph is not simple, this implementation throws an UnsupportedOperationException and should be overridden.

Specified by:
edgeIterator in interface Graph

traverser

public Traverser traverser(java.lang.Object node)

If this graph is directed, this implementation chains together the Traversers returned by outTraverser( node ) 55 and inTraverser( node ) 55 . If the wrapped Traversers allow modification to this graph, then so does the one returned by this method.

If this graph is not directed, this implementation throws an UnsupportedOperationException and should be overridden. In this case, isDirected() 55 should also be overridden.

Specified by:
traverser in interface Graph

outTraverser

public Traverser outTraverser(java.lang.Object node)

This implementation throws an UnsupportedOperationException and should be overridden if this graph is directed. In this case, inTraverser( node ) 55 should also be overridden.

Specified by:
outTraverser in interface Graph

inTraverser

public Traverser inTraverser(java.lang.Object node)

This implementation throws an UnsupportedOperationException and should be overridden if this graph is directed. In this case, outTraverser( node ) 55 should also be overridden.

Specified by:
inTraverser in interface Graph

iteratorCount

protected static final int iteratorCount(java.util.Iterator i)
Returns the number of elements accessed by the specified iterator.

iteratorClear

protected static final void iteratorClear(java.util.Iterator i)
Removes all elements accessed by the specified iterator.

iteratorRemove

protected static final java.lang.Object iteratorRemove(java.util.Iterator i,
                                                       java.lang.Object obj,
                                                       boolean useEquals)
Removes a single instance of the specified object accessed by the specified iterator.

iteratorContains

protected static final boolean iteratorContains(java.util.Iterator i,
                                                java.lang.Object obj,
                                                boolean useEquals)
Returns true if the specified iterator accesses the specified object.

Overview  Package   Class  Use  Deprecated  Index 
Home >> All >> com >> phoenixst >> [ plexus overview ]  PREV CLASS  NEXT CLASS
SUMMARY: JavaDoc of com.phoenixst.plexus.AbstractGraph JAVADOC | Sourc code of com.phoenixst.plexus.AbstractGraph SOURCE | Download com.phoenixst.plexus.AbstractGraph DOWNLOAD | NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD