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}
(2) 
_{Nov}
(4) 
_{Dec}
(2) 
2017 
_{Jan}
(4) 
_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 





1
(2) 
2

3

4

5

6

7

8

9
(1) 
10

11

12
(3) 
13
(1) 
14
(1) 
15
(2) 
16

17

18

19

20

21

22
(1) 
23

24

25

26
(1) 
27
(1) 
28

29

30


From: John Sichi <jsichi@gm...>  20110927 06:39:26

testsrc/org/jgrapht/alg/DijkstraShortestPathTest.java A*: no plans, but we always welcome contributions. Regarding the Fibonacci heap: I think you can figure that one out by browsing the code for a few minutes. JVS On Mon, Sep 26, 2011 at 1:39 PM, Mati Szaingurten <matigurten@...> wrote: > > Hello JGraphT team! > I have a couple of questions... First of all, I would very much like to get > access to an example of the usage of SimpleDirectedWeightedGraph. > I am writing a program where I need to solve a graph with the Dijkstra > algorithm and even though I have implemented both the data structure and the > algorithm by myself, I would much rather use an open source code (yours!). > Nevertheless, the classes are quite complex so if i could see an example of > how to create a simple directed weighted graph and run the dijkstra > algorithm on it, that would be great. I have tried the web, but didnt find a > suiting example. > Is the queue used in the dijkstra algorithm a fibonacci heap? I've read > that's the only way of achieving maximal efficiency for the algorithm. > For my last question, are you planning on implementing some other shortest > path algorithms like A* or some others? That would be great. > > Thanks! > Mati >  > All the data continuously generated in your IT infrastructure contains a > definitive record of customers, application performance, security > threats, fraudulent activity and more. Splunk takes this data and makes > sense of it. Business sense. IT sense. Common sense. > http://p.sf.net/sfu/splunkd2dcopy1 > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > > 
From: Mati Szaingurten <matigurten@gm...>  20110926 20:39:02

Hello JGraphT team! I have a couple of questions... First of all, I would very much like to get access to an example of the usage of SimpleDirectedWeightedGraph. I am writing a program where I need to solve a graph with the Dijkstra algorithm and even though I have implemented both the data structure and the algorithm by myself, I would much rather use an open source code (yours!). Nevertheless, the classes are quite complex so if i could see an example of how to create a simple directed weighted graph and run the dijkstra algorithm on it, that would be great. I have tried the web, but didnt find a suiting example. Is the queue used in the dijkstra algorithm a fibonacci heap? I've read that's the only way of achieving maximal efficiency for the algorithm. For my last question, are you planning on implementing some other shortest path algorithms like A* or some others? That would be great. Thanks! Mati 
From: Ben Johnson <bjohnson.professional@gm...>  20110922 12:48:13

Hi I'm just experimenting with your library and liking it so far, thanks! I was wondering if anyone had implemented what I would call 'validating edges', where a vertex could prevent an edge from being added if the other vertex did not meet certain criteria. For example, if I was modeling a directory structure and wanted certain directories to only contain certain types of files, so that any attempt to add an 'invalid' file type would throw an exception. I assume I can do this by subclassing DirectedAcyclicGraph and overriding the addEdge() methods so that it invokes a 'validate' method on each of the two vertices (as a generic solution  in my case I just need the directory vertex to validate the file vertex; the file vertex doesn't care about the directory vertex), but I was wondering if anyone had encountered this problem before and approached it differently. The idea is something like: addEdge(V vertex1, V vertex2) { ... // TODO: Check if vertices support 'validate' methods ... if ( !(vertex1.validate(vertex2)  vertex2.validate(vertex1))) { throw new IllegalArgumentException("..."); ... } Thanks very much Ben 
From: John Sichi <jsichi@gm...>  20110915 21:22:57

I wrote up a wiki page about this a long time ago: http://pub.eigenbase.org/wiki/JGraphT:EqualsAndHashCode I'll see about linking it from some of the JGraphT class Javadoc, but I think the java.lang.Object Javadoc already says it pretty clearly: "Note that it is generally necessary to override the hashCode method whenever this method is overridden, so as to maintain the general contract for the hashCode method, which states that equal objects must have equal hash codes." JVS On Thu, Sep 15, 2011 at 1:48 PM, Fabian Menges <fm744@...> wrote: > Hi jgrapht team, > > I just tried to implement something that uses a custom vertices class. > It would be great if you could mention in the documentation or in an > example that in order for this to work correctly you need to override > not only the equals() but more importantly the hashCode() methods. > > I had to look at your source code to see that you were using a > (linked)Hashmap to store the vertices which does not use equals() or a > comparator but the hashCode() method. > > Thanks your for great work, > > Fabian > 
From: Charles Galpin <cgalpin@lh...>  20110915 13:07:44

It looks like I'm going to have to do some research as it's the hardest case I am after! My initial plan was to do the shortest route, then remove one or more key edges and reroute which would be nice and easy, but the trick is to intelligently pick those :) Thanks for the advice and pointers, charles On Sep 14, 2011, at 3:33 PM, hnridder@... wrote: > > > Hi Charles, So you're looking at k shortest paths between two given vertices. If you google for 'k shortest path' you'll get many results, one of the first a nice article by David Eppstein, which has many pointers to other articles on varieties of the problem. Much depends on the requirements on the paths. Should they be simple or not? Vertexdisjoint? Edgedisjoint? Some varieties can be formulated as a maxflow problem. Or if you need e.g. edgedisjoint simple paths, then I would find the shortest path, remove its edges from the graph, find the second shortest path, and so on. Not elegant, but easy to implement. The hardest case seems to be simple paths that differ in at least one edge, but do not need to be vertex/edge disjoint. I'm afraid you can't get by without implementing an algorithm yourself. The good news is that the problem is wellstudied and efficient algorithms do exist. Ernst  Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org 
From: <hnridder@gr...>  20110914 19:33:16

