jgrapht-users — JGraphT user list.

Re: [jgrapht-users] Bug report

[John V. S. <js...@gm...>]

Thanks Santiago, but someone else beat you to it and it was fixed in a 
subsequent release.

You can find more of the blow-by-blow here:

http://cafenate.blogspot.com/2008/05/analysis-of-java-implementations-of.html

The latest code is here:

http://jgrapht.svn.sourceforge.net/viewvc/jgrapht/trunk/src/org/jgrapht/util/FibonacciHeap.java?revision=645&view=markup

Using 32 instead of the Math calls may be good enough, so if anyone 
notices excessive CPU usage from the Math calls showing up in a 
profiler, we could change it.

JVS

Santiago Gutierrez wrote:
> Dear Jgrapht team:
>  
>  
> My name is Santiago Gutierrez, I am from Colombia in South America. 
> While trying to solve a problem at ICPC I was in the need of a fibonnaci 
> heap. Browsing the internet I found the fibonacci heap from your project 
> and tried to use it in my problem. I then found that the fibonacci heap 
> was not as fast as it should be, making my algorithm O(n^2) and not 
> O(nlog(n)). After seeing the code I found that the problem was in this 
> function:
>  
>  
> Consolidates the trees in the heap by joining trees of equal degree 
> until there are no more trees of equal degree in the root list.
> Running time: O(log n) amortized
> 
>   protected void consolidate▾ <http://grepcode.com/file/repo1.maven.org$maven2@org.jgrapht$jgrapht-jdk1.5@0.7.3@org$jgrapht$util$FibonacciHeap.java#>()
> 435    {
> 436        int arraySize = nNodes + 1;
> 437        List <http://grepcode.com/file/repository.grepcode.com$java$root@jdk$openjdk@6-b14@java$util$List.java#List><FibonacciHeapNode <http://grepcode.com/file/repo1.maven.org$maven2@org.jgrapht$jgrapht-jdk1.5@0.7.3@org$jgrapht$util$FibonacciHeapNode.java#FibonacciHeapNode><T>> array =
> 438            new ArrayList <http://grepcode.com/file/repository.grepcode.com$java$root@jdk$openjdk@6-b14@java$util$ArrayList.java#ArrayList><FibonacciHeapNode <http://grepcode.com/file/repo1.maven.org$maven2@org.jgrapht$jgrapht-jdk1.5@0.7.3@org$jgrapht$util$FibonacciHeapNode.java#FibonacciHeapNode><T>>(arraySize);
> 439
> 440        // Initialize degree array
> 441        for (int i = 0; i < arraySize; i++) {
> 442            array.add <http://grepcode.com/file/repository.grepcode.com$java$root@jdk$openjdk@6-b14@java$util$List.java#List.add(org.jgrapht.util.FibonacciHeapNode)>(null);
> 443        }
> 
>  
> 
> I found through wikipedia that the fibonacci heap always mantain a degree of it's trees of 
> maximum log(n), thus the line:
> 
> int arraySize = nNodes + 1
> 
> 
> Can be safely change to:
> 
> int arraySize = 32
> 
> Effectively making the function the log(n) function that it should be. (And indeed my code acc).
> 
> Thanks a lot for all your hard effort,
> 
> Santiago Gutierrez A.
> 
> 
> ------------------------------------------------------------------------
> Connect to the next generation of MSN Messenger  Get it now! 
> <http://imagine-msn.com/messenger/launch80/default.aspx?locale=en-us&source=wlmailtagline>

[jgrapht-users] Jgrapht-0.8.1 with Eclipse

[Joshua T. <jos...@gm...>]

DEar Group,

I am a new user to jgraphT
I have used Eclipse to import jgraphT

I could not understand which files are the source files.

I tried with jgrapht-0-8-1 -> demo-> CompleteGraphDemo.java it shows me
launch error.

Can anyone help on this?>

JJ

Re: [jgrapht-users] Visualize path selection

[John V. S. <js...@gm...>]

Check out gralog, it is based on JGraphT and might have what you want:

http://gralog.sourceforge.net/

JVS

Joris Kinable wrote:
> Dear,
> 
> I'm about to start a project with some complex path selection
> algorithms. For that purpose I'm looking for a graph library which is
> easily adaptable so I can easily build in support for more complex
> edge costs. Furthermore, if I have a graph and run for example
> Dijkstra's shortest path algorithm on it, I would like to visualize
> the selected path in a graphical way. Do you know whether that is
> possible with JgraphT or are you aware of any other java libraries
> with such capabilities build in?
> 
> br,
> 
> Joris
> 
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry® Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay 
> ahead of the curve. Join us from November 9-12, 2009. Register now!
> http://p.sf.net/sfu/devconf
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> 

[jgrapht-users] Visualize path selection

[Joris K. <de...@gm...>]

Dear,

I'm about to start a project with some complex path selection
algorithms. For that purpose I'm looking for a graph library which is
easily adaptable so I can easily build in support for more complex
edge costs. Furthermore, if I have a graph and run for example
Dijkstra's shortest path algorithm on it, I would like to visualize
the selected path in a graphical way. Do you know whether that is
possible with JgraphT or are you aware of any other java libraries
with such capabilities build in?

br,

Joris

[jgrapht-users] Vertex/Cell layout when using the JGraphModelAdapter

[Stefan F. <sfr...@gm...>]

Hi all,

when using the JGraphModelAdapter to visualize a jgrapht graph all  
vertex objects are at the same position.
Is there a way to get a nice layout without using the JGraph layout 
managers (license needed)?
Maybe even an alternative to jgraph?

Thanks
Stefan

Re: [jgrapht-users] jgrapht fibonacci

[John V. S. <js...@gm...>]

Johan Henriksson wrote:
> Hello,

Hi Johan, thanks for writing.

> I am converting a C++ levelsets code and I am getting wrong results. the 
> question is then where the bug is; my conversion, the C++ code or the 
> fibonacci heap from jgrapht. I have rather high confidence in my 
> conversion, hence I wonder how well tested you consider the fibonacci 
> code? is it actively in use? (then I would consider it well tested). I 
> rely heavily on changing keys, hence fibonacci.

The fib code originally came from Nathan Fiedler.  It has been modified 
a few times since then based on other work (such as the addition of 
generics to JGraphT) and performance suggestions.

Nathan's code has undergone changes since then as well:

http://cafenate.blogspot.com/2008/05/analysis-of-java-implementations-of.html

I haven't followed up on everything in that post, but I'm not aware of 
any correctness issues.  The implementation is used by JGraphT's 
DijkstraShortestPath/ClosestFirstIterator, so it gets used heavily by a 
number of applications.  But you never know...there could certainly be a 
bug.  If you can isolate a unit test demonstrating incorrect behavior, 
that would be very valuable.

> also, why does the fibonacci node take a key, while insert() also takes 
> a key, and the node key cannot be changed? the design is very confusing. 
> I would expect a single location where the key can be set, either 
> insert() or new FibNode, not both.

Good question :)  I'll clean it up.

