You can subscribe to this list here.
2003 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}
(2) 
_{Nov}

_{Dec}


2004 
_{Jan}
(1) 
_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}
(1) 
_{Jul}
(1) 
_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}

_{Dec}
(2) 
2005 
_{Jan}

_{Feb}
(1) 
_{Mar}
(5) 
_{Apr}
(1) 
_{May}

_{Jun}
(12) 
_{Jul}
(6) 
_{Aug}
(7) 
_{Sep}
(2) 
_{Oct}

_{Nov}
(1) 
_{Dec}

2006 
_{Jan}
(4) 
_{Feb}
(3) 
_{Mar}
(2) 
_{Apr}
(3) 
_{May}
(6) 
_{Jun}
(2) 
_{Jul}
(3) 
_{Aug}
(12) 
_{Sep}
(6) 
_{Oct}
(3) 
_{Nov}
(12) 
_{Dec}

2007 
_{Jan}
(6) 
_{Feb}

_{Mar}
(6) 
_{Apr}
(8) 
_{May}
(2) 
_{Jun}
(8) 
_{Jul}
(2) 
_{Aug}
(3) 
_{Sep}
(7) 
_{Oct}
(3) 
_{Nov}

_{Dec}
(1) 
2008 
_{Jan}
(11) 
_{Feb}
(4) 
_{Mar}
(8) 
_{Apr}
(3) 
_{May}
(4) 
_{Jun}
(1) 
_{Jul}

_{Aug}
(3) 
_{Sep}
(1) 
_{Oct}
(4) 
_{Nov}
(5) 
_{Dec}
(5) 
2009 
_{Jan}
(3) 
_{Feb}
(12) 
_{Mar}
(14) 
_{Apr}
(9) 
_{May}
(8) 
_{Jun}
(1) 
_{Jul}
(4) 
_{Aug}
(10) 
_{Sep}

_{Oct}
(10) 
_{Nov}

_{Dec}
(4) 
2010 
_{Jan}
(9) 
_{Feb}
(16) 
_{Mar}
(14) 
_{Apr}
(19) 
_{May}
(1) 
_{Jun}
(3) 
_{Jul}
(17) 
_{Aug}
(9) 
_{Sep}
(4) 
_{Oct}
(4) 
_{Nov}
(11) 
_{Dec}
(8) 
2011 
_{Jan}
(10) 
_{Feb}
(11) 
_{Mar}
(10) 
_{Apr}
(14) 
_{May}
(6) 
_{Jun}
(8) 
_{Jul}
(9) 
_{Aug}
(11) 
_{Sep}
(13) 
_{Oct}
(7) 
_{Nov}
(9) 
_{Dec}
(1) 
2012 
_{Jan}
(5) 
_{Feb}
(14) 
_{Mar}
(4) 
_{Apr}
(25) 
_{May}
(18) 
_{Jun}
(18) 
_{Jul}
(3) 
_{Aug}
(6) 
_{Sep}
(3) 
_{Oct}
(16) 
_{Nov}
(5) 
_{Dec}
(12) 
2013 
_{Jan}
(1) 
_{Feb}
(6) 
_{Mar}
(14) 
_{Apr}
(34) 
_{May}
(9) 
_{Jun}
(3) 
_{Jul}
(8) 
_{Aug}

_{Sep}
(10) 
_{Oct}
(11) 
_{Nov}
(11) 
_{Dec}
(15) 
2014 
_{Jan}
(2) 
_{Feb}
(6) 
_{Mar}
(11) 
_{Apr}
(12) 
_{May}
(6) 
_{Jun}
(7) 
_{Jul}

_{Aug}
(4) 
_{Sep}
(1) 
_{Oct}
(1) 
_{Nov}
(5) 
_{Dec}
(6) 
2015 
_{Jan}
(15) 
_{Feb}
(4) 
_{Mar}
(7) 
_{Apr}
(8) 
_{May}
(1) 
_{Jun}
(18) 
_{Jul}
(27) 
_{Aug}
(13) 
_{Sep}
(4) 
_{Oct}
(8) 
_{Nov}
(7) 
_{Dec}
(6) 
2016 
_{Jan}
(4) 
_{Feb}
(5) 
_{Mar}

_{Apr}
(15) 
_{May}
(5) 
_{Jun}
(4) 
_{Jul}
(1) 
_{Aug}
(1) 
_{Sep}
(7) 
_{Oct}

