jgrapht-users — JGraphT user list.

[jgrapht-users] PrioritizedTopologicalOrderIterator

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

Regarding this discussion:

http://jgrapht.wikispaces.com/message/view/home/51349

I tried adding this, but it broke the retroweaver 1.4 backport (Queue 
was introduced in 1.5) so I'm going to wait until that gets fixed before 
changing JGraphT:

https://sourceforge.net/forum/message.php?msg_id=3929701

JVS

Re: [jgrapht-users] problem with JGraphT demo

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

Shadi Moradi wrote:
> Hello all,
> I am trying to run the demo but it seems that it has a problem. It does 
> not work.any help???

Sure, here's some help:

http://www.chiark.greenend.org.uk/~sgtatham/bugs.html

JVS

[jgrapht-users] problem with JGraphT demo

[Shadi M. <mor...@gm...>]

Hello all,
I am trying to run the demo but it seems that it has a problem. It does not
work.any help???

Regards
Sh

[jgrapht-users] EdgeReversedGraph and JGraphT class collaboration patterns

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

I've checked a new EdgeReversedGraph view into Subversion.  This allows 
you to create a view of a directed graph with all of the edges reversed, 
without having to pay the cost of copying the graph and flipping the 
edges.  This is useful in combination with iterators (e.g. 
reverse-topological-sort, or reverse DFS/BFS).

On the general topic of how various classes in JGraphT can be combined 
(and the pattern for adding new classes and methods), I've written up a 
wiki page with some of the philosophy I've been trying to live:

http://jgrapht.wikispaces.com/CollaborationPatterns

JVS

Re: [jgrapht-users] DijkstraShortestPath

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

Anderson Adolfs wrote:
>    Could you explain what this "retroweaver-generated
> backport" means ? Maybe It can help me. I need to use
> Bellman-Ford provided with 0.7.0, but like Dijkstra's
> Algorithm implementation, It doesn't work like was in
> 0.6.0.

To try to keep JGraphT useful to users stuck on JDK 1.4, we added a 
backport using Retroweaver:

http://retroweaver.sourceforge.net

As I mentioned in a previous post, the README.html file included with 
the JGraphT distribution explains which jar to use in which circumstances.

>    P.S.: LabeledElement was not unuseful =/

That must be why so many people kept posting to ask why it existed :)

With the advent of generics, it was definitely obsolete.  But if you're 
prevented from using generics, you can always just privately define the 
old interface yourself.

JVS

Re: [jgrapht-users] DFS Question

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

John V. Sichi wrote:
> I'll see if I can come up with something efficient when I fix it 
> permanently in 0.7.1.  There have been requests to keep track of the 
> discovery and finish time, so I can probably kill two birds with one 
> stone by keeping this info in the "seen data" and using it to know 
> whether something is still on the stack or not without linear search.

I've checked a more efficient fix into Subversion.  DepthFirstIterator 
now keeps track of the standard WHITE/GRAY/BLACK vertex visit states, 
and uses them to provide a finish event via TraversalListener.  No 
timestamps yet.  Code review by anyone who has time would be 
appreciated; maybe someone can enhance BreadthFirstIterator to publish 
vertex finish events in the same way.

Khanh Vu also reported a problem with CycleDetector, which I fixed.  It 
is now using StrongConnectivityInspector for one of the cases; it should 
probably be using it for more of them; I'll see about that as part of 
changing StrongConnectivityInspector to use DepthFirstIterator.

I'm going to take care of a few of the other recent requests and then 
put out 0.7.1.

JVS

Re: [jgrapht-users] public access to Subgraph#getBase?

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

Aaron Harnly wrote:
> Any objection to changing Subgraph#getBase from protected to public?  
> When passing subgraphs around, it gets quite tiresome to  
> simultaneously pass redundant references to the base graph. I can  
> make a public accessor in a subclass, which I've done, but I don't  
> see any general justification for prohibiting external access...

Makes sense.  We always start with the "need to know" principle; in this 
case exposing it as public seems like the right thing to do.  I'll 
change it for 0.7.1.

I suppose the subclasses need covariant accessor methods; e.g. 
UndirectedSubgraph should override getBase() to return an 
UndirectedGraph.  Luckily that's now possible in Java 1.5.  (We'll see 
what retroweaver makes of it.)

JVS

[jgrapht-users] public access to Subgraph#getBase?

