jrtom/jung

JUNG: Java Universal Network/Graph Framework

jung's Issues

JUnit should be a test dependency, not a compile one

When I import JUNG 2.1 into my Gradle project and review my dependencies in IntelliJ, I notice that JUnit 3.8.1 is imported by JUNG as a compile dependency. I believe this should be made a test dependency, because otherwise it gets imported into my project's build artifacts when I don't actually need it.

For my own project, I'm currently working around this by excluding JUnit 3.8.1 from my project's transitive deps as follows:

dependencies {
  compile("net.sf.jung:jung-graph-impl:2.1") {
    exclude group: 'junit', module: 'junit'
  }
}

I did a quick search of the JUNG codebase, and it seems to me this should be a simple fix of changing pom.xml so that the dependency:

...
<dependencyManagement>
   <dependencies>
     <dependency>
       <groupId>junit</groupId>
       <artifactId>junit</artifactId>
       <version>${junit.version}</version>
     </dependency>
     ...

is changed to:

...
<dependencyManagement>
   <dependencies>
     <dependency>
       <groupId>junit</groupId>
       <artifactId>junit</artifactId>
       <version>${junit.version}</version>
       <scope>test</scope>
     </dependency>
     ...

Font in JUNG labels and tooltips don't support CJK character sets

What steps will reproduce the problem?
1. Run edu.uci.ics.jung.samples.UnicodeLabelDemo sample
2. Replace current vv.setVertexToolTipTransformer() method with 
vv.setVertexToolTipTransformer(new UnicodeVertexStringer<Integer>(v));

What is the expected output? What do you see instead?
1) Expected text on the label and the tooltip for China flag: "欢迎使用  
JUNG!" 
2) Expected text on the label and the tooltip for  Japan flag: 
"JUNGへょぅこそ!"

What version of the product are you using? On what operating system?
JUNG2 (2.0.1) Windows XP SP3 with JRE 1.6.0_31

Please provide any additional information below.

I suspect that Swing JToolTip in JUNG viewer is set with the default Swing font 
that doesn't support all Unicode characters. The best is to expose a way for 
JUNG to change the font used in the tooltip.

Original issue reported on code.google.com by [email protected] on 30 Mar 2012 at 9:29

Unexpected behavior with EditingGraphMousePlugin using ObservableGraph

Setup: I'm trying to use do some editing using the standard EditingGraphMousePlugin on a visualization that is backed by an ObservableGraph to a DirectedSparseMultigraph. The initialization is roughly this:
private final DirectedGraph<QueryNode, QueryEdge> graph = new DirectedSparseMultigraph<>();
private final ObservableGraph<QueryNode, QueryEdge> observer = new ObservableGraph<>( graph );
private final Layout<QueryNode, QueryEdge> vizlayout = new StaticLayout<>( observer );
private final VisualizationViewer<QueryNode, QueryEdge> view = new VisualizationViewer<>( vizlayout );

Problem: EditingGraphMousePlugin::mousePressed checks to see if the underlying graph (in my case, the observer) is Directed, and if not the edge type is set to UNDIRECTED. However, UNDIRECTED edges cannot be added to my delegate graph.

Possible Solution 1: EditingGraphMousePlugin should check if the underlying graph is actually an observer, and if so, use it's delegate to determine edge type.

Possible Solution 2: EditingGraphMousePlugin should delegate to EdgeSupport to determine edge types if possible.

Get rid of redundant Layout implementations

We don't need SpringLayout and SpringLayout2, nor FRLayout and its twin.

There may also be other Layout implementations that we want to retire.

Support attribute type for GraphML export

Hi,

I'm using Gephi to debug my generated graphs. Therefore I export the graph to the GraphML format with the GraphMLWriter. It would be nice if each data key can get an attribute type. Gephi uses these attribute types for sorting and other purposes.

Example current export:

<?xml version="1.0" encoding="UTF-8"?>
<graphml [...]>
  <key id="weight" for="node">
    <desc>Weight</desc>
    <default></default>
  </key>
  [...]
</graphml>

Example required export (node the attr.type attribute of the key):

<?xml version="1.0" encoding="UTF-8"?>
<graphml [...]>
  <key id="weight" for="node" attr.type="double">
    <desc>Weight</desc>
    <default></default>
  </key>
  [...]
</graphml>

Best regards,
Jens

NullPointerException “AWT-EventQueue-0” labelVertex(BasicVertexLabelRenderer.java:84)

Minimal example. I use Scala so excuse me)

import java.awt.Dimension
import javax.swing.JFrame

import edu.uci.ics.jung.graph.util.EdgeType
import edu.uci.ics.jung.algorithms.layout.StaticLayout
import edu.uci.ics.jung.graph._
import edu.uci.ics.jung.visualization.{BasicVisualizationServer, GraphZoomScrollPane, VisualizationViewer}

