These release notes may be found at http://jung.sourceforge.net/ReleaseNotes.html
Each release consists of several files. Since version 1.4, these have included:

jung-#.#.#.jar
  The core and sample libraries; without source or tests.
jung-#.#.#-src.jar
  The core and sample libraries with source
jung-#.#.#.zip
  The full source distribution, with samples, source, Ant build file, and JUnit tests. Contains jung-#.#.#.jar within it.
jung-#.#.#-doc.zip
  The zipped Javadoc documentation.

## Release Notes

### 1.7.6 (Martin Luther King/Groundhog Day 2007)

Bug Fixes

Fixed typecasting error in `SubsetManager`.
Fixed problem leading to `NullPointerException` in `PluggableRenderer.paintIconForVertex()`.
`GraphZoomScrollPane` was fixed to properly handle view scaling. ScrollBar range was restored to the min max of the actual layout area, instead of a larger area.
Several fixes were made for Java6 to prevent class cast exceptions when a transformed Shape was cast to a GeneralPath.
`VisualizationViewer`'s `paintComponent` is no longer synchronized.
`VertexShapeFactory`'s polygons were fixed for more precise centering over the vertex location point.
When vertex shapes were used as a fallback for a vertex icon, the vertex shapes were not positioned properly.
Gradient painted edges were invisible for loop edges. Added a hack to fix it.
Added logic to not show tooltips on hidden vertices and edges.
`SpringLayout` modified to address `NullPointerException` problem for graphs which are modified after the Layout is created. (Note: this was actually fixed in 1.7.5, but not documented until now.)
Fixed `FRLayout` bug relating to calculation of vertex positions in the presence of locked vertices.

### 1.7.5 (Birth of the Bab 2006)

New Features

`Layout.isLocked(Vertex)` is required to report the locked state of the specified vertex (that is, whether the position of the vertex can be updated by the layout algorithm), as determined by calls to `lockVertex` and `unlockVertex`. This supersedes and replaces the now-deprecated `AbstractLayout.dontMove(Vertex)`, which now calls `isLocked` internally.
`AbsoluteCrossoverScalingControl` is a new class that allows the user to set an absolute scale instead of a scale relative to a previous value. At this time, there are no demos using this class.

Changes

`PluggableRenderer` now uses the following logic to render an individual vertex (changed portion italicized):

If there is a non-null `VertexIconFunction`

if there is a non-null `Icon` for this vertex, that icon is painted
otherwise, the `Shape` for this vertex is painted
previously, a "broken image" icon was painted if the icon was null

otherwise, the `Shape` for this vertex is painted.

If the user wants a broken image to be displayed if the `VertexIconFunction` cannot load an icon for the vertex, it is now the user's responsibility to provide a `VertexIconFunction` that checks the result of the load for "null" and returns a "broken image" icon.
This change allows users to render some vertices as icons and others as shapes, at their option, simply by specifying which vertices have a non-null icon; this can be used, for example, to render the selected vertex as an icon. (Of course, in this case the `VertexIconFunction` would need to have access to the `PickedInfo` instance.)
`GraphZoomScrollPane` has been modified so that the scroll bars move a rotated graph display in the expected direction. This was done by calculating the current rotation, removing it, translating the graph, and then restoring the rotation. Additionally, the GraphZoomScrollPane now calculates its range based on the actual size of the layout and the size of the viewer. Changes to the layout size will automatically be adjusted for by the scroll-bars.
`MapBinaryHeap` now implements the `Collection` interface. In particular, it now includes a `contains(Object)` method, an `iterator()` method, and the `insert` method has been renamed to `add` for compatibility. Note: the `Iterator` supplied does not support removal, and the methods which remove arbitrary elements (`remove, removeAll, retainAll`) are not supported.
Seed `EdgeShape` instances must now be defined as spanning from coordinates (0,0) to (1,0). These shapes are rotated, scaled, and translated into position for each edge displayed in the graph. Previously, the 'seed' edge shape was first scaled by its bounds, but that technique led to incorrect edge drawing when an edge shape's bounds exceeded its endpoints. As an example, consider an edge shape that passes and returns to its endpoint. Users who wish to use a seed edge shape that is not defined from coordinates (0,0) to (1,0) should first transform their seed edge shape to conform to this size.
`EdgeWeightLabeller` now includes a `removeWeight` method to allow the user to clear obsolete weights from this decorator, and a `clear` method that clears all weights from this decorator.
`UserDatumNumber{Vertex,Edge}Value` now each contain a constructor that allow the user to specify the `CopyAction` for the datum to be added. (The default remains `REMOVE`.)
`BernoulliEdgePermuter` now accepts mixed-mode graphs (graphs which permit directed and undirected edges); if the graph only permits undirected edges, only undirected edges are created; otherwise directed edges are created.
`GraphMLFileHandler` now creates `SparseGraph` instances; this reflects the fact that GraphML files can contain both directed and undirected edges (the edge default directionality is only a default, not a constraint) and can contain parallel edges.
NOTE: this means that graphs read in from GraphML files will, from now on, never be of type `DirectedGraph` or `UndirectedGraph` or enforce the corresponding constraints; code which assumes these types or constraints will fail.
`CrossoverScalingControl`: Added documentation and clarified variable names. Removed improper extends class.
`AbstractLensSupport`: The visible controls were simplified.
`GraphMouse` classes: Changed in/out scale values to 1.1f and 1/1.1f to improve accuracy. Previous values of 1.1f and 0.9f caused a 'creep' in scale values when applied repeatedly.

Bug Fixes

`DijkstraShortestPath.getPath` now properly checks to make sure that its inputs are elements of the constructor-specified graph; if they are not, an `IllegalArgumentException` is thrown.
`AbstractRanker` and `PageRank` now no longer assume that input edge weights are represented as `MutableDouble` values; instead they are assumed to be of the (more general) type `Number`.
Javadoc corrections: `BetweennessCentrality` and `PajekNetReader`.
`PajekNetReader`: now correctly handles different combinations of vertex labels and coordinates, and permits unquoted labels.
`VertexIconAndShapeFunction` and `VertexImageShaperDemo` now each check to make sure that the fetched `Icon` has > 0 width and height before attempting to cache the image. (This handles the case where the icon is not successfully loaded prior to its attempted first use.)
`MouseListenerTranslator.getVertex()` now correctly calls `vv.inverseViewTransform()` to get the vertex coordinates (rather than `vv.inverseTransform()`).
`GraphMLFile.saveUserData`: now includes the following checks (if either is true, nothing is written for the corresponding key):

if the `CopyAction` for a user datum is `UserData.REMOVE`
if the user datum is null

`GraphMLFile.saveEdgesSection()` now properly puts a space after the edge directedness tag.
`PluggableRenderer`:

Fixed occasional arrow orientation problem by setting a maximum number of iterations inside `getLastOutsideSegment`.
Fixed `GeneralPath` typecasting problem that can occur with Java6.

`GradientEdgePaintFunction` fixed so that loop edges no longer vanish.

### 1.7.4 (Ghana Independence Day 2006)

New Features

`Pair` now defines a more user-friendly `toString` method.
`TestGraphs.generateMixedRandomGraph` now has an optional argument specifying whether parallel edges are allowed in the generated graph.

Bug Fixes