[Aaron H. <jgr...@li...>]

Any objection to changing Subgraph#getBase from protected to public?  
When passing subgraphs around, it gets quite tiresome to  
simultaneously pass redundant references to the base graph. I can  
make a public accessor in a subclass, which I've done, but I don't  
see any general justification for prohibiting external access...

cheers
-Aaron

Re: [jgrapht-users] DijkstraShortestPath

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

Anderson Adolfs wrote:
>    But now, when using the same code, with 0.7 JGraphT
> jar jgrapht-jdk1.4.jar, a compiletime error is ocurred
> saying that "The method findPathBetween(Graph, Object,
> Object) in the type DijkstraShortestPath is not
> applicaple for the arguments (Graph, INode, INode)"
> 
>    What I need to understand to make this code
> possible with 0.7 JGraphT lib ?

First, please go over the README.html file included in the JGraphT 
distribution.  The section on "Getting Started" covers the supported 
JDK/JRE combinations.  It sounds like there may be a problem with the 
retroweaver-generated backport, but I'd have to see a reproducible test 
case before I could tell you more.  Depending on your deployment 
constraints, you may be able to use jgrapht-jdk1.5.jar instead.

JVS

[jgrapht-users] DijkstraShortestPath

[Anderson A. <and...@ya...>]

   Hello All,

   Does anybody could provide an example of using
BellmanFordShortestPath?

   There is a plugin of a GIS application using
version 0.6 of JGraphT that uses DijkstraShortestPath
using the codeline:

   List
list=DijkstraShortestPath.findPathBetween(graph,
nodeI, nodeF); /* nodeI and F are objects of a simple
class with getCoordinate() method implemented by an
interface INode; */

   But now, when using the same code, with 0.7 JGraphT
jar jgrapht-jdk1.4.jar, a compiletime error is ocurred
saying that "The method findPathBetween(Graph, Object,
Object) in the type DijkstraShortestPath is not
applicaple for the arguments (Graph, INode, INode)"

   What I need to understand to make this code
possible with 0.7 JGraphT lib ?

   ---

   Thanks.
   Anderson.

   ---

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 

Re: [jgrapht-users] JGraphT

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

Kevin Green wrote:
> Hi, I'm working on a summer research project and we are using JGraph and 
> JGraphT the thing we have now come across is that we would like to change from 
> not allowing multiple edges to allowing multiple edges. The thing is we are 
> currently using ListenableDirectedGraph which does not allow multiple edges 
> between the same two vetices. Also, I'm not sure exactly how to implement the 
> ListenableGraph with the DirectedMultigraph. Basically we need the missing 
> class ListenableDirectedMultigraph and I was wondering if someone may have 
> written this already or if I could get some help to write it. Thanks.

(Please mail to the list so that others will be able to find answers to 
similar questions later.)

The only thing special that DirectedMultigraph does is super(ef, true, 
true).  The extra parameters set allowMultipleEdges=true and 
allowLoops=true.  So you just need to do the same in your 
ListenableDirectedMultigraph constructor, which should extend 
DefaultListenableGraph and implement DirectedGraph (just copy 
ListenableDirectedGraph).

JVS

Re: [jgrapht-users] DFS Question

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

Welson Sun wrote:
> Thanks for the prompt reply and fix.
> 
> One related question is that if the SCC decomposition function in JGraphT
> uses this DFS function? It should be easy to find out, but I am just
> lazy............. 

StrongConnectivityInspector uses its own private little DFS routine 
because DepthFirstIterator doesn't provide the discovery/finish times. 
At the time that Christian contributed it, we discussed enhancing 
DepthFirstIterator to be reusable here, but didn't do anything about it. 
  Yet another TODO.

JVS

Re: [jgrapht-users] DFS Question

[Welson S. <wel...@ya...>]

Thanks for the prompt reply and fix.

One related question is that if the SCC decomposition function in JGraphT
uses this DFS function? It should be easy to find out, but I am just
lazy............. 

-----Original Message-----
From: John V. Sichi [mailto:js...@gm...] 
Sent: Friday, August 04, 2006 10:45 PM
To: Welson Sun
Cc: jgr...@li...
Subject: Re: [jgrapht-users] DFS Question