object GrViz {

private var svg = new SparseMultigraph[String,String]

def add(t: String, str: String, str1: String): Unit =
{
svg.addEdge(t, str,str1, EdgeType.DIRECTED)
}

def show_model {
add("t","a","b")
show
}

def show{
var layout = new StaticLayout(svg);
layout.setSize(new Dimension(800, 600));

var vv = new BasicVisualizationServer[String,String](layout);
vv.setPreferredSize(new Dimension(350,350)); //Sets the viewing area size

var frame = new JFrame("View");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.getContentPane().add(vv);
frame.pack();
frame.setVisible(true);

}
}

Create events only when necessary

Admittedly, one purpose of this issue is to just mention that it's great to see that someone takes the lead on further development of JUNG. It's a really powerful library that easily allows creating a nice graph visualization quickly, and still offer configurability for more sophisticated tweaks. I hope that I can allocate some time to have a closer look at the refactorings that are leading towards JUNG 3.0, and maybe post some thoughts about the design choices.

Now, to the point that this issue is actually about: It's comparatively minor, but may become relevant for large and/or very dynamic graphs: In addEdge and addVertex of https://github.com/jrtom/jung/blob/common.graph/jung-api/src/main/java/edu/uci/ics/jung/graph/ObservableNetwork.java#L67 , the event is generated even if it is not used. Changing

if (state) { ... }

to

if (state && !listenerList.isEmpty()) { ... }

would avoid the creation of garbage events.

---

Beyond that, I could point out (many) other minor issues, like

• The event class should extend EventObject
• The event class could be final
• The fields could be final
• ...
• General: Missing @Override annotations in some classes
• Broken indentation

but I just had a short glance at the code, and this sort of nitpicking may not be appropriate....

Remove bogus Maven POMs

these include:

• jung/jung-graph-impl/src/main/java/pom.xml
• jung/jung-visualization/src/main/java/pom.xml
• jung/jung-io/src/main/java/pom.xml
• jung/jung-samples/src/main/java/pom.xml

These look like accidental copies of the top-level pom.xml files located in the top-level subproject directories (jung/subproject/pom.xml). They probably don't hurt anything but AFAIK they're unnecessary and somewhat confusing.

TreeLayout neither implements reset(), nor calls it when setting a new graph

TreeLayout requires a non-null graph as an argument to its constructor. Thus the setGraph() method can only be intended for changing the graph post initialization. This clearly entails cleaning out the positions of the nodes from the old graph.

I propose adding the following implementation of reset(), and then calling reset() instead of buildTree() in the setGraph() method:

public void reset() {
    basePositions.clear();
    locations.invalidateAll();
    alreadyDone.clear();
    buildTree();
}

Refactor GraphMLReader2

See comments in #47:

