jgrapht-users — JGraphT user list.

Re: [jgrapht-users] Any function to return all paths between two vertices?

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

The closest thing is the KShortestsPaths algorithm.

JVS

On Mon, May 23, 2011 at 12:33 PM, Jack Gibson <ja...@ya...> wrote:
> Hi,
>
> Is there any class that returns me all paths that lead from vertice X to Y?
>
> I saw that there a couple of algorithms such as Dijkstra's but they all return
> *one* path from X to Y (in case of Dijkstra the shortest).
>
> The most interesting thing for me would be a functionality where I can define
> something like this:
>
>
> "Given that I have an undirected graph return me all possible paths from X to Y
> where the weight of the edges don't exceed a certain treshold!"
>
> Thanks!
>
> Gib
>
> ------------------------------------------------------------------------------
> What Every C/C++ and Fortran developer Should Know!
> Read this article and learn how Intel has extended the reach of its
> next-generation tools to help Windows* and Linux* C/C++ and Fortran
> developers boost performance applications - including clusters.
> http://p.sf.net/sfu/intel-dev2devmay
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] Graph Partitioning

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

Your requirements aren't clear, but if you mean you'd like to apply a
weight threshold to decide whether an edge should count as a
connection or not, then just create a subgraph view which filters the
edges based on weight, and then run ConnectivityInspector on that.

JVS

On Thu, Jun 2, 2011 at 11:17 AM, Ball, Nicholas S
<nic...@im...> wrote:
> Hello all,
> I see you have a way of generating Bipartite Graphs but do you have anything
> implemented that will split a graph into two graphs/sets based on the
> weighted values on the edges.
> If not, any idea where I can find a java implementation of this!? Been
> looking everywhere!
> Thank you and keep up the good work!
> Nicholas
>
> ------------------------------------------------------------------------------
> Simplify data backup and recovery for your virtual environment with vRanger.
> Installation's a snap, and flexible recovery options mean your data is safe,
> secure and there when you need it. Discover what all the cheering's about.
> Get your free trial download today.
> http://p.sf.net/sfu/quest-dev2dev2
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] Graph Partitioning

[Ball, N. S <nic...@im...>]

Hello all,

I see you have a way of generating Bipartite Graphs but do you have anything implemented that will split a graph into two graphs/sets based on the weighted values on the edges.

If not, any idea where I can find a java implementation of this!? Been looking everywhere!

Thank you and keep up the good work!

Nicholas

[jgrapht-users] my fault

[Ramin <ram...@un...>]

hi again,

I imported the wrong library. i looked into the JGraph library in the 
lib folder.
sorry for the inconvenience!

regards,
ramin

-- 
***********************************************************************
Ramin Soleymani-Fard
Networked Embedded Systems      http:   www.nes.uni-due.de
University of Duisburg-Essen    phone:  +49 (0)203-379-1609
Bismarckstr. 90, BC 519
47057 Duisburg
***********************************************************************

[jgrapht-users] classes in the library

[Ramin <ram...@un...>]

hello everyone,

i just downloaded the JGraphT library, because i need to calculate the 
k-connectivity of graphs.
As i wanted to start to use the library i noticed that the jar doesn't 
include multiple classes described in the
javadoc in particular for my use the SimpleGraph class and the 
ConnectivityInspector.
Am i missing something?

kind regards,
ramin

-- 
***********************************************************************
Ramin Soleymani-Fard
Networked Embedded Systems      http:   www.nes.uni-due.de
University of Duisburg-Essen    phone:  +49 (0)203-379-1609
Bismarckstr. 90, BC 519
47057 Duisburg
***********************************************************************

[jgrapht-users] Using jgrapht

[Ravali D. <rde...@pu...>]

Hello Everyone,

I am Ravali Devarapalli. I am currently pursuing Master's degree in Computer and Information Technology at Purdue University. I am interested in mining and analyzing location based information from webpages. I am planing to do my thesis in this regard.

My academic advisor has asked me to look into the workings of jgrapht as it is a popular graph analysis tool available today. I have never used it before...so i have gone through the website "www.jgrapht.org".

I have been able to find any installation or usage steps. It might be a simple question but i haven't been able to use it. I have downloaded the Windows version of latest version of jgrapht zip file. When i try to compile the programs "HelloJGrapht.java"...i get errors. Most of the errors are similar.