`BarabasiAlbertGenerator`: fixed a bug in the handling of parallel edges (introduced in 1.7.3; this caused `PluggableRendererDemo`, and anything else using `TestGraphs.generateMixedRandomGraph`, to fail in version 1.7.3).
`SpringLayout`: removed confusing console output.
`DefaultGraphLabelRenderer` now correctly uses the `Font` (if non-`null`) argument given to `getGraphLabelRendererComponent`. (Previously it had been using the `VisualizationViewer` default font, regardless of the argument's value.)

### 1.7.3 (Dr. Seuss' Birthday 2006)

New Features

`MagnifyTransformer` and `MagnifyShapeTransformer` were added to supply a magnifying glass like examiner lens feature. They are similar to the hyperbolic projection classes, but they do not distort the graph layout or shapes. `LensDemo` (formerly `HyperbolicLensDemo`) has added these classes so that they can be easily compared with the hyperbolic transform classes.

Changes

Constructor added to `DefaultSettableVertexLocationFunction` that takes a `VertexLocationFunction` and initializes the locations in the map. This will make it easier to load pre-existing vertices when changing layouts.
Changed the lens controls for the `HyperbolicLensSupport` so that they are drawn in the foreground `PostRenderPaintable`.
A grid-like graph option was added to `LensDemo` to show the lens effects more clearly.
The Hyperbolic projection support classes have been refactored to better represent their role as support classes for a special transform that is applied within an elliptical shaped Lens area of the visualization. `HyperbolicTransformer` and `HyperbolicShapeTransformer` now extend a generalized `LensTransformer` class that applies the transform within the lens. In addition to the hyperbolic transform classes, there are two more extensions to `LensTransformer`. They are `MagnifyTransformer` and `MagnifyShapeTransformer`, which only zoom the area within the elliptical lens. See the new version of `LensDemo` as an example.
`PluggableRenderer` has been changed internally so that it sets the font for graph labels before it sets the text.
`DegreeDistributions` now has a `getDegreeValues` method (analogous with `getIndegreeValues`, etc.).
`GraphZoomScrollPane` now saves the scale value that is computed the first time the visual components are realized. This value is used to normalize the scale value that subsequently determines the size of the scrollbar thumb adjusters. In most cases, the initial scale will be 1.0, but in cases where the user has initialized the graph layout to be a different size than the `VisualizationViewer`, this change will keep the scrollbar sizes consistent with the initial view that the user has established.
`BarabasiAlbertGenerator` now lets the user specify whether it is permissible to create parallel edges; the default is "no parallel edges", which differs from the previous default of "allow parallel edges".
`StructuralHoles`: changed visibility of `localConstraint` and `aggregateConstraint` to `public`.

Bug Fixes

`LensDemo` changed to use a `LayoutScalingControl` for the zoom buttons when in the hyperbolic projection mode. This mirrors the behavior of the `GraphMouse` in that mode.
Changed the `EditingPopupGraphMousePlugin` so that after you add a new Vertex, it locks all existing Vertices prior to calling restart. This makes the behavior consistent with the `EditingGraphMousePlugin`.
Fixed level of second arrowHit test in `PluggableRenderer` so that hits are computed properly.
`GraphLabelRenderer` and `DefaultGraphLabelRenderer` changed to pass `Font` parameter in `getGraphLabelRenderer` method. This should help the label to correctly set its size.
`EdmondsKarpMaxFlow`: internal method `finalizeIterations` now correctly casts the capacities to `Number` (rather than `MutableInteger`); also fixed typos in Javadoc.
`BarabasiAlbertGenerator`: now creates vertices appropriate to the specified directionality of the graph. (Previously the vertices created could only attach to undirected edges.)
`StructuralHoles`: fixed calculation of mutual weight:

Edges are now no longer required to be either undirected or reciprocated.
Nonexistent edges are now treated (for weight calculation purposes) as equivalent to edges of weight 0.
An exception is no longer thrown if the mutual weight of a vertex with itself is asked for. (Instead, 0 is returned.)

Also edited documentation to emphasize that all edges must have non-null assigned weights.

### 1.7.2 (Veterans' Day/Remembrance Day 2005)

New Features

`GraphEditorDemo` is a new demo that shows how to create a graph interactively using mouse events. New classes to support this demo are `EditingGraphMousePlugin` and `EditingModalGraphMouse`.
The details of controlling view, layout, and crossover scaling are now delegated to implementations of the new `ScalingControl` interface; for example, the `CrossoverScalingControl` class now handles the internal crossover scaling work done in the `CrossoverScalingGraphMousePlugin`. They may also be used to handle scaling control in the action listeners for zoom buttons or keyboard events, and all demos have been updated to do so. This should make it easier for users to create their own scaling controls.

Changes

Made the default lens size larger in `HyperbolicTransformer`.
`AbstractLayout`:

The order of the calls to `initialize_local()` and `initializeLocations()` is now the same in both `restart()` and `initialize()` methods: the order is now, in each case, `initialize_local()` followed by `initializeLocations()`. (Previously, `restart()` and `initialize()` had not called these methods in the same order.)
`initialize_local` has been changed to be a non-abstract stub method, rather than an abstract method.

Documentation changed for the `restart()` method in `Layout` and `AbstractLayout`. This method is no longer specified to scramble the graph, but to restore the vertices' initial locations according to the `VertexLocationFuction` specified at initialization (which may have been randomly generated). To generate new initial random locations, users may call `layout.initialize(layout.getCurrentSize())` instead.

Bug Fixes

`ShapePickSupport` constructor changed to actually set the passed `layoutTransformer` reference. This bug affected no existing code, as the `setLayoutTransformer` method is called by `VisualizationViewer` when the `vv.setPickSupport(pickSupport)` is called, if `pickSupport` is an instance of `ShapePickSupport`.
`VertexIconAndShapeFunction` `getShape(Vertex v)` method: First line expression changed from `(Icon)iconMap.get(v)` to `getIcon(v)` so that subclasses could more easily override the behavior.
Moved `event.consume()` call to inside of modifier test conditional in `AnimatingPickingGraphMousePlugin`.
Changed `DefaultModalGraphMouse` creating of JComboBox so that current mode is always selected on creation of mode combo box.
`EdgeShape` modified so that the edge shapes that allow parallel edges also enable parallel self-loops (this restores the behavior that existed in 1.6.0). `CubicCurve` now also properly uses the static loop instance to draw self-loops.
`SatelliteRotatingGraphMousePlugin` and `SatelliteShearingGraphMousePlugin` modified to correct the center of rotation and shear for the `SatelliteVisualizationViewer`.
Changed `setGraphLayout(Layout layout, Dimension viewSize)` method in class `DefaultVisualizationModel` to call either `initialize(Dimension d)` or `restart()`, but never both.

### 1.7.1 (US National Mole Day 2005)

Changes

`KKLayout` now

takes an optional `Distance` parameter as its means of measuring distances between vertices. This means that users can base the algorithm on weighted or unweighted network distances, or even distances that have nothing to do with the network topology at all.
supports graphs with directed edges: `KKLayout` now uses the minimum of the a->b and b->a shortest path lengths as its canonical a-b "distance".
stores distances internally using a `double[][]` array, rather than a `DoubleMatrix2D`; this should reduce the memory footprint somewhat.
allows the user to specify a "length factor" which partially determines the "preferred" length of the edges (in conjunction with the size of the window and the diameter of the network).
allows the user to specify a "disconnected distance multiplier" which specifies the fraction of the graph's diameter to use as the distance between disconnected vertices.
The above two parameters can be used to control the amount of the screen that the graph occupies, and thus to ensure that disconnected components are not drawn offscreen.

`FRLayout` now has two settable parameters that specify the multiplicative factors used to calculate vertex repulsion and attraction. (Previously these two factors were the same, and were not user-settable.)
New Interfaces added: `LayoutTransformer` and `ViewTransformer` provide methods to map points from layout to screen coordinate systems, and from screen to layout coordinates.
VisualizationViewer now declares that it implements `Transformer`, `LayoutTransformer`, and `ViewTransformer`. There are no new methods added; the new interfaces' contracts are satisfied with existing `VisualizationViewer` methods.
`PickedState` now implements `ItemSelectable. MultiPickedState` accepts `ItemListeners` and fires `ItemEvents` when the picked vertices and edges change. `PickEventListener` has been deprecated and its functionality replaced by `ItemListener`.
`ShapePickSupport` has been internally modified to use a `LayoutTransformer` to assist with picking. Users may not notice this change, as the `LayoutTransformer` is normally set by the `VisualizationViewer` during its `setPickSupport(PickSupport ps)` method.
`PajekNetReader` now throws an exception if it encounters an edge type that is not supported by the type of the supplied graph (e.g., it throws if it encounters an "*Edges" section and the graph only accepts directed edges). (Previously, it had simply ignored such incompatible edges, which occasionally resulted in an unexpectedly empty graph with no explanation.)
Changed the declared plugins in `DefaultModalGraphMouse` to the more general `GraphMousePlugin` type.
Added `{get, set}Delegate()` methods to `LayoutDecorator`.
The `ShowLayouts` demo now allows the user to select any of several different graphs for display; this makes it easier for users to evaluate the fitness of each layout algorithm for their purpose.

Bug Fixes

`DefaultVisualizationModel.stop`: wrapped the call to `relaxer.interrupt()` in a try-catch block to sidestep an applet security violation problem.
`GradientEdgePaintFunction` now takes a `LayoutTransformer` in its constructor. The `LayoutTransformer` is used to propery apply the gradient at the endpoints of the edges.
`TranslatingGraphMousePlugin` modified so that the graph element translation remains coincident with the mouse pointer at extreme zoom-out values.
`MultiPickedState` was modified so that it only fires events when the picked state actually changes. This will prevent its participation in an infinite loop of pick related events.
`PajekNetReader` now no longer throws an exception when given input that has no vertex labels.
Fixed bug in `SatelliteCrossoverScalingGraphPlugin` that caused improper crossover behavior.
`SpringLayout`: removed incorrect division of "stretch" by 100, which caused the edges' "springs" to be too weak (leading to a disorganized and chaotic visualization).

### 1.7.0 (Autumnal Equinox 2005)

New Features

#### Visualization Architecture Improvements

Tom Nelson has once again done (a) great (deal of) work on the visualization architecture. New and continuing JUNG users may want to take a look at the new short guide "Understanding the JUNG Visualization System" (written primarily by Danyel Fisher) to get an overview of the entire architecture as it currently stands, and tips for using it.

The class called `GraphDraw` has been deprecated. See the aforementioned Visualization Guide for pointers on how to create JUNG visualizations using `VisualizationViewer` directly.
`Transformers`

Transformations of the Graph are handled by implementations of the `Transformer` interface. Available transformations include:

scaling
translating
rotating
shearing
hyperbolic projection

Graphs can now be scaled in two ways:

view - a scaling transform is applied to the graphics context so that vertices and labels change size as the graph changes size
layout - a scaling transform is applied as a filter to the Layout so that vertices and labels stay the same size and their locations zoom in and out

The supplied mouse listener classes allow access to both kinds of scaling. Additionally, there is a mouse listener class `CrossoverScalingGraphMousePlugin` that changes from layout scaling when you zoom in, to view scaling when you zoom out. This preserves the look of the graph as it gets very small.

`DefaultGraphLabelRenderer`

All `Vertex` and `Edge` labels are now drawn with a `CellRenderer` component, just like `javax.swing.JTree` and `javax.swing.JTable` use.
This allows the use of html for multi-line, multi-color, multi-font, multi-language labels.
Edge labels are now drawn parallel to the edge itself by default. For parallel edges, the labels are offset vertically so they do not overlap. This behavior can be controlled thru a property of the `DefaultGraphLabelRenderer` class which has a `setRotateEdgeLabels(boolean)` and `isRotateEdgeLabels()` method. See it demonstrated in the EdgeLabelDemo.

`VertexIconFunction`

Allows you to use an Icon to represent a Vertex.
see `UnicodeLabelDemo` and the `ImageShaperDemo` for examples.
The `ImageShaperDemo` also uses the `FourPassImageShaper` to return only the outline of the opaque part of a transparent image in order that the picking and the edge arrow placement conforms to the exact shape of the non-rectangular image.

`VisualizationViewer` refactoring

`VisualizationModel` interface represents the state of the `VisualizationViewer`
`DefaultVisualizationModel` class holds the values for the state of the `VisualizationViewer`
Separation of the model from the view will make it easier to show multiple views of one graph. See `MultiViewDemo` and `TwoModelDemo`.
double buffering

`VisualizationViewer` can use double buffering, painting the graph to an offscreen image then blitting the image to the Window.
Double buffering was the default in version 1.6.0. DoubleBuffering is an option in version 1.7 and the default setting is off.

`VertexLocationFunction` is a new interface with two methods: `Point2D getLocation(ArchetypeVertex)` and `Iterator getVertexIterator()`:

`Layout` now extends this interface; this gives users a more efficient way of fetching vertex locations (than `getX` and `getY`.
`AbstractLayout.initialize()` now has an optional `VertexLocationFunction` parameter that allows the user to specify a set of (initial) locations for the vertices:

Since `Layouts` are also `VertexLocationFunction` instances, this allows users to "chain" layouts together (that is, to use the existing locations specified by one `Layout` as the input to another).
`PajekNetReader` and `PajekNetWriter` now include optional parameters to read coordinate information from a Pajek-formatted file and store it in a `VertexLocationFunction` instance (and vice versa).

`StaticLayout` is a new subclass of `AbstractLayout` that does not alter the locations specified to it on input; this is useful for users that already have an existing layout (with known locations) that they like.
`SettableVertexLocationFunction` extends this interface to include a method `setLocation(ArchetypeVertex, Point2D)`; `DefaultSettableVertexLocationFunction` provides a default implementation of this interface.

`VertexShapeFactory` now provides shapes that are cached singletons.

should improve performance, particularly in large graphs, as far fewer new Objects are created
`Edge` shapes were already cached in version 1.6.0

`HasShapeFunctions` interface implemented by `PluggableRenderer`.

has two methods:

`VertexShapeFunction getVertexShapeFunction()`
`EdgeShapeFunction getEdgeShapeFunction()`

Used by `ShapePickSupport` to supply exact shape definitions for picking with the mouse.

`PluggableGraphMouse` provides a means to add from a set of supplied `GraphMousePlugin` instances, or develop your own. The supplied `GraphMousePlugin` classes provide picking, translating, scaling (layout or view), rotating, and shearing. All are configurable as to the mouse event modifiers that will activate them. The `ZoomPanGraphMouse` is re-implemented to use `PluggableGraphMouse` with appropriate plugins. The `DefaultModalGraphMouse` uses all of the supplied plugins in a configuration intended to follow mainstream applications.
`ModalGraphMouse` has two modes: TRANSFORMING and PICKING. Switching between modes allows a better choice of mouse buttons and modifiers for both the picking and transforming mode.
`Coordinates` is now a subclass of `java.awt.geom.Point2D.Float`

improves efficiency of transform code without breaking legacy use of `Coordinates` class

`BirdsEyeVisualizationViewer` has been deprecated and replaced with `SatelliteVisualizationViewer`. The latter provides a much improved representation of all of the new transforms that can be applied to your graph. See `SatelliteViewerDemo` as an example.
`TreeLayout`, contributed in the support list by Toni Karlheinz, has been included. See `TreeLayoutDemo` for an example of its use.

#### Hypergraphs

Hypergraphs are a generalization of undirected graphs in which hyperedges connect sets (rather than pairs) of (hyper)vertices; this is a natural representation for affiliations and groupwise (rather than pairwise) interactions, such as meetings and multiparty collaborations. JUNG has for some time included a prototype version of hypergraph support based on `BipartiteGraph` and related classes. JUNG now provides "native" implementations of `Hypergraph`, `Hyperedge`, and `Hypervertex`, as well as some new capabilities.
Hyperedges are created as empty sets of vertices; hyperedges and hypervertices may be connected using `Hypervertex.connectEdge` or `Hyperedge.connectVertex` (equivalent operations). However, "orphaned" hyperedges and hypervertices (those that are not elements of existing graphs) may not be connected, and hyperedges/vertices that are removed from a graph are automatically disconnected from all incident hypervertices/hyperedges.
Implementations
Generally, a `Hypergraph` is a set of hyperedges and hypervertices with certain operations defined on it. Currently we have one implementation of `Hypergraph`: `SetHypergraph`.

Hypervertices and hyperedges are duals of one another: hyperedges are connected to sets of hypervertices, and vice versa.
We provide several implementations of hyperedges and hypervertices:

`AbstractHyper{vertex,edge}` define most of the functionality of the types, but do not specify storage. (All implementations of `Archetype{Vertex,Edge}` must prevent duplicates in their internal data structures, but internally they need not use `Set`s for this storage.)
`CollectionHyper{vertex,edge}` are abstract subclasses of `AbstractHyper{vertex,edge}` that specify a `Collection` as the type of storage.
`ListHyper{vertex,edge}` are subclasses of `CollectionHyper{vertex,edge}` that use space-efficient `List` instances to store their incident elements; they have O(d) time complexity for query operations such as `isIncident`, where d is the size of the incident element collection.
`SetHyper{vertex,edge}` are subclasses of `CollectionHyper{vertex,edge}` that use `Set` instances to store their incident elements; they require more space than the `ListHyper{vertex,edge}` classes, but have expected O(1) time complexity for query operations.

Note: nothing prevents users from creating Map-based implementations of hyperedges and hypervertices that are analogous to the Map-based implementations of edges and vertices that JUNG already provides (that is, that represent a hypervertex's incident and adjacent elements internally as a Map from adjacent vertices to the corresponding connecting edge set). However, users are cautioned that such an implementation, while it would make the `findEdge[Set]` operations efficient, would be expensive in terms of space: the storage required would be equivalent to maintaining a clique (complete graph) on the vertices of each hyperedge.

#### Miscellaneous

New package `algorithms.metrics` contains two new classes: `StructuralHoles` (calculates some of the measures presented in Burt's "Structural Holes") and `TriadicCensus` (counts the number of times that each possible configuration of three vertices appears in a specified graph). Thanks to Jasper Voskuilen and Diederik van Liere of the Department of Information and Decision Sciences at Erasmus University for their donation of the code on which `StructuralHoles` is based.
`BaryCenter` is a new vertex ranking class which ranks vertices based on the sum of their shortest path distances. Contributed by Dan Bolser.
`Element` now has a new method `getIncidentElements`. This allows an element to access its incident elements even if its subtype (vertex or edge) is not known; this is useful in the context of hypergraphs, since vertices and hyperedges in a hypergraph are duals of one another and can be treated in some ways equivalently.
`HypergraphReader` creates a `Hypergraph` based on a `Reader` whose format is similar to that of `BipartiteGraphReader`.
The `Distance` methods now take `ArchetypeVertex` arguments rather than `Vertex`. This applies to all implementations of `Distance`, including `UnweightedShortestPath`. However, `UnweightedShortestPath` still only works on `Graph` instances (for now).
`ShortestPath` is now an interface; the `getPath` method has been refactored into a static method in the new `ShortestPathUtils` class.
`DijkstraShortestPath` has been refactored into two classes: `DijkstraDistance` (which implements `Distance`) and `DijkstraShortestPath`, which extends `DijkstraShortestPath` and implements `ShortestPath`. For users of `DijkstraShortestPath`, this change is transparent, but has the following ramifications:

`DijkstraDistance` functions on all graph types, including hypergraphs.
If all you want to calculate are distances (that is, you don't need the actual paths), `DijkstraDistance` is more time- and space-efficient.
`DijkstraShortestPath` stores the "incoming edge" map information as before, for all graph types. However, the `ShortestPathUtils.getPath` method will only work on incoming edge maps that contain `Edge` instances. (Getting "the other end" of an edge only works on edges with exactly two vertices.)

In addition, `Dijkstra*` now has the following additional capabilities:

`getDistanceMap(ArchetypeVertex, Set)` calculates the distance to each element of the `Set`. The user is responsible for ensuring that each of these "target" vertices is an element of the graph specified in the constructor; this method will not validate the targets.
`setMaxDistance(double)`: after a vertex is discovered whose distance from the source is at least this value, no further distances will be calculated.
`setMaxTargets(int)`: after distances to this many "target" vertices have been calculated, no further distances will be calculated.

New `GraphUtils` methods:

`{add,remove}{Vertices,Edges}({Graph,Hypergraph}, Set)`
syntactic sugar for repeated calls to `g.{add,remove}{Vertex,Edge}`
`vertexMapToDAL`: converts Maps of vertices to Number values to a `DoubleArrayList` using a specified Indexer to determine where to put the value for a given vertex. This makes it easier for users to apply CERN Colt statistical routines (see cern.jet.stat) to JUNG vertex-value maps. (See the changes to `GraphStatistics` for an example; the new methods return vertex-value maps rather than DALs.)
`copyValues(ArchetypeGraph g, NumberVertexValue src, NumberVertexValue dst)`
for each vertex in g, reads values from src and writes them to dst
`getVertexGenerator(ArchetypeGraph)`
Returns the `VertexGenerator`, if any, stored in the graph's user data at the standardized location specified by the VG interface: `VertexGenerator.TAG`.

`PredicateUtils`: new method `getSatisfyingElements(Collection, Predicate)`
`KPartiteFolder` has been renamed to `FoldingTransformer`, and several other changes have been made as well:

Methods for folding instances of `Hypergraph` are now also provided.
The folding methods now have the option of decorating the edges in the new graph with the number of paths in the original graph that they represent.
Parallel edges in the input graph are no longer specifically prohibited, but they are ignored.

The `UserData` architecture has been modified:

`UserDataFactory` is a new class with a single method, `getInstance`, which returns a `UserDataContainer` instance. Used by `UserDataDelegate` (see below).
The graph, vertex, and edge classes now extend the new class `UserDataDelegate`, rather than `UserData`. The purpose of this new class is to allow users to specify their own implementations of the `UserDataContainer` interface; this can be done on an object-by-object basis. `UserDataDelegate` has a static method called `setUserDataFactory`, which specifies the `UserDataFactory` to use to get a `UserDataContainer` instance for each vertex/edge/graph as it is created.
The available implementations of `UserDataContainer` now include the following, each of which implements `UserDataFactory`:

`DefaultUserData`: this is the original JUNG implementation, in which each vertex, edge, and graph maintains a separate HashMap which maps keys to (value, copy action) pairs. Straightforward and time-efficient (all operations are O(1) except for `importUserData`, which requires O(d) time, where d is the number of data to import), but requires a fair amount of space overhead (O(N) maps, where N is the number of vertices, edges, and graphs in use).
`UnifiedUserData`: this is a new implementation which maintains a single Map of key values to Maps from vertices/edges/graphs to (value, copy action) pairs. This implementation is time efficient except for `getUserDatumKeyIterator`, which requires O(k) time (where k is the number of keys in use) and for `importUserData`, which requires O(k + d) time. However, it requires much less space overhead (O(k) maps).
Warning: this implementation has not yet been extensively unit tested, although it has been used in a number of experiments on very large data sets. Also, since vertex and edges that are equal to one another (copies) have the same hash code, all copies of a single element will have the same user data repository. As such, this implementation, as it currently stands, may not be suitable for all applications.

`UserData` is now primarily an auxiliary class which contains the SHARED, REMOVE, and CLONE `CopyAction` singleton instances.
`UserDataContainer` now implements `Cloneable`; implementations must provide a public `clone` method.

`GraphMatrixOperations` now has a few new options for converting Colt matrices to JUNG `Graph` objects and vice versa; among other things, edge weights may now be specified using `NumberEdgeValue` instances.
`BarabasiAlbertGenerator` now optionally produces a directed graph. (The default remains an undirected graph.)
New interface `ParallelEdgeIndexFunction` and implementations `ParallelEdgeIndexSingleton` and `DefaultParallelEdgeIndexFunction` are now used in the visualization code (and may be used elsewhere) to define a consistent 0-based index. `PluggableRenderer` now has a way to plug implementations of this interface in; these classes are used by PR to order parallel edges for consistent rendering. User implementations may generate indices on any desired basis (lexicographic ordering based on edge labels, properties of edges, creation ordering, etc.).
All the various experimental database code in the `scratch.danyel.db` and `scratch.dawit.db` packages has been moved to a new project in the CVS, JUNG-DB. We encourage you to use these as starting points in building database-backed JUNG projects. (And let us know what you come up with!)

Changes

`ArchetypeGraph.remove{Vertices,Edges}(Set)` have been tentatively deprecated in favor of the new removal methods added to `GraphUtils` (see above). This is part of an ongoing investigation into the possible simplification of the JUNG interfaces.
`ErdosRenyiGenerator` and `DegreeDistributionRanker` have been cleaned up a bit and are now slightly more efficient. Thanks to Dirk Koschuetzki for the suggestions.
`Indexer` now stores its vertex-to-index information using an array rather than a Map, which increases both time and space efficiency. Thanks to Dirk for the suggestion.
`VertexStringer` and `EdgeStringer`: the `getLabel` signature now specifies `Archetype{Vertex,Edge}`, i.e., these now work on any kind of vertex and edge, respectively.
`VoltageClusterer` and `KMeansClusterer` now use the CERN Colt random number generator, and allow the setting of the random seed.
The graph clustering class method signatures now specify `ArchetypeGraph` rather than `Graph`: specifically, `GraphClusterer.extract`'s argument, the constructor argument for `ClusterSet`, and the return value for `ClusterSet.getUnderlyingGraph` are now all of type `ArchetypeGraph`. Also, `WeakComponentClusterer` can now operate on any `ArchetypeGraph`.
`PajekNetReader` now has a new constructor which allows the user to specify a `VertexGenerator` that will be used to create the vertices.
`GraphStatistics`:

`clusteringCoefficients` and `averageDistances` now return their results in the form of a `Map` from vertices to the corresponding values (coefficients or average distances). (Previously these results were returned in `DoubleArrayList`s, which made it impossible to reliably associate vertices and their values.)
`averageDistances` and `diameter` now have an optional `Distance` parameter which specifies the distance metric to use in calculating the results.
`diameter` now returns `Double.POSITIVE_INFINITY` if the graph is disconnected (that is, if there exists at least one pair of vertices `(a,b)` for which no a-b path exists). Similarly, `averageDistances` stores a value of infinity if not all vertices are reachable from the specified vertex.
now operates on `ArchetypeGraph` instances.

Bug Fixes

`MultiPickedState`: fixed bug in pick(ArchetypeEdge, boolean) [was looking at vertices rather than edges]
`UnweightedShortestPath`: fixed bug inside getShortestPathsFromSource which failed on disconnected graphs
`Pair.equals` and `AbstractArchetypeVertex.equals` now each check for reference equality (==) as well as `Object.equals`. (Previously, for an orphaned `ArchetypeVertex` `v`, `v.equals(v)` would return false, and would therefore, among other things, be useless as a hash key.)
Several broken and outdated links have been cleaned up in the JUNG manual.
`EdgeWeightLabeller.getWeight` now internally casts EWL's stored values to a `Number` rather than an `Integer`, so that if its `setNumber` method is used to store non-Integers, it will not throw a `ClassCastException`.

### 1.6 (April Fools'/Earth Day 2005)

Announcement: Tom Nelson and Jens Krefeldt have joined the JUNG development team; Tom has been doing a lot of work on the visualization system, and Jens has contributed a mechanism (not yet released) for listening to changes to user data repositories. Welcome!

New Features

New decorators and decorator interfaces

`EdgeShapeFunction`

allows users to specify arbitrary shapes for edges
`AbstractEdgeShapeFunction` provides several implementations: `Line`, `BentLine`, `QuadCurve`, `CubicCurve`, `SimpleLoop`, `Loop`, and `Wedge`. All but `Line`, `SimpleLoop`, and `Wedge` adapt themselves to render parallel edges distinctly; this makes picking individual edges easier.

`{Vertex,Edge}PaintFunction`

provide separate methods for specifying draw (outline) and fill (interior) `Paint` objects for each vertex/edge; these are analogous to the "foreground" and "background" colors that could be specified by `VertexColorFunction`
replaces (deprecated) `{Vertex,Edge}ColorFunction`. Since `Paint` is a superclass of `Color`, this enables use of `GradientPaint` and `TexturePaint`, in addition to `Color`, to customize vertex and edge visualizations. (`GradientEdgePaintFunction` is an example of this.)
for examples, see the `graph.decorators` package, including `ConstantVertexPaintFunction` and `ContantEdgePaintFunction`, as well as `PluggableRendererDemo`.

Three `Converter` classes have been created to convert edge color, vertex color, and edge thickness functions to edge paint, vertex paint, and edge stroke functions respectively.

`PluggableRenderer` has been heavily refactored internally, and has a number of new features; see the revised `PluggableRendererDemo` to see them in action. Some of these include:

can specify paint functions (see above), which allow for more flexible visualizations than color functions
can specify edge shapes; see above for examples. The edge shapes supplied will be scaled in the x-direction to the distance between the appropriate vertex locations.
arrowheads are now placed at vertex shape boundaries with an iterative method whose tolerance the user can specify
demonstrates a sample `PopupGraphMouse` class that shows popup menus over vertices.

Zooming, panning, and scrolling views

`GraphZoomScrollPane` is a `JScrollPane`-like container for the `VisualizationViewer`. To use it, simply pass the `GraphDraw` or the `VisualizationViewer` in the `GraphZoomScrollPane` constructor, and then add the `GraphZoomScrollPane` to your application. The `GraphZoomScrollPane` scrollbars automatically update to show the zoom and pan of the graph, and the scrollbars may be used to pan the graph. For an example, see `GraphZoomScrollPaneDemo`.
`BirdsEyeVisualizationViewer` and its `Lens`, which facilitate the creation of a separate "zoom" window, have been enhanced to work better with `VisualizationViewer`. No user-code should be required to access the full functionality. See the `ZoomDemo` as an example.
`ZoomPanGraphMouse` adds the ability to zoom the graph with the mouse wheel and pan the graph with a mouse-button-one drag. A pick-drag on a `Vertex` will reposition the Vertex. A pick-drag elsewhere will pan the graph display.

Vertex and edge picking has been redesigned.

`PickSupport` provides a standard interface for classes that "pick" a vertex or edge based on a specified pick location, which is typically derived from a mouse event. `VisualizationViewer` now uses this mechanism internally. Two implementations are provided: `ShapePickSupport` picks only when the mouse point is inside the Vertex shape or when a small footprint around the mouse point intersects the Edge shape. `RadiusPickSupport` picks when the mouse point is 'close enough' to the object; this corresponds to the former picking behavior that JUNG supplied.
`PickedState` extends the `PickedInfo` interface, and provides a standard interface for manipulation of the "picked" state itself. Implementations can support either single or multiple picks. Currently one implementation, `MultiPickState`, is provided.
The `PickEventListener` interface may be implemented by classes that want to register themselves as listeners to changes to a `PickedState instance`. `PickedState` specifies methods for adding and removing such listeners.

`AbstractLayout` now implements `PickEventListener`.
`VisualizationViewer` ensures that its layouts, if they implement `PickEventListener`, register themselves as listeners to the existing `PickState` instance. However, if the `VisualizationViewer`'s `PickedState` is changed, the listeners must be re-registered with the new `PickedState`.

The renderer and layout interfaces' and classes' methods that relate to this (for example, `Layout.getVertex(x,y)`) have been deprecated and are no longer used internally by JUNG. Layout and renderer implementations in future will no longer be required to handle picking directly.
The `ZoomingPluggableRendererDemo` demonstrates a new variant on picking: you can pick a single vertex with mouse button one, and add to the selection with mouse button two. Picking with mouse button two toggles the picked state of the Vertex or Edge that is picked.

Other `VisualizationViewer` changes

You may add pre-render and post render operations to the `VisualizationViewer`, using the `Paintable` interface (a nested interface inside `VisualizationViewer`). The methods are `{add, remove}PreRenderPaintable(Paintable p)` and `{add, remove}PostRenderPaintable(Paintable p)`. A user defined `Paintable` implementation can be added to the rendering chain. The `Paintable` interface also includes a `boolean useTransform()` method to allow implementors to specify whether their `Paintable` should be transformed by the `VisualizationViewer`'s current zoom/pan transform or not. This feature can be used to set a background image, to place titles, or to overlay custom drawing on the graph. See `GraphZoomScrollPaneDemo` for an example that uses a background image and a foreground title. The `ShortestPathDemo` uses a postRenderPaintable to overlay the shortest path on the existing graph, connecting the path by drawing over the vertices.
There is now a setter method for the sleep time of `VisualizationViewer`'s relaxer thread.
The graph `Layout` size and the `VisualizationViewer` size are independent now. You can initialize the graph `Layout` to a large size and the `VisualizationViewer` will automatically zoom out to show all of it when you pass the `Layout` in the constructor of `VisualizationViewer`, or when you call `setGraphLayout`.

`Element` is a new superinterface of `ArchetypeVertex` and `ArchetypeEdge`, and subinterface of `UserDataContainer`. This is useful for defining classes or methods (such as decorators) that can apply to either vertices or edges. Classes such as `AbstractRanker` and its subclasses have been refactored to use this interface rather than UserDataContainer.

Changes

Some visualization classes originally contributed by Tom Nelson have now been moved out of the visualization.contrib package into the main visualization directory.
`GraphDraw`:

now has a constructor `GraphDraw(Layout l)` that allows users to supply their own layout, rather than having to replace the default layout algorithm (possibly after it had been doing some computation).
most of its methods (primarily those which were pass-throughs to `VisualizationViewer`, the `Layout`, or the `Renderer`) have been deprecated; this is part of an ongoing gradual redesign of the visualization architecture. See the Javadoc documentation for these methods for appropriate replacements.

`SubsetManager`: changed so that it uses Predicates internally, not VertexPredicates or EdgePredicates.
`KPartiteSparseGraph`: added "addallnotinitializers" code to conversion constructor
`EdgeThicknessFunction` has been deprecated; use `EdgeStrokeFunction` instead.
`PluggableRenderer`'s control point offset setter has been removed; the new version no longer uses it. See `EdgeShapeFunction` for a method that allows the user to set a control point multiplier.
`SettableRenderer` has been deprecated, and replaced in JUNG's demos and sample code by `PluggableRenderer`.
`Layout` and subclasses: the `wiggleRoom` methods have been removed.
`ArrowFactory`'s methods now take `float` arguments rather than `int` arguments.
`EdgeWeightLabeller` now implements `NumberEdgeValue`.

Bug Fixes

`EdmondsKarpMaxFlow` now performs sanity checks on its constructor's inputs (source and sink must be part of the specified graph, and distinct). Thanks to Michael Telgkamp for spotting the problem and suggesting the fix.

### 1.5.4 (US National Polar Bear Day 2005)

New Features

Several new features in `visualization`, `visualization.contrib`, and `samples.graph`, courtesy of Tom Nelson:

`GraphZoomScrollPane` implements zooming and panning using scrollbars; `GraphZoomScrollPaneDemo` demonstrates how to use this class.
The `Lens` class now implements zooming by a specified percentage value; this capability is reflected in `BirdsEyeVisualizationViewer`.
`PersistentLayoutImpl` now supports edge selection.
`ZoomDemo` has been cleaned up and refactored somewhat; it now also provides an alternate user interface for zooming in and out.

Bug Fixes

`GraphUtils.union` now properly copies edges (the edge iterator had been iterating over the vertices).
`PluggableRenderer`'s `DOTTED` and `DASHED` constants redefined to specify a valid value for the (technically unused) 'mitering' value.
`MouseListenerTranslator` now properly accounts for scaling and offset (zooming and panning) in calculating the location of a mouse click (also thanks to Tom Nelson).

### 1.5.3 (Christa McAuliffe Day 2005)

Bug Fixes

`PajekNetReader` now correctly handles the `*Arcslist` and `*Edgeslist` tags.
`GraphMatrixOperations.matrixToGraph()` now works properly for symmetric (that is, undirected) graphs: only one edge is created for each symmetric pair of matrix entries.
`HyperGraphBPG.getUserDatum()` now does the right thing (rather than returning the `CopyAction` for the specified key, which is what it was doing). Thanks to Elwood Johnson for spotting this.

New Features

`PluggableRenderer` new capabilities:

`setVertexIncludePredicate`: predicate specifies which vertices are to be drawn
`setEdgeControlOffsetFunction`: value specifies the control point offset to use to draw the edges; a nonzero offset causes edges to be drawn as bent lines (otherwise they are drawn as straight lines). This can be used to distinguish between edge types (default behavior: directed edges are bent, undirected edges are straight) or to handle the drawing of parallel edges: if each parallel edge is given a different control offset, then they won't be drawn on top of one another.
Side effects of this change:

`PluggableRenderer.CONTROL_OFFSET` is no longer used and has been removed
`drawDirectedEdge` and `drawUndirectedEdge` (protected methods) have been replaced by `drawSimpleEdge`.

`PluggableRendererDemo` has been enhanced to demonstrate the selective vertex and edge display capabilities.

Changes

`EdgeBetweennessClusterer` has been altered so that it no longer operates on a copy of the graph, but on the graph itself. (The original graph will be modified by this algorithm, but will be restored to its original state before the algorithm returns.) This should speed up the algorithm somewhat.
`ConstantDirectionalEdgeLabelClosenessFunction` has been renamed to the (fortunately, shorter) `ConstantDirectionalEdgeValue`, which better reflects its generality.

### 1.5.2 (Fiesta de Nuestra Señora de Guadalupe 2004)

Note: several users have recently had difficulty in acquiring a copy of Colt 1.2.0, for use with JUNG 1.5.x. We have made a mirror of the Colt zip file available as one of the releases on our SourceForge website.

Bug Fixes

`GraphDraw.getRender()`, which returns the default renderer, has been deprecated. It is also now declared to return a `Renderer` rather than a `SettableRenderer`; this may cause compile errors with user code which assumed that the renderer returned was a `SettableRenderer`.
It has been replaced by `getRenderer`, which returns the `Renderer` that the `GraphDraw` instance is currently using.
`BicomponentCluster` has been reimplemented, and now returns the correct biconnected components. (Note that by definition, a single isolated vertex and two vertices joined by a single edge are biconnected components; see the Javadoc documentation for more details.)
`PajekNetWriter` now breaks lines using `Writer.newLine()` instead of the `"\n"` character, which should make the output more portable (and usable by Pajek itself).

Changes

`utils.StringInputStream` is deprecated, and no longer used internally by JUNG. Users are recommended to use `StringReader` in its place.
`PajekNetReader` now ignores (skips) lines consisting of whitespace.

### 1.5.1 (Hannukah 2004)

Bug Fixes

`UserDataContainer.Clone.onCopy()`, which is used in UserData.CLONED, now properly lets objects which inherit a public `clone()` method to be cloned. (Previously it only allowed objects whose classes declared public `clone()` methods to be cloned.)
`SimpleSparseVertex` now removes undirected self-loops without reporting an error.
Moved `DiscreteDistribution` into the release (package jung.statistics), so that `VoltageClusterer` and `KMeansClusterer` can be compiled and run.

Changes

Tom Nelson's contributed code (in `jung.visualization.contrib`) to provide support for persistent layout and zooming/panning has evolved somewhat:

`Lens`: updates and comments
`BirdsEyeGraphDraw` replaces `ReadOnlyGraphDraw.java`
`BirdsEyeVisualizationViewer` replaces `ReadOnlyVisualizationViewer`

These new names are intended to better reflect the functions of the classes. The BirdsEyeVisualizationViewer uses a nested class called Lens to draw the zoom/pan area as a rectangle. The Lens fires PropertyChangeEvents to cause the main graph view to zoom and pan.

Note that BirdsEyeVisualizationViewer has no getLens() method. The way to add PropertyChangeListeners to the Lens is to add them to the BirdsEyeVisualizationViewer which will later pass them to the Lens after the Lens has been created. This change fixes the NullPointerException that a user would get if they attempted to add listeners to the Lens before it was created.

In addition, `samples.graph.PersistentLayoutAndZoomDemo` has been replaced by two separate programs: `ZoomDemo`, which just shows the zoom/pan feature, and `PersistentLayoutDemo`, which shows the persistent Layout.

JUNG's Ant build file (`build.xml`) is now included in the src/ directory of `jung-#.#.#.zip`; this is known to work with Ant version 1.6.2. This may be used to facilitate building your own custom versions of JUNG.
JUNG no longer uses the type `sun.misc.Queue`.

### 1.5 (Remembrance Day 2004)

Summary: new visualization features (updated `VisualizationViewer`, new `PluggableRenderer`, and `SpringLayout` to make them more flexible and powerful; take a look at `PluggableRendererDemo`), new clustering and ranking algorithms, new vertex mapping mechanisms, new ways of reporting and diagnosing constraint violations, numerous new decorators and predicates; a number of improvements in usability and function to existing classes (including GraphML and Pajek I/O), and a number of bug fixes, including extensive revisions to the Barabasi preferential-attachment graph generator. Also now using COLT 1.2 (whose new license requirements should free JUNG for use in commercial development) and Commons-Collections 3.1.

New Features

`VisualizationViewer`: added contributed code to do tooltip visualization, zooming/panning, saving layout to a file and restoring, setting rendering hints (see `java.awt.RenderingHints`)--which allows things like antialiasing of text and graphics, as well as other speed/quality tradeoffs; see `visualization.contrib` for related new classes (courtesy of Tom Nelson, RABA Technologies, tom.nelson@raba.com). Antialiasing now turned on by default in `VisualizationViewer`.
`PluggableRenderer` is the successor to `SettableRenderer`. Using the appropriate methods, the user can override the default properties/behaviors for vertex color, stroke, shape, label, label font, and label centering; and for edge color, stroke, label, arrows, label font, and label positioning. These behaviors are generally controlled by supplying decorators. (in `visualization`)
`samples.graph.PluggableRendererDemo` shows off many of these functions.
new decorators: `VertexAspectRatioFunction`, `VertexFontFunction`, `VertexShapeFunction`, `VertexSizeFunction`, `VertexStrokeFunction`; `EdgeArrowFunction`, `EdgeFontFunction`, `EdgeStrokeFunction`; constant implementations of each of these interfaces; `ConstantEdgeValue`, `UserDatumNumber{Edge,Vertex}Value`, `NumberVertexValue`, `Number{Edge,Vertex}ValueStringer` (all in `graph.decorators`)
`VertexShapeFactory`: a utility class for generating shapes for drawing vertices. See `samples.PluggableRendererDemo` and `EllipseVertexShapeFunction` for some examples of its use.
`ArrowFactory`: generates arrow shapes for use in `SettableRenderer`.
`KMeansClusterer`: a utility class for clustering objects with n-dimensional coordinates according to their proximity to one another, using the k-means algorithm.
`VoltageRanker`: ranks vertices in a graph according to their 'voltage' in an approximate solution to the Kirchoff equations. This is accomplished by tying "source" vertices to specified positive voltages, "sink" vertices to 0 Volts, and iteratively updating the voltage of each other vertex to the (weighted) average of the voltages of its neighbors.
`VoltageClusterer`: Clusters vertices of a `Graph` based on their ranks as calculated by `VoltageRanker`.
`ConstraintViolation`: a new exception type which is thrown when a vertex or edge which violates a graph's constraints is added; it provides a method (`getViolatedConstraint()`) which returns a reference to the violated constraint, which makes it easier to diagnose the problem (see new `PredicateUtils.evaluateNestedPredicates()` method). Extends `IllegalArgumentException`. Developers of graph classes who plan to throw this exception should note that the violated constraint is a required constructor parameter.
`PredicateUtils.evaluateNestedPredicates()`: returns the separate results of evaluating the constituent predicates of the specified predicate, if any, as a Map from predicates to evaluations. (Some predicates, such as `AndPredicate`, are `PredicateDecorator`s, which operate on other predicates.) This method can be used to determine which constituent predicates pass/fail for a specified object, which may be useful for understanding constraint violations. Note that this method can be used recursively on the constituents of a `PredicateDecorator`.
`GraphUtils.union()`: merges two graphs into a single graph (thanks to Pablo Olmos for the suggestion and for a draft version)
`DirectionTransformer` now has a new option to create new vertices of the correct type rather than copying the old vertices

advantage: original vertex type does not have to support directed & undirected
disadvantages: any class-specific fields won't be copied (since this mechanism does not use clone()), and vertices in the transformed graph will not be "equal to" the corresponding vertices in the original graph

`AbstractRenderer.getPickedKey()`: new method that allows the user to get the user data key that this instance uses to keep track of selected vertices
`findEdge[Set]()`: this has been a `Vertex` method, but it should have been an `ArchetypeVertex` method; now, it is. (The `Vertex` version still exists for backward compatibility.)
new predicates: `ContainsUserDataKeyVertexPredicate`, `SourceVertexPredicate`, `SinkVertexPredicate`, `ReciprocatedDirectedEdgePredicate`, `ThresholdPredicate` (all in the `graph.predicates` package)
`VertexMapper` and its implementations (`AbstractVertexMapper`, `StringLabellerVertexMapper`, and `CopyVertexMapper`) provide a general mechanism for defining vertex/vertex mappings. These do not replace vertex equality as created by `ArchetypeVertex.copy`, but rather give a way for mappings to be created that don't depend on vertex equality. `SettableVertexMapper` is an interface for `VertexMapper` implementations that allow users to write the mappings as well as read them; `HashSettableVertexMapper` is an implementation of this interface. (`utils` package)

Changes

Now using the new version of the COLT library (now 1.2; was 1.0.3); we are told that it no longer uses packages whose licenses that prohibit commercial use, so JUNG, in turn, should now be available for commercial use. This involved no user-level changes, but some minor changes in random number generation and formatted output.
`GraphML` now writes out mixed-mode graphs (and properly labels edges of the non-default type as necessary; default for mixed mode is 'directed'); some minor format issues also cleaned up (thanks to Pietro Pilolli)
`ConnectedGraphPredicate` now returns `true` on an empty graph (was throwing `NullPointerException`).
`SpringLayout`: what were constants (FORCE_CONSTANT, STRETCH, RANGE) are now documented instance variables with setters and getters, which allow users to change some aspects of its behavior.
`EdgeWeightLabeller` default UserData key now has public (not package) visibility
`UnweightedShortestPath` now provides `reset()` methods which clear out the hash maps that it uses to store the distances and incoming edge maps.
moved `LeanSparseVertex` from `samples` to `graph.impl`; this permits one of the unit tests to compile properly without the samples directory, and also makes this class more readily available. `LeanSparseVertex` is an alternative to `SparseVertex` that uses a lighter-weight internal implementation; it is not as fast as `SparseVertex` for some operations, but has less space overhead.
`AbstractSparseVertex` and subtypes: `getEdges_internal()` and `getNeighbors_internal()` now return a `Collection` rather than a `Set`, which allows for more flexibility in internal implementations. This involved some signature changes in vertex implementations, but no changes to signatures of public methods.
`PajekNetReader`:

Removed `Collection` of edge constraints from constructor. Edge constraints are now defined implicitly by (optionally) passing a `Graph` to the `load()` method. The edge data are filtered according to the graph's constraints, if any; thus, if the graph only accepts directed edges, any undirected edges in the input are ignored.
Now throws `IllegalArgumentException` if vertex numbers are outside of range [1, n], where n is the number of vertices; had been throwing `NullPointerException`. Thanks to Dirk Koschuetzki for the suggestion.

Everybody's favorite trivial change: `StringLabeller` now implements `VertexStringer`.
`TypedVertexGenerator` has a new constructor that takes an `ArchetypeGraph` and extracts the constraints it needs from it.
`DijkstraShortestPath`: now defaults to edge weights of 1 if no edge values specified; also provides some new constructors.
`KPartiteFolder` now has a `setCopyAction()` method so that users can choose to let `FOLDED_DATA` be accessible to copies of the edges (default copy action remains `REMOVE`)
`UserDatum{Edge,Vertex}Predicate` now test for equality with `equals()` rather than `==`
`EvolvingGraphGenerator.reset()` documentation changed: previously claimed to set |V| and |E| to 0; this doesn't work for Barabasi generator because it has to start with a seed. Now claims that it resets this instance to the state it had just after the constructor had completed.
`VertexColorFunction`, `EdgeColorFunction`, `EdgeThicknessFunction` moved from `visualization.graphdraw` to `graph.decorators`
JUNG now requires version 3.1 of the commons-collections package (up from 3.0).

Bug Fixes

`GraphMLFileHandler`: tag parser now no longer calls `toLowerCase()` on output of `attrs.getQName()`, which caused problems with saving/restoring a graph (thanks to Damon for spotting this)
`VisualizationViewer.prerelax()` no longer emits messages to console
`SouthernWomen` sample: date format now specifies the US locale, so the applet can be run in places where this locale is not the default. (Thanks to Julien Kronegg for reporting this.)
`BarabasiAlbertGenerator`:

elapsed time now being calculated properly (had been incremented twice for the same operation)
now properly disallows self-loops
now properly allows parallel edges
probabilities (and therefore edge attachments) were not being calculated correctly; now all existing vertices have positive probability of being connected even if they have degree 0
now has a required parameter that specifies the correct number of initial "seed" vertices

`AbstractRanker`: fixed bug which resulted, for ranking algorithms that could rank either vertices, edges, or both (such as `BetweennessCentrality`), in the unexpected removal of vertex decorations.
`BetweennessCentrality`: wasn't re-initializing the decorations inside computeBetweenness(), so that if the vertex decorations were still there from a previous run, it would incorporate those values into the new calculations. This has now been fixed; the fix adds O(V+E) to the time required for the algorithm, but with the current `AbstractRanker` architecture this may not be avoidable.
`PajekNetReader`, `PajekNetFile`: fixed parsing bug relating to leading space on input lines (input lines are now run through `trim()` to remove leading/trailing whitespace)
`SimpleSparseVertex.findEdgeSet()` now correctly returns both directed and undirected edges if both exist (previously had only been returning one or the other)
replaced references to `biao.net` (old filename) with `simple.net`

Known Issues

`GraphStatistics.diameter()` returns the largest *finite* distance
`BiComponentCluster` appears to be broken (see forum message from Patrick Godeau)
`DirectionTransformer`: currently ignores parallel edges, if any; user data importing has some peculiarities (see documentation)

### 1.4.3 (Summer Solstice 2004)

New Features

New predicate: `ReciprocatedDirectedEdgePredicate` returns `true` if its input is a `DirectedEdge` `e1 = <u,v>`, and there exists a `DirectedEdge` `e2 = <v,u>` in the same graph (that is, if there exists an edge `e2` such that `e1`'s source is `e2`'s destination and vice versa; such edges are also known as antiparallel edges).

Bug Fixes

`PajekNet{Reader,Writer}` are now actually in the release, in the `jung.io` package. (This was mentioned in the 1.4.0 release notes (see below), but the files were not actually included in the collection of those in the release packages.)

Changes

`UserData.addUserDatum()` now rejects (with an IllegalArgumentException) attempts to add user data whose key value is null.
The website now contains only the most recent version of the documentation; browser requests for the old versions are redirected to the most recent version. (This is to prevent people accidentally connecting to old versions of the documentation when they access it via a search engine.) Older versions of the documentation are still available as one of the release files for the appropriate version of JUNG.
The constructors for `{Edge,Vertex}PredicateFilter` each can now take a plain `Predicate`; this allows these filters to accept compound predicates (such as those provided by commons-collections, for example: `AndPredicate`, `OrPredicate`, and `NotPredicate`).

### 1.4.2 (Memorial Day 2004)

Bug Fixes

The `Simple*SparseVertex` classes now properly prevent parallel edges from being attached to them.
`DirectedSparseVertex.findEdgeSet()` had a bug which has now been fixed; this had resulted in an error when `DirectedSparseVertex` was used in conjunction with a graph which disallowed parallel edges (such as the default configuration of `DirectedSparseGraph`.)
Alpha-level Prefuse support has graduated to a separate project, also to be released from jung.sourceforge.net. This means you don't need an annoying jar just to compile jung samples.
Updated SouthernWomenBipartite to use (and thus demonstate) the new KPartite infrastructure... It was a little bumpy at first, and 1.4.1 has errors in the transition. It should be fixed now.
However, before now, BipartiteGraphReader was producing BipartiteGraphs that couldn't be copied, because their userdata fields were not SHARED between instances. It is now fixed.

New Features

StringLabeller and GlobalStringLabeller contain support for removeLabel, which removes the label that had been there and returns the corresponding vertex. This allows you to set up a new vertex with an old label.

    		sl.setLabel( v1, "test" );
    		sl.removeLabel("test");
    		sl.setLabel( v2, "test" );

### 1.4.1 (A few days after Cinco de Mayo 2004: bugfixes and memory leaks)

Bug fixes: Memory leaks

Now prevents near-duplicate predicates from being added to the graph. In the previous version, when a graph was copied, the predicates it stored were copied--but a new set was created, too, in the initialize() method. Now predicates added in "initialize" should be tagged with "isInitializePredicate", which will prevent them from being copied.
Filters only keep a copy of their previous graph when assemble( true ) is called; the GraphAssemblyRecord is stored in userdata and is set on REMOVE, so it is not copied.
Vertices point to their graphs with a WeakReference. This means that if you are in the habit of hanging on to your graphs with just the vertex, it may go away on you; on the other hand, a stray vertex (fox example, in the GlobalStringLabeller) will not keep your graph from being garbage collected.

Bug Fixes: GraphDraw

SpringLayout is now compatible with dynamic graphs.
Generally, dynamic graphs are better handled within classic graphdraw: some functions are now synchronized; and it is now possible to find out whether the visrunner thread is running. See samples.addNodeDemo.
(Minor: Now arrows on self-loops only draw if self-loops are turned on.)

New Features

SparseTree implements a directed, rooted tree: getRoot() returns the root. It is implmeneted with constraints; every edge must point from a node to a node lower on the tree. Note that the tree allows for single isolated nodes in the graph; however, edges must be added DOWN the tree, from root downward.
Experimental support for creating prefuse graphs inline is now available. You can create your JUNG graph, filter and decorate appropriately, and then use the powerful Prefuse visualization system to view it. See `samples.prefuse`

Gotchas

Unfortunately, it is entirely too easy to create a predicate that knows its own graph. This is a potential problem when you copy the graph and the predicate with it--JUNG does not adjust where the "own" pointer points, so the predicate will be obsolete.

### 1.4 (Cinco de Mayo 2004)

New Features

Predicates

With this release, JUNG introduces the use of `Predicates` (a Jakarta Commons-Collections API interface). A `Predicate` tests whether an `Object` satisfies a specific implementation-defined property. Predicates may be logically combined using such Jakarta-defined predicates as `AndPredicate` (which returns true if all input predicates return true). JUNG uses `Predicates` (found in the `graph.predicates` package) for the following tasks:

defining constraints on edges and vertices added to a graph (=> graphs that only allow vertices with a certain decoration, or that only allow directed edges)
defining/creating edge and vertex subsets (create a subset of all vertices with label "student")
general testing for properties of edges, vertices, and graphs (is this graph connected?)

Note: Some predicates are unsuitable for use as constraints (and some predicates are only suitable for use as constraints). We have tried to make these distinctions clear in the documentation for each predicate. Users are strongly advised to read the documentation for a predicate before using it.
For more information on `Predicates` and their use, see the commons-collections website and the package documentation for the `predicates` package.

Constraints

Graph classes (implementations of ArchetypeGraph) now provide mechanisms for maintaining constraints on vertices and edges, each of which are specified by user-supplied criteria. Constraints specified must be satisfied by each vertex or edge added to the graph.
Thus, for example, a user can now create a k-partite graph (which consists of k disjoint sets of vertices, such that each edge connects vertices from distinct partitions; a bipartite graph is a 2-partite graph) by starting with a `SparseGraph` and adding specifications for vertex subsets (see Subsets/Partitions, below) and edge constraints.
Specifications for edge types that graphs can accept (e.g., undirected, directed, parallel) are now implemented in terms of these constraints. As a consequence, JUNG now supports mixed-mode graphs (graphs which contain both directed and undirected edges) and graphs with parallel edges (also known as multigraphs).
Two distinct edges are considered to be parallel to one another if the following conditions hold:

the edges are both directed or both undirected
if undirected, the incident vertex sets for each edge are the same
if directed, the edges each have the same source vertex and the same destination vertex

`SparseGraph`: new extension of AbstractSparseGraph, which, by default, imposes no constraints on its vertex and edge sets; it allows directed, undirected, and parallel edges.
`KPartiteGraph`: an interface which extends `Graph`, implementations of which must be k-partite graphs. (k-partite graphs consist of k disjoint sets of vertices, each of whose edges connects vertices from distinct partitions.)
`KPartiteSparseGraph`: an implementation of `KPartiteGraph` which extends `SparseGraph`; it optionally creates subsets for each vertex partition (see Subsets/Partitions, below).
A constructor is available that creates a new `KPartiteSparseGraph` from an existing `Graph` whose vertices and edges satisfy specified constraints. The new graph contains all the user data from the original graph and its components.
`BipartiteGraph` has not (yet) been formally deprecated, but it has essentially been superseded by `KPartiteGraph` and `KPartiteSparseGraph`.)
`PredicateUtils` is a new class that provides utility methods for dealing with constraints and subsets.

Subsets/Partitions

`SubsetManager`: allows users to create, remove, and access cached subsets of vertices and edges. The membership of each subset is specified by a `Predicate` (those vertices/edges that pass a given predicate are added to the corresponding subset). An instance of `SubsetManager`, when created, adds itself to the `UserData` of the constructor-specified graph (with key `ArchetypeGraph.SUBSET_MANAGER` and registers itself as a listener to this graph, so that it can update the memberships of the subsets as vertices and edges are added to and removed from the graph.

Transformers

`KPartiteFolder`: converts a k-partite graph into a 1-partite graph. (This is a generalization of `BipartiteGraph.fold()`.)
`DirectionTransformer`: provides methods (formerly part of `GraphUtils`) for converting graphs of one type to another (e.g., directed to undirected). The `GraphUtils.transform` methods have been deprecated.

`AbstractArchetypeGraph`: implements those methods of `ArchetypeGraph` which apply to all graph types (e.g., constraint management)
`BipartiteGraphReader`: Creates a `KPartiteGraph` (k=2, aka a bipartite graph) based on structured input from a Java `Reader`. Also provides partition-specific decoration methods.
The `SparseVertex` class was designed to support mixed-mode graphs with parallel edges. For the sake of efficiency, we have created several new vertex types (`[Simple][[Un]Directed]SparseVertex`) which are optimized for different combinations of directed, undirected, and parallel edges; graphs which use the most restrictive vertex type possible will be faster and require less memory.
`VertexGenerator`: an interface for vertex factories. Implemented by `TypedVertexGenerator`, which, given a graph's edge constraints, create a vertex of the most efficient implementation (of those listed above) that supports edges with those constraints.
EdgeStringer interface: returns a String for a given edge.

Changes

Graph.isDirected() is now deprecated (AbstractSparseGraph calls PredicateUtils.enforcesDirected())
getEquivalent{Vertex,Edge}() has been deprecated in favor of getEqual{Vertex,Edge}() to avoid confusion with the term "structural equivalence" from the field of social network analysis.
The distance-related methods have been refactored out of the `ShortestPath` abstract class into a new interface, `Distance`. These methods now specify that if the distance between two vertices cannot be calculated (for instance, because one is not reachable from the other for a graph-based distance metric), such a 'distance' should be represented as a null value.
This has resulted in a change of behavior for the `DijkstraShortestPath` and `UnweightedShortestPath` classes (which formerly used `Double.POSITIVE_INFINITY` and `-1`, respectively, to indicate unreachability).
Since `DijkstraShortestPath` no longer is required to generate distance values for unreachable vertices (see above), it tends to run considerably faster (and use less memory) if either of the following is true:

the graph is not (strongly) connected (that is, if not all vertices are reachable from the source vertex)
you are only asking for the closest k vertices to the source vertex.

`PajekNetFile` has been superseded by `PajekNetReader` and `PajekNetWriter`. These classes can read and write mixed-mode graphs, make available different modes of vertex labeling (depending on whether your labels must be unique), have a more general edge weight decoration interface than `PajekNetFile`, and are generally more robust (i.e., the Reader should be able to handle a wider variety of correctly formatted input than its predecessor).
`PajekNetFile` now takes a `Reader` instead of a `BufferedReader`.
Some bad calls (for example, trying to add a vertex to a graph that is already in that graph or another graph) now throw `IllegalArgumentException` rather than `FatalException`.
`ArchetypeVertex.getEquivalentVertex()` and `ArchetypeEdge.getEquivalentEdge()` have been renamed (deprecated) in favor of `getEqualVertex()` and `getEqualEdge()` respectively. This better reflects the fact that the `equals()` method respects the relationship described, and addresses the possible confusion with the term "structural equivalence" used in the social network analysis literature (and in the blockmodel code introduced in version 1.3).
`ToStringLabeller` now exists; it creates a StringLabeller that will read from the toString method of a vertex. Note that this is not settable.
`UserDataContainer` now supplies a `containsKey` method that returns true if the object's user data repository contains an item with this key.
`UserData` has been refactored to reduce its memory footprint.
EdgeStringer is a new interface for labelling edges with strings; the sample version is the EdgeWeightLabellerStringer, which returns a string for each edge.
KKLayoutInt added; this is a version of KKLayout that stores only integers. This should look similar; for some larger graphs, it may help economize on storage.
`AbstractSparseEdge.toString()` now returns a `String` of the following format: `E[id]([v1.toString()],[v2.toString()])`. (Previously the edge's ID was not part of the string; `toString()` can now distinguish between different parallel edges.)
`GraphUtil` methods `translateAll` and `translateAllEdges` have been deprecated and replaced by `getEqualVertices` and `getEqualEdges`, respectively.

UI and GraphDraw changes

`GraphDraw`: By default, now HIDES the status bar; call `showStatus()` to show it.
VisualizationViewer now guarantees that edge (x1, y1 x2, y2) order sent to the renderer is (front, back)
`SettableRenderer` improved:

By default, the SettableRenderer now draws small squares, and puts the text label on the side. (You may call renderer.setLightDrawing( false ) to restore this)
SettableRenderer now draws self-loops when appropriate (change with setShouldDrawSelfLoops)
... and arrows for directed edges (call setShouldDrawDirectedArrows)
... but no arrows for undirected edges (call setShouldDrawUndirectedArrows to change)
It labels edges with an "EdgeStringer" interface, which returns a String for each edge. You may return a number with the EdgeWeightLabellerStringer.
All methods are protected; it should be easy to override.

new Arrow class draws arrows pointing to vertices at the ends of edges.
EdgeThicknessFunction now returns a `float` rather than `an int`. This is a change in behavior, and may require some classes to be (slightly) rewritten.

NewGraphDraw changes

samples.preview_new_graphdraw is still in preview (but moving toward beta fast). There's a new architecture since the last time:

An EmittedLayout stores (x,y) locations for vertices
A StaticLayout can initialize locations based on an input dimension and a Graph object. This is the right choice for iniital locations (e.g. CircleLayout) and for reading in a layout from disk.
An IterableLayout can be initailized with a first position, called with emit() to get the current state, and can be called with advance() to move it forward. This divorces the calculation step from the coding step, and so accelerates offscreen pre-iteration.
A Transformer modifies an EmittedLayout to (for example) force it to the size of a diagram, or modify all vertices or edges in a particular way.
An EdgeRenderer or VertexRenderer draws a layout on screen.

The user may invoke a LocalGraphDraw with new LocalGraphDraw( Graph, StaticLayout, [IterableLayout,] VertexRenderer, EdgeRenderer) or may construct the elements on their own. They may extract the JPanel within it, by calling localGraphDraw.getPanel() and add that to a UI. The use of the StaticLayout at start ensures that there can be a deterministic view of the network.
We provide several interesting systems to demonstrate the power of this approach:

`IterableFromStaticEmittedLayout` is a StaticLayout shows what happens with a layout after it has terminated. (This, it is not necessary to watch animation on screen: it jumps to the fully-laid-out mode.)
`IterableToStaticLayout` does something similar, although it starts from a StaticLayout.
`InterpolatingIterableLayout` iterates from one EmittedLayout into another.
`WrappedIterableLayout` runs one iterable layout until it has concluded, then runs another for several frames.
`UnmovingIterableLayout` simulates an IterableLayout, but doesn't move.

Bug Fixes

`GraphUtils.translateAll()` and `translateAllEdges()` were storing a 'null' in the set of values returned if one of the vertices/edges in the input set did not have an equal vertex/edge in the target graph. This has been fixed.
AbstractSparseVertex now has a working implementation of findEdgeSet
`PajekNetFile.load()` no longer incorrectly rejects .net files that contain both an "*Arcs" and an "*Edges" specification (although it does not read mixed-mode graphs; see below).

Known Issues

`PajekNetFile.load()` does not correctly handle mixed-mode graphs; they are interpreted as either strictly directed or strictly undirected. (As noted above, `PajekNetFile` has been superseded by `PajekNetReader` and `PajekNetWriter`.)
`PajekNetReader` does not currently correctly interpret arcs or edges in list form.
`BipartiteGraphReader` can load directed graphs, but only those that have directed edges that go from vertices in partition A to those in partition B. (The format cannot represent directed edges that go the other way.)

### 1.3.0 (Washington's Birthday 2004)

New Features

Blockmodel code supports Structural Equivalence, and the ability to collapse sets of equivalent vertices.
Classic Visualization system now supports mouse clicks (with GraphMouseListener) and layouts that can change on the fly (with LayoutMutable)
Some methods and fields in visualization modified to be protected instead of private.
Preview visualization system now supports FitOnScreenLayout
`DijkstraShortestPath`: new methods allow the paths to be extracted. Includes some code contributed by Christoph Schmitz.
`ShortestPath`: new abstract class for shortest path algorithms covers DijkstraShortestPath and UnweightedShortestPath.

Bug Fixes

`DijkstraShortestPath`: fixed bug in vertex distance comparisons that caused distances to compare equal when they differed by less than 1. Courtesy of Christoph Schmitz.
Bug fix to GraphML
Bug fix to UnweightedShortestPath
BetweenessCentrality now works for directed graphs.

Changes

Documentation for Vertex.findEdge() has been updated to clarify its function on directed edges, and now reads, in part:

> `Returns a directed outgoing edge from this vertex to `v`, or an undirected edge that connects this vertex to `v`. (Note that a directed incoming edge from `v` to this vertex will not be returned: only elements of the edge set returned by `getOutEdges()` will be returned by this method.)`

JUNG now requires version 3.0 of the commons-collections library and version 1.0.3 of the CERN COLT library. (Previous versions have known bugs which impact the JUNG routines.) See this for information on how to get these libraries.
SimulatedAnnealer removed temporarily from release: please contact us if you need it back. Still available from CVS repository under scratch.scott.optimization

### 1.2.0 (Julian Christmas 2003)

New Features

Added file I/O support for ascii matrices
Preliminary Hypergraph support available (for graphs where mutable edges can touch multiple vertices); while they cannot be used for layout, visualization, or most algorithms, the data can be stored. See Hypergraph and HypergraphBPG
Graph event infrastructure added
New layout algorithms contributed: `CircleLayout`, `KKLayout`, `DAGLayout`

> Note that these algorithms are not fully tested, and may be quirky. In particular, KKLayout is known to have some irregular difficulties when changing between layout algorithms; CircleLayout and KKLayout do not fully respect filters. We felt that they are important enough additions to add to the project anyway, and placed them in a subpackage under visualization, "contrib".

New graph generation algorithms added: `ErdosRenyi` (contributed), `SimpleRandom` (contributed), `BarabasiAlbertGenerator`, `Lattice1DGenerator`, `Lattice2DGenerator`
New contributed save routine for GraphMLFile
Incident vertices of an `AbstractSparseEdge` can now be accessed with `getEndpoints()`, which returns a `Pair`.
`GraphUtils.equivalentGraphs(g1, g2)`: returns true iff each vertex and edge in `g1` has an equivalent in `g2` and vice versa.
`Vertex.findEdgeSet(Vertex)`: returns all edges that connect these two vertices as a `Set` [hook for parallel edge support]

Previews

`samples.graph.southern.BipartiteFile` reads in bipartite files.
`samples.preview_new_graphdraw` previews a new framework for visualizing graphs.

Changes

`addDirectedVertices` and `addUndirectedVertices` in GraphUtils now just forward their requests to `addVertices`. The former methods will be removed shortly.
BipartiteGraph now requires BipartiteVertex as well as BipartiteEdge.
refactored `AbstractSparseEdge`, `AbstractSparseGraph` to use edge IDs to define equivalence

added `getEdgeById()` [internal method] and corresponding data structure `mEdgeIDs`
note: this means that edge equivalence is now defined in the same way as vertex equivalence: two edges are equivalent iff one is a copy of (an ancestor-by-copy of) the other. This provides a more consistent definition of equivalence, and enables the support of parallel edges in a future release.

renamed `AbstractSparseGraph.mVertexLookupTable` to `mVertexIDs`
moved down in the hierarchy from `ArchetypeGraph` to `Graph`

        removeVertex(ArchetypeVertex) -> Graph.removeVertex(Vertex)
        removeEdge(ArchetypeEdge) -> Graph.removeEdge(Edge)
        addVertex(ArchetypeVertex) -> Graph.addVertex(Vertex)
        addEdge(ArchetypeEdge) -> Graph.addEdge(Edge)

refactored out `AbstractSparseGraph.registerVertexID()` back into `addVertex()`
`AbstractSparseEdge.copy()` now uses `clone()` to create new edge rather than `GraphUtils.addEdge()`
`AbstractSparseGraph.mVertices` and `mEdges` are now `HashSets`, not `LinkedHashSets`
Fixed test cases for probabilistic algorithms `TestEppsteinPowerLawGenerator() and TestSimulatedAnnealer` now uses `clone()` to create new edge rather than `GraphUtils.addEdge()`
`AbstractSparseGraph.mVertices` and `mEdges` are now `HashSets`, not `LinkedHashSets`

Deleted

`removeAll*Edges()` signatures in `Vertex` and `ArchetypeVertex`, and corresponding methods from `AbstractSparseVertex` (`removeAllIncidentEdges()` was moved into the deprecated `*DirectedSparseVertex classes`, to avoid breaking existing user code that might be using it)
`ArchetypeVertex.setEquivalentTo()` [had been commented out]
`AbstractSparseEdge get{From, To}_internal` (superseded by `AbstractSparseEdge.getEndpoints()`)
`AbstractSparseVertex.wipeVertex()` (replaced with existing `AbstractSparseVertex.initialize()`)
`GraphUtils.getLabel(StringLabeller, Vertex)` (use `StringLabeller.getLabel(Vertex)` instead)

Bug Fixes

StringLabeller's ctor is now protected, so users can create their own if they want.
GraphUtils.copyLabels() now stores vertices from the target graph in the target StringLabeller.
Added unit test for `BipartiteGraph.copy()`--and modified the graph heavily, as a result.
The check for parallel edges has been moved from the `AbstractSparseEdge` constructor into `AbstractSparseGraph.addEdge()`. This will have no effect on code that does not create orphaned edges, but will do a better job of enforcing the no-parallel-edge restriction than previous versions.
replaced, in `AbstractSparseEdge.copy()` and `AbstractSparseVertex.copy()`:
`if (newGraph == this) --> if (newGraph == this.getGraph())`
visibility of (`DirectedEdge.get{Source, Dest}, Edge.getOpposite(), ArchetypeEdge.copy()`, and most of `ArchetypeVertex`) are now public (were package-visible)
`AbstractSparseGraph.removeVertices()`: now does not operate directly on set given to it, but on a new HashSet made from it
removed dependence on vertex set ordering from `TestPajekNetFile`, `GraphMatrixOperationsTest`

Known Issues

The behavior of the following methods is undefined if the invoking object and the parameter are not elements of the same graph: `ArchetypeEdge.isIncident(ArchetypeVertex)`, `ArchetypeVertex`: `isIncident(ArchetypeEdge)` and `isNeighbor(ArchetypeVertex)`, and `Vertex`: `isPredecessorOf(Vertex)`, `isSuccessorOf(Vertex)`, `isSource(Edge)`, and `isDest(Edge)`.

### Version 1.1.1 (Interim Release, Thanksgiving 2003)

New Features/Changes

Jars are now named as jung-1.1.1.jar: be sure to delete your previous version from your classpath, or rename this to jung.jar to overwrite.
`SparseVertex` is the new canonical type for the Vertex implementation. `Directed` and `UndirectedSparseVertex` are now deprecated (and will show as such when you compile). The result of this is that a Vertex no longer cares whether it is directed or not; indeed, it may have both directed and undirected edges attached to it (in which case, Graph.isDirected() will throw an exception).
Thus, vertex "directionality" has been eliminated:

new class `SparseVertex`: replaces now-deprecated `DirectedSparseVertex` and `UndirectedSparseVertex`
`GraphUtils.addVertices()` now correct `GraphUtils` method to add multiple vertices to a graph (other `add*Vertices()` methods deprecated)

`BipartiteGraph.getPartition(Vertex)` returns the partition of a vertex in a `BipartiteGraph`
`SettableRenderer` now no longer kills a GraphDraw process if it can't find a StringLabeller associated with the graph; rather, it draws a "?" on the vertex.
`DijkstraShortestPath` can now control whether results are cached or not (constructor and new method `enableCaching`)
It is now possible to terminate a `Relaxer` thread inside a `VisualizationViewer` with `GraphDraw.stop()` or `VisualizationViewer.stop()`.
`DropSoloNodeFilter` can now be extended.
new counting methods for vertices:

`ArchetypeVertex.numNeighbors()` returns the number of neighbors that the vertex has

`Vertex.numPredecessors()` and `numSuccessors()` return the number of predecessors and successors that the vertex has.

Bug Fixes

documentation for PageRank and PageRankWithPriors now correctly states time complexity
BipartiteGraph: getAllVertices(): now throws if given invalid partition
getPartition(): new method, returns partition of a given vertex
addVertex(): now throws if vertex has already been inserted; error message depends on partition selected

Known Issues

GraphDraw is still hard to control (especially in getting events in and out, and for handling objects that are not dots connected by straight lines); the entire mechanism is being replaced.
Decorators are still being improved; the mechanism may shortly be modified.

### Version 1.1

New Features/Changes

added new community finding algorithm: ExactFlowCommunity
added two new node betweenness algorithms: RandomWalkBetweenness and RandomWalkSTBetwenness
added new graph generator to generate small world networks using Watts' beta model: BetaSmallWorldGenerator
Added min-cut edge retrieval to EdmondsKarpMaxFlow
Added directed to undirected graph transformations in GraphUtils
modified GraphMatrixOperations.graphToSparseMatrix method to support adjacency matrices
added GraphMatrixOperations.computeVoltageMatrix
added new method GraphMatrixOperations.createVertexDegreeDiagonalMatrix
ArchetypeVertex (and subclasses): renamed isNeighbor() to isNeighborOf() (for similarity with isPredecessorOf() and isSuccessorOf() )
DijkstraShortestPath

caches results in class, does not decorate vertices
map returned is ordered by distance to source
calculation of k nearest vertices
incremental calculation (uses old partial results as a starting point)
constructor now takes NumberEdgeValue
allows early termination when distance to target vertex found

BipartiteGraph

new data structure for bipartite graphs
provides a method `fold()` which converts bipartite graphs to general binary graphs

Bug Fixes

Fixed GraphStatistics.clusteringCoefficients
Fixed EppsteinPowerLawGraphGenerator
Remove LinkedHashSet order dependency for TestBFSDistanceLabeller and TestExactFlowCommunity
AbstractSparseVertex.copy() now throws IllegalArgumentException if source and destination graphs are the same (was: FatalException)
AbstractSparseEdge.copy() now throws IllegalArgumentException if source and destination graphs are the same (previously: not checked)
AbstractSparseGraph.removeVertex(): vertex ID was not being removed from hash table
DijkstraShortestPath now works (reimplemented; see above for new features)

New Documentation

algorithms.cluster: definitions of "biconnected", "betweenness", and "weakly connected" have been added
io.PajekNetFile: changed documentation so that it specifies that vertices must be specified in order from 1 to n
added another example to GraphMLFile
StringLabeller, EdgeWeightLabeller, Indexer corrected and enhanced. Decorator clarifies the role and location of its storage because it deeply affects what happens when you add or remove vertices.

Known Issues

decorators

offset tag for values > 0 may be dangerous, and must be used with caution
StringLabeller expects unique labels. This may not always be what you want.

utils

GeneralUtils, UserDataUtils: no docs
docs of CopyAction.{Clone, Remove, Shared} incorrect: they do not implement UserData.{CLONE, REMOVE, SHARED}, but are classes of which the latter are instances
docs of UserData.SHARED: confusing. Code examples are best laid out in lines rather than all on the same line, and an example that actually uses UserData would be better.
docs of UserData.REMOVE: "useful for temporary userdata that isn't used"? (Huh?)

samples

BasicRenderer has no Javadoc

graph.impl

lack of type safety in addEdge/Vertex, edge constructors, ...