• The constructors should be able to share almost all their code.
• The init() method should be more defensive in design: right now it will throw if both inputStream and fileReader are null. (Ideally, in fact, perhaps at least that aspect of the initialization that init() does could be moved into the constructors so that we wouldn't need to have an if-else at all.)

PluggableRendercontext does not properly reset EdgeShape

When setting a new graph on a model/layout/visualizer it would be expected that this works correctly. Unfortunately EdgeShape keeps a reference to the original graph and attempts to use that to determine whether there is a loop (and fails). A workaround is to manually reset the edgeshapetransform on the pluggablerendercontext after setting the graph.

The Kotlin code below shows the problem (and the workaround), I'd like to get rid of the last two code lines.

var graph: Graph<MyVertex, MyEdge> = graph
   set(value)
   {
      field = value
      graphViewer.graphLayout = FRLayout(graph)
      // Hack as edgeshape is broken in that it keeps a reference to the previous graph
      graphViewer.renderContext.edgeShapeTransformer = EdgeShape.quadCurve(graph)
    }

What to do with "internal implementation detail" classes and other "utils" classes?

@jrtom Currently, there are a number of classes in JUNG which seem to be either internal implementation details which nonetheless have the public modifier, meaning JUNG users can use them as well; or which look like they were designed specifically for JUNG but may be useful in a more general sense and could be part of the "endorsed" public API.

Two classes come to mind:

1. edu.uci.ics.jung.algorithms.util.BasicMapEntry: it seems that this class is just a simple implementation of Map.Entry and is only used by DijkstraDistance, so it looks to be just an implementation detail, despite it being a public type. In this case, it could simply be replaced with AbstractMap.SimpleImmutableEntry or Guava's Maps.immutableEntry().
2. edu.uci.ics.jung.algorithms.util.MaxBinaryHeap: this seems like a potentially generally useful collection class. Might it be worth moving into its own separate package e.g. edu.uci.ics.jung.collect, and perhaps into its own module (jung-collect)?

There may very well be other classes like these two that deserve this sort of attention as well.

One possible way of treating such classes, if we still find them useful, would be to move them into appropriate internal subpackages, and state in the README.md or elsewhere that all classes in subpackages with the name internal are implementation details and may go away in future releases. This would reduce the likelihood of people depending on those classes, giving us a bit more room to organise the code base better.

Bron Kerbosch Clique Finder Algo

I attached both a test file and the code. The algo used is 
http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm. Let me know if I 
need to make any changes before commit.

Reuben

Original issue reported on code.google.com by [email protected] on 24 Apr 2011 at 3:38

Attachments:

• BronKerboschCliqueFinder.java
• BronKerboschCliqueFinderTest.java

designing Layout for JUNG 3.0: types and type parameters

tl;dr: as the lead JUNG designer, I'm looking for feedback on how we should handle this particular issue. Please comment if you have thoughts on this subject.

As it currently stands in JUNG 2.x, the Layout<V, E> interface has two type parameters: V for nodes and E for edges.

However, Layout doesn't actually operate on anything relating to edges; it only specifies node positions. So, with one exception, there's nothing about it that should require an edge type parameter.

The catch is that Layout also provides a getGraph() method that returns the graph whose node positions are specified by the Layout. This is the reason why it's historically needed the E parameter: so that the type returned by getGraph() could be fully parameterized as a Graph<V, E>.

JUNG 3.0 will replace the JUNG graph types with Guava's common.graph types: Graph<N>, ValueGraph<N, V>, and Network<N, E>. Network has an asGraph() method which returns a Graph<N> (and ValueGraph<N, V> likely will have asGraph() as well once the dust settles).

For the moment, the visualization system will probably still operate on Networks (which are the closest analog to the JUNG 2.x Graph type). But we'd like to leave the door open for being able to use this visualization system to handle other graph types.

To sum up: Layout needs N for actually laying out nodes, but it only needs an edge type parameter (E or V) in order to be able to return a fully-specified Network or ValueGraph.

I see a few possibilities; there may be others.

(1) Layout keeps an edge type parameter, and supports hanging onto (and providing) a reference to its graph:
(1a) for Network only, i.e., getGraph() returns Network (status quo, essentially)
(1b) for Graph, ValueGraph, and Network (separate getGraph(), getValueGraph(), getNetwork() methods, only one of which will work for any given layout instance)

(I thought about (1c), which would introduce a generic graph type, something like Layout<G<N, E> extends Object, N, E>, such that Layout::getGraph() would return G, but that appears to break down for Graph<N>.)

(2) Layout gets rid of its edge type parameter and no longer provides a getGraph() method.
Instead of taking a graph as its input, it would take a Set<N> (or possibly an Iterable<N>).

(3) Create separate subtypes of Layout: NetworkLayout, GraphLayout, etc. These then would each provide their own getGraph() methods with appropriate return types. (You might also want a convenience method to provide the type, so as to help the user avoid repeated instanceof calls.)

(1a) works but doesn't get us any closer to resolving the underlying issue that we'd like to support other graph types for visualization.

(1b) would be kind of a mess: you'd have to have two methods for each supported graph type (one for specifying the graph in the construction and one for providing it), plus (perhaps) an extra convenience method to tell you which type of graph was actually being operated on (so you'd know which query method to call).

(2) works, but at the cost of refactoring the visualization system so that the layout isn't the object that's responsible for providing the graph reference as needed. It also means that the connection between the layout and the graph would be lost, which seems unfortunate.

(3) works, but feels like it makes the layout type more complex than I'd like (and the visualization system, likewise).

I'm leaning towards (2) at the moment, but I'm open to other ideas, and I'd be interested to know what other people think.

MinimumSpanningTree-related issues

• MinimumSpanningTree generates directed graphs (for interoperation), but they should be undirected
• TreeLayout’s rendering of the MSTs in MinimumSpanningTreeDemo seems a bit odd (upside down and rectilinear)

clean up use of Visualization* types in jung-visualization

This mostly boils down to using VisualizationServer (interface) or VisualizationModel in place of VisualizationViewer (class) where possible.

TreeLayout throws a NPE when laying out an empty tree

When TreeUtils's getRoots() method is called on an empty tree, it returns a collection containing null rather than an empty collection. This propagates though buildTree() and calculateDimensionX() in TreeLayout, eventually resulting in a NullPointerException (see test).

If this is indeed the intended behavior of getRoots() then it becomes necessary to filter out null roots recieved in buildTree(). For example:

Collection<V> roots = new ArrayList<V>();
for (V v : TreeUtils.getRoots(graph)) {
    if (v != null)
        roots.add(v);
}

BalloonLayout also relys on getRoots(), and also requires the same sort of filtering to avoid an exception.

Alternately, one could modify getRoots() to only return legitimate root vertices. This may be the more elegant solution, but it does change the public API.

Attachments (test cases and fixes using the above filtering):

• TreeLayout.java

• TestTreeLayout.java

• BalloonLayout.java

• TestBalloonLayout.java

Swing Interface

Hi,

some years ago I developed a simple graph program using Jung 2.0.1 for showing some new graphs algorithms. The program allows a user to draw a graph, edit node/edge properties and run some checking algorithms.