_{Nov}

_{Dec}

From: John V. Sichi <jsichi@gm...>  20090511 19:21:47

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@..., org.jgrapht.alg.KShortestPaths$PathWrapper@...] > > Where is my mistake? > > Thanks! 
From: Achim Beutel <A.B<eutel@gm...>  20090511 15:38:28

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@..., org.jgrapht.alg.KShortestPaths$PathWrapper@...] 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/freedslsurfflat/?ac=OM.AD.PD003K11308T4569a 
From: John V. Sichi <jsichi@gm...>  20090507 01:08:23

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 
From: Claudio Martella <claudio.martella@gm...>  20090506 21:07:21

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 <jsichi@...> 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 reimplementing 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 claudio.martella@... 
From: John V. Sichi <jsichi@gm...>  20090506 18:09:51

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 reimplementing 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 
From: Claudio Martella <claudio.martella@gm...>  20090506 10:35:42

Hi, 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 reimplementing 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. TIA /CM  Claudio Martella claudio.martella@... 
From: John V. Sichi <jsichi@gm...>  20090430 19:28:37

Claudio Martella wrote: > yes, that's what i want. i guess i should first transform my graph > into adjacent matrix representation in order to do so. Is there an > efficient way in jgrapht? We don't currently have the code for that; you could consider contributing it if you develop it. JVS 
From: Claudio Martella <claudio.martella@gm...>  20090430 15:01:44

yes, that's what i want. i guess i should first transform my graph into adjacent matrix representation in order to do so. Is there an efficient way in jgrapht? On Wed, Apr 29, 2009 at 9:10 PM, John V. Sichi <jsichi@...> wrote: > Hi Claudio, > > You probably want to first run an allpairs shortest path algorithm such as > FloydWarshall and then analyze the results from that. > > http://en.wikipedia.org/wiki/FloydWarshall_algorithm > > JGraphT does not yet have this in the library. > > JVS > > Claudio Martella wrote: >> >> Hello list! >> >> I'm trying to calculate the average path length of my graph and the >> diameter (longest shortest path). >> >> At the moment it's nonoptimized: >> >> for(Vertex source: graph.vertexSet()){ >> for(Vertex destination: graph.vertexSet()){ >> if(!source.equals(destination)){ >> List<DefaultWeightedEdge> path = >> DijkstraShortestPath.findPathBetween(graph, source, destination); >> if(path != null) >> averagePathLength += path.size(); >> } >> } >> } >> N = graph.vertexSet().size(); >> averagePathLength /= (N*(N1)); >> >> This code is simplified to explain you what I'm doing now. There's of >> course a misusage of resources and computational time. Any idea what >> is the best way to calculate average path lengths, diameter and every >> kind of graph property that would need to calculate paths reusing >> resources and partial solutions? >> >> TIA >> >> /CM >> >> > >  Claudio Martella claudio.martella@... 
From: John V. Sichi <jsichi@gm...>  20090429 19:10:38

Hi Claudio, You probably want to first run an allpairs shortest path algorithm such as FloydWarshall and then analyze the results from that. http://en.wikipedia.org/wiki/FloydWarshall_algorithm JGraphT does not yet have this in the library. JVS Claudio Martella wrote: > Hello list! > > I'm trying to calculate the average path length of my graph and the > diameter (longest shortest path). > > At the moment it's nonoptimized: > > for(Vertex source: graph.vertexSet()){ > for(Vertex destination: graph.vertexSet()){ > if(!source.equals(destination)){ > List<DefaultWeightedEdge> path = > DijkstraShortestPath.findPathBetween(graph, source, destination); > if(path != null) > averagePathLength += path.size(); > } > } > } > N = graph.vertexSet().size(); > averagePathLength /= (N*(N1)); > > This code is simplified to explain you what I'm doing now. There's of > course a misusage of resources and computational time. Any idea what > is the best way to calculate average path lengths, diameter and every > kind of graph property that would need to calculate paths reusing > resources and partial solutions? > > TIA > > /CM > > 
From: Claudio Martella <claudio.martella@gm...>  20090429 17:09:10