Error: Cannot find symbol DefaultEdge, SimpleGraph.

It is also giving me an error in "org.jgrapht.*" does not exist. I might have to set classpath in environmental variable. I don't know the solution. I tried looking up in discussion forums but could not find any relevant solution.

Could you please let me know where i am going wrong. and also how to properly exceute demo programs and any other programs that i may write in future.

Thank you for your time,
-Ravali Devarapalli.

[jgrapht-users] Any function to return all paths between two vertices?

[Jack G. <ja...@ya...>]

Hi, 

Is there any class that returns me all paths that lead from vertice X to Y? 

I saw that there a couple of algorithms such as Dijkstra's but they all return 
*one* path from X to Y (in case of Dijkstra the shortest). 
 
The most interesting thing for me would be a functionality where I can define 
something like this:


"Given that I have an undirected graph return me all possible paths from X to Y 
where the weight of the edges don't exceed a certain treshold!"

Thanks!

Gib

[jgrapht-users] Creating a tree with dynamic variables presenting the vertices

[hussel <ho...@ya...>]

Hello,

I want to create a tree, but I don't know initially the vertices of this
tree.
Thus I will have vertices: "v1" "v2", ....."vn".
How should I do to dynamically create variables that will make vertices and
also how to create links between the vertices.

Thank you very much for your help!

--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Creating-a-tree-with-dynamic-variables-presenting-the-vertices-tp2921540p2921540.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] [Fwd: dynamic DAG implementation, DirectedAcyclicGraph.java]

[anant.damle <ana...@gm...>]

Peter,
It has really helped me, Thanks a lot.

Thanks,
Anant Damle

--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Fwd-dynamic-DAG-implementation-DirectedAcyclicGraph-java-tp107898p2893090.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Getting all connected sets of a graph as graphs

[Tim J. <ts...@rc...>]

 Hi,

 On Mon, 25 Apr 2011 22:26:13 -0700, John Sichi <js...@gm...> 
 wrote:

> Does your ProteinGraph add anything interesting?  If not, you might
> consider discarding it and just using the out-of-the-box classes
> directly.

 Yes, it adds some functions that are specific for protein graphs, e.g. 
 determining the N-terminus and T-terminus of the protein chain and 
 returning different linear notations for protein graphs. I also plan to 
 add functions that draw the graph and write them to an image file.

 But I think my current way of implementing the ProteinGraph class is 
 far from perfect. I'll start a new thread for this though.

> If you need it for some reason, then either do what you said at the
> end to make copies of the subgraphs (using Graphs.addGraph), or else
> make ProteinGraph an interface and create subclasses for extending
> SimpleGraph and UndirectedSubgraph.

 Thanks a lot for, I didn't know about Graphs.addGraph() and it does 
 exactly what I wanted. Here's what I do now:

 List<Set<SSE>> conVertSets = ci.connectedSets();
 
 // Create graphs out of the connected sets
 for(Integer j = 0; j < conVertSets.size(); j++) {

             UndirectedSubgraph<SSE, LabeledEdge> sg = new 
 UndirectedSubgraph<SSE, LabeledEdge>(g, conVertSets.get(j), null);
             ProteinGraph<SSE, LabeledEdge> psg = new ProteinGraph<SSE, 
 LabeledEdge>(new ClassBasedEdgeFactory<SSE, 
 LabeledEdge>(LabeledEdge.class));
             Graphs.addGraph(psg, sg);
 }

 This works. :)


-- 
 Tim

Re: [jgrapht-users] Getting all connected sets of a graph as graphs

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

Does your ProteinGraph add anything interesting?  If not, you might
consider discarding it and just using the out-of-the-box classes
directly.

If you need it for some reason, then either do what you said at the
end to make copies of the subgraphs (using Graphs.addGraph), or else
make ProteinGraph an interface and create subclasses for extending
SimpleGraph and UndirectedSubgraph.

JVS

