jgrapht-users — JGraphT user list.

[jgrapht-users] JGraphT Version 0.7.1 Released

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

This is a maintenance release which includes a number of bugfixes and 
contributions which have accumulated since the 0.7.0 release.

Many thanks to all who have contributed code, tests, bugs, bugfixes, 
questions, and answers!

JVS

[jgrapht-users] answered my own question!

[Filip I. <dj...@gm...>]

Actually, Im quite impressed, It simply is a breadth first iterator!
That saves me so much time, Thanks!!!

It works like a charm.

[jgrapht-users] Breadth First Search?

[Filip I. <dj...@gm...>]

Hello,
Im new to JGraphT and it seems like a great API. I was wondering if
someone could direct me to a breadth first iteration example?
Specifically, what I need to do is split a graph into n subgraphs
equally. For example, I have a graph that resembles a square  box with
many evenly connected boxes (vertices) inside it.  I would like to
iterate through in a breadth first manor, adding an even split of the
number of vertices into each of the n subgraphs. I want to essentially
evenly distribute connected vertices based on a total vertex count /
number of subgraphs with a breadth first iteration.

This may be a stupid question and as easy as just calling the
iterator's next function, but Im just curious if I need to use the
encounterNextVertex(), encoutnerVertexAgain() and
isConnectedComponentExhausted()  or if can just simply do this:

BreadthFirstIterator<UndirectedWeightedGraph<int,
DefaultWeightedEdge>> bf = new......
while (!bf.isConnectedComponentExhausted())
{
   vertex v = provideNextVertex();
   set.add(v);
}

Thanks for the help.
Filip

Re: [jgrapht-users] Maps as graphs

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

Trevor Harmon wrote:
> On Jan 23, 2007, at 12:28 PM, Richard Moore wrote:
> 
>> I'm interested in modelling a map of a city as a JGraphT graph.  
>> I've had
>> reasonable success so far, using custom objects at nodes to represent
>> junctions, etc. I'd like to be able to associate names with edges,  
>> in order
>> to implement street names. I've tried extending  
>> DefaultWeightedEdge, with a
>> new object, but this doesn't seem to work. Has anyone got any  
>> experience
>> with this, or suggestions how this may be done, without recourse to a
>> secondary data structure to lookup edge names?
> 
> Couldn't you just add a "name" field to whatever class you're using  
> for edges?

Richard, this discussion on the wiki may be relevant:

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

JVS

Re: [jgrapht-users] Maps as graphs

[Trevor H. <tr...@vo...>]

On Jan 23, 2007, at 12:28 PM, Richard Moore wrote:

> I'm interested in modelling a map of a city as a JGraphT graph.  
> I've had
> reasonable success so far, using custom objects at nodes to represent
> junctions, etc. I'd like to be able to associate names with edges,  
> in order
> to implement street names. I've tried extending  
> DefaultWeightedEdge, with a
> new object, but this doesn't seem to work. Has anyone got any  
> experience
> with this, or suggestions how this may be done, without recourse to a
> secondary data structure to lookup edge names?

Couldn't you just add a "name" field to whatever class you're using  
for edges?

Trevor

[jgrapht-users] Maps as graphs

[Richard M. <ric...@ho...>]

Hi,
I'm interested in modelling a map of a city as a JGraphT graph. I've had 
reasonable success so far, using custom objects at nodes to represent 
junctions, etc. I'd like to be able to associate names with edges, in order 
to implement street names. I've tried extending DefaultWeightedEdge, with a 
new object, but this doesn't seem to work. Has anyone got any experience 
with this, or suggestions how this may be done, without recourse to a 
secondary data structure to lookup edge names?
Many thanks,
Richard Moore

_________________________________________________________________
Get Hotmail, News, Sport and Entertainment from MSN on your mobile.  
http://www.msn.txt4content.com/

Re: [jgrapht-users] degree of a vertex

[Trevor H. <tr...@vo...>]