Welson Sun wrote:
> Since it is impossible to share my source code due to various reasons, 
> I have attached a very simple Java code which reproduce this problem. 
> It creates a graph with the same topology, and use 
> org._3pq.jgrapht.traverse.DepthFirstIterator to do DFS. See the .jpg 
> for the graph, and the DFS output is:
> 
> A
> B
> C
> G
> I
> F
> E
> H
> D  <---- This is wrong
> J
> K
> L

Doh.  This is embarrassing.  Looks like the bug has been there from the very
first version in which DFS appeared (0.4.1), even before I joined the
project, but has survived numerous refactorings by me!  The problem is that
encounterVertexAgain should be promoting J when it sees it the second time,
but it currently just leaves it where it is in the middle of the stack.

At some point certain parties even made an attempt to tell me about it, but
because I couldn't understand their description and they didn't follow up
with a testcase, I closed the bug:

http://sourceforge.net/tracker/index.php?func=detail&aid=1169182&group_id=86
459&atid=579687

So thank you very much for raising it.  A simple fix is to change
DepthFirstIterator.encounterVertexAgain to do this:

int i = m_stack.indexOf(vertex);
if (i != -1) {
     m_stack.remove(i);
     m_stack.add(vertex);
}

I'll see if I can come up with something efficient when I fix it permanently
in 0.7.1.  There have been requests to keep track of the discovery and
finish time, so I can probably kill two birds with one stone by keeping this
info in the "seen data" and using it to know whether something is still on
the stack or not without linear search.

JVS

Re: [jgrapht-users] DFS Question

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

Welson Sun wrote:
> Since it is impossible to share my source code due to various reasons, I
> have attached a very simple Java code which reproduce this problem. It
> creates a graph with the same topology, and use
> org._3pq.jgrapht.traverse.DepthFirstIterator to do DFS. See the .jpg for the
> graph, and the DFS output is:
> 
> A
> B
> C
> G
> I
> F
> E
> H
> D  <---- This is wrong
> J
> K
> L

Doh.  This is embarrassing.  Looks like the bug has been there from the 
very first version in which DFS appeared (0.4.1), even before I joined 
the project, but has survived numerous refactorings by me!  The problem 
is that encounterVertexAgain should be promoting J when it sees it the 
second time, but it currently just leaves it where it is in the middle 
of the stack.

At some point certain parties even made an attempt to tell me about it, 
but because I couldn't understand their description and they didn't 
follow up with a testcase, I closed the bug:

http://sourceforge.net/tracker/index.php?func=detail&aid=1169182&group_id=86459&atid=579687

So thank you very much for raising it.  A simple fix is to change 
DepthFirstIterator.encounterVertexAgain to do this:

int i = m_stack.indexOf(vertex);
if (i != -1) {
     m_stack.remove(i);
     m_stack.add(vertex);
}

I'll see if I can come up with something efficient when I fix it 
permanently in 0.7.1.  There have been requests to keep track of the 
discovery and finish time, so I can probably kill two birds with one 
stone by keeping this info in the "seen data" and using it to know 
whether something is still on the stack or not without linear search.

JVS

Re: [jgrapht-users] DFS Question

[Welson S. <wel...@ya...>]

Since it is impossible to share my source code due to various reasons, I
have attached a very simple Java code which reproduce this problem. It
creates a graph with the same topology, and use
org._3pq.jgrapht.traverse.DepthFirstIterator to do DFS. See the .jpg for the
graph, and the DFS output is:

A
B
C
G
I
F
E
H
D  <---- This is wrong
J
K
L


Welson
 

-----Original Message-----
From: John V. Sichi [mailto:js...@gm...] 
Sent: Friday, August 04, 2006 8:01 PM
To: Welson Sun
Cc: jgr...@li...
Subject: Re: [jgrapht-users] DFS Question

Welson Sun wrote:
> I have got a DG (see attached pic), using 
> org._3pq.jgrapht.traverse.DepthFirstIterator I got the following DFS
> sequence:
> 
> START
> input
> ._2biquad.Add
> ._2biquad.b3
> ._2biquad.Add2
> ._2biquad.b
> ._2biquad.a3
> ._2biquad.Add7
> ._2biquad.a2
> ._2biquad.Add1
> output
> STOP
> 
> I don't think this sequence is correct, any insights before I dig into 
> the source code?

The sequence is not correct, but without the source code for a JUnit
testcase reproducing the problem in isolation, it's hard to say more.

JVS

Re: [jgrapht-users] DFS Question

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