I would like to update the program to Jung 2.1.1.
I checked the notes of 2.1.0 version and changed interfaces/library accordingly, but this is not sufficient to have the update.
It seems that the Swing interface has been changed in other aspects.
Is there a guide/tutorial/howto about the new visualization module architecture of the library in order to make easier the update of programs based on the 2.0.1 visualization version?

Thanks,
Roberto

Multiple viewers for multiple graphs within a common frame.

This is probably easy but currently the viewer displays in the content container of a JFrame. I would like to have multiple vv's displaying in separate panels of a single JFrame I tried replacing the JFrame with a JPanel but got nothing. I do not have a deep understanding of awt so I'm probably missing something but would it be possible to enable this feature?

PluggableRendererDemo known issues

The following items don't work:

• vertex stretching
• displaying voltages (values seem incorrect)
• filter when degree < 4 includes a node with what looks like a single self-loop
  • but maybe this is the parallel edge thing being busted again
• enabling/disabling vertex size by voltage
• changing edge shape
• edge gradients (aren’t the edges undirected?)

Audit dependencies

• jung-io still claims a dependency on COLT. Remove it.
• Bump up Guava version to 19.0 once we have resolved the TODO in PersistentLayoutImpl.java

Barabasi-Albert Probability Calculation Wrong

I believe the Barabasi-Albert generator may be incorrect in its probability assignments (both in this and in previous versions of JUNG). Whilst it is noted in the docs that a Lagrangian smoothed version of the original formula is used I believe this still has the issues contained.

The docs state that the original formula proposed by Barabasi and Albert is p(v) = deg(v)/|E| but this is incorrect. The original formula is p(v) = deg(v)/(sum deg(v) for all v) which, via the Handshake Lemma, becomes p(v) = deg(v)/2|E|. This scaling means the probabilities no longer sum to 1 over all vertices.

Similarly, the equation actually utilised has the same issue; whilst the numerator uses degree the denominator uses |E| which once again means that the numerator is scaled compared to the denominator and produces total probabilities exceeding 1.

Unless I'm missing something, this is problematic. Whilst it might still produce graphs exhibiting scale-free properties I cannot state this for sure.

DelegateTree's removeVertex method doesn't properly handle removal of the root

I have a use case where I would like to empty an existing DelegateTree and add a new root vertex. However, the removeVertex() method does not set the root field to null when called to remove the root vertex. Because addVertex() will throw an exception if the root field is not null, this means that addVertex() can never be used to set a new root even after the original root has been removed. The fix is very simply to add

if (root != null && root.equals(vertex)) {
    root = null;
}

to removeVertex().

I can understand a school of thought that says that we don't handle empty trees, and that replacing the root should involve the creation of a new tree. (This would be inconvenient for my use case, but it would be an understandable position.) However, this isn't consistent with the the rest of DelegateTree. First, DelegateTree has constructors that allow the creation of empty trees. Second, and more damning, removeVertex() is currently fine with removing the root vertex from the delegate and removing the stored depth of the root vertex. This leaves the DelegateTree in a corrupted state where getRoot() will still return a reference to the removed vertex, even though the rest of the object will behave as if it is no longer present in the tree.

Add proper LICENSE/AUTHORS/CONTRIBUTING.md files to ease external contribution.

"vertex" -> "node"

The new term of art is "node", so replace "vertex" with "node" (and "V" where it refers to a node type with "N").

EdgeShape.cubicCurve() returns QuadCurve, not CubicCurve

Looks like a copy/paste/forget-to-edit bug:

public static <V, E> EdgeShape<V, E>.QuadCurve cubicCurve(Graph<V, E> graph) {
        return new EdgeShape<V, E>(graph).new QuadCurve();
}

BTW, I'm not sure the refactoring of EdgeShape to make the curves inner, not nested, classes, is really a good idea - it adds overhead for the VM, and is completely avoidable here. Also the outer instance of EdgeShape has to hold state and fields for shapes that will, in most cases, never be used. I think you were trying to make the generic signature simpler - and it does that if you're writing Jung - not sure if that's the case if you're writing a client of Jung.

Documentation

Hi,
Is there any kind of documentation available?

thanks.

Patch for /trunk/jung/jung-io/src/main/java/edu/uci/ics/jung/io/MatrixFile.java

Decimal separators are different in different countries, e.g. comma instead of 
a dot.
String.format uses default locale whereas load() method uses 
Double.parseDouble() which can't cope with commas.

Original issue reported on code.google.com by marcin.czekaj on 6 Nov 2011 at 6:41

Attachments:

• MatrixFile.java.patch

Xlint:path error with JUNG, Gradle and Error Prone

When I try to run gradle run with the following build.gradle

plugins {
  id 'application'
  id 'java'
  id 'net.ltgt.errorprone' version '0.0.8'
}

group 'org.jbduncan'
version '1.0-SNAPSHOT'