JVS

Re: [jgrapht-users] servlets

[John V. S. <js...@gm...>]

JGraphT is an algorithm library (not a rendering library) so it's up to 
you to layer on views.

JVS

Tim Whitten wrote:
> I’m trying to use jgrapht in a servlet. Is there any way to display the 
> graph via a servlet?
> 
>  
> 
> Tim Whitten
> 
> Software Engineer
> 
> Applied Enterprise Solutions, LLC
> 
> tim...@ae... <mailto:tim...@ae...>
> 
> Phone: (662) 213-9187
> 
>  
> 
> 
> ------------------------------------------------------------------------
> 
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day 
> trial. Simplify your report design, integration and deployment - and focus on 
> what you do best, core application coding. Discover what's new with 
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

Re: [jgrapht-users] Graph comparator

[John V. S. <js...@gm...>]

Stefan Fritz wrote:
> Hi all,
> 
> I'm looking for a graph libary which supports comparing 2 graphs.
> I'd like to create a graph of interactions in our software framework,  
> compare the resulting graph to a predefined "expected" graph.
> These graphs can be very complex and deep.
> 
> Is this use case supported by jgrapht?
> Any examples?

There is some brute-force code for isomorphism in the experimental 
package, but it's unlikely to be what you're looking for unless you 
already have distinguishing labels on the vertices (in which case it's a 
rather trivial problem).

JVS

[jgrapht-users] Graph comparator

[Stefan F. <sfr...@gm...>]

Hi all,

I'm looking for a graph libary which supports comparing 2 graphs.
I'd like to create a graph of interactions in our software framework,  
compare the resulting graph to a predefined "expected" graph.
These graphs can be very complex and deep.

Is this use case supported by jgrapht?
Any examples?

Thanks
Stefan

[jgrapht-users] servlets

[Tim W. <Tim...@ae...>]

I'm trying to use jgrapht in a servlet. Is there any way to display the graph via a servlet?