On Jan 19, 2007, at 6:49 AM, Odemir Bruno wrote:

> I would like to know, how to get the degree of a vertex (number of
> edges) using jgrapht.

Graph.edgesOf(V).size()

or

UndirectedGraph.degreeOf(V)

Trevor

[jgrapht-users] iterator code error

[Odemir B. <br...@ic...>]

Hi,

I am trying to use the Iterator to browse the edges. What is wrong with 
my code ?


       DefaultWeightedEdge e;
        
        .
        .
        .
        
        Set conj;
        Iterator Iter;
        conj = g.edgeSet();
        Iter = conj.iterator();
        e = Iter.next();

      error message:  cannot convert from Object to DefaultWeightedEdge

Thanks,
Bruno

[jgrapht-users] degree of a vertex

[Odemir B. <br...@ic...>]

Hello,

I would like to know, how to get the degree of a vertex (number of 
edges) using jgrapht.
Could someone help me?

Thanks,

Bruno

Re: [jgrapht-users] Bug in removeAllEdges?

[Trevor H. <tr...@vo...>]

On Nov 26, 2006, at 6:47 AM, John V. Sichi wrote:

> This one is easy to fix; we can just apply  
> Collections.unmodifiableSet to the computed Set returned from  
> edgesOf.  Then you'll get the UnsupportedOperationException in all  
> cases (at the price of one extra object allocation, and possible  
> breakage for existing apps).

Thanks; consistency is important.

> (although you should be using ArrayList instead of Vector).

Good point; I've changed it in my code.

> If you want, log an enhancement request for convenience methods to  
> be added to the Graphs utility class (removeEdgesOf,  
> removeOutgoingEdgesOf, and removeIncomingEdgesOf).  If you were  
> searching for them, others probably are too.

That's okay. The ArrayList idiom works well enough for now.

Trevor

Re: [jgrapht-users] Bug in removeAllEdges?

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

Trevor Harmon wrote:
> On Nov 25, 2006, at 10:49 PM, Trevor Harmon wrote:
> 
>> But the following JGraphT program throws a
>> ConcurrentModificationException:
>>
>> DirectedGraph<String, DefaultEdge> g =
>>     new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
>> String s1 = "s1";
>> String s2 = "s2";
>> g.addVertex(s1);
>> g.addVertex(s2);
>> g.addEdge(s1, s2);
>> g.edgesOf(s1).clear();
> 
> Oops, I don't think I tested this correctly. The above program doesn't 
> throw an exception. In fact, it doesn't do anything. The graph remains 
> unchanged!
> 
> Also, replacing the edgesOf call with outgoingEdgesOf causes an 
> UnsupportedOperationException.
> 
> The latter may be acceptable behavior, but surely the former is not.

This one is easy to fix; we can just apply Collections.unmodifiableSet 
to the computed Set returned from edgesOf.  Then you'll get the 
UnsupportedOperationException in all cases (at the price of one extra 
object allocation, and possible breakage for existing apps).

>> Regardless of this problem, how is one supposed to remove all
>> outgoing edges from a vertex?
> 
> So far, the best I've come up with is this:
> 
> removeAllEdges( new Vector<Edge>(outgoingEdgesOf(node)) );
> 
> where "Edge" is the edge class and "node" is a vertex instance.
> 
> Unfortunately, this requires allocating a temporary vector and copying 
> every edge into it. Is there a more efficient way?

There is no more efficient way (although you should be using ArrayList 
instead of Vector).  This is a standard pattern for dealing with the 
same issue in the Java collection classes, and is used in the 
implementation for AbstractBaseGraph.removeVertex too.

If you want, log an enhancement request for convenience methods to be 
added to the Graphs utility class (removeEdgesOf, removeOutgoingEdgesOf, 
and removeIncomingEdgesOf).  If you were searching for them, others 
probably are too.

JVS

Re: [jgrapht-users] Bug in removeAllEdges?

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

