Bug Fixes
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.
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):
VertexIconFunction
Icon
for this vertex, that icon is painted
otherwise, the Shape
for this vertex is painted
Shape
for this vertex is painted.
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.
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.
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):
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
:
getLastOutsideSegment
.
Fixed GeneralPath
typecasting problem that can occur with Java6.
GradientEdgePaintFunction
fixed so that loop edges no longer vanish.
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.)
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
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:
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
HyperbolicTransformer
.
AbstractLayout
:
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.
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.
Changes
KKLayout
now
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.
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).
New Features
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 calledGraphDraw
has been deprecated. See the aforementioned
Visualization Guide for pointers on how to create JUNG visualizations using
VisualizationViewer
directly.
Transformers
Transformer
interface. Available transformations include:
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
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
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:
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.
Edge
shapes were already cached in version 1.6.0
HasShapeFunctions
interface implemented by PluggableRenderer
.
VertexShapeFunction getVertexShapeFunction()
EdgeShapeFunction getEdgeShapeFunction()
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
Coordinates
classBirdsEyeVisualizationViewer
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.
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
Hypergraph
is a set of hyperedges and hypervertices
with certain operations defined on it. Currently we have one implementation of
Hypergraph
: SetHypergraph
.
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.
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.
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.)
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.
GraphUtils
methods:
{add,remove}{Vertices,Edges}({Graph,Hypergraph}, Set)
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)
getVertexGenerator(ArchetypeGraph)
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:
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.
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).
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, 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
.
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
EdgeShapeFunction
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
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
.
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:
PopupGraphMouse
class
that shows popup menus over vertices.
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.
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
.
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.
VisualizationViewer
changes
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.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
GraphDraw
:
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.
New Features
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).
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. 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.
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
.
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).
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.
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.
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
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.
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
.
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.
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
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)
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
:
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.
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).
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
:
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
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)
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).
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.)
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
).
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.
sl.setLabel( v1, "test" );
sl.removeLabel("test");
sl.setLabel( v2, "test" );
samples.prefuse
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:
Predicates
and their
use, see
the
commons-collections website and the package documentation for the predicates
package.
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).
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).
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.
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.
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.
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.
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:
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.
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:
float
rather
than an int
. This is a change in behavior, and may
require some
classes to be (slightly) rewritten.
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).
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.)
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.
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.
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
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]
samples.graph.southern.BipartiteFile
reads in
bipartite files.
samples.preview_new_graphdraw
previews a new
framework for visualizing graphs.
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
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.
AbstractSparseGraph.mVertexLookupTable
to mVertexIDs
moved down in the hierarchy from ArchetypeGraph
to Graph
removeVertex(ArchetypeVertex) -> Graph.removeVertex(Vertex)refactored out
removeEdge(ArchetypeEdge) -> Graph.removeEdge(Edge)
addVertex(ArchetypeVertex) -> Graph.addVertex(Vertex)
addEdge(ArchetypeEdge) -> Graph.addEdge(Edge)
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)
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
ArchetypeEdge.isIncident(ArchetypeVertex)
,
ArchetypeVertex
: isIncident(ArchetypeEdge)
and
isNeighbor(ArchetypeVertex)
, and Vertex
:
isPredecessorOf(Vertex)
, isSuccessorOf(Vertex)
,
isSource(Edge)
, and isDest(Edge)
.
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:
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.
fold()
which converts
bipartite graphs to general binary graphs