Welson Sun wrote:
> I have got a DG (see attached pic), using
> org._3pq.jgrapht.traverse.DepthFirstIterator I got the following DFS
> sequence:
> 
> START
> input
> ._2biquad.Add
> ._2biquad.b3
> ._2biquad.Add2
> ._2biquad.b
> ._2biquad.a3
> ._2biquad.Add7
> ._2biquad.a2
> ._2biquad.Add1
> output
> STOP
> 
> I don't think this sequence is correct, any insights before I dig into the
> source code?

The sequence is not correct, but without the source code for a JUnit 
testcase reproducing the problem in isolation, it's hard to say more.

JVS

[jgrapht-users] DFS Question

[Welson S. <wel...@ya...>]

I have got a DG (see attached pic), using
org._3pq.jgrapht.traverse.DepthFirstIterator I got the following DFS
sequence:

START
input
._2biquad.Add
._2biquad.b3
._2biquad.Add2
._2biquad.b
._2biquad.a3
._2biquad.Add7
._2biquad.a2
._2biquad.Add1
output
STOP

I don't think this sequence is correct, any insights before I dig into the
source code?


Welson

Re: [jgrapht-users] all against all shortest path

[Aaron H. <aa...@li...>]

Hmm, for a sparse graph, which I'd wager your 1% graph could be  
considered, doing an iterated Dijkstra will be more efficient than  
the Floyd-Warshall -- O(N E log N) vs O(N^3), if I remember right.  
Other than that I don't have a clear intuition beyond John's good  
idea...

good luck!
-A
--
Aaron Harnly
Center for Computational Learning Systems
Columbia University
http://harnly.net

On Jul 21, 2006, at 3:35 PM, John V. Sichi wrote:

> Muhamad Abu-Much wrote:
>>  i have a undirected weighted graph, i want to find a shortest  
>> path which contains the given set of nodes, or as many as possible  
>> of the given
>>  set.
>>
>>  any idea would be appreciated
>>
>>  i have implemented warshall algorithm but the all pairs solution  
>> but it is time consuming since my graph is a littile bit large
>>  5552 vertices and 235222 edges.
>>
>>  which iterator should i use ?, the shortest path is based on the  
>> weight of the edge.
>
> There's probably a standard algorithm for this if you check a graph
> theory book.  Off the top of my head, maybe you could start from the
> desired "waypoint" set and for each member, find a shortest path to  
> the
> source and target independently.  Link up the two halves, do that for
> each vertex in the waypoint set, and then score them based on combined
> pathlength and number of other waypoint vertices included,  
> weighting the
> two in whatever way makes sense for your application.
>
> Whatever you come up with, please consider contributing it (and your
> all-pairs implementation) to JGraphT if it can be expressed  
> generically.
>
> JVS
>
> ---------------------------------------------------------------------- 
> ---
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to  
> share your
> opinions on IT & business topics through brief surveys -- and earn  
> cash
> http://www.techsay.com/default.php? 
> page=join.php&p=sourceforge&CID=DEVDEV
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

Re: [jgrapht-users] all against all shortest path

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

Muhamad Abu-Much wrote:
>  i have a undirected weighted graph, i want to find a shortest path which contains the given set of nodes, or as many as possible of the given 
>  set.
> 
>  any idea would be appreciated
> 
>  i have implemented warshall algorithm but the all pairs solution but it is time consuming since my graph is a littile bit large 
>  5552 vertices and 235222 edges.
> 
>  which iterator should i use ?, the shortest path is based on the weight of the edge.

There's probably a standard algorithm for this if you check a graph 
theory book.  Off the top of my head, maybe you could start from the 
desired "waypoint" set and for each member, find a shortest path to the 
source and target independently.  Link up the two halves, do that for 
each vertex in the waypoint set, and then score them based on combined 
pathlength and number of other waypoint vertices included, weighting the 
two in whatever way makes sense for your application.

Whatever you come up with, please consider contributing it (and your 
all-pairs implementation) to JGraphT if it can be expressed generically.

JVS

[jgrapht-users] JGraphT Version 0.7.0 Released

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

Or should I say JGraphT<V,E>? Generics are here, and there are a lot of
interface-breaking changes in this release, so it will be the bumpiest
upgrade yet, but it should be well worth it to anyone interested in
type-safety.

I have also created a wiki for the JGraphT community (free/ad-supported
hosting courtesy of wikispaces.com):