Trevor Harmon wrote:
> Well, that part I would still say is a bug. I could understand it if 
> outgoingEdgesOf, incomingEdgesOf, and edgesOf all ended up causing the 
> ConcurrentModificationException -- at least that would be consistent. 
> But that's not the case here. The behavior of an API shouldn't be left 
> to chance. :)

Go ahead and create a bug report for this inconsistency.  It may not get 
addressed for a while because the fix isn't trivial.

For a directed graph, edgesOf has to be computed on the fly by combining 
the incoming and outgoing edge sets of the vertex.  And that computation 
isn't something that's easy to express as a derived Set implementation, 
due to the requirement to filter out the duplicates for self-loops.  So 
the fix requires us to maintain a graph-level timestamp which can be 
used by ArrayUnenforcedSet to detect the ConcurrentModificationException.

One side-effect of the fix would be that any application code which is 
currently relying on the buffering behavior of edgesOf would break.  But 
in this case, a more consistent and less surprising API trumps 
backward-compatibility.

JVS

Re: [jgrapht-users] Bug in removeAllEdges?

[Trevor H. <tr...@vo...>]

On Nov 25, 2006, at 10:49 PM, Trevor Harmon wrote:

> But the following JGraphT program throws a
> ConcurrentModificationException:
>
> DirectedGraph<String, DefaultEdge> g =
> 	new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
> String s1 = "s1";
> String s2 = "s2";
> g.addVertex(s1);
> g.addVertex(s2);
> g.addEdge(s1, s2);
> g.edgesOf(s1).clear();

Oops, I don't think I tested this correctly. The above program  
doesn't throw an exception. In fact, it doesn't do anything. The  
graph remains unchanged!

Also, replacing the edgesOf call with outgoingEdgesOf causes an  
UnsupportedOperationException.

The latter may be acceptable behavior, but surely the former is not.  
And in any case, shouldn't there be some built-in way to remove all  
edges from a vertex?

> Regardless of this problem, how is one supposed to remove all
> outgoing edges from a vertex?

So far, the best I've come up with is this:

removeAllEdges( new Vector<Edge>(outgoingEdgesOf(node)) );

where "Edge" is the edge class and "node" is a vertex instance.

Unfortunately, this requires allocating a temporary vector and  
copying every edge into it. Is there a more efficient way?

Trevor

Re: [jgrapht-users] Bug in removeAllEdges?

[Trevor H. <tr...@vo...>]

On Nov 25, 2006, at 1:24 PM, John V. Sichi wrote:

> Trevor Harmon wrote:
>> The attached program throws a ConcurrentModificationException, and  
>> I don't know why. Even stranger, if outgoingEdgesOf is changed to  
>> edgesOf, the exception is not thrown. Doesn't make sense. Is this  
>> a bug?
>
> Not a bug, unless you consider the program below to indicate a bug  
> in the JDK :)

Let me rephrase my question then. The following JDK program works as  
expected:

List<String> list = new ArrayList<String>();
list.add("arm");
list.add("leg");
List<String> sublist = list.subList(0,1);
sublist.clear();

But the following JGraphT program throws a  
ConcurrentModificationException:

DirectedGraph<String, DefaultEdge> g =
	new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
String s1 = "s1";
String s2 = "s2";
g.addVertex(s1);
g.addVertex(s2);
g.addEdge(s1, s2);
g.edgesOf(s1).clear();

Regardless of this problem, how is one supposed to remove all  
outgoing edges from a vertex? That's all I'm trying to do. With the  
large number of methods available in JGraphT, I would have expected  
the API to provide a straightforward way of doing this (without  
having to iterate over the edges myself).

> The outgoingEdgesOf vs edgesOf behavior is just a matter of getting  
> lucky with one.

Well, that part I would still say is a bug. I could understand it if  
outgoingEdgesOf, incomingEdgesOf, and edgesOf all ended up causing  
the ConcurrentModificationException -- at least that would be  
consistent. But that's not the case here. The behavior of an API  
shouldn't be left to chance. :)