sourceCompatibility = 1.8

mainClassName = 'org.jbduncan.helloworld.HelloWorld'

repositories {
  jcenter()
}

dependencies {
  compile 'net.sf.jung:jung-graph-impl:2.1.1'
  errorprone 'com.google.errorprone:error_prone_core:2.0.11'
}

tasks.withType(JavaCompile) {
  options.encoding = 'UTF-8'
  options.compilerArgs = [
    '-Xlint:all',
    '-Werror'
  ]
}

and this class

package org.jbduncan.helloworld;

public final class HelloWorld {
  public static void main(String[] args) {
    System.out.println("Hello, world!");
  }
}

it emits the following message.

:compileJava                                                                     
warning: [path] bad path element "C:\Users\Jonathan\.gradle\caches\modules-2\files-2.1\net.sf.jung\jung-graph-impl\2.1.1\8293acb2ab4c00a3939cb99a8751e5d38a4299dc\jung-api-2.1.1.jar": no such file or directory
warning: [path] bad path element "C:\Users\Jonathan\.gradle\caches\modules-2\files-2.1\net.sf.jung\jung-graph-impl\2.1.1\8293acb2ab4c00a3939cb99a8751e5d38a4299dc\guava-19.0.jar": no such file or directory
warning: [path] bad path element "C:\Users\Jonathan\.gradle\caches\modules-2\files-2.1\net.sf.jung\jung-api\2.1.1\e47ee4efdfacce12f0af620747d9d0e44bf2eaa4\guava-19.0.jar": no such file or directory
error: warnings found and -Werror specified
1 error                     
3 warnings
:compileJava FAILED

FAILURE: Build failed with an exception.

* What went wrong:
Execution failed for task ':compileJava'.
> Compilation failed with exit code 1; see the compiler error output for details.

* Try:
Run with --stacktrace option to get the stack trace. Run with --info or --debug option to get more log output.

BUILD FAILED

Total time: 5.488 secs

When I investigate the contents of my Gradle cache, I can see that, indeed, the jar files mentioned above simply don't exist.

When I look into C:\Users\Jonathan\.gradle\caches\modules-2\files-2.1\net.sf.jung\jung-graph-impl\2.1.1\8293acb2ab4c00a3939cb99a8751e5d38a4299dc\jung-graph-impl-2.1.1.jar, the META-INF/MANIFEST.MF contains this text.

Manifest-Version: 1.0
Archiver-Version: Plexus Archiver
Created-By: Apache Maven 3.0.5
Built-By: jrtom
Build-Jdk: 1.8.0-google-v7
Class-Path: jung-api-2.1.1.jar guava-19.0.jar

I get the same problem with JUNG versions 2.1 and 2.0, and no other library with dependencies I've tried seems to have this problem.

However the problem goes away when I exclude from build.gradle the lines id 'net.ltgt.errorprone' version '0.0.8' and errorprone 'com.google.errorprone:error_prone_core:2.0.11', so it's not clear to me if this is a problem with JUNG or if it's gradle-errorprone-plugin or Error Prone related.

Retire `Pair` type

Now that the JUNG graph types are gone, it's only used (internally) by the StructurallyEquivalent class. At the least we don't need a public type for this, and we probably don't need something that is basically an ImmutableList anyway.

NullPointerException: edu.uci.ics.jung.graph.util.Context#hashCode

java.lang.NullPointerException: null
    at edu.uci.ics.jung.graph.util.Context.hashCode(Context.java:38)
    at java.util.HashMap.hash(HashMap.java:338)
    at java.util.HashMap.get(HashMap.java:556)
    at edu.uci.ics.jung.graph.util.DefaultParallelEdgeIndexFunction.getIndex(DefaultParallelEdgeIndexFunction.java:60)
    at edu.uci.ics.jung.visualization.renderers.BasicEdgeLabelRenderer.labelEdge(BasicEdgeLabelRenderer.java:81)
    at edu.uci.ics.jung.visualization.renderers.BasicRenderer.renderEdgeLabel(BasicRenderer.java:82)
    at edu.uci.ics.jung.visualization.renderers.BasicRenderer.render(BasicRenderer.java:42)
    at edu.uci.ics.jung.visualization.BasicVisualizationServer.renderGraph(BasicVisualizationServer.java:348)
    at edu.uci.ics.jung.visualization.BasicVisualizationServer.paintComponent(BasicVisualizationServer.java:303)

I think the issue is that Context#getInstance is called with a null Graph initiated at BasicEdgeLabelRenderer.java:81.

      at edu.uci.ics.jung.graph.util.Context.getInstance(Context.java:31)
      at edu.uci.ics.jung.graph.util.DefaultParallelEdgeIndexFunction.getIndex(DefaultParallelEdgeIndexFunction.java:60)
      at edu.uci.ics.jung.visualization.renderers.BasicEdgeLabelRenderer.labelEdge(BasicEdgeLabelRenderer.java:81)
      at edu.uci.ics.jung.visualization.renderers.BasicRenderer.renderEdgeLabel(BasicRenderer.java:82)
      at edu.uci.ics.jung.visualization.renderers.BasicRenderer.render(BasicRenderer.java:42)
      at edu.uci.ics.jung.visualization.BasicVisualizationServer.renderGraph(BasicVisualizationServer.java:348)
      at edu.uci.ics.jung.visualization.BasicVisualizationServer.paintComponent(BasicVisualizationServer.java:303)