On Mon, Apr 25, 2011 at 4:00 AM, Tim Jesussek <ts...@rc...> wrote:
>
>  Hi list,
>
>  I'm new to jgrapht and I'm using it to model protein graphs. What I
>  need to do is split a graph G into multiple graphs, each of which should
>  represent a connected set of G. I have found the ConnectivityInspector
>  class and its connectedSets() method, but I'm not sure on how to turn
>  the edge set it returns into a new graph. Can anybody tell me how to do
>  that?
>
>  Some more details on what I've done so far follow: I have written a
>  ProteinGraph class that extends SimpleGraph<V, E> and implements
>  UndirectedGraph<V, E>. I have also written a LabeledEdge class that
>  extends DefaultEdge. Both of this shouldn't make much of a difference I
>  guess. Here is my code so far:
>
>
>  // Creates a ProteinGraph from the connectivity matrix of all
>  super-secondary structures of a protein chain
>  ProteinGraph<SSE, LabeledEdge> g = chainCM.toJGraph();
>
>  // Get all connected sets
>  ConnectivityInspector<SSE, LabeledEdge> ci = new
>  ConnectivityInspector<SSE, LabeledEdge>(g);
>  List<Set<SSE>> conSets = ci.connectedSets();
>
>  // Create graphs out of the connected sets
>  for(Integer j = 0; j < conSets.size(); j++) {
>
>     // I can do this...
>     UndirectedSubgraph<SSE, LabeledEdge> subGraph = new
>  UndirectedSubgraph<SSE, LabeledEdge>(g, conSets.get(j), null);
>
>     // ... but I would like to do something like this:
>     ProteinGraph<SSE, LabeledEdge> psg = new UndirectedSubgraph<SSE,
>  LabeledEdge>(g, conSets.get(j), null);
>     // or
>     ProteinGraph<SSE, LabeledEdge> psg = subGraph.toGraph();
>  }
>
>
>  Using that code, my question could also be formulated as 'How can I
>  turn a UndirectedSubgraph into a new Graph of a certain type (my
>  ProteinGraph class, in this case). Is there any way to do this? Or
>  should I write a new constructor for ProteinGraph that uses the SubGraph
>  to construct the ProteinGraph based on the vertix  set and edge set in
>  the subgraph?
>
>  Thanks for any hints,
>
>
> --
>  Tim
>
> ------------------------------------------------------------------------------
> Fulfilling the Lean Software Promise
> Lean software platforms are now widely adopted and the benefits have been
> demonstrated beyond question. Learn why your peers are replacing JEE
> containers with lightweight application servers - and what you can gain
> from the move. http://p.sf.net/sfu/vmware-sfemails
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] Getting all connected sets of a graph as graphs

[Tim J. <ts...@rc...>]

 Hi list,

 I'm new to jgrapht and I'm using it to model protein graphs. What I 
 need to do is split a graph G into multiple graphs, each of which should 
 represent a connected set of G. I have found the ConnectivityInspector 
 class and its connectedSets() method, but I'm not sure on how to turn 
 the edge set it returns into a new graph. Can anybody tell me how to do 
 that?

 Some more details on what I've done so far follow: I have written a 
 ProteinGraph class that extends SimpleGraph<V, E> and implements 
 UndirectedGraph<V, E>. I have also written a LabeledEdge class that 
 extends DefaultEdge. Both of this shouldn't make much of a difference I 
 guess. Here is my code so far:


 // Creates a ProteinGraph from the connectivity matrix of all 
 super-secondary structures of a protein chain
 ProteinGraph<SSE, LabeledEdge> g = chainCM.toJGraph();

 // Get all connected sets
 ConnectivityInspector<SSE, LabeledEdge> ci = new 
 ConnectivityInspector<SSE, LabeledEdge>(g);
 List<Set<SSE>> conSets = ci.connectedSets();
 
 // Create graphs out of the connected sets
 for(Integer j = 0; j < conSets.size(); j++) {

     // I can do this...
     UndirectedSubgraph<SSE, LabeledEdge> subGraph = new 
 UndirectedSubgraph<SSE, LabeledEdge>(g, conSets.get(j), null);

     // ... but I would like to do something like this:
     ProteinGraph<SSE, LabeledEdge> psg = new UndirectedSubgraph<SSE, 
 LabeledEdge>(g, conSets.get(j), null);
     // or
     ProteinGraph<SSE, LabeledEdge> psg = subGraph.toGraph();
 }


 Using that code, my question could also be formulated as 'How can I 
 turn a UndirectedSubgraph into a new Graph of a certain type (my 
 ProteinGraph class, in this case). Is there any way to do this? Or 
 should I write a new constructor for ProteinGraph that uses the SubGraph 
 to construct the ProteinGraph based on the vertix  set and edge set in 
 the subgraph?

 Thanks for any hints,


-- 
 Tim