Trevor

Re: [jgrapht-users] Bug in removeAllEdges?

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

Trevor Harmon wrote:
> The attached program throws a ConcurrentModificationException, and I 
> don't know why. Even stranger, if outgoingEdgesOf is changed to edgesOf, 
> the exception is not thrown. Doesn't make sense. Is this a bug?

Not a bug, unless you consider the program below to indicate a bug in 
the JDK :)

The outgoingEdgesOf vs edgesOf behavior is just a matter of getting 
lucky with one.

JVS

----

import java.util.*;

public class Goodbye
{
     public static void main(String [] args)
     {
         List<String> list = new ArrayList<String>();
         list.add("arm");
         list.add("leg");
         List<String> sublist = list.subList(0,1);
         list.removeAll(sublist);
     }
}

[jgrapht-users] Bug in removeAllEdges?

[Trevor H. <tr...@vo...>]

The attached program throws a ConcurrentModificationException, and I  
don't know why. Even stranger, if outgoingEdgesOf is changed to  
edgesOf, the exception is not thrown. Doesn't make sense. Is this a bug?

Trevor

Re: [jgrapht-users] Doubt - Graph class / Weighted Graphs

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

These wiki pages may be helpful:

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

http://jgrapht.wikispaces.com/MigrationTo0.7

I'll send you a wikispaces invite so that if you want to share what you 
learn, you can update the migration page.

JVS

Anderson Adolfs wrote:
> Due to some changes with Graph class provided with
> JGraphT 0.7 lib, I am experiencing a problem.
> 
> /* An example code using JGraphT 0.6 lib */
> 
> Graph graph = new WeightedPseudograph();
> 
> INode node1 = new Node2D();
> graph.addVertex(node1);
> INode node2 = new Node2D();
> graph.addVertex(node2);
> 
> MyEdge edge = new MyEdge(node1, node2, f);
> edge.setWeight(feature.getGeometry().getLength());
> graph.addEdge(edge);
> 
> /* In 0.7 lib these relations were modified,
>  * Graph class has no more this addEdge method.
>  * Using JGraphT 0.7 lib, I'm trying:
>  */
> 
> WeightedGraph graph = new WeightedPseudograph(
> Edge.class );
> 
> INode node1 = new Node2D();
> graph.addVertex(node1);
> INode node2 = new Node2D();
> graph.addVertex(node2);
> 
> graph.setEdgeWeight(graph.addEdge(node1, node2),
> feature.getGeometry().getLength());
> 
> /* But I got a RuntimeException: Edge Factory failed
> */
> 
> java.lang.RuntimeException: Edge factory failed
> 	at
> org.jgrapht.graph.ClassBasedEdgeFactory.createEdge(Unknown
> Source)
> 	at
> org.jgrapht.graph.AbstractBaseGraph.addEdge(Unknown
> Source)
> 	at
> com.shortestpath.topology.GraphFactory.createGraph(GraphFactory.java:124)
> 	at
> com.shortestpath.jgraphtLib.PlugIn.run(PlugIn.java:101)
> 	at 
> 
> com.vividsolutions.jump.workbench.ui.task.TaskMonitorManager$TaskWrapper.run(TaskMonitorManager.java:118)
> 	at java.lang.Thread.run(Thread.java:595)
> Caused by: java.lang.InstantiationException:
> com.shortestpath.topology.Edge
> 	at java.lang.Class.newInstance0(Class.java:335)
> 	at java.lang.Class.newInstance(Class.java:303)
> 	... 6 more
> 
>    I´ll be thankfull for any help.
> 
>    Anderson.

[jgrapht-users] Doubt - Graph class / Weighted Graphs

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

Due to some changes with Graph class provided with
JGraphT 0.7 lib, I am experiencing a problem.

/* An example code using JGraphT 0.6 lib */

Graph graph = new WeightedPseudograph();