Tim Whitten
Software Engineer
Applied Enterprise Solutions, LLC
tim...@ae...<mailto:tim...@ae...>
Phone: (662) 213-9187

[jgrapht-users] GraphML importer?

[Khanh N. <kn...@cs...>]

Hi,

Is there a way to save and load a graph using jgrapht? I found
GraphMLExporter but couldn't find an importer for it.

Thanks

-k

Re: [jgrapht-users] get a set of neighbors

[Khanh N. <kn...@cs...>]

Hi,

Thank you very much for your response. I took a closer look yesterday,
I'm currently using NeighborIndex, is it efficient? My graph has
10.000 nodes.

-k

On Tue, Aug 11, 2009 at 12:18 AM, Xueyang Zhu<xue...@gm...> wrote:
> HI,
>
> Try the following:
>
> for(DefaultEdge e:g.edgesOf(X)){
>        Vertex v=g.getEdgeTarget(e);
>        .....
>
> }
>
>
>
> 2009/8/10 Khanh Nguyen <ngu...@gm...>
>>
>> Hello all,
>>
>> I am new to JGraphT (just started this morning). I am working on a
>> simple random search on a graph and I need to get the set of neighbors
>> of each vertex. How do I do it?
>>
>> My attempt is to use edgesOf() method to get the set of edges of
>> vertex X, but I don't know how to go next from there, as all methods
>> in DefaultVertex are protected. It looks like this
>>
>> Set<DefaultEdge> s = g.edgesOf(X);
>> ...?
>>
>> I guess, I could also try to implement an Iterator? but it seems more
>> advanced at this point for me.
>>
>> Thanks.
>>
>> -k
>>
>>
>> ------------------------------------------------------------------------------
>> Let Crystal Reports handle the reporting - Free Crystal Reports 2008
>> 30-Day
>> trial. Simplify your report design, integration and deployment - and focus
>> on
>> what you do best, core application coding. Discover what's new with
>> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

Re: [jgrapht-users] get a set of neighbors

[Xueyang Z. <xue...@gm...>]

HI,

Try the following:

for(DefaultEdge e:g.edgesOf(X)){
       Vertex v=g.getEdgeTarget(e);
       .....

}



2009/8/10 Khanh Nguyen <ngu...@gm...>

> Hello all,
>
> I am new to JGraphT (just started this morning). I am working on a
> simple random search on a graph and I need to get the set of neighbors
> of each vertex. How do I do it?
>
> My attempt is to use edgesOf() method to get the set of edges of
> vertex X, but I don't know how to go next from there, as all methods
> in DefaultVertex are protected. It looks like this
>
> Set<DefaultEdge> s = g.edgesOf(X);
> ...?
>
> I guess, I could also try to implement an Iterator? but it seems more
> advanced at this point for me.
>
> Thanks.
>
> -k
>
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
> trial. Simplify your report design, integration and deployment - and focus
> on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] get a set of neighbors

[Khanh N. <ngu...@gm...>]

Hello all,

I am new to JGraphT (just started this morning). I am working on a
simple random search on a graph and I need to get the set of neighbors
of each vertex. How do I do it?

My attempt is to use edgesOf() method to get the set of edges of
vertex X, but I don't know how to go next from there, as all methods
in DefaultVertex are protected. It looks like this

Set<DefaultEdge> s = g.edgesOf(X);
...?

I guess, I could also try to implement an Iterator? but it seems more
advanced at this point for me.

Thanks.

-k

Re: [jgrapht-users] All shortest paths problem

[John V. S. <js...@gm...>]

Daniel Bell wrote:
> Is it possible to use DijkstraShortestPath to calculate the shortest 
> paths to all destinations from a specified vertex? If not, is there a 
> way that you would recommend extending the framework to accommodate this 
> use case? I’d be happy to contribute the code if that’s the case.

Yes, you can use an instance of 
org.jgrapht.traverse.ClosestFirstIterator for this purpose.  The 
DijkstraShortestPath class is actually just a wrapper for it.

JVS

Re: [jgrapht-users] JGraphT Version 0.8.1 Released

[John V. S. <js...@gm...>]

John V. Sichi wrote:
> This release includes a number of bugfixes and contributions which have 
> accumulated since the 0.8.0 release. You can find a description of the 
> changes here:
> 
> http://jgrapht.wikispaces.com/Release0.8.1
> 
> Big thanks to all who made suggestions and code contributions for this
> release, especially Andrew Newell and Tom Larkworthy for the new 
> algorithm implementations.

I forgot to mention Ilya Razenshteyn's contribution of GraphUnion; I've 
corrected the release notes in wiki and Subversion.