[jgrapht-users] ConnectivityInspector and NeighborIndex

[Ethan K. <et...@gm...>]

Hi,

I have questions regarding the ConnectivityInspector and NeighborIndex
classes. If I were to use NeighborIndex's neighborsOf(V v) method, while
adding/removing edges in the graph, do I need to make a customized graph
type (that extends SimpleGraph, say), and add the NeighborIndex as a
listener?

In other words, if I declare NeighborIndex object using a SimpleGraph object
itself, a call to neighborsOf(V v) method would be inefficient?

I guess similar question can be asked for ConnectivityInspector's
connectedSetOf(V v), etc.


On another note, how does the above neighborsOf() method differ from using
Graph's method "edgesOf(V vertex)" method?

Any comments would be appreciated. Thanks!

Ethan Kim

[jgrapht-users] Changing Simple things

[Diego O. <die...@gm...>]

Hi Everybody,

I want to change simple things like the SHAPE of the Nodes and the color of
the background and font...

I have this code in method *private void positionVertexAt(Object vertex, int
x, int y) {* :
Map attr = cell.getAttributes();
        Rectangle2D b = GraphConstants.getBounds(attr);

        //2 = background of the NODE
        //5 = font of the NODE
        for (Object object : attr.values()) {
            System.out.println("MAP= " + object.toString());
        }

        //widht
        //height
        GraphConstants.setBounds(attr, new Rectangle(x, y, WIDTH, HEIGTH));


-----


There is a simple way right? How is it?

Thank you very much!

-- 
Diego Oliveira
Master's Program in Computer Science
Federal University of Rio Grande do Norte - UFRN
Natal-RN-Brazil

Re: [jgrapht-users] How do I get an ordered dependency iterator using JGraphT

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

Hey,

It's easier if you post some more information about your graph. Some
functions/classes that might come in handy for you:
-Graphs.getOppositeVertex(Graph<V,E> g, E e, V v):  Gets the vertex
opposite another vertex across an edge.
-Graph.getNeighbors()
Also, check the depthFirstIterator.
Besides that, you should be a bit more specific about your graph, type
of graph, properties like cyclic/simple/etc. Perhaps some short code
snippets.

br,

Joris


On Sun, Apr 10, 2011 at 11:46 AM, Peter Wilkinson <pro...@gm...> wrote:
> Hi, I'm working on a js dependency management project. I've been pointed at
> JGraphT which seems to offer a lot of handy stuff.
>
> However I'm having trouble finding the specific info I want which is how I
> can retrieve the vertexes in dependency order from a given starting node.
>
> e.g. I have a tree with 3 Vertexes A => B, B => C, A => C
>
> I want to iterate through the vertexes in order of A, B, C. I'm finding I
> get results like A, C, B.
>
> Cheers,
>
> Pete
>
> ------------------------------------------------------------------------------
> Xperia(TM) PLAY
> It's a major breakthrough. An authentic gaming
> smartphone on the nation's most reliable network.
> And it wants your games.
> http://p.sf.net/sfu/verizon-sfdev
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

Re: [jgrapht-users] vertex color change: how to?

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

Sure. Best thing you could do is just download the jgraphx package and
follow their tutorial on how to build a graph using jgrahpx. Next you
take your jgrapht graph and you replicate your graph in jgraphx.
Jgraphx has quite some fancy coloring support. Just change the
property of a vertex/edge. For example, set the property:
"fillColor=blue".

br,

Joris

On Wed, Apr 6, 2011 at 7:43 PM,  <jl...@ol...> wrote:
> Is there a way to make each vertex a different color?
>
>
>
> ------------------------------------------------------------------------------
> Xperia(TM) PLAY
> It's a major breakthrough. An authentic gaming
> smartphone on the nation's most reliable network.
> And it wants your games.
> http://p.sf.net/sfu/verizon-sfdev
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] How do I get an ordered dependency iterator using JGraphT

[Peter W. <pro...@gm...>]

Hi, I'm working on a js dependency management project. I've been pointed at
JGraphT which seems to offer a lot of handy stuff.

However I'm having trouble finding the specific info I want which is how I
can retrieve the vertexes in dependency order from a given starting node.

e.g. I have a tree with 3 Vertexes A => B, B => C, A => C

I want to iterate through the vertexes in order of A, B, C. I'm finding I
get results like A, C, B.