Using version 2.1.

Dijkstra*: refactor for performance and API cleanup

DijkstraDistance and DijkstraShortestPath each (optionally) cache information about previously calculated shortest distances/paths, as a time/space tradeoff in case those distances/paths are needed again.

However, they don't do so in a very intelligent fashion: when we've calculated the shortest path/distance from A to C, and the path passes through B, we already know the shortest path/distance from B to C also, but we don't store it in such a way as to be able to take advantage of this.

This is known to be a problem in practice; one user has reported that with a graph of ~10k nodes and 100k edges, after a number of calls for path lengths, there are ~2M distances being stored. :(

The task here is to come up with a better representation of the cached distances/paths that is more compact. Offhand I'd guess that this can be done in O(m + n) space (i.e., basically the size of the input graph), or perhaps O(n^2); what we have now looks more like O(mn).

(While we're in here, we should also clean up the API, e.g., make use of builders, make the interface more uniform, etc.)

Fix up the maven poms so that deployment to sonatype is a one-liner

This should include:

• Update the deployment information to point to sonatype
• Add a profile keyed on a flag like -DperformRelease=true
• Move Jung to declare -SNAPSHOT versions at-head, reserving non-snapshot versions for release
• File issues on issues.sonatype.org for Josh and any other developers who need to perform releases
• throw a script in to ease release, or use maven-release-plugin and configure accordingly.

Optional:

• Set up travis-ci.org configuration to run continuous integration on successful merges to master
• Set up the .travis.yml to auto-deploy snapshot releases to sonatype on successful merge to master.

Code review request

[Testing the built-in code review system for Google Code.]

Purpose of code changes on this branch:
Change JUNG from using collections-generic to using Guava.

When reviewing my code changes, please focus on:
anything broken

After the review, I'll merge this branch into:
/trunk

Original issue reported on code.google.com by [email protected] on 26 Jul 2010 at 5:24

Switching layouts is busted [common.graph]

This issue has two parts: fixing VisualizationViewer so that switching layouts actually works, and fixing the sample code so that the selection and creation of Layouts works (i.e., no longer uses reflection).

The first part manifests in several demos, including BalloonLayoutDemo, *AddNodeDemo, L2RLayoutDemo, TreeLayoutDemo, VertexCollapseDemoWithLayouts.

specifying a new Tree API

In the common.graph branch (the precursor to JUNG 3.0) there are now some types for supporting tree structures: https://github.com/jrtom/jung/tree/common.graph/jung-api/src/main/java/edu/uci/ics/jung/graph

*CTree* are placeholder names.

In that branch, the Tree types and implementations have been removed, so those names are now available. (I'm not worried about breaking anyone by reusing those types, because JUNG 3.0 has already burned that barn behind us, as it were: moving from JUNG 2.x to JUNG 3.x will require a migration from existing users.)

Points to consider:

• Are we going to try to also provide an API for binary trees? If so, what should that look like?
• We already have a Network-based variant, i.e., "CTreeNetwork". Which would be better: "TreeNetwork" or "NetworkTree"? Is there some third alternative?
• We don't yet have a ValueGraph analogue. That should probably be ValueTree (which perhaps militates in favor of "NetworkTree").

Format code base

Five potential options:

1. Use a Maven plugin for google-java-format, like https://github.com/coveo/fmt-maven-plugin.
   • Advantage:
     • Formats code automatically.
     • Easiest automatic option to setup.
   • Disadvantage:
     • Doesn't order imports according to Google Java Style Guide or remove unused imports (spotify/fmt-maven-plugin#11).
2. Use Checkstyle's support for compliance with the Google Java Style Guide.
   • Advantage:
     • Has supported Google Java Style Guide the longest, so probably has most extensive implementation.
   • Disadvantage:
     • Cannot automatically reformat code AFAIK - one manually formats code until it complies with Checkstyle.
3. Use google-java-format from the CLI.
   • Advantage:
     • Formats code automatically.
     • Orders imports properly and removes unused imports.
   • Disadvantages:
     • Hard to setup - requires knowledge of Shell and Travis to manually integrate it with Travis.
     • No native checking capability - CLI tool is unable to verify at CI time that code meets the expected format, so one would need to use a downstream tool which fixes this like sormuras/google-java-format (google/google-java-format#106).
4. Format manually with google-java-format before each new commit.
   • Advantage:
     • Little to no setup required.
   • Disadvantage:
     • Easy to forget to format code - no help from CI.
5. Migrate to Gradle and use Spotless plugin.
   • Advantages:
     • Formats code automatically.
     • Orders imports properly and removes unused imports.
   • Disadvantages:
     • Hardest to setup - requires migrating from Maven to Gradle.

JAVAFX 8

Any new developments in porting Jung to JavaFX 8?
I've found some code for this but using old JavaFX 2.2...

Thank you in advance.

Refactor algorithms package

Potential areas for improvement:

• reduce the number of subpackages and classes
• use the Builder pattern to avoid multiple overlapping constructors
• generally unify the way in which algorithms are invoked

Do various code cleanups

Including:

• Remove BasicMapEntry - superseded by AbstractMap.SimpleImmutableEntry.
• Add braces to all if/else/for/while statements.
• Run IntelliJ inspections and fix the ones deemed appropriate.
• Rename variables, fields, parameters and method names from snake_case to camelCase.
• Replace cases of if (condition) { throw *Exception() } with com.google.common.base.Preconditions as appropriate.
• Add final modifier to classes and other places in the code base as appropriate.
• Use immutable collections classes like Immutable{List,Set,Map} as appropriate.
• Use Collections API interfaces more consistently, e.g.
  1. ArrayList<String> strings = new ArrayList<>(); --> List<String> strings = new ArrayList<>():
  2. LinkedHashSet<String> methodName(int parameter1, LinkedList<Integer> parameter2) { ... } --> Set<String> methodName(int parameter1, Iterable<Integer> parameter2) { ... }.
• Use Streams, lambda expressions and other Java 8 idioms more consistently and as appropriate.
• Separate out variable declarations like int a, b; into int a; int b;.
• Use @FunctionalInterface annotation wherever applicable.
• Replace usages of Stack with ArrayDeque for likely performance improvements.
• Use java.util.function functional interfaces instead of com.google.common.base ones.

Connedted graph task

I'm

looking for one that helps with Graph of ( characters ) .

I want to design a test task that the user should try to connect characters

by order . For example connect (1) to (2) then (2) to (3) . can Jung help m with this ?

how do i use JUNG

Is there a GUI to start testing algorithms?

Support for distributed algorithms

Does this library provide support for distributed algorithms (election for example). If so, is there any sample codes.
Thanks

BasicVisualizationServer causes NullPointerException

Running even simple visualisations such as https://gist.github.com/dominic-jones/5fdb31055838aefe07e2 will cause a NullPointerException in 2.1

Traced back to a refactoring done here acf6eac.

In short, the PluggableRenderContext was previously (in 2.0.1) initalised at field declaration. Now in 2.1 intialisation has been relocated to the constructors.

Since several of these constructors call a main one, any data set into PluggableRenderContext by the primary constructor is overridden.

Ultimately, the NPE occurs later at BasicVertexLabelRenderer#84 where the pickedVertexState in PluggableRenderContext has been nulled.

Happy to contribute back a test and a fix for this if that would be easier for you.

NullPointerException when using RadialTreeLayout due to vertex not being identified as root

This is a follow up from:
https://sourceforge.net/p/jung/bugs/196/

I've hit this behavior again.

I have a directed graph with 3 roots (e.g. vertices that are not the end point for any directed edges in the graph). In the method:

protected void buildTree() throws Exception

There is code:

            if (roots.size() > 0 && graph != null) {
                    calculateDimensionX(roots);
                    for(V v : roots) {
                            calculateDimensionX(v);
                            m_currentPoint.x += this.basePositions.get(v)/2 + this.distX;
                            buildTree(v, this.m_currentPoint.x);
                    }
            }

I see that roots.size()==1 in my case, despite there being 3 roots. I'm debugging the construction of the roots object and will post details on the cause once identified.

RenderContext cleanup

• a bunch of places assume that various Predicates or Functions can be null. Either use Optional or require them to be present instead. (Or mark as @nullable.)
• maybe don’t even have getBlahPredicate()/getBlahTransformer(); just expose isBlah()/applyBlah() instead
• edgeIncludePredicate() should just go ahead and check the edge’s endpoints as well so that the caller doesn’t have to
• edgeArrowPredicate/Transformer: just have something that provides an Optional Arrow for a given edge (get rid of the Predicate)
  • or a boolean that specifies for the entire RenderContext whether edge arrows are wanted
• figure out whether we want “? super V” or not
• use java.util.Function and .Predicate instead of their Guava counterparts
• consider making instance variables in PluggableRendererContext private instead of protected
• add @Override annotations
• add documentation for each method

Consider changing EdgeShape inner classes to nested static classes

In the refactoring of EdgeShape.java (moving from 2.0 to 2.1), we changed the Line, QuadCurve, etc. classes from nested static classes into inner classes. While in general the refactoring was a distinct improvement, the static->inner change is one we should consider undoing.

Credit where due: this was originally brought up by @timboudreau in #69.

Lattice2DGenerator getRow() bug

The calculation for getRow() is currently incorrect. Consider the following scenario. The numbers represent vertices and are arranged in a 2-row, 5-col lattice.

0 1 2 3 4
5 6 7 8 9

getRow() currently returns i / row_count which means that vertices 2-3 are incorrectly said to be in row 1, 4-5 in row 2 (non-existent), 6-7 in row 3 (non-existent), etc.

Changing it to i / col_count produces the desired results: 0-4 are row 0, 5-9 are row 1.

This code doesn't seem to be used anywhere except in the Kleinberg generator but within that it is used to calculate the distance metric between nodes for making the long-distance connections. This means that the probabilities assigned to the nodes is incorrect as the nodes are thought to be potentially much further away than they are.

It also means that it is possible for the vertices to have self-loops/duplicate attempted edges as the check to prevent this relies on the distance between the nodes.

Consider refactoring KMeansClusterer to use a user-provided function for generating random numbers

@jrtom I don't know how likely this is, but I suspect there's a chance that the level of randomness produced by the default Random instance that JUNG's KMeansClusterer uses to do its job is not random enough for everyone.

Consider introducing a method like public void setRandomNumberSupplier(DoubleSupplier randomNumberSupplier) or public void setRandomNumberGenerator(RandomGenerator randomGenerator) (where RandomGenerator would be similar to http://commons.apache.org/proper/commons-math/javadocs/api-3.6.1/org/apache/commons/math3/random/RandomGenerator.html) to meet this potential need.

NullPointerException for a non initialized PickedState in PluggableRenderContext

I was tryin to display a single graph but it stops me when i try to execute for the first time this code:

Forest<String, String> g = new DelegateForest<String, String>();
[...]
Layout<String, String> l = new TreeLayout<String, String>(g);
BasicVisualizationServer<String, String> vv = new BasicVisualizationServer<String, String>(l);
[...]
vv.setPreferredSize(graphPane.getSize());
graphPane.add(vv, BorderLayout.CENTER);

It basically creates a Forest, fills the Forest (code not shown), and uses a default TreeLayout to visualize it in a BasicVisualizationServer. version 2.0.1 worked fine, after updating at 2.1 it gives me a NullPointerException.

After a bit of debug I discovered that the PluggableRenderContext that vv uses as a default doesn't initialize the two PickedState, vetrtex and edge, and it hangs exactly on the call to the the vertexPickedState.

This is the exception:

java.lang.NullPointerException at edu.uci.ics.jung.visualization.renderers.BasicVertexLabelRenderer.labelVertex(BasicVertexLabelRenderer.java:84) at edu.uci.ics.jung.visualization.renderers.BasicRenderer.renderVertexLabel(BasicRenderer.java:74) at edu.uci.ics.jung.visualization.renderers.BasicRenderer.render(BasicRenderer.java:59) at edu.uci.ics.jung.visualization.BasicVisualizationServer.renderGraph(BasicVisualizationServer.java:348) at edu.uci.ics.jung.visualization.BasicVisualizationServer.paintComponent(BasicVisualizationServer.java:303) at javax.swing.JComponent.paint(JComponent.java:1056) at javax.swing.JComponent.paintToOffscreen(JComponent.java:5210) at javax.swing.RepaintManager$PaintManager.paintDoubleBuffered(RepaintManager.java:1579) at javax.swing.RepaintManager$PaintManager.paint(RepaintManager.java:1502) at javax.swing.RepaintManager.paint(RepaintManager.java:1272) at javax.swing.JComponent._paintImmediately(JComponent.java:5158) at javax.swing.JComponent.paintImmediately(JComponent.java:4969) at javax.swing.RepaintManager$4.run(RepaintManager.java:831) at javax.swing.RepaintManager$4.run(RepaintManager.java:814) at java.security.AccessController.doPrivileged(Native Method) at java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:76) at javax.swing.RepaintManager.paintDirtyRegions(RepaintManager.java:814) at javax.swing.RepaintManager.paintDirtyRegions(RepaintManager.java:789) at javax.swing.RepaintManager.prePaintDirtyRegions(RepaintManager.java:738) at javax.swing.RepaintManager.access$1200(RepaintManager.java:64) at javax.swing.RepaintManager$ProcessingRunnable.run(RepaintManager.java:1732) at java.awt.event.InvocationEvent.dispatch(InvocationEvent.java:311) at java.awt.EventQueue.dispatchEventImpl(EventQueue.java:756) at java.awt.EventQueue.access$500(EventQueue.java:97) at java.awt.EventQueue$3.run(EventQueue.java:709) at java.awt.EventQueue$3.run(EventQueue.java:703) at java.security.AccessController.doPrivileged(Native Method) at java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:76) at java.awt.EventQueue.dispatchEvent(EventQueue.java:726) at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:201) at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:116) at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:105) at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:101) at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:93) at java.awt.EventDispatchThread.run(EventDispatchThread.java:82)