Hi Charles, So you're looking at k shortest paths between two given vertices. If you google for 'k shortest path' you'll get many results, one of the first a nice article by David Eppstein, which has many pointers to other articles on varieties of the problem. Much depends on the requirements on the paths. Should they be simple or not? Vertexdisjoint? Edgedisjoint? Some varieties can be formulated as a maxflow problem. Or if you need e.g. edgedisjoint simple paths, then I would find the shortest path, remove its edges from the graph, find the second shortest path, and so on. Not elegant, but easy to implement. The hardest case seems to be simple paths that differ in at least one edge, but do not need to be vertex/edge disjoint. I'm afraid you can't get by without implementing an algorithm yourself. The good news is that the problem is wellstudied and efficient algorithms do exist. Ernst  Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org 
From: Charles Galpin <cgalpin@lh...>  20110913 18:10:27

I forgot to follow up with my findings. 1. The dijkstra shortest path algorithm works nice and fast  faster than with pgroutng. 2. Building a new graph of out of a smaller area of coverage helps, but not by enough to make it feasible, and the graph build time itself takes about 4 seconds on my test cases, so still 8+ seconds to do the top 3 routes using KShortestPaths If you have any ideas how I might be able to get better performance with the KShortestPaths algorithm, please let me know. Thanks, charles On Sep 12, 2011, at 8:22 AM, Charles Galpin wrote: > Hi Ernst > > Good question :) I am currently using postgresql/postgis/pgrouting and it's Dijkstra routing algorithm for my routing and it works well for a single shortest route from one point to another. A single route is usually a few hundred milliseconds. However I now need to generate the n shortest routes between two points so they can be offered as alternatives, where depending on the results I expect to to be anywhere from 3 to 10 (I am unsure the differences in routes will all be useful) and I'd like to keep this under a second as well. > > I don't think I need the negative weight as it is a fully directed graph so each vertex is oneway. Is there a way I can make this faster without that? > > This morning I'll try the other algorithms as a comparison to pgrouting, as well as try build a smaller graph each time I do the routing and see what that does for the speed as well. > > Thanks, > charles > > On Sep 12, 2011, at 3:26 AM, hnridder@... wrote: > >> Dear Charles, >> >> What ARE your needs? >> >> Depending on what they are, I dare say they can be fulfilled faster than the KShortestPaths algorithm does, because >> 1. This algorithm can handle negative weight cycles. Do you need this? >> 2. Your graph is very sparse. >> >> Did you try e.g. the Dijkstra or FloydWarshall algorithms? >> >> Regards, >> Ernst 
From: Charles Galpin <cgalpin@lh...>  20110912 12:22:54

Hi Ernst Good question :) I am currently using postgresql/postgis/pgrouting and it's Dijkstra routing algorithm for my routing and it works well for a single shortest route from one point to another. A single route is usually a few hundred milliseconds. However I now need to generate the n shortest routes between two points so they can be offered as alternatives, where depending on the results I expect to to be anywhere from 3 to 10 (I am unsure the differences in routes will all be useful) and I'd like to keep this under a second as well. I don't think I need the negative weight as it is a fully directed graph so each vertex is oneway. Is there a way I can make this faster without that? This morning I'll try the other algorithms as a comparison to pgrouting, as well as try build a smaller graph each time I do the routing and see what that does for the speed as well. Thanks, charles On Sep 12, 2011, at 3:26 AM, hnridder@... wrote: > Dear Charles, > > What ARE your needs? > > Depending on what they are, I dare say they can be fulfilled faster than the KShortestPaths algorithm does, because > 1. This algorithm can handle negative weight cycles. Do you need this? > 2. Your graph is very sparse. > > Did you try e.g. the Dijkstra or FloydWarshall algorithms? > > Regards, > Ernst 
From: <hnridder@gr...>  20110912 07:26:01