Cheers,

Pete

[jgrapht-users] vertex color change: how to?

[<jl...@ol...>]

Is there a way to make each vertex a different color?

Re: [jgrapht-users] Dijkstra Algorithm

[Daniel B. <DB...@it...>]

Hi Alejandro,
I had a similar situation a couple of years ago. John suggested using org.jgrapht.traverse.ClosestFirstIterator, a delegate of DijkstraShortestPath, which solved my problem. I ended up implementing something very similar to DijkstraShortestPath to calculate all shortest paths, but unfortunately couldn't contribute it at the time. Hope that helps.
http://jgrapht-users.107614.n3.nabble.com/All-shortest-paths-problem-td107976.html

Cheers,
Daniel


-----Original Message-----
From: Alexander Herz [mailto:ale...@my...] 
Sent: Wednesday, April 06, 2011 4:19 PM
To: jgr...@li...
Subject: Re: [jgrapht-users] Dijkstra Algorithm

Hi,

I realized this as well. What John probably means is that Dijkstra is
supposed to give you single soure shortest pairs,
so the shortest paths from a singlde node to all other nodes in the
graph. Currently, jgrapht only returns the shortest path in between
two nodes (and it is unclear if it caches any information or if each
call to Dijkstra has to recompute everything).

Also it wold be nice to get some more shortest path algos for specific
graphs (like DAG).

Alex

Am 06.04.2011 06:39, schrieb John Sichi:
> If you want all pairs, use FloydWarshallShortestPaths instead.
>
> JVS
>
> On Tue, Apr 5, 2011 at 1:53 PM, Alejandro Riveros Cruz
> <lal...@gm...> wrote:
>> Hi,
>>
>> First of all  thanks for your great work in the design and support of
>> JGraphT.
>> Currently i'm working in my master final  work, in this work i need to
>> calculate some similarity measures, based on path distances between vertex
>> over directed graphs, for this purpose a develop a java program that
>> performs the calculus using jgrapht.
>> Currently i have some problems, first the graphs are big, each graph has in
>> average 50000 vertex and more than 50000  edges.
>> I read about the Dijkstra algorithm and i know that if using the appropiate
>> structure  i.e. a priority queue, this algorithm can perform the search of
>> all shortest path between a selected vertex and all other vertex, in a
>> computational reasonable time.
>>
>> Searching on jGraphT library i found a Dijkstra implementaion for searching
>> the shortest path between two nodes, but no the implementation for searching
>> the shortest path between  all nodes, for this reason i  need to know if my
>> assumption about the implementation of Dijkstra is true? in such case, you
>> have planned the release of that algorithm soon?
>>
>>
>> Thanks in advance,
>>
>> Alejandro Riveros
>>
>> --
>> Alejandro Riveros Cruz
>> Ingeniero de Sistemas
>> Universidad Nacional de Colombia
>>
>> ------------------------------------------------------------------------------
>> Xperia(TM) PLAY
>> It's a major breakthrough. An authentic gaming
>> smartphone on the nation's most reliable network.
>> And it wants your games.
>> http://p.sf.net/sfu/verizon-sfdev
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>>
> ------------------------------------------------------------------------------
> Xperia(TM) PLAY
> It's a major breakthrough. An authentic gaming
> smartphone on the nation's most reliable network.
> And it wants your games.
> http://p.sf.net/sfu/verizon-sfdev
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users


-- 
-------------------------------------------------------
Lehrstuhl I2 Seidl
Sprachen und Beschreibungsstrukturen der Informatik
Institut fuer Informatik
Technische Universitaet Muenchen

Boltzmannstrasse 3  85748 Garching
http://www2.in.tum.de

Telefon: +89 289 181806
Fax: +89 289 18161
------------------------------------------------------- 


------------------------------------------------------------------------------
Xperia(TM) PLAY
It's a major breakthrough. An authentic gaming
smartphone on the nation's most reliable network.
And it wants your games.
http://p.sf.net/sfu/verizon-sfdev
_______________________________________________
jgrapht-users mailing list
jgr...@li...
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

Re: [jgrapht-users] Dijkstra Algorithm

[Alexander H. <ale...@my...>]

Hi,

I realized this as well. What John probably means is that Dijkstra is
supposed to give you single soure shortest pairs,
so the shortest paths from a singlde node to all other nodes in the
graph. Currently, jgrapht only returns the shortest path in between
two nodes (and it is unclear if it caches any information or if each
call to Dijkstra has to recompute everything).