Hello list! I'm trying to calculate the average path length of my graph and the diameter (longest shortest path). At the moment it's nonoptimized: for(Vertex source: graph.vertexSet()){ for(Vertex destination: graph.vertexSet()){ if(!source.equals(destination)){ List<DefaultWeightedEdge> path = DijkstraShortestPath.findPathBetween(graph, source, destination); if(path != null) averagePathLength += path.size(); } } } N = graph.vertexSet().size(); averagePathLength /= (N*(N1)); This code is simplified to explain you what I'm doing now. There's of course a misusage of resources and computational time. Any idea what is the best way to calculate average path lengths, diameter and every kind of graph property that would need to calculate paths reusing resources and partial solutions? TIA /CM  Claudio Martella claudio.martella@... 
From: Leo Sendra <leo_senpao@ya...>  20090427 19:54:31

Hi all, In JGraphAdapterDemo, there is a JScrollPane with jgraph object as its component. When I drag a vertex into an invisible part of JFrame, the scroll doesn't appear. It seems don't work. So, a dragged vertex can't be seen again after that. How can I show the scroll bar when a vertex is dragged to invisible area of JFrame? So, I can use this scroll bar to see a dragged vertex.... Thanks... Terhubung langsung dengan banyak teman di blog dan situs pribadi Anda? Buat Pingbox terbaru Anda sekarang! http://id.messenger.yahoo.com/pingbox/ 
From: Claudio Martella <claudio.martella@gm...>  20090414 11:02:35

thank you john, i ended up extending the Graph with the encapsulation: good solution. On Tue, Apr 7, 2009 at 11:14 PM, John V. Sichi <jsichi@...> wrote: > Your mission, should you choose to accept it, is to get Sun (IBM?) to change > java.util.Set to allow you to "look up" an object already in the set. Good > luck. JGraphT strives to follow the patterns set by java.util. > > For cases like this, I usually take the approach you mention of maintaining > my own HashMap outside of the graph (in an encapsulating class). If someone > wanted to contributed something like a generic "KeyedGraph", that would be > fine, but I think we should leave the existing interfaces alone. > > JVS > > Claudio Martella wrote: >> >> Hello to the list members. >> >> I write for a topic that looks kind of hot in here: the >> Graph.getVertex() method. >> I'm using a SimpleDirectedWeightedGraph ecl to represent words with >> my own WordNode class and their relationships (with a >> DefaultWeightedEdge). Each graph vertex (a word for me) has a payload >> for some statistics (i.e. the number of occurences in the >> document/corpus). >> >> While parsing the document ( or while the application is running ) i >> want to get access to the node to read its data. I've overidden the >> .equals() for my WordNode class, so that it actually checks the >> WordNode.getWord()  String, so the idea is to do a >> graph.getVertex(new WordNode("whatever")).getOccurences() without >> the need to hold all the vertexes in another datastructure (like a >> HashMap), or without surfing the expensive graph.vertexSet(). >> AFAIK, this is not possible in jgrapht. I don't actually want the >> getVertex() to work for referenceequality, but for my valueequality >> through the equals() "interface". >> >> Any suggestions? >> >> TIA >> >> Claudio Martella >> > >  Claudio Martella claudio.martella@... 
From: John V. Sichi <jsichi@gm...>  20090407 21:14:28

Your mission, should you choose to accept it, is to get Sun (IBM?) to change java.util.Set to allow you to "look up" an object already in the set. Good luck. JGraphT strives to follow the patterns set by java.util. For cases like this, I usually take the approach you mention of maintaining my own HashMap outside of the graph (in an encapsulating class). If someone wanted to contributed something like a generic "KeyedGraph", that would be fine, but I think we should leave the existing interfaces alone. JVS Claudio Martella wrote: > Hello to the list members. > > I write for a topic that looks kind of hot in here: the > Graph.getVertex() method. > I'm using a SimpleDirectedWeightedGraph ecl to represent words with > my own WordNode class and their relationships (with a > DefaultWeightedEdge). Each graph vertex (a word for me) has a payload > for some statistics (i.e. the number of occurences in the > document/corpus). > > While parsing the document ( or while the application is running ) i > want to get access to the node to read its data. I've overidden the > .equals() for my WordNode class, so that it actually checks the > WordNode.getWord()  String, so the idea is to do a > graph.getVertex(new WordNode("whatever")).getOccurences() without > the need to hold all the vertexes in another datastructure (like a > HashMap), or without surfing the expensive graph.vertexSet(). > AFAIK, this is not possible in jgrapht. I don't actually want the > getVertex() to work for referenceequality, but for my valueequality > through the equals() "interface". > > Any suggestions? > > TIA > > Claudio Martella > 
From: Claudio Martella <claudio.martella@gm...>  20090407 17:01:01