INode node1 = new Node2D();
graph.addVertex(node1);
INode node2 = new Node2D();
graph.addVertex(node2);

MyEdge edge = new MyEdge(node1, node2, f);
edge.setWeight(feature.getGeometry().getLength());
graph.addEdge(edge);

/* In 0.7 lib these relations were modified,
 * Graph class has no more this addEdge method.
 * Using JGraphT 0.7 lib, I'm trying:
 */

WeightedGraph graph = new WeightedPseudograph(
Edge.class );

INode node1 = new Node2D();
graph.addVertex(node1);
INode node2 = new Node2D();
graph.addVertex(node2);

graph.setEdgeWeight(graph.addEdge(node1, node2),
feature.getGeometry().getLength());

/* But I got a RuntimeException: Edge Factory failed
*/

java.lang.RuntimeException: Edge factory failed
	at
org.jgrapht.graph.ClassBasedEdgeFactory.createEdge(Unknown
Source)
	at
org.jgrapht.graph.AbstractBaseGraph.addEdge(Unknown
Source)
	at
com.shortestpath.topology.GraphFactory.createGraph(GraphFactory.java:124)
	at
com.shortestpath.jgraphtLib.PlugIn.run(PlugIn.java:101)
	at 

com.vividsolutions.jump.workbench.ui.task.TaskMonitorManager$TaskWrapper.run(TaskMonitorManager.java:118)
	at java.lang.Thread.run(Thread.java:595)
Caused by: java.lang.InstantiationException:
com.shortestpath.topology.Edge
	at java.lang.Class.newInstance0(Class.java:335)
	at java.lang.Class.newInstance(Class.java:303)
	... 6 more

   I´ll be thankfull for any help.

   Anderson.



 
____________________________________________________________________________________
Sponsored Link

$420k for $1,399/mo. 
Think You Pay Too Much For Your Mortgage? 
Find Out! www.LowerMyBills.com/lre

Re: [jgrapht-users] doubt - LabeledElement

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

Anderson Adolfs wrote:
>    Hi,
> 
>    I am trying to understand a code of a plugin which
> uses a previous version of jgrapht lib.
>    There was a code which was using LabeledElement
> class to retrieve geographical informations, like
> this:
> 
>    Feature f =
> (Feature)((LabeledElement)list.get(i)).getLabel();
>    System.out.println(f.getGeometry());
> 
>    /* The output is: LINESTRING (3015.39 2030.00,
> 2852.40 1808.96) */
> 
>    Well, in JGraphT 0.7, the class LabeledElement was
> removed, how could I retrieve this information, using
> 0.7 lib, without the possibility of casting ? Is there
> any similar class ?

The application will have to be changed in order to work with 0.7.  The 
LabeledElement class was trivial; you can just put it back as private to 
the application if you really want to keep using it.

JVS

[jgrapht-users] doubt - LabeledElement

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

   Hi,

   I am trying to understand a code of a plugin which
uses a previous version of jgrapht lib.
   There was a code which was using LabeledElement
class to retrieve geographical informations, like
this:

   Feature f =
(Feature)((LabeledElement)list.get(i)).getLabel();
   System.out.println(f.getGeometry());

   /* The output is: LINESTRING (3015.39 2030.00,
2852.40 1808.96) */

   Well, in JGraphT 0.7, the class LabeledElement was
removed, how could I retrieve this information, using
0.7 lib, without the possibility of casting ? Is there
any similar class ?

   Thanks,

   Anderson.



 
____________________________________________________________________________________
Do you Yahoo!?
Everyone is raving about the all-new Yahoo! Mail beta.
http://new.mail.yahoo.com

Re: [jgrapht-users] Upgrading from 0.5.1 to 0.7

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

Naweed T wrote:
> Currently the project we're running uses jgrapht 0.5.1, and we're
> considering upgrading to version 0.7.  Is there a list of bug fixes
> and new features implemented from 0.5.1 to 0.6 to 0.7 so we can
> determine if the upgrade is worthwhile?  Also, is there a list of
> problems we can expect during the migration?