Also it wold be nice to get some more shortest path algos for specific
graphs (like DAG).

Alex

Am 06.04.2011 06:39, schrieb John Sichi:
> If you want all pairs, use FloydWarshallShortestPaths instead.
>
> JVS
>
> On Tue, Apr 5, 2011 at 1:53 PM, Alejandro Riveros Cruz
> <lal...@gm...> wrote:
>> Hi,
>>
>> First of all  thanks for your great work in the design and support of
>> JGraphT.
>> Currently i'm working in my master final  work, in this work i need to
>> calculate some similarity measures, based on path distances between vertex
>> over directed graphs, for this purpose a develop a java program that
>> performs the calculus using jgrapht.
>> Currently i have some problems, first the graphs are big, each graph has in
>> average 50000 vertex and more than 50000  edges.
>> I read about the Dijkstra algorithm and i know that if using the appropiate
>> structure  i.e. a priority queue, this algorithm can perform the search of
>> all shortest path between a selected vertex and all other vertex, in a
>> computational reasonable time.
>>
>> Searching on jGraphT library i found a Dijkstra implementaion for searching
>> the shortest path between two nodes, but no the implementation for searching
>> the shortest path between  all nodes, for this reason i  need to know if my
>> assumption about the implementation of Dijkstra is true? in such case, you
>> have planned the release of that algorithm soon?
>>
>>
>> Thanks in advance,
>>
>> Alejandro Riveros
>>
>> --
>> Alejandro Riveros Cruz
>> Ingeniero de Sistemas
>> Universidad Nacional de Colombia
>>
>> ------------------------------------------------------------------------------
>> Xperia(TM) PLAY
>> It's a major breakthrough. An authentic gaming
>> smartphone on the nation's most reliable network.
>> And it wants your games.
>> http://p.sf.net/sfu/verizon-sfdev
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>>
> ------------------------------------------------------------------------------
> Xperia(TM) PLAY
> It's a major breakthrough. An authentic gaming
> smartphone on the nation's most reliable network.
> And it wants your games.
> http://p.sf.net/sfu/verizon-sfdev
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users


-- 
-------------------------------------------------------
Lehrstuhl I2 Seidl
Sprachen und Beschreibungsstrukturen der Informatik
Institut fuer Informatik
Technische Universitaet Muenchen

Boltzmannstrasse 3  85748 Garching
http://www2.in.tum.de

Telefon: +89 289 181806
Fax: +89 289 18161
------------------------------------------------------- 

Re: [jgrapht-users] Dijkstra Algorithm

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

If you want all pairs, use FloydWarshallShortestPaths instead.

JVS

On Tue, Apr 5, 2011 at 1:53 PM, Alejandro Riveros Cruz
<lal...@gm...> wrote:
> Hi,
>
> First of all  thanks for your great work in the design and support of
> JGraphT.
> Currently i'm working in my master final  work, in this work i need to
> calculate some similarity measures, based on path distances between vertex
> over directed graphs, for this purpose a develop a java program that
> performs the calculus using jgrapht.
> Currently i have some problems, first the graphs are big, each graph has in
> average 50000 vertex and more than 50000  edges.
> I read about the Dijkstra algorithm and i know that if using the appropiate
> structure  i.e. a priority queue, this algorithm can perform the search of
> all shortest path between a selected vertex and all other vertex, in a
> computational reasonable time.
>
> Searching on jGraphT library i found a Dijkstra implementaion for searching
> the shortest path between two nodes, but no the implementation for searching
> the shortest path between  all nodes, for this reason i  need to know if my
> assumption about the implementation of Dijkstra is true? in such case, you
> have planned the release of that algorithm soon?
>
>
> Thanks in advance,
>
> Alejandro Riveros
>
> --
> Alejandro Riveros Cruz
> Ingeniero de Sistemas
> Universidad Nacional de Colombia
>
> ------------------------------------------------------------------------------
> Xperia(TM) PLAY
> It's a major breakthrough. An authentic gaming
> smartphone on the nation's most reliable network.
> And it wants your games.
> http://p.sf.net/sfu/verizon-sfdev
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] Dijkstra Algorithm

[Alejandro R. C. <lal...@gm...>]

Hi,