Unfortunately, Ilya did not get a chance to finish up with optimizations 
and unit tests due to illness, so if anyone else wants to finish up the 
development here, please send me your code/tests.

Thanks,
JVS

[jgrapht-users] JGraphT Version 0.8.1 Released

[John V. S. <js...@gm...>]

This release includes a number of bugfixes and contributions which have 
accumulated since the 0.8.0 release. You can find a description of the 
changes here:

http://jgrapht.wikispaces.com/Release0.8.1

Big thanks to all who made suggestions and code contributions for this
release, especially Andrew Newell and Tom Larkworthy for the new 
algorithm implementations.

JVS

Re: [jgrapht-users] JGraphT update -- Floyd-Warshal algorithms

[John V. S. <js...@gm...>]

Thanks a lot!  I have committed it to Subversion.

JVS

Tom Larkworthy wrote:
> Hello, I wrote this in order to get the diameter of a graph
> 
> Calculates all shortests path pairs in O(n^3)
> 
> in (correct) package:-
> 
> org.jgrapht.alg
> 
> 
> There is a test in the main
> 
> Hope it helps
> 
> Tom Larkworthy
> 

[jgrapht-users] (no subject)

[Alexandros M. <al...@di...>]

Hi i am using the following code to create a graph from an adjacency
Table and to find the maximal cliques


void findAllCliques() {
        UndirectedGraph<Integer, DefaultEdge> g = new
SimpleGraph<Integer, DefaultEdge>(DefaultEdge.class);
        for (int i = 0; i < this.adjacencyTable.length; i++) {
            g.addVertex(i);
        }

        for (int i = 0; i < this.adjacencyTable.length; i++) {
            for (int j = i + 1; j < this.adjacencyTable.length; j++) {
                //if (i == j) {
                //    continue;
                //}
                if (this.adjacencyTable[i][j] > 0) {
                    if( g.containsEdge( i, j ) == false )
                        g.addEdge(i, j);
                    //else {
                    //    System.out.println( i + " " + j + "is all
ready in" );
                    //}

                }
            }
        }
        //System.out.println("calling Libarary");
        BronKerboschCliqueFinder algorithm = new
BronKerboschCliqueFinder(g);
        //System.out.println("library finished");
        this.cliques = algorithm.getAllMaximalCliques();
        //System.out.println("cliques geted");
}



But it seems like the library goes into an infinite loop becouse it
never returns from the

this.cliques = algorithm.getAllMaximalCliques();

has anyone seen this problem again??

Re: [jgrapht-users] KShortestPaths issues

[John V. S. <js...@gm...>]

I've checked in a toString implementation which just calls toString on 
the edge list.

JVS

John V. Sichi wrote:
> There is no mistake; it's just that the KShortestPaths.PathWrapper does 
> not have a toString() method, so List.toString prints the Java object 
> ID's instead.
> 
> JVS
> 
> Achim Beutel wrote:
>> Hi,
>>
>> I am trying to use the getPath() method from the KShortestPaths class 
>> but without any luck (current version).
>>
>> I defined a new graph:
>> DirectedGraph<String, DefaultEdge> directedGraph = new 
>> DefaultDirectedGraph<String, DefaultEdge> (DefaultEdge.class);
>>
>> and added some vertices and edges. Then:
>>
>> KShortestPaths shortestPaths = new KShortestPaths(directedGraph, 
>> "vertex1", 2);
>> List path = shortestPaths.getPaths("vertex2");
>>
>> Now, I get an output like this for 'path':
>> [org.jgrapht.alg.KShortestPaths$PathWrapper@24f420, 
>> org.jgrapht.alg.KShortestPaths$PathWrapper@24f410]
>>
>> Where is my mistake?
>>
>> Thanks!
> 
> 

Re: [jgrapht-users] KShortestPaths issues

[John V. S. <js...@gm...>]

There is no mistake; it's just that the KShortestPaths.PathWrapper does 
not have a toString() method, so List.toString prints the Java object 
ID's instead.

JVS

Achim Beutel wrote:
> Hi,
> 
> I am trying to use the getPath() method from the KShortestPaths class but without any luck (current version).
> 
> I defined a new graph:
> DirectedGraph<String, DefaultEdge> directedGraph = new DefaultDirectedGraph<String, DefaultEdge> (DefaultEdge.class);
> 
> and added some vertices and edges. Then:
> 
> KShortestPaths shortestPaths = new KShortestPaths(directedGraph, "vertex1", 2);
> List path = shortestPaths.getPaths("vertex2");
> 
> Now, I get an output like this for 'path':
> [org.jgrapht.alg.KShortestPaths$PathWrapper@24f420, org.jgrapht.alg.KShortestPaths$PathWrapper@24f410]
> 
> Where is my mistake?
> 
> Thanks!

