$Id: CHANGELOG,v 1.59 2007/04/01 20:18:23 rconner Exp $
LEGAL STUFF
============================================================
Copyright (C) 1994-2007 by Phoenix Software Technologists, Inc. and
others. All rights reserved.
THIS PROGRAM AND DOCUMENTATION IS PROVIDED UNDER THE TERMS OF THE
COMMON PUBLIC LICENSE ("AGREEMENT") WHICH ACCOMPANIES IT. ANY USE,
REPRODUCTION OR DISTRIBUTION OF THE PROGRAM CONSTITUTES RECIPIENT'S
ACCEPTANCE OF THE AGREEMENT.
The license text can also be found at
http://opensource.org/licenses/cpl.php
INTRODUCTION
============================================================
This history is from the perspective of a Plexus user, as opposed to
someone who is working on the package itself. For those who want the
details, check the CVS history.
I am using a typical hierarchical release numbering system. Until
version 1.0, any change in the second number (0.1 -> 0.2, e.g)
signifies that the release is definitely not backward compatible. A
change in the third number means that code which simply uses classes
from the library does not need to change, but classes, interfaces, or
methods may have been added. So any new implementations or extensions
may have to change.
Releases are tagged "ver-x-y" for version x.y. If I have to branch
again, I'll develop a tag naming scheme for that.
============================================================
v0.1
Initial version.
============================================================
v0.2
OVERVIEW:
- There is now an Edge inner interface of Graph, causing many changes.
One intended side effect is that Edges may now point to other Edges.
- Removed the NodeIterator interface.
- Added an observable Graph facility.
- Major overhaul to GraphWrapper and its subclasses.
- Changes to DefaultGraph:
- Implements ObservableGraph.
- Moved AdjacencyList into DefaultGraph as a private inner class.
- Traverser.remove() now works.
- Traversers and edge iterators can usually tolerate changes to the
underlying graph without throwing concurrent mod exceptions.
- Changed the format of the text returned by toString().
- Bug fixes in AbstractGraph:
- Self-edges for an undirected graph are now correctly counted twice
by degree( node ).
- Fixed a bug in the directed traverser() implementation where
actions in one of a pair of sub-Traversers could invalidate the
other.
- Other miscellaneous changes:
- Graph.removeNode() now either returns true or false.
- Removed Graph.add( Graph ).
Added GraphUtils.add( Graph destination, Graph source ).
- Removed GraphUtils.unmodifiableTraverser().
- CompleteGraph, Path, Cycle, and CompleteTree now return Edges with
consistent tails and heads.
DETAILS:
----------------------------------------
There is now an Edge inner interface of Graph. All Graph
implementations in the Plexus library now provide their own Edge
implementations of this interface. This is to correctly implement
Edge.equals(); see below for further info on this. The following
changes have resulted:
- New Graph.Edge interface with the following methods:
boolean isDirected();
Object getUserObject();
void setUserObject( Object object );
Object getTail();
Object getHead();
Object getOtherEndpoint( Object node );
- Graph interface (and all implementations)
- addEdge( object, tail, head ) now returns the newly created Edge
object, or null if it didn't add it.
- removed:
boolean removeEdge( object )
boolean removeEdge( tail, head )
boolean removeEdge( object, tail, head )
boolean containsEdge( object )
boolean containsEdge( tail, head )
boolean containsEdge( object, tail, head )
- added:
boolean removeEdge( Edge )
boolean containsEdge( Edge )
- getEdge( tail, head ) now returns an Edge instead of the contained
user object. This method now also works for multi-graphs,
returning the first edge found.
- edgeIterator() now returns an Iterator (returned objects implement
Edge).
- edgeIterator( tail, head ) now returns an Iterator (returned
objects implement Edge).
- Changed some formal parameter names from 'edge' to 'object' to be
less confusing. Variables named 'edge' should normally implement
the Edge interface.
- EdgeIterator
Removed.
- Traverser
- getEdge() now returns an Edge.
- Removed setEdge().
- class com.phoenixst.plexus.Edge
Removed.
- ObjectEdge
Removed.
- Added DefaultEdge, DefaultObjectEdge, and DefaultSimpleEdge.
- GraphUtils
- Removed EMPTY_EDGE_ITERATOR.
- Removed unmodifiableEdgeIterator().
- singletonEdgeIterator() now takes a Graph and an Edge argument
instead of a user-object, tail, and head. In addition, it is
modifiable.
- singletonTraverser() now takes a Graph, Edge, and node arguments
instead of a user-object, tail, and head. In addition, it is
modifiable.
- Weight
- get/setWeight() now take an Edge argument instead of a
user-object, tail, and head.
- AbstractGraph
- removeEdge( Edge ) throws an UnsupportedOperationException if the
graph is simple. This is to avoid mutual recursion with
edgeIterator( tail, head ).remove().
For the moment, Edge.isDirected() reflects whether or not the Graph
containing the edge is directed, but at some point in the future a
Graph will be allowed to have both directed and undirected edges.
Users of this library should use Edge.isDirected() if possible.
As for Edge.equals() (and hashCode), it is vitally important that two
Edges only be .equals() when they refer to the same actual edge in the
same graph. Which edge this is does *not* change when the contained
user-defined object changes (and, hence, the contained user-defined
object should not be used in computing the Edge's hash code). In a
multigraph, the endpoints and contained user-defined object are
generally not sufficiently distinguishing characteristics. Accepting
the default implementation from Object, which uses reference equality,
should be preferred unless Edges are lazily created on demand.
----------------------------------------
Removed the NodeIterator interface.
- Graph.nodeIterator() now returns a simple Iterator.
- Traverser now extends Iterator directly.
- Removed GraphUtils.EMPTY_NODE_ITERATOR.
- Removed GraphUtils.singletonNodeIterator().
- Removed GraphUtils.unmodifiableNodeIterator().
----------------------------------------
Added an observable Graph facility. Added ObservableGraph,
GraphEvent, GraphListener and ObservableGraphWrapper. Added
unmodifiable and synchronized views for an ObservableGraph to
GraphUtils.
----------------------------------------
Nothing in the Graph interface prohibits Edges from pointing to other
Edges. In other words, Edges can be used as nodes, and the
DefaultGraph implementation allows this. These two aspects of any
particular Edge are independent. Adding or removing an Edge as a node
has no impact upon the object's existence as an Edge, and vice versa.
Care should be taken when copying a Graph with Edges acting in this
way, as there are now dependencies on the order in which things are
done. A node which happens to be an Edge must be created as an Edge
before being added to the Graph as a node. The new GraphUtils.add(
Graph destination, Graph source ) method handles this correctly.
----------------------------------------
Moved AdjacencyList into DefaultGraph, as they are now way too tightly
coupled to be separate. Much of AdjacencyList and the DefaultGraph
internals have changed as a result. As a user of DefaultGraph, this
particular change has little effect, except that Traverser.remove()
now works.
As a side-effect, traversers and edge iterators are much more robust.
They can usually handle changes to the underlying graph without
throwing concurrent mod exceptions. See the javadocs for particulars.
----------------------------------------
Major overhaul to GraphWrapper and its subclasses. This update has
affected GraphWrapper, GraphTransformer, ObservableGraphWrapper, and
all the wrappers in GraphUtils.
Rewrote GraphWrapper to factor in a bunch of stuff previously
delegated to subclasses. It now has protected methods that wrap and
unwrap nodes, user-defined edge objects, Edges, and the various
iterators from the underlying wrapped graph. This localizes any
transformations that the wrapper might be performing into a few
methods rather than having them peppered throughout the code.
Nodes and user-defined edge objects are passed through unchanged by
default. Edges, however, are always wrapped and know from which
GraphWrapper they were produced. This is to make sure that an Edge
produced by one wrapper cannot be used by another, even if that
wrapper is of the same class. Two Edges produced by different Graph
instances should never be .equals().
SynchronizedGraphWrapper now syncs on its iterator methods as well,
just in case they perform some non-trivial processing.
Added an InvertableTransformer interface and GraphTransformer now uses
two of these instead of four normal Transformers.
============================================================
v0.2.1
OVERVIEW:
This release adds a general capability for performing filtered edge
iteration and traversals. Methods on Graph that are superceded by the
new functionality have been deprecated, and will be removed in version
0.3.
DETAILS:
----------------------------------------
Added interface specifications for the new filters. To be consistent
with the required new interface for TraverserFilter, a new interface
was defined for EdgeFilter as well instead of reusing Predicate.
EdgeFilter
public boolean evaluate( Graph.Edge edge );
TraverserFilter
public boolean evaluate( Object baseNode, Graph.Edge edge );
The new methods on Graph are:
Edge getEdge( EdgeFilter edgeFilter )
Iterator edgeIterator( EdgeFilter edgeFilter )
Object getAdjacentNode( Object node, TraverserFilter traverserFilter )
Traverser traverser( Object node, TraverserFilter traverserFilter )
These Graph methods are now deprecated:
Edge getEdge( Object tail, Object head )
Iterator edgeIterator( Object tail, Object head )
Traverser outTraverser( Object node )
Traverser inTraverser( Object node )
----------------------------------------
Removed TraverserFactory and the constant instances of it from
GraphUtils. A TraverserFilter can now be used to accomplish the same
thing.
----------------------------------------
Added the following to GraphUtils:
direction bit mask constants
a direction bit mask inversion method
constant true and false Predicates
some simple constant EdgeFilters
some simple constant TraverserFilters
----------------------------------------
Added the following predicate and filter implementations:
EqualsPredicate - a trivially simple Predicate
EqualsEdgeFilter - a trivially simple EdgeFilter
EqualsTraverserFilter - a trivially simple TraverserFilter
DefaultEdgeFilter - a default EdgeFilter, see the javadocs
DefaultTraverserFilter - a default TraverserFilter, see the javadocs
----------------------------------------
Added the following default filtering iterator implementations:
FilteredEdgeIterator
FilteredTraverser
----------------------------------------
Rewrote a lot of AbstractGraph, completely changing the method
interdependencies that existed before. See the javadocs for details.
============================================================
v0.3
Removed the following deprected methods from Graph and
implementations:
Edge getEdge( Object tail, Object head )
Iterator edgeIterator( Object tail, Object head )
Traverser outTraverser( Object node )
Traverser inTraverser( Object node )
Added the following method to Graph and all implementations:
getIncidentEdge( Object node, TraverserFilter traverserFilter )
Added a new com.phoenixst.plexus.util subpackage.
Moved the following classes (some of them private inner classes of
GraphUtils) to the new util subpackage:
FilteredEdgeIterator
FilteredTraverser
EqualsEdgeFilter
EqualsTraverserFilter
SingletonEdgeIterator
SingletonTraverser
SynchronizedGraphWrapper
SynchronizedObservableGraphWrapper
UnmodifiableGraphWrapper
UnmodifiableObservableGraphWrapper
Added TraverserEdgeIteratorAdapter to the util subpackage, which wraps
a Traverser to look like an edge Iterator.
Changed the parameter order for GraphUtils.singletonTraverser().
Added the following filter helper methods to GraphUtils:
public static Graph.Edge getEdge( graph, edgeFilter )
public static Iterator edgeIterator( graph, edgeFilter )
public static Graph.Edge getIncidentEdge( graph, node, traverserFilter )
public static Traverser traverser( graph, node, traverserFilter )
Updated AbstractGraph and GraphWrapper to use the new GraphUtils
filter helper methods.
Removed explicit mutex parameter versions for synchronized Graph
methods in GraphUtils. They're still available as alternate
constructors for the newly separated classes.
============================================================
v0.4
----------------------------------------
Graphs are no longer explicitly directed/undirected or simple/multi.
Of course, any particular Graph implementation may choose to only have
directed edges, or it may disallow duplicate edges and self-loops, but
the Graph interface no longer enforces any such distinction. As a
result of this, the following changes have been made:
Removed the following methods from Graph and all of its
implementations:
boolean isSimple()
boolean isDirected()
Changed the signature of Graph.addEdge() and all of its
implementations to:
Edge addEdge( Object object,
Object tail, Object head,
boolean isDirected );
Since Graphs are no longer distinguished as directed or not,
Graph.outDegree() and Graph.inDegree() will no longer throw an
UnsupportedOperationException.
----------------------------------------
Added a capability to filter entire Graphs. These are the new
interfaces and classes:
- GraphFilter: interface similar to EdgeFilter and TraverserFilter
- DefaultGraphFilter: default implementation of GraphFilter
- FilteredGraph: constructed with a Graph and a GraphFilter, presents
just the subgraph that passes the filter
- util.FilteredNodeIterator: helper class
----------------------------------------
All example graphs except PetersenGraph now have directed edges.
PetersenGraph now extends IntegerNodeGraph and is lazy.
Join and Product now allow operands with any mixture of
directed/undirected edges. Added a boolean isDirected parameter to
the Join constructor which sets the directedness of the created edges
between the two Join operands.
Added com.phoenixst.plexus.util.SingletonGraph class and a
GraphUtils.singletonGraph(node) method to create them.
Product Edge implementations now create their endpoints on demand.
Added some more efficiency FIXME's to Product.
Modified GraphUtils.add() to be more correct in behavior. It will now
tolerate the destination graph not allowing particular nodes from the
source graph to be added.
Fixed some methods of returned Iterators not being synchronized in
SynchronizedGraphWrapper.
Updated overview and package docs.
============================================================
v0.5
Added Graph.degree( node, TraverserFilter ).
Removed Graph.out/inDegree( node ).
Removed Traverser.getOtherEndpoint().
Moved various copies of equals(a,b) methods into a single public
GraphUtils method.
----------------------------------------
Added the following interfaces:
GraphView
RootedGraphView
OrientedForestView
RootedTreeView
Added the following classes:
AbstractOrientedForestView
DefaultOrientedForestView
DefaultRootedTreeView
----------------------------------------
Made FilteredGraph observable.
GraphWrapper now implements ObservableGraph. The add/remove listener
operations will throw exceptions if the wrapped graph is not
observable. ObservableGraphWrapper no longer extends GraphWrapper.
Removed:
UnmodifiableObservableGraphWrapper
SynchronizedObservableGraphWrapper
GraphUtils.unmodifiableObservableGraph()
GraphUtils.synchronizedObservableGraph()
Added ObservableGraphDelegate, a helper class for ObservableGraph
implementations. Updated DefaultGraph, GraphWrapper, and
ObservableGraphWrapper to use ObservableGraphDelegate.
----------------------------------------
Added the following util classes:
IteratorChain
TraverserChain
UnmodifiableIterator
UnmodifiableTraverser
The IteratorChain in Jakarta commons-collections fails if a
sub-iterator is empty. Mine is also a little different. If/when
Jakarta fixes theirs, I'll update TraverserChain to mirror its
functionality.
Updated Join to use the new chain iterators.
Removed the Graph implementation NodeOffsetTransformer. Added the
InvertibleTransformer implementation IntegerOffsetTransformer.
Modified Star, Wheel, and CompleteBipartiteGraph to take this into
account.
----------------------------------------
Moved this change log from README to new file CHANGELOG. Added README
to distribution jar.
Added more jars to distribution build:
plexus-core.jar - base package and util subpackage
plexus-operations.jar - operations subpackage
plexus-examples.jar - examples subpackage
The orignal plexus.jar is still all the class files.
Removed build.properties and added build.properties.sample. By
default, compiler debug is now off.
Fix for random NPE on dual-processor machines.
Made a number of optimizations to DefaultGraph and FilteredGraph.
============================================================
v0.6
Added the following to the core plexus package:
PruningTraverser
Walker
BreadthFirstTraverser
PreOrderTraverser
PostOrderTraverser
DepthFirstTraverser
ForestTreeAdapter
Removed Graph.isEmpty().
DefaultGraphFilter and FilteredGraph now check their constructor
arguments for being non-null.
Made internal filters used by FilteredGraph serializable.
AbstractOrientedForestView.getHeight() is no longer recursive, at the
expense of using more heap for a DepthFirstTraverser.
Changed the documented exceptional conditions for Traverser.getEdge()
and removeEdge(). Previously, these methods were specified to throw a
NoSuchElementException if no Edge was traversed to reach the last node
returned by next(). Now, getEdge() is specified to return null and
removeEdge() should throw an IllegalStateException.
----------------------------------------
Changed some of the semantics of RootedTreeView. It is now an
OrientedForestView which is restricted to the descendants of a single
root node. It is no longer necessary that all nodes of the underlying
graph be part of the tree. Many RootedTreeView methods may
*optionally* throw a NoSuchNodeException if given a node not in the
tree, as documented in the javadocs.
Added a new method RootedTreeView.isTreeNode( node ) to help support
the new RootedTreeView semantics.
Changed the following methods of DefaultRootedTreeView to throw an
exception if given a node not in the tree. The other methods do not
perform this check.
getRoot( node )
getLeastCommonAncestor( aNode, bNode )
getDepth( node )
----------------------------------------
Moved the following to the util subpackage:
DefaultEdge
DefaultObjectEdge
DefaultSimpleEdge
Added the following to the util subpackage:
EdgeIteratorTraverserAdapter
TraverserNodeIteratorAdapter
DefaultTraverserFactory
ChildTraverserFactory
DefaultIncidentEdgeGetter
ParentEdgeGetter
Allow SingletonTraverser to use a null Edge.
----------------------------------------
Added new com.phoenixst.plexus.algorithms subpackage.
Added the following to the algorithms subpackage:
AbstractDepthFirstForestView (package-private)
DepthFirstTreeView
DepthFirstForestView
----------------------------------------
Added new com.phoenixst.collections package. This package contains
additions and/or fixes to the Jakarta-Commons Collections package.
Much of the functionality here has been made obsolete by the release
of version 3.0 of that package, but I can't upgrade the Plexus Graph
Library until other unrelated products have also been upgraded (Plexus
is currently in production use and must integrate well with JBoss,
struts, etc.).
Moved the following to the collections package:
plexus.InvertibleTransformer
plexus.EqualsPredicate (renamed to EqualPredicate)
plexus.util.IteratorChain
plexus.util.UnmodifiableIterator
Added the following to the collections package:
AllPredicate
AndPredicate
AnyPredicate
IdentityPredicate
InstanceofPredicate
NotPredicate
OrPredicate
PredicateUtils
SimpleStack
Removed GraphUtils.TRUE and GraphUtils.FALSE.
----------------------------------------
Added the following to the examples subpackage:
FileSystemForest
CirculantGraph
LoopGraph
RandomGraphFactory
Cycle now inherits from LoopGraph.
----------------------------------------
Serialization updates across the whole library.
- Defined serialVersionUID for all serializable classes.
- The following are not serializable:
Iterators
Inner classes
- The following are serializable:
All concrete Graph implementations
All Edge implementations
All concrete GraphView implementations
All EdgeFilter implementations
All TraverserFilter implementations
All GraphFilter implementations
All GraphUtils filter constants
GraphEvent
NoSuchNodeException
EqualsPredicate
IntegerOffsetTransformer
Updated some .equals() methods.
Added javadoc.linksource property to build.xml. Have to remember to
set that property to "no" when building online docs.
============================================================
v0.6.1
This is the first step in an update to convert all uses of EdgeFilter
and TraverserFilter to use standard Predicates instead. Basically,
this step adds the requisite methods and functionality to all
implementations, but not to the Graph interface itself. This is so
that everything depending on Plexus will still build. After dependent
projects have been updated, the next step will be to add the methods
to the Graph interface and deprecate the old filter usage. Then,
finally, the filters will be removed.
Added accessor methods to compound Predicates in the collections
subpackage.
Adding legacy bridge classes to be used for imminent migration:
EdgeFilterPredicateAdapter
TraverserFilterPredicateAdapter
PredicateEdgeFilterAdapter
PredicateTraverserFilterAdapter
Added
DefaultEdgePredicate
DefaultTraverserPredicate
EqualsTraverserPredicate
Converted EdgeFilter use in DefaultGraphFilter to a Predicate.
Added predicate equivalents to all filter fields and methods in
GraphUtils.
Made the following classes use Predicates, and made
Edge/TraverserFilter constructors delegate to the new Predicate
constructors.
plexus
BreadthFirstTraverser
DepthFirstTraverser
PostOrderTraverser
PreOrderTraverser
Walker
plexus.util
DefaultIncidentEdgeGetter
DefaultTraverserFactory
FilteredEdgeIterator
FilteredTraverser
plexus.algorithms
AbstractDepthFirstForestView
DepthFirstForestView
DepthFirstTreeView
Added these methods:
Graph.Edge getEdge( Predicate edgePredicate )
Iterator edgeIterator( Predicate edgePredicate )
int degree( Object node, Predicate traverserPredicate )
Object getAdjacentNode( Object node, Predicate traverserPredicate )
Graph.Edge getIncidentEdge( Object node, Predicate traverserPredicate )
Traverser traverser( Object node, Predicate traverserPredicate )
To these graph implementations:
plexus
DefaultGraph
AbstractGraph
GraphWrapper
ObservableGraphWrapper
FilteredGraph
plexus.examples
EmptyGraph
plexus.util
SingletonGraph
SynchronizedGraphWrapper
Moved inner Product.OrderedPair class to a new top-level class in the
collections subpackage, and made it mutable.
Updated GraphTest.OrderdPair to extend the new public class.
Minor rewrite of EqualPredicate equals test, for possible efficiency
gain.
Javadoc and formatting updates, import cleanup, etc.
============================================================
v0.6.2
Added the following methods to the Graph interface:
Graph.Edge getEdge( Predicate edgePredicate )
Iterator edgeIterator( Predicate edgePredicate )
int degree( Object node, Predicate traverserPredicate )
Object getAdjacentNode( Object node, Predicate traverserPredicate )
Graph.Edge getIncidentEdge( Object node, Predicate traverserPredicate )
Traverser traverser( Object node, Predicate traverserPredicate )
Deprecated EdgeFilter and TraverserFilter.
Completely rewrote DefaultGraph to be optimized for Predicates instead
of Filters.
Removed EqualsEdgeFilter and EqualsTraverserFilter.
GraphUtils - Removed the following:
Edge/TraverserFilter constants and inner classes.
getEdge( Graph, EdgeFilter )
edgeIterator( Graph, EdgeFilter )
getIncidentEdge( Graph, node, TraverserFilter )
traverser( Graph, node, TraverserFilter )
Rewrote the filter methods in AbstractGraph and GraphWrapper to
delegate using a filter-predicate adapter since the GraphUtils methods
they used to call have been removed.
Removed the filter-using constructors in the following classes:
BreadthFirstTraverser
DepthFirstTraverser
PostOrderTraverser
PreOrderTraverser
Walker
util.DefaultIncidentEdgeGetter
util.DefaultTraverserFactory
util.FilteredEdgeIterator
util.FilteredTraverser
algorithms.DepthFirstForestView
algorithms.DepthFirstTreeView
Migrated the following to use Predicates. Fully implemented the
Predicate or Predicate-using methods.
FilteredGraph
ObservableGraphWrapper
util.DefaultIncidentEdgeGetter
util.DefaultTraverserFactory
examples.RandomGraphFactory
Rewrote DefaultOrientedForestView to use Predicates. Added Predicate
constructors to DefaultRootedTreeView and made filter constructors
delegate to them.
Removed filter methods completely from examples.EmptyGraph, they are
now inherited from AbstractGraph.
============================================================
v0.7
Removed EdgeFilter, TraverserFilter, all implementations of them, and
all other references to them.
============================================================
v0.7.1
Deprecated the following methods on Graph (to be removed in 0.8):
int nodeSize()
int edgeSize()
void clear()
Iterator nodeIterator()
Iterator edgeIterator()
Iterator edgeIterator( Predicate )
Traverser traverser( node )
Added the following methods to the Graph interface:
Collection nodes( Predicate nodePredicate )
Collection edges( Predicate edgePredicate )
Collection adjacentNodes( Object node, Predicate traverserPredicate )
Collection incidentEdges( Object node, Predicate traverserPredicate )
Object getNode( Predicate nodePredicate )
The Collection-returning methods return views. That is, they reflect
the current state of the underlying Graph and are write-through.
Although none of the Collection views implemented in Plexus support
add(), they do support removal. Note that removing a node from an
adjacentNodes() view will remove one instance of the node from being
adjacent, it will not remove the node from the graph. In other words,
it will remove one connecting edge.
Just about every Graph implementation has changed as a result. Added
a bunch of support classes to help with this (all com.phoenixst...)
collections.AbstractSingletonCollection
collections.AbstractUnmodifiableCollection
collections.CollectionWrapper
collections.CompositeCollection
collections.FilteredCollection
collections.FilteredIterator
plexus.util.AbstractEdgeCollection
plexus.util.AbstractNodeCollection
plexus.util.AdjacentNodeCollection
plexus.util.IncidentEdgeCollection
plexus.util.SingletonEdgeCollection
plexus.util.SingletonNodeCollection
plexus.util.TraverserAdjacentNodeIteratorAdapter
----------------------------------------
The new FilteredIterator is a much more robust version than previous
attempts. It now implements remove() by calling remove() on the
wrapped iterator if it hasn't advanced the underlying iterator. If
the underlying iterator has been advanced, then it delegates to a
protected remove( Object ) method which throws an exception by
default. FilteredEdgeIterator and FilteredNodeIterator now extend
this class, and FilteredTraverser is modeled after it.
Extensions behave as follows for these cases:
- FilteredCollection.iterator().remove() delegates to
Collection.remove( Object ).
- FilteredNodeIterator delegates to Graph.removeNode( Object ).
- FilteredEdgeIterator delegates to Graph.removeEdge( Object ).
----------------------------------------
Removed the GraphFilter interface and the DefaultGraphFilter
implementation. FilteredGraph now takes a node and edge Predicate
instead. Also, FilteredGraph internally handles the logic to test
that the endpoints of an edge pass the node filter before testing the
edge filter, so it is no longer the user's responsibility to deal with
this. The wrapped graph may be given an AndPredicate for an edge
filter, depending upon the constructor arguments.
----------------------------------------
Added the following methods to ObservableGraphDelegate:
- GraphListener[] getGraphListeners()
- void removeAllGraphListeners()
----------------------------------------
Completely rewrote GraphWrapper and its subclasses
(SynchronizedGraphWrapper, UnmodifiableGraphWrapper, and
GraphTransformer). The protected methods which can be overridden are
now:
Object wrapNode( Object node )
Object unwrapNode( Object node )
Object wrapEdgeObject( Object edgeObject )
Object unwrapEdgeObject( Object edgeObject )
EdgeWrapper createEdge( Graph.Edge edge )
Traverser wrapTraverser( Traverser traverser )
Predicate wrapNodePredicate( Predicate nodePredicate )
Predicate wrapEdgePredicate( Predicate edgePredicate )
Predicate wrapTraverserPredicate( Predicate traverserPredicate )
Subclasses now should not handle the possibility that a node might be
also be an edge within the wrap/unwrapNode() methods. This case is
dealt with before those methods see the object.
The Predicate wrapper methods already do a great deal of translation
on the argument, if it is a standard Predicate instance (a GraphUtils
constant Predicate, a DefaultEdgePredicate, etc.). These should only
be overridden to handle application specific cases, and then they
should delegate to the implementation defined in GraphWrapper if it is
not such a case.
----------------------------------------
Removed the following methods from GraphUtils:
Iterator edgeIterator( graph, edgePredicate )
Graph.Edge getEdge( graph, edgePredicate )
Graph.Edge getIncidentEdge( graph, node, traverserPredicate )
Traverser traverser( graph, node, traverserPredicate )
----------------------------------------
Factored out the reaping functionality used by DefaultGraph into a
more general implementation in the com.phoenixst.collections package
(Reapable, Reaper, and ReapableCollection).
============================================================
v0.8
Removed the following deprecated methods from Graph and all of its
implementations:
int nodeSize()
int edgeSize()
void clear()
Iterator nodeIterator()
Iterator edgeIterator()
Iterator edgeIterator( Predicate )
Traverser traverser( node )
Renamed AbstractGraph.toBeRenamed(node) to traverser(node).
Added SynchronizedCollection to the collections subpackage. This
differs from the one provided by java.util.Collections in that the
mutex can be specified in the constructor. Rewrote SynchronizedGraph
to use this new Collection wrapper.
============================================================
v0.9
Removed DefaultEdgePredicate and DefaultTraverserPredicate. Added new
interfaces EdgePredicate and TraverserPredicate. Added new factory
classes EdgePredicateFactory and TraverserPredicateFactory. See the
javadocs for details.
----------------------------------------
Plexus now uses Log4J. See the README for details.
A default log4j.properties file is packaged in plexus.jar and
plexus-core.jar, so that using Plexus does not *require* manual
configuration from the user. The bundled log4j.properties file
defines a standard ConsoleAppender and sets the Level of the
"com.phoenixst" Logger to WARN. If you have your own log4j
configuration which defines an appender at or above "com.phoenixst",
then it will also handle logs from Plexus. In particular, if you
define a ConsoleAppender for the root Logger, then all logs from
Plexus will go to the console twice, which is probably not what you
want.
----------------------------------------
Added LoggingSupport, LoggingCollection, and LoggingIterator to the
collections subpackage. Added LoggingGraph and LoggingTraverser to
the main package and the util subpackage, respectively.
LoggingSupport is a simple base class with some useful methods that is
extended by the other Logging classes.
These Logging classes are all wrappers which log the invocation of
every method of the implemented interface, both arguments and return
values. LoggingCollection and LoggingGraph also log invocations of
equals(), hashCode(), and toString(). Thrown Exceptions are neither
caught nor logged. Alternate constructors allow the user to specify
both the Logger to use and the Level at which to log.
----------------------------------------
ObservableGraphDelegate now logs each invocation of fireXXX() to a
Logger and Level optionally specified by the constructor. Any
exceptions thrown by listeners are logged to the ERROR Level. If the
Logger and Level are not specified, they default to
"com.phoenixst.plexus.util.ObservableGraphDelegate" and DEBUG.
Graph implementations which use an ObservableGraphDelegate now supply
their own logger. These include DefaultGraph, FilteredGraph,
GraphWrapper, and ObservableGraphWrapper. The event Logger for
DefaultGraph is "com.phoenixst.plexus.DefaultGraph.Event", just in
case the user wants to log those events at a different level than
DefaultGraph's normal logging output (of which there isn't any at the
moment).
----------------------------------------
Added some debug logging to the following classes:
DefaultGraph
BreadthFirstTraverser
DepthFirstTraverser
PreOrderTraverser
PostOrderTraverser
DepthFirstForestView
DepthFirstTreeView
Added some debug logging to:
GraphUtils.add( Graph destination, Graph source )
Added these protected constructors to DefaultGraph which allow
subclasses to specify a different logger to use.
protected DefaultGraph( Logger logger, Logger eventLogger )
protected DefaultGraph( Graph g, Logger logger, Logger eventLogger )
----------------------------------------
Fixed bugs in ObservableGraphWrapper:
nodes( Predicate ).containsAll( Collection )
edges( Predicate ).containsAll( Collection )
----------------------------------------
Changed when the protected event delivery extension points are called
in DefaultGraph. They are now called after all events have been
delivered. Added new extension points which are called before any
events have been delivered. As an example, the sequence for removing
a node is now:
nodeRemoving( node )
remove incident edges (which causes its own events/notifications)
actually remove the node from internal structures
fire nodeRemoved events
nodeRemoved( node )
The pre-event methods are called before any action is taken, but after
it has been verified that the action is possible. For example,
nodeRemoving() won't be called on a node that is not present in the
graph, and will be called before removing any incident edges.
----------------------------------------
Added protected DefaultGraph.createEdge(...) method, which allows
subclasses to override the kind of Graph.Edge created when an edge is
added to the graph. This method should simply create the requested
edge, without checking to see whether it already exists. DefaultGraph
will not allow two edges which are .equals() in the same adjacency
list. The addEdge() method has been updated to return null if the new
edge already exists in either endpoint's adjacency list.
----------------------------------------
These Predicate implementations now implement .equals() (and
hashCode()) semantically:
- all implementations in the collections subpackage
- All Predicates produced by EdgePredicateFactory and
TraverserPredicateFactory
- Internal implementations in FilteredGraph, which it may pass to the
wrapped graph
- EqualsTraverserPredicate
----------------------------------------
Refactored Product to be more efficient in its implementation of
Iterators and Traversers.
============================================================
v0.10
Added a new traversals subpackage and moved the following classes and
interfaces there:
BreadthFirstTraverser
DepthFirstTraverser
PostOrderTraverser
PreOrderTraverser
PruningTraverser
Walker
Added TopologicalSortTraverser and GraphStructureIterator to the
traversals subpackage. Rewrote GraphUtils.add() to use the new
GraphStructureIterator.
----------------------------------------
Separated the forest/tree interaces from GraphView. This will allow
both forest/tree implementations that are views (as before) and those
that simply are graphs, or even implementations that are neither.
Added new interfaces:
Rooted
OrientedForest
RootedTree
Removed interfaces:
RootedGraphView
OrientedForestView
RootedTreeView
Added DefaultOrientedForest, which is an extension of DefaultGraph
that also implements the OrientedForest interface. It provides an
implementation where the parent/child relationships are "hard-wired"
in the internal representation. Once an edge is created, it is always
either a forest edge or not. This fills the use case where whether or
not an edge is forest has nothing to do with its endpoints, direction,
or contained user-defined object. It is also more efficient to
traverse than predicate-based views. Note that there is nothing
preventing a forest GraphView from wrapping a DefaultOrientedForest
and presenting a different forest structure; it is fundamentally still
a Graph after all.
Added a rootNodes() method to the OrientedForest interface. Changed
the name of DepthFirstForestView.getRoots() to the new method. The
implementations of rootNodes() for DefaultOrientedForest and
DefaultOrientedForestView are lazy.
Renamed AbstractOrientedForestView to AbstractOrientedForest.
ForestTreeAdapter now takes an OrientedForest and implements
RootedTree.
FileSystemForest now implements Graph directly instead of GraphView.
Added the following helper methods to GraphUtils:
Object getLeastCommonAncestor( OrientedForest forest,
Object a, Object b )
Object getFirstCommonNode( Transformer incidentEdgeGetter,
Object a, Object b )
----------------------------------------
Updated the following classes to use OrientedForest instead of
OrientedForestView:
BreadthFirstTraverser
DepthFirstTraverser
PostOrderTraverser
PreOrderTraverser
Walker
ChildTraverserFactory
ParentEdgeGetter
Each of the above Traverser implementations (Breadth, Depth, PreOrder,
PostOrder, & Walker) now exposes a previously private constructor of
the following form (the Transformer for Walker should return an
incident edge rather than a Traverser):
public BreadthFirstTraverser( Object startNode,
Graph graph,
Transformer traverserFactory )
The Traverser constructors which use an OrientedForest (like this
one):
public BreadthFirstTraverser( Object startNode,
OrientedForest forest )
Now have the behavioral restriction that startNode cannot be removed
by the remove() method (this form of the Walker constructor is
completely unmodifiable). If it is necessary to allow the removal of
the startNode, then the newly exposed constructor above must be used.
----------------------------------------
Changed how the protected DefaultGraph.createEdge() method works by
adding an extra argument that can be supplied by subclasses. Added a
protected addEdge() method which takes that extra argument and passes
it on to createEdge(). This was to solve an operation ordering issue
with DefaultOrientedForest, so that created edges are fully formed
when event delivery to listeners takes place.
----------------------------------------
Added Identifier to the collections subpackage.
----------------------------------------
Made PetersenGraph a singleton.
============================================================
v0.11
Added TrivialOrientedForestView, ForestTreeExtension.
Added OrderedPair.get/setFirst/Second() convenience methods. Added a
no-arg OrderedPair constructor, which inits the elements to null.
Changed all usages for Predicates used in a Traverser context (the
ones whose evaluate() methods are expecting List arguments) to use
OrderedPair objects exclusively.
Rewrote Product to only use OrderedPairs for nodes.
Made Identifier serializable.
Changed some usages like this:
graph.degree( node, predicate ) == 0;
to this:
graph.getIncidentEdge( node, predicate ) == null;
The extra overhead should be minimal in those cases where it is worse,
but in many instances it will perform much better.
Added GraphUtils.directionFlagsToString( int flags ) method.
Implemented toString() for default EdgePredicate and
TraverserPredicate implementations.
Added classpath attribute to test.compile target.
Minor javadoc fixes.
============================================================
v0.12
Updated to use JDK 1.5, which is now required.
Added version numbers to the jar filenames.
----------------------------------------
Added the following to the collections package:
UnorderedPair
ContainsPredicate
ClosureChain
TransformerChain
Added the following to the util subpackage:
ForwardingGraphListener
FilteredGraphListener
TransformingGraphListener
Renamed IntegerNodeGraph to AbstractIntegerNodeGraph.
Added CharSequence GraphUtils.getTextValue( edge, includeUserObject? ),
a convenience method for use by Graph.Edge.toString() implementations.
Many classes have changed serialization UID's, including
DefaultOrientedForest, but not DefaultGraph.
----------------------------------------
Changed from throwing an NPE for null arguments to throwing an
IllegalArgumentException.
Fixed a minor synchronization bug in ObservableGraphDelegate.
Removed synchronization from DefaultGraph.add/removeGraphListener().
Changed ForestTreeExtension.isTreeNode() to return false only if a
NoSuchNodeException is thrown by the delegate forest, not if any
Exception is thrown.
The CompositeCollection, IteratorChain, and TraverserChain constructors
now copy their array-valued arguments.
----------------------------------------
Added constructors to all classes that didn't have one, removing any
reliance on the default no-arg constructor (except for anonymous
classes).
Avoid calling overridable methods in constructors.
Made inner classes as private as possible, and static when not too
onerous.
Made fields, methods, and constructors as private as possible, and
final when possible. In some cases, protected get() accessors were
added for subclass use.
Moved some initialization from constructors to declarations.
Rename some identifiers to be more descriptive.
Used StringBuilder instead of StringBuffer or the concat operator.
Better exception messages.
----------------------------------------
Renamed CloneableTestCase to AbstractCloneableTestCase.
Renamed GraphTest to AbstractGraphTest.
============================================================
v0.12.1
Fixed a bug in a few OrientedForest.getHeight() implementations where
the result would be one greater than it should have been.
Added GraphUtils.NULL_GRAPH, an immutable, constant ObservableGraph
instance with no nodes or edges.
Moved the definition of GraphUtils.EMPTY_TRAVERSER into a private inner
class and made it Serializable.
The internal Predicate implementations in DefaultOrientedForest now
implement Serializable.
============================================================
v0.13
Plexus has been updated to use Jakarta-Commons Collections version
2.1.1, and the resulting deprecation warnings have been removed. This
version will not work with version 2.1, clients *must* upgrade. It
should now be safe to use 3.1, although I haven't tried it. There
will be some naming conflicts with classes from that version and the
collections sub-package here.
----------------------------------------
A fundamental change has been made to an assumption concerning Edge
identity in Plexus, that a given Edge could only be in one Graph.
Previously, it had been considered best practice that different Graphs
should not produce Graph.Edge instances which could be .equals() to
one another. This behavioral restriction is no longer assumed or even
encouraged.
There are two reasons for doing this. One is that the overhead
involved with creating the wrapper edges can be significant,
especially if they are serializable, since they must keep track of the
Graph which created them. The other is that it is extremely
inconvenient for Graphs which are views of other Graphs (unmod, sync,
filtered, forest->tree, etc.) to not be consistent with each other.
An adverse side-effect is that a Graph which delegates to more than
one other Graph will not necessarily be able to tell from which of its
delegates a particular Edge comes.
----------------------------------------
ObservableGraphDelegate now uses a CopyOnWriteArrayList internally to
maintain its list of listeners. Adding or removing a listener will be
slower, but event firing will be faster since it no longer requires
synchronization. The fireXxx methods will no longer perform any
logging if there are no registered listeners; there is now an early
return for that case.
ForwardingGraphListener, FilteredGraphListener, and
TransformingGraphListener now maintain a WeakReference to their
wrapped ObservableGraphDelegate. If these listeners ever receive an
event and the Reference has been cleared, they will remove themselves
as listeners from the Graph which was the source of the event.
Rewrote the listener handling in DefaultGraph, SynchronizedGraph,
UnmodifiableGraph, FilteredGraph, LoggingGraph, GraphWrapper, and
ObservableGraphWrapper. They no longer create and dispose of the
internal ObservableGraphDelegate and/or forwarding listeners when the
set of listeners changes between empty and non-empty. Since the
utility classes now return quickly in the empty case, there is no
compelling reason for the extra code.
Added a hasListeners() method to ObservableGraphDelegate. The
removeGraphListener( listener ) method now has return type void.
Added null checks to the add/removeGraphListener( listener ) methods
of ObservableGraphDelegate.
----------------------------------------
Separated the Reaper implementation into an interface (Reaper) and
implementation (RunnableReaper). The interface defines only this
method:
Reference createReference( Reapable reapable, Object referent );
Note that createReference() is now defined to return a general
Reference, rather than a WeakReference in particular. A Reaper
implementation shouldn't create PhantomReferences if the referent
needs to be retrievable while it is still referencable through other
paths, or if the Reference.clear() is not guaranteed to be called.
The RunnableReaper implementation differs from the original in that it
implements Runnable, but does not extend Thread. Static factory
methods are provided which also create a Thread to run the Reaper.
Completely rewrote ReapableCollection. It now explicitly maintains
its own storage array and is much more aggressive in reclaiming space.
In practice, this implementation should use at most half the space of
the previous one and will usually be 10-20% faster.
----------------------------------------
SynchronizedGraphWrapper and UnmodifiableGraphWrapper have been
renamed to SynchronizedGraph and UnmodifiableGraph. These classes no
longer extend GraphWrapper, and also no longer wrap Edges from the
underlying delegate Graph.
The Edges retrieved from an UnmodifiableGraph (or by using the
GraphUtils.unmodifiableGraph() method) *allow* the contained
user-defined object to be modified.
The Edges retrieved from a SynchronizedGraph (or by using the
GraphUtils.synchronizedGraph() method) are not synchronized.
----------------------------------------
FilteredGraph, ObservableGraphWrapper, and GraphWrapper are no longer
serializable, but have been rewritten to support serializable
subclasses. See Effective Java, item #54, for a description of the
usage pattern which GraphWrapper and GraphTransformer use.
GraphUtils.EMPTY_TRAVERSER is no longer serializable.
Made CompositeCollection serializable.
Added null element checks to the constructors and deserialization of
AllPredicate, AnyPredicate, CompositeCollection, ClosureChain,
TransformerChain, IteratorChain, and TraverserChain.
Moved methods associated with serialization to just after
constructors, since they are related.
----------------------------------------
Join no longer checks that its operands have disjoint node sets,
although it will definitely behave strangely if they aren't.
Join no longer wraps Edges originating from its delegate graphs.
The Product constructor no longer checks that its operand graphs have
more than zero nodes.
The Edges produced by Product graphs no longer reference the enclosing
Product, and so that is not used as a distinguishing factor in
Edge.equals(). So, if you create two Products of the same two operand
Graphs, their edges will be indistinguishable. As a side effect, the
Edge serialization has changed.
Refactored the internal classes of Join and Product.
----------------------------------------
The Logger and event Logger for DefaultGraph and DefaultOrientedForest
are no longer configurable through the constructors. DefaultGraph now
uses a normal constant Logger.
Removed LoggingSupport and refactored its subclasses to use Log4J
objects directly.
Removed equals() and hashCode() from LoggingCollection and
LoggingGraph, since .equals() cannot be symmetric while simply
delegating to the wrapped object.
----------------------------------------
The Edge implementation of AbstractIntegerNodeGraph (and all of its
subclasses) no longer knows which Graph created it. So the 0->1 Edge
from a Path is .equals() to the 0->1 Edge from a CompleteTree.
AllPredicate and AnyPredicate now (shallow) copy their constructor
arguments rather than using the provided Collection of Predicates
directly. The getOperands() method now returns an unmodifiable List
rather than a reference to the internal data.
Added CartesianProduct to the collections sub-package.
Added CompositeCollection.getOperands().
Added toString() method to ObservableGraphWrapper.
Walker and DefaultGraph now use enums rather than int constants for
some internal state management. No external changes should be visible
from this.
============================================================
v0.13.1
Fixed a bug in DefaultGraph.incidentEdges(node,predicate) where
constructing the incident edge collection with a null/true predicate
would cause contains/remove() to throw a NPE.
DefaultSimpleEdge no longer keeps track of its owning Graph, and so
its constructor has changed.
SimpleObjectEdge in the junit test suite no longer keeps track of its
owning Graph, and so its constructor has changed.