See the History section in this document:

http://jgrapht.svn.sourceforge.net/viewvc/*checkout*/jgrapht/trunk/README.html?revision=517

And this wiki page:

http://jgrapht.wikispaces.com/MigrationTo0.7

JVS

[jgrapht-users] Upgrading from 0.5.1 to 0.7

[Naweed T <na...@ho...>]

Hello,

Currently the project we're running uses jgrapht 0.5.1, and we're consideri=
ng upgrading to version 0.7.  Is there a list of bug fixes and new features=
 implemented from 0.5.1 to 0.6 to 0.7 so we can determine if the upgrade is=
 worthwhile?  Also, is there a list of problems we can expect during the mi=
gration?

Thanks,
NT=

Re: [jgrapht-users] new user vertex selection question

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

Angela S. Wise wrote:
>
> Hi, I’ve looked through the forum and mailing list archive and I’ve 
> seen this question asked but never answered. Any help I would very 
> much appreciate.
>
> I am trying to represent a smallish network topology (< 40 vertices) 
> but each of the vertices has a lot of information associated with it 
> (too much to display in the actual visualized node) so I would like to 
> allow the user to select a vertex and display the information in a 
> separate jPanel. However, all of the examples I’ve seen with node 
> selection have used JGraph, which seems too heavy-weight for my 
> project. Is there any way to fire an event when a user dynamically 
> selects a vertex in jGrapht?
>
> It looks like the JGraphAdapterDemo.java file is straddling the line 
> between using JGraph and JGraphT features, but I only needed to 
> install JGraphT to make it work. Are there additional JGraph features 
> that will work after only having installed JGraphT?
>
JGraphT includes a full distribution of JGraph, and by running 
JGraphAdapterDemo, you are already using JGraph. As the class name 
indicates, this is only meant as a demo; if you want to do anything 
serious with JGraph, you have to dig deeper into their API.

For example, JGraphModelAdapter.JGraphListener handles events from 
JGraph and translates them into corresponding modifications to the 
JGraphT model, but it doesn't do anything with selection events. For 
those, you would probably need to start here:

http://www.jgraph.com/pub/api/org/jgraph/event/GraphSelectionListener.html

JVS

[jgrapht-users] new user vertex selection question

[Angela S. W. <an...@ri...>]

Hi, I've looked through the forum and mailing list archive and I've seen
this question asked but never answered.  Any help I would very much
appreciate. 

 

I am trying to represent a smallish network topology (< 40 vertices) but
each of the vertices has a lot of information associated with it (too much
to display in the actual visualized node) so I would like to allow the user
to select a vertex and display the information in a separate jPanel.
However, all of the examples I've seen with node selection have used JGraph,
which seems too heavy-weight for my project.  Is there any way to fire an
event when a user dynamically selects a vertex in jGrapht?

 

It looks like the JGraphAdapterDemo.java file is straddling the line between
using JGraph and JGraphT features, but I only needed to install JGraphT to
make it work.  Are there additional JGraph features that will work after
only having installed JGraphT?

 

Thanks for your help,

Angela  (an...@ri...)

Re: [jgrapht-users] Jgrapht and java 1.3

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

Scemama Gerard wrote:
> Hi,
> I'm using Jgrapht for its shortest path algorithm.
> I'm developing an application for pda using j9 IBM which is compatible 
> only with java 1.3
> *Could you provide me with an older version of the library which is 
> compatible with java 1.3 ?
> *the version I use is only compaible with java 1.4.
> Thanks for answering.

If you go to the downloads page and scroll down to the pre-0.6.0 
releases, you should be able to get it.

http://sourceforge.net/project/showfiles.php?group_id=86459

Also, retroweaver now has support for producing pre-1.4 backports, so 
you could try that with the latest JGraphT and see if it works.

JVS