First of all  thanks for your great work in the design and support of
JGraphT.
Currently i'm working in my master final  work, in this work i need to
calculate some similarity measures, based on path distances between vertex
over directed graphs, for this purpose a develop a java program that
performs the calculus using jgrapht.
Currently i have some problems, first the graphs are big, each graph has in
average 50000 vertex and more than 50000  edges.
I read about the Dijkstra algorithm and i know that if using the appropiate
structure  i.e. a priority queue, this algorithm can perform the search of
all shortest path between a selected vertex and all other vertex, in a
computational reasonable time.

Searching on jGraphT library i found a Dijkstra implementaion for searching
the shortest path between two nodes, but no the implementation for searching
the shortest path between  all nodes, for this reason i  need to know if my
assumption about the implementation of Dijkstra is true? in such case, you
have planned the release of that algorithm soon?


Thanks in advance,

Alejandro Riveros

-- 
Alejandro Riveros Cruz
Ingeniero de Sistemas
Universidad Nacional de Colombia

[jgrapht-users] independent sub-graphs

[Kyle D. <kyl...@gm...>]

We have a dependency graph mechanism built on JGraphT, and today we traverse
our directed graph in a serial manner, in topological order.

I want to experiment with multi-threading the graph traversal. Is there
anything I can use built into JGraphT that can analyze a graph to identify
opportunities for parallel traversal?

Re: [jgrapht-users] Algorithms for flow graphs

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

You could create a view graph which delegates to the real graph for
everything else, but returns the desired attribute when getEdgeWeight
is called.

See AsWeightedGraph for a similar case where we impose weights on top
of an unweighted graph.

JVS

On Thu, Mar 24, 2011 at 10:47 AM, Joris Kinable <de...@gm...> wrote:
> Hello,
>
> I'm about to build an algorithm for min-cost flow graphs. As you can
> imagine, this needs a flow graph which typically has the following
> properties:
>
> 1. Edges have a Capacity and a Cost
> 2. Vertices have a real postive/negative value indicating the
> demand/supply associated with each vertex.
> 3. The graph is directed
>
> Due to the generics in JgraphT I can easily create vertex/edge classes
> which maintain these values. There is however a problem with the
> currently existing algorithms in JgraphT. For example, in a flow
> graph, a shortest path is usually (or at least in my case) calculated
> using the edge costs as 'distances'. Furthermore, a max flow algorithm
> utilizes the edge capacities. When I would use
> org.jgrapht.alg.DijkstraShortestPath, the algorithm uses the
> getEdgeWeight(E edge) function to obtain the distances. Similarly,
> org.jgrapht.alg.EdmondsKarpMaximumFlow utilizes the getEdgeWeight(E
> edge) function to read the edge capacities. The getEdgeWeight(E edge)
> function can only return one value: either the edge capacity or the
> edge cost. What would be the cleanest way to resolve this issue
> (preferably something reusable by the jgrapht community)?
>
> ------------------------------------------------------------------------------
> Enable your software for Intel(R) Active Management Technology to meet the
> growing manageability and security demands of your customers. Businesses
> are taking advantage of Intel(R) vPro (TM) technology - will your software
> be a part of the solution? Download the Intel(R) Manageability Checker
> today! http://p.sf.net/sfu/intel-dev2devmar
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] Algorithms for flow graphs

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

Hello,

I'm about to build an algorithm for min-cost flow graphs. As you can
imagine, this needs a flow graph which typically has the following
properties:

1. Edges have a Capacity and a Cost
2. Vertices have a real postive/negative value indicating the
demand/supply associated with each vertex.
3. The graph is directed

Due to the generics in JgraphT I can easily create vertex/edge classes
which maintain these values. There is however a problem with the
currently existing algorithms in JgraphT. For example, in a flow
graph, a shortest path is usually (or at least in my case) calculated
using the edge costs as 'distances'. Furthermore, a max flow algorithm
utilizes the edge capacities. When I would use
org.jgrapht.alg.DijkstraShortestPath, the algorithm uses the
getEdgeWeight(E edge) function to obtain the distances. Similarly,
org.jgrapht.alg.EdmondsKarpMaximumFlow utilizes the getEdgeWeight(E
edge) function to read the edge capacities. The getEdgeWeight(E edge)
function can only return one value: either the edge capacity or the
edge cost. What would be the cleanest way to resolve this issue
(preferably something reusable by the jgrapht community)?