Hello to the list members. I write for a topic that looks kind of hot in here: the Graph.getVertex() method. I'm using a SimpleDirectedWeightedGraph ecl to represent words with my own WordNode class and their relationships (with a DefaultWeightedEdge). Each graph vertex (a word for me) has a payload for some statistics (i.e. the number of occurences in the document/corpus). While parsing the document ( or while the application is running ) i want to get access to the node to read its data. I've overidden the .equals() for my WordNode class, so that it actually checks the WordNode.getWord()  String, so the idea is to do a graph.getVertex(new WordNode("whatever")).getOccurences() without the need to hold all the vertexes in another datastructure (like a HashMap), or without surfing the expensive graph.vertexSet(). AFAIK, this is not possible in jgrapht. I don't actually want the getVertex() to work for referenceequality, but for my valueequality through the equals() "interface". Any suggestions? TIA Claudio Martella  Claudio Martella claudio.martella@... 
From: lalitha vadlamani <lalitha1519@ya...>  20090401 14:40:31

Hi, I have created a simpleWeightedGraph and i have to find the nodes with top k degrees. How can i use VertexDegreeComparator with sort() function of java to do this? Thanks Lalitha 
From: John V. Sichi <jsichi@gm...>  20090312 08:32:05

Thanks; this is definitely a bug (the test should be using equals instead of == in all cases). I've checked in the fix and unit test in Subversion. JVS Michaël Michaud wrote: > Hi, > > Maybe somebody can tell me if this behaviour is normal or if it's a bug. > I want to build a graph with a unique cycle (one edge, one vertex) > I use two classes MyVertex and MyEdge, a WeightedPseudograph (version > 0.7.3 of jGraphT), and here is my test case : > > v1 = new MyVertex(); > graph.addVertex(v1); > graph.addEdge(v1,v1,new MyEdge()); > ==> build a graph with 1 vertex and 1 edge, vertex has degree 2 (that is > OK!) > > v1 = new MyVertex(); > v2 = new MyVertex(); // where n2.equals(n1) > graph.addVertex(v1); > graph.addVertex(v2); > graph.addEdge(v1,v2,new MyEdge()); > ==> build a graph with 1 vertex and 1 edge, vertex has degree 4 ! > > Seems like addVertex uses equals to compare vertices and add only one > vertex if v1!=v2 but v1.equals(v2) > That's fine for me > There is still 1 vertex after addEdge, but that time, the degreeOf > method returns 4 instead of 2 > > I find this code in AbstractBaseGraph (line 1109) : > if (source != target) {getEdgeContainer(target).addEdge(e);} > //here == is used, not equals > and also this (line 1125) : > if (getEdgeSource(e).equals(getEdgeTarget(e))) { degree += 2;} > > Any help is welcome > > Michaël > > > >  > Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are > powering Web 2.0 with engaging, crossplatform capabilities. Quickly and > easily build your RIAs with Flex Builder, the Eclipse(TM)based development > software that enables intelligent coding and stepthrough debugging. > Download the free 60 day trial. http://p.sf.net/sfu/wwwadobecom > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > 
From: Michaël Michaud <michael.michaud@fr...>  20090312 07:52:11

Hi, Maybe somebody can tell me if this behaviour is normal or if it's a bug. I want to build a graph with a unique cycle (one edge, one vertex) I use two classes MyVertex and MyEdge, a WeightedPseudograph (version 0.7.3 of jGraphT), and here is my test case : v1 = new MyVertex(); graph.addVertex(v1); graph.addEdge(v1,v1,new MyEdge()); ==> build a graph with 1 vertex and 1 edge, vertex has degree 2 (that is OK!) v1 = new MyVertex(); v2 = new MyVertex(); // where n2.equals(n1) graph.addVertex(v1); graph.addVertex(v2); graph.addEdge(v1,v2,new MyEdge()); ==> build a graph with 1 vertex and 1 edge, vertex has degree 4 ! Seems like addVertex uses equals to compare vertices and add only one vertex if v1!=v2 but v1.equals(v2) That's fine for me There is still 1 vertex after addEdge, but that time, the degreeOf method returns 4 instead of 2 I find this code in AbstractBaseGraph (line 1109) : if (source != target) {getEdgeContainer(target).addEdge(e);} //here == is used, not equals and also this (line 1125) : if (getEdgeSource(e).equals(getEdgeTarget(e))) { degree += 2;} Any help is welcome Michaël 
From: John V. Sichi <jsichi@gm...>  20090311 20:35:11