Dear Charles, What ARE your needs? Depending on what they are, I dare say they can be fulfilled faster than the KShortestPaths algorithm does, because 1. This algorithm can handle negative weight cycles. Do you need this? 2. Your graph is very sparse. Did you try e.g. the Dijkstra or FloydWarshall algorithms? Regards, Ernst  Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org  Reply message  From: "Charles Galpin" <cgalpin@...> To: <jgraphtusers@...> Subject: [jgraphtusers] KShortestPaths performance Date: Fri, Sep 9, 2011 22:21 Hi All I'm new to jgrapht, have just downloaded it today to try out the kshortest paths algorithm. I made a simple test program to load up my network graph (happens to be road data) as a SimpleDirectedWeightedGraph which has about 60500 vertices and 97000 edges. I then ran the KShortestPaths algorithm in a loop with the number of paths ranging from 1 to 10. It takes 8 or 9 seconds to calculate one path, 24 for 2, 42 for 3, and so on until 10 takes 3.5 to 4 minutes. The paths are roughly 145  155 edges in length. This is way too slow for my needs. Is there any way I can optimize this? I'm guessing the answer is going to be to reduce my graph size to all that is necessary, and I'll try that next. I'm just afraid that the overhead of creating a new graph for every KShortestPaths is going to be pretty high as well (it takes about 30 seconds to load the whole graph from a database and I'll have to do a query to get the network data inside a bounding box containing the start and end points including some buffer) TIA, charles  Why CloudBased Security and Archiving Make Sense Osterman Research conducted this study that outlines how and why cloud computing security and archiving is rapidly being adopted across the IT space for its ease of implementation, lower cost, and increased reliability. Learn more. http://www.accelacomm.com/jaw/sfnl/114/51425301/ _______________________________________________ jgraphtusers mailing list jgraphtusers@... https://lists.sourceforge.net/lists/listinfo/jgraphtusers 
From: <hnridder@gr...>  20110912 07:12:40

Dear Ulrich, by the common graphtheoretic definition of connectivity, the socalled 'underlying' graph is used, which is to say the edges with their direction removed. If the ConnectivityInspector would do something else, it wouldn't obey the usual definitions anymore. As a visual example, assume you want to draw a big graph on the pages of a notebook, without any edges crossing pages. You can do this by splitting the graph in its connected components and drawing a connected component on every page. Note also that connectivity is an equivalence relation: A graph can be partitioned in its connected components and then every vertex is in precisely one component. When you would obey directions, you're studying reachability instead of connectivity and this property doesn't hold anymore: in a>b>c, you'd get {a,b,c}, {b,c}, {c}. Regards, Ernst  Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org 
From: Charles Galpin <cgalpin@lh...>  20110909 20:21:46

Hi All I'm new to jgrapht, have just downloaded it today to try out the kshortest paths algorithm. I made a simple test program to load up my network graph (happens to be road data) as a SimpleDirectedWeightedGraph which has about 60500 vertices and 97000 edges. I then ran the KShortestPaths algorithm in a loop with the number of paths ranging from 1 to 10. It takes 8 or 9 seconds to calculate one path, 24 for 2, 42 for 3, and so on until 10 takes 3.5 to 4 minutes. The paths are roughly 145  155 edges in length. This is way too slow for my needs. Is there any way I can optimize this? I'm guessing the answer is going to be to reduce my graph size to all that is necessary, and I'll try that next. I'm just afraid that the overhead of creating a new graph for every KShortestPaths is going to be pretty high as well (it takes about 30 seconds to load the whole graph from a database and I'll have to do a query to get the network data inside a bounding box containing the start and end points including some buffer) TIA, charles 
From: Wielant, Ulrich <U.Wielant@ge...>  20110901 10:02:12

This gives a list of neighbours but I want to have all reachable vertices (not only neighbours). Of course it would be possible to write a simple algorithm that uses this function to create such a list. Thanks Uli Ursprüngliche Nachricht Von: Joris Kinable [mailto:deus87@...] Gesendet: Mittwoch, 31. August 2011 15:45 An: Wielant, Ulrich Cc: jgraphtusers@... Betreff: Re: [jgraphtusers] Connectivity of Directed Graphs Is the function neighborListOf(Graph<V,E> g, V vertex) defined in the class Graphs the thing you are looking for? br, Joris On Tue, Aug 30, 2011 at 11:11 AM, Wielant, Ulrich <U.Wielant@...> wrote: > Hello everyone, > > first of all a big congratulation for maintaining this great > framework. I am using it since 4 years and I am still happy with it > :) > > Now my question: > > I am using a DirectedGraph and I want to get a list of vertices that are reachable from a given vertex with respect to the directions. The ConnectivityInspector does not care about the edge directions whereas the StrongConnectivityInspector only uses strong (so double directed) connections. > Any hints how I can achieve the list of reachable nodes? > > Example: > > A <> B < C > > reachable(A) => [B] > reachable(B) => [A] > reachable(C) => [A,B] > > Thanks! > Uli > > http://www.gematronik.com > http://www.selexsi.de > > Selex Systems Integration GmbH > Sitz der Gesellschaft / Registered Office: Neuss Registergericht / > Register Court: Neuss HR B 1242 Gesch?ftsf?hrer / Managing Director: > Ulrich Nellen > >  >  Special Offer  Download ArcSight Logger for FREE! > Finally, a worldclass log management solution at an even better > pricefree! And you'll get a free "Love Thy Logs" tshirt when you > download Logger. Secure your free ArcSight Logger TODAY! > http://p.sf.net/sfu/arcsisghtdev2dev > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > http://www.gematronik.com http://www.selexsi.de Selex Systems Integration GmbH Sitz der Gesellschaft / Registered Office: Neuss Registergericht / Register Court: Neuss HR B 1242 Geschäftsführer / Managing Director: Ulrich Nellen 
From: Wielant, Ulrich <U.Wielant@ge...>  20110901 10:01:35

Ernst, you are right! That's exactly what I was looking for. I didn't think of using these iterators because they are used in the ConnectivityInspector. But the ConnectivityInspector uses an UndirectedGraph even if it is called with a DirectedGraph. Does that make sense? Wouldn't it be better if the ConnectivityInspector respects the directions in a DirectedGraph? Maybe one has to implement a new Inspector. The current ConnectivityInspector cannot be inherited for this because the graph field is private and could not be modified. So it seems that it has to be copied and only the constructor has to be changed: public ConnectivityInspector(DirectedGraph<V, E> g) { init(); // old: // this.graph = new AsUndirectedGraph<V, E>(g); // new: this.graph = g; } Uli ________________________________ Von: hnridder@... [mailto:hnridder@...] Gesendet: Mittwoch, 31. August 2011 16:21 An: Wielant, Ulrich; 'jgraphtusers@...' Betreff: Re: [jgraphtusers] Connectivity of Directed Graphs Hi Ulrich, can't you use the BreadthFirstIterator or the DepthFirstIterator? I'd think either should do what you want. Regards, Ernst  Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org  Reply message  From: "Wielant, Ulrich" <U.Wielant@...> To: "'jgraphtusers@...'" <jgraphtusers@...> Subject: [jgraphtusers] Connectivity of Directed Graphs Date: Tue, Aug 30, 2011 11:11 Hello everyone, first of all a big congratulation for maintaining this great framework. I am using it since 4 years and I am still happy with it :) Now my question: I am using a DirectedGraph and I want to get a list of vertices that are reachable from a given vertex with respect to the directions. The ConnectivityInspector does not care about the edge directions whereas the StrongConnectivityInspector only uses strong (so double directed) connections. Any hints how I can achieve the list of reachable nodes? Example: A <> B < C reachable(A) => [B] reachable(B) => [A] reachable(C) => [A,B] Thanks! Uli http://www.gematronik.com http://www.selexsi.de Selex Systems Integration GmbH Sitz der Gesellschaft / Registered Office: Neuss Registergericht / Register Court: Neuss HR B 1242 Gesch?ftsf?hrer / Managing Director: Ulrich Nellen  Special Offer  Download ArcSight Logger for FREE! Finally, a worldclass log management solution at an even better pricefree! And you'll get a free "Love Thy Logs" tshirt when you download Logger. Secure your free ArcSight Logger TODAY! http://p.sf.net/sfu/arcsisghtdev2dev _______________________________________________ jgraphtusers mailing list jgraphtusers@... https://lists.sourceforge.net/lists/listinfo/jgraphtusers http://www.gematronik.com http://www.selexsi.de Selex Systems Integration GmbH Sitz der Gesellschaft / Registered Office: Neuss Registergericht / Register Court: Neuss HR B 1242 Gesch?ftsf?hrer / Managing Director: Ulrich Nellen 