[jgrapht-users] KShortestPaths issues

[Achim B. <A.B...@gm...>]

Hi,

I am trying to use the getPath() method from the KShortestPaths class but without any luck (current version).

I defined a new graph:
DirectedGraph<String, DefaultEdge> directedGraph = new DefaultDirectedGraph<String, DefaultEdge> (DefaultEdge.class);

and added some vertices and edges. Then:

KShortestPaths shortestPaths = new KShortestPaths(directedGraph, "vertex1", 2);
List path = shortestPaths.getPaths("vertex2");

Now, I get an output like this for 'path':
[org.jgrapht.alg.KShortestPaths$PathWrapper@24f420, org.jgrapht.alg.KShortestPaths$PathWrapper@24f410]

Where is my mistake?

Thanks!
-- 
Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a

Re: [jgrapht-users] DirectedNeighborIndex

[John V. S. <js...@gm...>]

Claudio Martella wrote:
> I just want to understand if this is the correct thing or if you have
> any furthers suggestion for speed optimization for local neighborhood
> analysis.

Your code looks correct to me.

JVS

Re: [jgrapht-users] DirectedNeighborIndex

[Claudio M. <cla...@gm...>]

Ok, what I did after I wrote the email is change my graph to
ListenableDirectedWeightedGraph and then i changed the constructor to
this:

public MyGraph() {
	super(DefaultWeightedEdge.class);
	indexer = new DirectedNeighborIndex<MyVertex, DefaultWeightedEdge>(this);
	addGraphListener(indexer);
}

Then i implemented two methods:

public Set<MyVertex> successorsOf(MyVertex vertex) {
    return indexer.successorOf(vertex);
}

public Set<MyVertex> precedessorsOf(MyVertex vertex){
    return indexer.precedessorsOf(vertex);
}

I just want to understand if this is the correct thing or if you have
any furthers suggestion for speed optimization for local neighborhood
analysis.

TIA

/CM

On Wed, May 6, 2009 at 8:09 PM, John V. Sichi <js...@gm...> wrote:
> Claudio Martella wrote:
>>
>> I'm implementing a few algorithms that make extensive use of local
>> neighborhoods of Vertexes. Therefore I'd like to use
>> DirectedNeighborIndex class to speed up the computation. At the moment
>> I've extended SimpleDirectedWeightedGraph and added the methods
>> outgoingVertexesOf(V) and incomingVertexesOf(V), both cycling over the
>> results of outgoingEdgesOf() and incomingEdgesOf(). What I'm trying to
>> understand is re-implementing these outgoingVertexesOf() and
>> incomingVertexesOf() with calls to  predecessorOf() and successorOf()
>> of DirectedNeighborhorIndex is the smartest way to optimize my code.
>> My second question, connected to the first one, is if it's possible,
>> if it's not already been used, to ask the graph to cache the calls
>> internally for some computation.
>
> I don't understand.  The DirectedNeighborIndex javadoc explains that you are
> supposed to create the index and then add it as a listener to the graph; you
> don't need to modify the graph itself.  The caching already happens inside
> of DirectedNeighborIndex.
>
> JVS
>



-- 
    Claudio Martella
    cla...@gm...

Re: [jgrapht-users] DirectedNeighborIndex

[John V. S. <js...@gm...>]

Claudio Martella wrote:
> I'm implementing a few algorithms that make extensive use of local
> neighborhoods of Vertexes. Therefore I'd like to use
> DirectedNeighborIndex class to speed up the computation. At the moment
> I've extended SimpleDirectedWeightedGraph and added the methods
> outgoingVertexesOf(V) and incomingVertexesOf(V), both cycling over the
> results of outgoingEdgesOf() and incomingEdgesOf(). What I'm trying to
> understand is re-implementing these outgoingVertexesOf() and
> incomingVertexesOf() with calls to  predecessorOf() and successorOf()
> of DirectedNeighborhorIndex is the smartest way to optimize my code.
> My second question, connected to the first one, is if it's possible,
> if it's not already been used, to ask the graph to cache the calls
> internally for some computation.

I don't understand.  The DirectedNeighborIndex javadoc explains that you 
are supposed to create the index and then add it as a listener to the 
graph; you don't need to modify the graph itself.  The caching already 
happens inside of DirectedNeighborIndex.

JVS