Francesco Cioffi wrote: > Hi guys, > > I'm new to jgrapht and I would like to use as graph library in my Project. > > I must create a graph, save it in a file, and then reload it for some purpose. > > I have found some utilities for exporting but I don't found utilities > for load a graph from a file. > > > Can you suggest me, how can I do that? Right, we currently only have exporters, without importers. However, most JGraphT data structures implement Serializable, so that is one option for persistence, although I personally am not a big fan of it due to issues like incompatibilities during migration to newer versions. JVS 
From: Francesco Cioffi <fcioffi@gm...>  20090311 13:12:19

Hi guys, I'm new to jgrapht and I would like to use as graph library in my Project. I must create a graph, save it in a file, and then reload it for some purpose. I have found some utilities for exporting but I don't found utilities for load a graph from a file. Can you suggest me, how can I do that? Thank you, Francesco Cioffi 
From: John V. Sichi <jsichi@gm...>  20090309 22:44:12

Thanks Guillaume. I'll poke around a bit and update the Javadoc with what I find. Olivier, if you are interested in implementing one of the newer algorithms, we can incorporate that into the library too. JVS gu boulmi wrote: > Hi, > > I have not implemented this algorithm based on a reference paper. So, > it's not Jimenez and Marzal! > Though I'm sure that what I've written is not new and must have > been explained previously in many papers. > > The algorithm is a *variant of the BellmanFord algorithm* but instead > of only storing the best path I store the "*k*" best paths at each pass > (se differences between methods KShortestPathsIterator#next and > BellmanFordIterator#next). > > Complexity "*/m*n/*" is because it's a variant of BellmanFord (whose > complexity is /*O(m*n)*/) and the "*/k/*" factor is because the method > RankingPathElementList#addPathElements is /*O(k)*/ where *k* is the > number of expected paths to be computed (by the way I notice that this > "O(k)" piece of information is not in the javadoc documentation). > > If you find a paper pointing to this kind of algorithm, feel free to > update the javadoc documentation. > > Regards, > > Guillaume > >  En date de : *Mer 4.3.09, John V. Sichi /<jsichi@...>/* a écrit : > > De: John V. Sichi <jsichi@...> > Objet: Re: Question on JGraphT > À: lefevrol@... > Cc: jgraphtusers@..., boulmigu@... > Date: Mercredi 4 Mars 2009, 1h09 > > Olivier Lefevre wrote: > > Hi, > > > > What is the algorithm used for Kshortest paths in JGraphT: the REA > algorithm of Jimenez and Marzal? > > > > Regards, > > > > Olivier Lefevre > > Freelance bioinformatics developer > > Berlin, Germany > > Greetings Olivier, > > I don't know the answer, so I'm cc'ing your question to the users > mailing list, as well as Guillaume Boulmier, who developed this code. > > Jimenez and Marzal is O(m+Knlog(m/n)), whereas Guillaume's comments have > O(K*m*n) for the running time. > > JVS > > 
From: John V. Sichi <jsichi@gm...>  20090309 22:10:18

maria esther sanchez wrote: > I was wondering if there is a method in JGraphT to get the aislated > subgraphs inside a graph? (Like the graphs inside a graph) To find them, you can use org.jgrapht.alg.ConnectivityInspector or StrongConnectivityInspector. To manipulate them individually once you find them, you can use org.jgrapht.graph.Subgraph (or one of its variants such as DirectedSubgraph). JVS 
From: gu boulmi <boulmigu@ya...>  20090309 13:30:06

Hi, I have not implemented this algorithm based on a reference paper. So, it's not Jimenez and Marzal! Though I'm sure that what I've written is not new and must have been explained previously in many papers. The algorithm is a variant of the BellmanFord algorithm but instead of only storing the best path I store the "k" best paths at each pass (se differences between methods KShortestPathsIterator#next and BellmanFordIterator#next). Complexity "m*n" is because it's a variant of BellmanFord (whose complexity is O(m*n)) and the "k" factor is because the method RankingPathElementList#addPathElements is O(k) where k is the number of expected paths to be computed (by the way I notice that this "O(k)" piece of information is not in the javadoc documentation). If you find a paper pointing to this kind of algorithm, feel free to update the javadoc documentation. Regards, Guillaume  En date de : Mer 4.3.09, John V. Sichi <jsichi@...> a écrit : De: John V. Sichi <jsichi@...> Objet: Re: Question on JGraphT À: lefevrol@... Cc: jgraphtusers@..., boulmigu@... Date: Mercredi 4 Mars 2009, 1h09 Olivier Lefevre wrote: > Hi, > > What is the algorithm used for Kshortest paths in JGraphT: the REA algorithm of Jimenez and Marzal? > > Regards, > > Olivier Lefevre > Freelance bioinformatics developer > Berlin, Germany Greetings Olivier, I don't know the answer, so I'm cc'ing your question to the users mailing list, as well as Guillaume Boulmier, who developed this code. Jimenez and Marzal is O(m+Knlog(m/n)), whereas Guillaume's comments have O(K*m*n) for the running time. JVS 
From: gu boulmi <boulmigu@ya...>  20090309 13:22:49

Hi, I have not implemented this algorithm based on a reference paper, though I'm sure that what I've written is not new and must have been explained previously in many papers. The algorithm is a variant of the BellmanFord algorithm but instead of only storing the best path I store the "k" best paths at each pass (se differences between KShortestPathsIterator#next and BellmanFordIterator#next). Complexity "m*n" is because it's a variant of BellmanFord and the "k" factor is because the method RankingPathElementList#addPathElements is O(k). If you find  En date de : Mer 4.3.09, John V. Sichi <jsichi@...> a écrit : De: John V. Sichi <jsichi@...> Objet: Re: Question on JGraphT À: lefevrol@... Cc: jgraphtusers@..., boulmigu@... Date: Mercredi 4 Mars 2009, 1h09 Olivier Lefevre wrote: > Hi, > > What is the algorithm used for Kshortest paths in JGraphT: the REA algorithm of Jimenez and Marzal? > > Regards, > > Olivier Lefevre > Freelance bioinformatics developer > Berlin, Germany Greetings Olivier, I don't know the answer, so I'm cc'ing your question to the users mailing list, as well as Guillaume Boulmier, who developed this code. Jimenez and Marzal is O(m+Knlog(m/n)), whereas Guillaume's comments have O(K*m*n) for the running time. JVS 
From: gu boulmi <boulmigu@ya...>  20090309 12:59:50

Hi, I'm Implmentation  En date de : Mer 4.3.09, John V. Sichi <jsichi@...> a écrit : De: John V. Sichi <jsichi@...> Objet: Re: Question on JGraphT À: lefevrol@... Cc: jgraphtusers@..., boulmigu@... Date: Mercredi 4 Mars 2009, 1h09 Olivier Lefevre wrote: > Hi, > > What is the algorithm used for Kshortest paths in JGraphT: the REA algorithm of Jimenez and Marzal? > > Regards, > > Olivier Lefevre > Freelance bioinformatics developer > Berlin, Germany Greetings Olivier, I don't know the answer, so I'm cc'ing your question to the users mailing list, as well as Guillaume Boulmier, who developed this code. Jimenez and Marzal is O(m+Knlog(m/n)), whereas Guillaume's comments have O(K*m*n) for the running time. JVS 
From: John V. Sichi <jsichi@gm...>  20090304 08:19:30

maria esther sanchez wrote: > Hello! I am having trouble with the references. I would like to know how > to duplicate, clone or copy a graph in with there are no references amog > them. I tryed this method: Graphs.addGraph(simpleGraph,graph)... but i > still have the same problem. If a modify a vertex from simplegrap, the > node that corresponds to graph is modified also. > How can i make a copy that does afect from the graph that i am copying, > and the other way arround. > Thank u for you help! Hi Maria, You can code this as follows: 1) create a Map<V,V> m 2) write a new cloneAllVertices like addAllVertices which does vPrime = v.clone(), adds an entry (v,vPrime) to m, and puts vPrime in the destination graph 3) write a new addAllEdgesForClones like addAllEdges which uses m to map each s and t to sPrime and tPrime before calling addEdge I forget how the interactions between generics and clone work out, but if you get a generic version of this working along with a unit test, please send it to me and I'll check it in as a new utility method on class org.jgrapht.Graphs. JVS 