http://wiki.jgrapht.org

Join now and let us know how you're using the project!

JVS

Re: [jgrapht-users] preparing for 0.7 release

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

Aaron Harnly wrote:
> One question: What exactly is the purpose of the Edge classes at this 
> point?
> 
> There's all this bother in specifying the type for generics, and passing 
> the class, yet they seem to do very little. As far as I can tell, 
> there's no particular interface they need implement, nor any public 
> methods in the DefaultEdge class. So is it being held onto just in case 
> we want to subclass and add our own behaviors? Yet it the edge doesn't 
> know its source and target vertices, how much interesting behavior could 
> we really add -- or is the idea mainly leaving room for arbitrary 
> labels, for example?

It's type-safety in general (labels are just one possible use).  To take 
today's current fad, suppose you're modeling a social network; you might 
have class Person as vertex and class Relationship as edge, where 
Relationship has extra attributes like isFriend, isColleague, or isEnemy 
(I'm still waiting for anti-social networking).

Then you would do things like

Graph<Person,Relationship> socialNetwork = ...;
Relationship r = socialNetwork.getEdge(valjean, javert);
if (r.isFriend()) {
     ...
}

No more casting.  However, you may only have a vertex class but no edge 
class; in that case you have to specify DefaultEdge everywhere, which is 
a pain.  Maybe one day Sun will add default values for generic 
parameters (available in C++ templates for years now).

Note that when using an edge class, it increases efficiency if you make 
it extend DefaultEdge, because intrusive references hidden in 
IntrusiveEdge allow us to avoid hash-lookups in the implementations of 
getEdgeSource and getEdgeTarget.

JVS

[jgrapht-users] preparing for 0.7 release

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

I spent the weekend on a lot of cleanup work in preparation for the release:

- purging a lot of obsolete code in experimental, and getting the rest 
buildable again

- eliminating all lint warnings except for experimental and test code

- moving isomorphism code to experimental (needs more work for generics 
and some other things before it's ready for prime time)

- standardizing file headers and Subversion keyword expansion

- fixing all Javadoc errors/warnings

- fixing Eclipse warnings

It would be helpful if anyone who has the time could pull the latest 
code from Subversion and test it out, in particular on Windows since I 
do all of my development on Linux.

I still have the items below to take care of before release:

- fix/suppress warnings in experimental and test

- run Jalopy

- test out retroweaver

- figure out how to rework CVS tags support in build.xml to target 
Subversion instead

- update release notes, wiki, sample code, etc.

JVS

[jgrapht-users] wiki for JGraphT

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

I've created a wiki for the JGraphT project:

http://jgrapht.wikispaces.com

If you use JGraphT, please join the space and (once you get 
authorization to edit) add some info about yourself and your project.

JVS

Re: [jgrapht-users] Auto-Layout and JGraphAddons

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

John V. Sichi wrote:
> Recently, someone named Carl Anderson contacted me saying he could 
> contribute code to integrate JGraphT with Touchgraph (see 
> www.touchgraph.com).  I've asked him for the files; I'll check them in 
> once he sends them to me.

Carl sent me the files, so I have committed them to Subversion.

For now, I put his converter into the experimental area.  (It's not a 
full adapter like we have for JGraph.)  To run the touchgraph demo, run 
"ant exp.touchgraph".  I don't know what I'm doing with GUI stuff so the 
way it comes out you have to resize the window to see anything, and it 
would disappear immediately if it weren't for the 
Thread.currentThread.sleep call I put in.  Help!

JVS

Re: [jgrapht-users] Auto-Layout and JGraphAddons

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

Xinuo Chen wrote:
> I searched the forum and found that this problem is related to layout thing
> and layout needs JGraphAddons. But I can't find it in jgraph.com. 

The JGraph folks seem to have pushed layout over into their commercial 
side.  For old open-source versions of jgraphaddons, you should be able 
to get it from their sf.net download site if you dig.

I have an old copy available here:

http://p4web.eigenbase.org//open/dev/thirdparty/jgraphaddons-1.0.5-src.zip

> By the way, I am using JGraph to draw many network nodes and show their
> connections on the graph.

Recently, someone named Carl Anderson contacted me saying he could 
contribute code to integrate JGraphT with Touchgraph (see 
www.touchgraph.com).  I've asked him for the files; I'll check them in 
once he sends them to me.

JVS