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}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 



1

2

3

4
(1) 
5

6

7

8

9

10

11
(1) 
12

13

14

15

16

17
(1) 
18

19
(2) 
20
(1) 
21
(1) 
22
(5) 
23
(5) 
24
(1) 
25

26

27

28

29

30

31



From: Vladimir Kostyukov <vladimir.kostukov@gm...>  20120524 08:39:12

It's just a duplicate of GitHub discussion: Here is my Graph equals vision: Ok. Regarding my implementation we can say that two graphs are equals if: a) they are implements the same Graph interface (for example Weighted graph). In this case there are no difference in implementation. I mean two graphs WeightedMultigraph and WeightedPseudograph could be equals if following conditions are true. b) they has identical edge sets and vertex sets. If uses instance of IntrusiveEdge as edge its hashCode/equals features doesn't matter. It's just a dynamicallycreated fakeedge which shows that two vertices are connected. c) they has the same weight for identical edges On Tue, May 22, 2012 at 11:23 PM, Vladimir Kostyukov < vladimir.kostukov@...> wrote: > Hi John, > > First of all, thank you for fast reply! > > Regarding equals() and hashCode(). I've already implemented something and > sent pullrequest in GitHub (see GitHub project page). I hope you'll find > my implementation useful :) > > BTW, I've also added two unit tests and it passes. > > > On Tue, May 22, 2012 at 11:06 PM, John Sichi <jsichi@...> wrote: > >> CC'ing jgraphtusers list. >> >> Hi Vladimir, >> >> I'm not clear on the intent of your equals method. Comparing hash >> codes is not meaningful; two graphs could have the same hash code and >> yet be totally unrelated; in this case equals should return false, not >> true. >> >> There are three meaningful possibilities: >> >> 1) Java object identity (in this case the default equals/hashCode are >> good enough) >> 2) identical edge sets and vertex sets (I'm not sure whether this >> makes sense, but it's easy to implement in terms of the corresponding >> Collections methods) >> 3) isomorphism (waaaaay too expensive even if some day it turns out to >> be nonexponential) >> >> JVS >> >> On Tue, May 22, 2012 at 12:58 AM, Vladimir Kostyukov >> <vladimir.kostukov@...> wrote: >> > Oops. I've sent old hashCode implementation. Here is new one: >> > >> > public int hashCode() >> > { >> > int result = 17; >> > for (E e: edgeSet()) >> > { >> > int code = 27; >> > int source = getEdgeSource(e).hashCode(); >> > int target = getEdgeTarget(e).hashCode(); >> > >> > // This is a paring function (see details here: >> > http://en.wikipedia.org/wiki/Pairing_function) (VK) >> > int paring = ((source + target) * (source + target + 1) / >> 2) + >> > target; >> > long weight = (long) getEdgeWeight(e); >> > >> > code = 37 * code + e.hashCode(); >> > code = 37 * code + paring; >> > code = 37 * code + (int) (weight ^ (weight >>> 32)); >> > >> > result += code; >> > } >> > >> > return result; >> > } >> > >> > >> > On Tue, May 22, 2012 at 2:41 PM, Vladimir Kostyukov >> > <vladimir.kostukov@...> wrote: >> >> >> >> Hi all, >> >> >> >> I've just forked JGraphT library in GitHub and started work on >> >> implementation better serialization mechanism  I am planning to use >> >> Externalizable instead of Serializable. It should works more faster (I >> >> guess, we can get something about 2x4x speed up). Now it takes about >> 10 >> >> seconds on my laptop in demo (I've added serialization/deserialization >> >> sections in PerformanceDemo). >> >> >> >> First of all, I've decided to implement hashCode() and equals() >> methods in >> >> AbstractGraph class. Iilve also created simple Unit tests for my >> >> implementation. But in first run I got two tests failed. Here is: >> >> >> >> Failed tests: >> testLinearGraph(org.jgrapht.alg.BlockCutpointGraphTest): >> >> expecte d:<4> but was:<2> >> >> testNotBiconnected(org.jgrapht.alg.BlockCutpointGraphTest): >> expected:<3> >> >> but was:<2> >> >> >> >> I've tried to look into this, but I didn't find any Graph::equals usage >> >> there. Could you guys, help me in this issue? Why it happens? >> >> >> >> Here is my implementation in AbstractGraph class: >> >> >> >> public int hashCode() >> >> { >> >> int result = 17; >> >> for (E e: edgeSet()) >> >> { >> >> long source = getEdgeSource(e).hashCode(); >> >> long target = getEdgeTarget(e).hashCode(); >> >> >> >> // This is a paring function (see details here: >> >> http://en.wikipedia.org/wiki/Pairing_function) (VK) >> >> long paring = ((source + target) * (source + target + 1) / >> 2) >> >> + target; >> >> long weight = (long) getEdgeWeight(e); >> >> >> >> result += 27 * (int) (paring ^ (paring >>> 32)); >> >> result += 37 * (int) (e.hashCode() ^ (e.hashCode() >>> >> 32)); >> >> result += 47 * (int) (weight ^ (weight >>> 32)); >> >> } >> >> >> >> return result; >> >> } >> >> >> >> public boolean equals(Object object) >> >> { >> >> if (this == object) return true; >> >> if (object == null) return false; >> >> if (!(object instanceof Graph)) return false; >> >> >> >> // TODO: maybe we should add class checking here: >> >> // for example: Undirected and Directed are different graphs, but >> could >> >> looks the same (have same hashCodes()) (VK) >> >> >> >> Graph<?, ?> g = (Graph<?, ?>) object; >> >> >> >> if (vertexSet().size() != g.vertexSet().size() >> >>  edgeSet().size() != g.edgeSet().size()) return false; >> >> >> >> // TODO: maybe we should add vertices and edges factory >> checking >> >> here (VK) >> >> >> >> //return super.equals(object); >> >> return (hashCode() == g.hashCode()); >> >> } >> >> >> >> BTW, my unit tests pass with my implementation. >> >> >> >> >> >> I am going to send you my pullrequest when I finish. It should >> contains: >> >> unit tests, new PerfromanceDemo, new serialization mechanism, >> >> equals/hashCode implementations. >> >> >> >>  >> >> Thanks, >> >> Vladimir Kostyukov >> >> >> > >> > >> > >> >  >> > Thanks, >> > Vladimir Kostyukov >> > >> > > > >  > Thanks, > Vladimir Kostyukov > >  Thanks, Vladimir Kostyukov 
From: nnn123 <nurielzru@gm...>  20120523 12:36:49

how i use bellman ford in jgrapht i post my code that i tried to give weights and add edge and vertex but when i use it i get the wrong path and getcost give me 2  View this message in context: http://jgraphtusers.107614.n3.nabble.com/bellmanfordtp4006658p4008545.html Sent from the jgraphtusers mailing list archive at Nabble.com. 
From: Georg Hieronimus <m.asurn@go...>  20120523 11:49:55

Yes Sent from my mobile Am 23.05.2012 13:44 schrieb "nnn123" <nurielzru@...>: > My graph doesn't contains cycles I need to find bound. the bound is the > longest path with bellman ford with > negating weights. > i can give jgrapht weights and use it in bellman ford algorithm ? > >  > View this message in context: > http://jgraphtusers.107614.n3.nabble.com/bellmanfordtp4006658p4008456.html > Sent from the jgraphtusers mailing list archive at Nabble.com. > > >  > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > 
From: nnn123 <nurielzru@gm...>  20120523 11:44:15

My graph doesn't contains cycles I need to find bound. the bound is the longest path with bellman ford with negating weights. i can give jgrapht weights and use it in bellman ford algorithm ?  View this message in context: http://jgraphtusers.107614.n3.nabble.com/bellmanfordtp4006658p4008456.html Sent from the jgraphtusers mailing list archive at Nabble.com. 
From: Joris Kinable <deus87@gm...>  20120523 10:43:11

Just a comment on what you want to achieve: Finding the longest path in a graph is an NPhard problem. Finding the longest path using Bellman Ford by simply negating the edge weights might not result in your desired 'longest path'. Refer for example to this text for a more detailed explanation: http://courses.csail.mit.edu/6.006/fall11/lectures/lecture17.pdf Section: "Longest Simple Path and Shortest Simple Path": "Finding the longest simple path in a graph with nonnegative edge weights is an NP hard problem, for which no known polynomialtime algorithm exists. Suppose one simply negates each of the edge weights and runs BellmanFord to compute shortest paths. BellmanFord will not necessarily compute the longest paths in the original graph, since there might be a negativeweight cycle reachable from the source, and the algorithm will abort. Similarly, if we have a graph with negative cycles, and we wish to nd the longest simple path from the source s to a vertex v, we cannot use BellmanFord. The shortest simple path problem is also NPhard." As to your question: "Is there a way to make jgrapht get weights that I give him?" I'm not sure what you want to do. In general, as mentioned by Georg Hieronimus you can set edge weights using the setEdgeWeight() function, e.g.: double myEdgeWeight=5.0; Vertex v1= g.addVertex(1); Vertex v2=g.addVertex(2); Edge e=g.addEdge(v1,v2); g.setEdgeWeight(e, myEdgeWeight); Note that an edge can only have 1 edge weight. br, Joris On Wed, May 23, 2012 at 8:22 AM, nnn123 <nurielzru@...> wrote: > I need to display the branch and bound algorithm on a the graph so I use > listenablegraph, I need to find the longest path I use bellman ford with > negative weights but i get rong path so I check with a positive weight also > did not work. > > Is there a way to make jgrapht get weights that I give him? > >  > View this message in context: http://jgraphtusers.107614.n3.nabble.com/bellmanfordtp4006658p4008075.html > Sent from the jgraphtusers mailing list archive at Nabble.com. > >  > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers 
From: nnn123 <nurielzru@gm...>  20120523 06:22:34

I need to display the branch and bound algorithm on a the graph so I use listenablegraph, I need to find the longest path I use bellman ford with negative weights but i get rong path so I check with a positive weight also did not work. Is there a way to make jgrapht get weights that I give him?  View this message in context: http://jgraphtusers.107614.n3.nabble.com/bellmanfordtp4006658p4008075.html Sent from the jgraphtusers mailing list archive at Nabble.com. 
From: John Sichi <jsichi@gm...>  20120522 21:54:43

CC'ing jgraphtusers list. As part of fixing some bugs, the author of the implementation (Guillaume Boulmier) notified me that the upper bound on the worstcase had to be raised, hence the discrepancy across different JGraphT versions. JVS On Tue, May 22, 2012 at 2:18 PM, Gao, Long <gaolong@...> wrote: > Dear JGraphT team, > > Recently I am using the JGraphT lib to do some analysis, and I found it's > really convenient to handle graph problem by taking advantages of your lib. > But I am a little confused with the KShortestPath algorithm. The Java doc > shows that the time complexity of this algorithm is O(k*n*m^2) , but in this > link http://yecolsworldwind.googlecode.com/svnhistory/r15/trunk/worldwind0.6.358.13015/src/org/jgrapht/alg/KShortestPaths.java it > shows the complexity is O(k*m*n). Since this implementation is a variant of > BellmanFord algorithm which has a complexity of O(m*n), I think the > complexity of your implementation should be O(k*m*n). > > Best, > Long Gao 
From: Georg Hieronimus <m.asurn@go...>  20120522 20:49:30

Hello I guess you have to use the graph.setEdgeweight(E edge, double weight) function to make this algorithm work properly. As far I can tell, jgrapht does not support edge classes with its own defined weight. I'm not sure why do you use listenablegraph? If not needed you can switch to simpledirectedgraph or something like this. Sent from my mobile Am 22.05.2012 17:03 schrieb "nnn123" <nurielzru@...>: > down vote favorite > share [g+] share [fb] share [tw] > > > I would like to use jgrapht in order to find the shortest path. > > I saw that jgrapht has a Bellman Ford algorithm, I have tried to use it but > didn't get the right answer > > Given below the code I have used: > > import java.awt.List; > import java.util.ArrayList; > import java.util.Scanner; > > import org.jgrapht.alg.BellmanFordShortestPath; > import org.jgrapht.graph.ListenableDirectedWeightedGraph; > > public class test { > public static void main(String[] args) > { > List lis=new List(); > > BellmanFordShortestPath<Step, MyWeightedEdge> bf;// the bellmanford > ListenableDirectedWeightedGraph<Step,MyWeightedEdge > g;// is the > graph > g = new ListenableDirectedWeightedGraph<Step,MyWeightedEdge > >(MyWeightedEdge.class); > > Step start=new Step(2,2,3); > Step fin=new Step(2,2,2); > g.addVertex(start); > Step fin1=new Step(2,2,2); > Step m=new Step(2,2,2); > g.addVertex(fin); > g.addVertex(m); > MyWeightedEdge w=new MyWeightedEdge(start,fin,5.0); > MyWeightedEdge mm=new MyWeightedEdge(start,m,2.0); > g.addEdge(start, m, mm); > MyWeightedEdge m2=new MyWeightedEdge(m,fin1,1.0); > > g.addVertex(fin1); > g.addEdge(m, fin1, m2); > MyWeightedEdge w1=new MyWeightedEdge(fin,fin1,3.0); > g.addEdge(start, fin, w); > g.addEdge(fin, fin1, w1); > System.out.println(w); > bf= new BellmanFordShortestPath<Step, MyWeightedEdge>(g,start); > System.out.print( bf.findPathBetween(g,start, fin1)); > > System.out.print( bf.getCost(fin1)); > > And: > > import org.jgraph.graph.DefaultEdge; > import org.jgrapht.graph.*; > > public class MyWeightedEdge extends DefaultEdge > { > private Step n1; > private Step n2; > > private double weight; > > public MyWeightedEdge(Step n1, Step n2, double weight) > { > this.n1 = n1; > this.n2 = n2; > this.weight = weight; > } > > public Step getSource() > { > return n1; > } > > public Step getTarget() > { > return n2; > } > > public double getWeight() > { > return weight; > } > > 5.0 [5.0, 3.0] 2.0 > > I get the wrong path. > > Another question: If I want to find the longest path by using Bellman Ford > with negative weight, how I would implement this? > > >  > View this message in context: > http://jgraphtusers.107614.n3.nabble.com/bellmanfordtp4006658.html > Sent from the jgraphtusers mailing list archive at Nabble.com. > > >  > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > 
From: Vladimir Kostyukov <vladimir.kostukov@gm...>  20120522 16:23:07

Hi John, First of all, thank you for fast reply! Regarding equals() and hashCode(). I've already implemented something and sent pullrequest in GitHub (see GitHub project page). I hope you'll find my implementation useful :) BTW, I've also added two unit tests and it passes. On Tue, May 22, 2012 at 11:06 PM, John Sichi <jsichi@...> wrote: > CC'ing jgraphtusers list. > > Hi Vladimir, > > I'm not clear on the intent of your equals method. Comparing hash > codes is not meaningful; two graphs could have the same hash code and > yet be totally unrelated; in this case equals should return false, not > true. > > There are three meaningful possibilities: > > 1) Java object identity (in this case the default equals/hashCode are > good enough) > 2) identical edge sets and vertex sets (I'm not sure whether this > makes sense, but it's easy to implement in terms of the corresponding > Collections methods) > 3) isomorphism (waaaaay too expensive even if some day it turns out to > be nonexponential) > > JVS > > On Tue, May 22, 2012 at 12:58 AM, Vladimir Kostyukov > <vladimir.kostukov@...> wrote: > > Oops. I've sent old hashCode implementation. Here is new one: > > > > public int hashCode() > > { > > int result = 17; > > for (E e: edgeSet()) > > { > > int code = 27; > > int source = getEdgeSource(e).hashCode(); > > int target = getEdgeTarget(e).hashCode(); > > > > // This is a paring function (see details here: > > http://en.wikipedia.org/wiki/Pairing_function) (VK) > > int paring = ((source + target) * (source + target + 1) / 2) > + > > target; > > long weight = (long) getEdgeWeight(e); > > > > code = 37 * code + e.hashCode(); > > code = 37 * code + paring; > > code = 37 * code + (int) (weight ^ (weight >>> 32)); > > > > result += code; > > } > > > > return result; > > } > > > > > > On Tue, May 22, 2012 at 2:41 PM, Vladimir Kostyukov > > <vladimir.kostukov@...> wrote: > >> > >> Hi all, > >> > >> I've just forked JGraphT library in GitHub and started work on > >> implementation better serialization mechanism  I am planning to use > >> Externalizable instead of Serializable. It should works more faster (I > >> guess, we can get something about 2x4x speed up). Now it takes about 10 > >> seconds on my laptop in demo (I've added serialization/deserialization > >> sections in PerformanceDemo). > >> > >> First of all, I've decided to implement hashCode() and equals() methods > in > >> AbstractGraph class. Iilve also created simple Unit tests for my > >> implementation. But in first run I got two tests failed. Here is: > >> > >> Failed tests: testLinearGraph(org.jgrapht.alg.BlockCutpointGraphTest): > >> expecte d:<4> but was:<2> > >> testNotBiconnected(org.jgrapht.alg.BlockCutpointGraphTest): > expected:<3> > >> but was:<2> > >> > >> I've tried to look into this, but I didn't find any Graph::equals usage > >> there. Could you guys, help me in this issue? Why it happens? > >> > >> Here is my implementation in AbstractGraph class: > >> > >> public int hashCode() > >> { > >> int result = 17; > >> for (E e: edgeSet()) > >> { > >> long source = getEdgeSource(e).hashCode(); > >> long target = getEdgeTarget(e).hashCode(); > >> > >> // This is a paring function (see details here: > >> http://en.wikipedia.org/wiki/Pairing_function) (VK) > >> long paring = ((source + target) * (source + target + 1) / > 2) > >> + target; > >> long weight = (long) getEdgeWeight(e); > >> > >> result += 27 * (int) (paring ^ (paring >>> 32)); > >> result += 37 * (int) (e.hashCode() ^ (e.hashCode() >>> 32)); > >> result += 47 * (int) (weight ^ (weight >>> 32)); > >> } > >> > >> return result; > >> } > >> > >> public boolean equals(Object object) > >> { > >> if (this == object) return true; > >> if (object == null) return false; > >> if (!(object instanceof Graph)) return false; > >> > >> // TODO: maybe we should add class checking here: > >> // for example: Undirected and Directed are different graphs, but > could > >> looks the same (have same hashCodes()) (VK) > >> > >> Graph<?, ?> g = (Graph<?, ?>) object; > >> > >> if (vertexSet().size() != g.vertexSet().size() > >>  edgeSet().size() != g.edgeSet().size()) return false; > >> > >> // TODO: maybe we should add vertices and edges factory checking > >> here (VK) > >> > >> //return super.equals(object); > >> return (hashCode() == g.hashCode()); > >> } > >> > >> BTW, my unit tests pass with my implementation. > >> > >> > >> I am going to send you my pullrequest when I finish. It should > contains: > >> unit tests, new PerfromanceDemo, new serialization mechanism, > >> equals/hashCode implementations. > >> > >>  > >> Thanks, > >> Vladimir Kostyukov > >> > > > > > > > >  > > Thanks, > > Vladimir Kostyukov > > >  Thanks, Vladimir Kostyukov 
From: John Sichi <jsichi@gm...>  20120522 16:06:20

CC'ing jgraphtusers list. Hi Vladimir, I'm not clear on the intent of your equals method. Comparing hash codes is not meaningful; two graphs could have the same hash code and yet be totally unrelated; in this case equals should return false, not true. There are three meaningful possibilities: 1) Java object identity (in this case the default equals/hashCode are good enough) 2) identical edge sets and vertex sets (I'm not sure whether this makes sense, but it's easy to implement in terms of the corresponding Collections methods) 3) isomorphism (waaaaay too expensive even if some day it turns out to be nonexponential) JVS On Tue, May 22, 2012 at 12:58 AM, Vladimir Kostyukov <vladimir.kostukov@...> wrote: > Oops. I've sent old hashCode implementation. Here is new one: > > public int hashCode() > { > int result = 17; > for (E e: edgeSet()) > { > int code = 27; > int source = getEdgeSource(e).hashCode(); > int target = getEdgeTarget(e).hashCode(); > > // This is a paring function (see details here: > http://en.wikipedia.org/wiki/Pairing_function) (VK) > int paring = ((source + target) * (source + target + 1) / 2) + > target; > long weight = (long) getEdgeWeight(e); > > code = 37 * code + e.hashCode(); > code = 37 * code + paring; > code = 37 * code + (int) (weight ^ (weight >>> 32)); > > result += code; > } > > return result; > } > > > On Tue, May 22, 2012 at 2:41 PM, Vladimir Kostyukov > <vladimir.kostukov@...> wrote: >> >> Hi all, >> >> I've just forked JGraphT library in GitHub and started work on >> implementation better serialization mechanism  I am planning to use >> Externalizable instead of Serializable. It should works more faster (I >> guess, we can get something about 2x4x speed up). Now it takes about 10 >> seconds on my laptop in demo (I've added serialization/deserialization >> sections in PerformanceDemo). >> >> First of all, I've decided to implement hashCode() and equals() methods in >> AbstractGraph class. Iilve also created simple Unit tests for my >> implementation. But in first run I got two tests failed. Here is: >> >> Failed tests: testLinearGraph(org.jgrapht.alg.BlockCutpointGraphTest): >> expecte d:<4> but was:<2> >> testNotBiconnected(org.jgrapht.alg.BlockCutpointGraphTest): expected:<3> >> but was:<2> >> >> I've tried to look into this, but I didn't find any Graph::equals usage >> there. Could you guys, help me in this issue? Why it happens? >> >> Here is my implementation in AbstractGraph class: >> >> public int hashCode() >> { >> int result = 17; >> for (E e: edgeSet()) >> { >> long source = getEdgeSource(e).hashCode(); >> long target = getEdgeTarget(e).hashCode(); >> >> // This is a paring function (see details here: >> http://en.wikipedia.org/wiki/Pairing_function) (VK) >> long paring = ((source + target) * (source + target + 1) / 2) >> + target; >> long weight = (long) getEdgeWeight(e); >> >> result += 27 * (int) (paring ^ (paring >>> 32)); >> result += 37 * (int) (e.hashCode() ^ (e.hashCode() >>> 32)); >> result += 47 * (int) (weight ^ (weight >>> 32)); >> } >> >> return result; >> } >> >> public boolean equals(Object object) >> { >> if (this == object) return true; >> if (object == null) return false; >> if (!(object instanceof Graph)) return false; >> >> // TODO: maybe we should add class checking here: >> // for example: Undirected and Directed are different graphs, but could >> looks the same (have same hashCodes()) (VK) >> >> Graph<?, ?> g = (Graph<?, ?>) object; >> >> if (vertexSet().size() != g.vertexSet().size() >>  edgeSet().size() != g.edgeSet().size()) return false; >> >> // TODO: maybe we should add vertices and edges factory checking >> here (VK) >> >> //return super.equals(object); >> return (hashCode() == g.hashCode()); >> } >> >> BTW, my unit tests pass with my implementation. >> >> >> I am going to send you my pullrequest when I finish. It should contains: >> unit tests, new PerfromanceDemo, new serialization mechanism, >> equals/hashCode implementations. >> >>  >> Thanks, >> Vladimir Kostyukov >> > > > >  > Thanks, > Vladimir Kostyukov > 
From: nnn123 <nurielzru@gm...>  20120522 13:35:32

down vote favorite share [g+] share [fb] share [tw] I would like to use jgrapht in order to find the shortest path. I saw that jgrapht has a Bellman Ford algorithm, I have tried to use it but didn't get the right answer Given below the code I have used: import java.awt.List; import java.util.ArrayList; import java.util.Scanner; import org.jgrapht.alg.BellmanFordShortestPath; import org.jgrapht.graph.ListenableDirectedWeightedGraph; public class test { public static void main(String[] args) { List lis=new List(); BellmanFordShortestPath<Step, MyWeightedEdge> bf;// the bellmanford ListenableDirectedWeightedGraph<Step,MyWeightedEdge > g;// is the graph g = new ListenableDirectedWeightedGraph<Step,MyWeightedEdge >(MyWeightedEdge.class); Step start=new Step(2,2,3); Step fin=new Step(2,2,2); g.addVertex(start); Step fin1=new Step(2,2,2); Step m=new Step(2,2,2); g.addVertex(fin); g.addVertex(m); MyWeightedEdge w=new MyWeightedEdge(start,fin,5.0); MyWeightedEdge mm=new MyWeightedEdge(start,m,2.0); g.addEdge(start, m, mm); MyWeightedEdge m2=new MyWeightedEdge(m,fin1,1.0); g.addVertex(fin1); g.addEdge(m, fin1, m2); MyWeightedEdge w1=new MyWeightedEdge(fin,fin1,3.0); g.addEdge(start, fin, w); g.addEdge(fin, fin1, w1); System.out.println(w); bf= new BellmanFordShortestPath<Step, MyWeightedEdge>(g,start); System.out.print( bf.findPathBetween(g,start, fin1)); System.out.print( bf.getCost(fin1)); And: import org.jgraph.graph.DefaultEdge; import org.jgrapht.graph.*; public class MyWeightedEdge extends DefaultEdge { private Step n1; private Step n2; private double weight; public MyWeightedEdge(Step n1, Step n2, double weight) { this.n1 = n1; this.n2 = n2; this.weight = weight; } public Step getSource() { return n1; } public Step getTarget() { return n2; } public double getWeight() { return weight; } 5.0 [5.0, 3.0] 2.0 I get the wrong path. Another question: If I want to find the longest path by using Bellman Ford with negative weight, how I would implement this?  View this message in context: http://jgraphtusers.107614.n3.nabble.com/bellmanfordtp4006658.html Sent from the jgraphtusers mailing list archive at Nabble.com. 
From: gu boulmi <boulmigu@ya...>  20120521 08:03:00

/* ========================================== * JGraphT : a free Java graphtheory library * ========================================== * * Project Info: http://jgrapht.sourceforge.net/ * Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh) * * (C) Copyright 20032008, by Barak Naveh and Contributors. * * This library is free software; you can redistribute it and/or modify it * under the terms of the GNU Lesser General Public License as published by * the Free Software Foundation; either version 2.1 of the License, or * (at your option) any later version. * * This library is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public * License for more details. * * You should have received a copy of the GNU Lesser General Public License * along with this library; if not, write to the Free Software Foundation, * Inc., * 59 Temple Place, Suite 330, Boston, MA 021111307, USA. */ /*  * KSPExampleGraph.java *  * (C) Copyright 20072008, by France Telecom * * Original Author: Guillaume Boulmier and Contributors. * * $Id: KSPExampleGraph.java 645 20080930 19:44:48Z perfecthash $ * * Changes *  * 23Sep2007 : Initial revision (GB); * */ package org.jgrapht.alg; import org.jgrapht.graph.*; /** * <img src="./KSPExample.png"> */ @SuppressWarnings("unchecked") public class KSPExample2Graph extends SimpleDirectedGraph<String, DefaultWeightedEdge> { // ~ Static fields/initializers //  /** * <img src="./Picture1.jpg"> */ public KSPExample2Graph() { super(DefaultWeightedEdge.class); addVertices(); addEdges(); } // ~ Methods //  private void addEdges() { addEdge("L1", "a"); addEdge("a", "L2"); addEdge("L2", "b"); addEdge("b", "L3"); addEdge("L3", "d"); addEdge("d", "L4"); addEdge("L4", "e"); addEdge("e", "L5"); addEdge("L3", "c"); addEdge("c", "V2"); addEdge("V2", "f"); addEdge("f", "V3"); addEdge("V3", "g"); addEdge("g", "V5"); // to V5 addEdge("L5", "j"); addEdge("j", "V1"); addEdge("V1", "m"); addEdge("m", "V5"); // to V5 addEdge("L5", "h"); addEdge("L5", "i"); addEdge("h", "L6"); addEdge("i", "L7"); addEdge("L6", "k"); addEdge("L7", "l"); addEdge("k", "L8"); addEdge("l", "L9"); addEdge("L8", "n"); addEdge("L9", "o"); addEdge("n", "V4"); addEdge("o", "V4"); // to V4 addEdge("V4", "p"); addEdge("p", "V5"); // to V5 addEdge("V5", "q"); addEdge("q", "V6"); } private void addVertices() { addVertex("L1"); addVertex("a"); addVertex("L2"); addVertex("b"); addVertex("L3"); addVertex("c"); addVertex("d"); addVertex("L4"); addVertex("V2"); addVertex("e"); addVertex("f"); addVertex("L5"); addVertex("V3"); addVertex("g"); addVertex("h"); addVertex("i"); addVertex("j"); addVertex("L6"); addVertex("L7"); addVertex("V1"); addVertex("k"); addVertex("l"); addVertex("m"); addVertex("L8"); addVertex("L9"); addVertex("n"); addVertex("o"); addVertex("V4"); addVertex("p"); addVertex("V5"); addVertex("q"); addVertex("V6"); } } // End KSPExampleGraph.java 
From: John Sichi <jsichi@gm...>  20120520 04:10:29

See Graphs.addGraph. You can call it twice with the same destination to combine two disjoint graphs. Or if you use GraphUnion to create a merged view of two graphs, you can call Graphs.addGraph with the union as the source to copy it into another empty graph. JVS On Sat, May 19, 2012 at 1:31 PM, alessandro sighinolfi <alexmilano88@...> wrote: > how to merge two graphs, and make the result be changed? > I saw the class graphUnion but it is readonly, there is a way to overcome > this limitation ? > > >  > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > 
From: alessandro sighinolfi <alexmilano88@gm...>  20120519 21:43:15

i found a bit of problem 1 : all the methods of the class are public, even those protected and private... 2 i use DefaultEdge in "AsUndirectedGraph" , i put default edge,i get array of it with .getAllEdges(),but the method getSource,getTarget return "null" for every edge!!? 
From: alessandro sighinolfi <alexmilano88@gm...>  20120519 20:31:44

how to merge two graphs, and make the result be changed? I saw the class graphUnion but it is readonly, there is a way to overcome this limitation ? 
From: 许洪云 <xjyc2007@gm...>  20120517 07:02:03

From: wynchurch <wynchurch@gm...>  20120511 17:02:31

Hi  I am generating a set of shortest paths via KShortestPaths algorithm. My vertices are arranged in "groups" and I am not allowed more that two consecutive vertices from the same "group" in an endtoend path. Therefore I generate all possible paths and postprocess to "strip out" ones that have too many "consecutive" paths. This smells bad/inefficient Is there a "standard" solution here  ideally I would like ... new KShortestPaths<V, DefaultEdge>(graph, A, numPaths).getPaths(Z, excludedSubPaths); where I define a set of "bad excludedSubPaths" e.g. I have a "group" with A,B,C,D which are all interconnected to each other so my paths may optionally include : AB AC AD BC DC BD but must not include more that two consecutive vertices e.g. the following subpaths would be prohibited ABC ABCD ACB BDCA etc etc I thought about modelling just the groups themselves in the graph but that got messy as i can have several edges between groups Many Thanks Kieran.  View this message in context: http://jgraphtusers.107614.n3.nabble.com/getshorthestpathsbutexcludingasetofsubpathstp3980520.html Sent from the jgraphtusers mailing list archive at Nabble.com. 
From: C Robinson <starknight__@ex...>  20120504 07:51:02

Hi jgrapht users, Just a quick note to say I believe it is my code that has the fault. While the nodes do exist, their reference seems to change at some point during the program. Trying to figure out where is quite the challenge. Cheers, Charles Original Message From: "C Robinson" [starknight__@...] Date: 04/30/2012 07:53 AM To: jgraphtusers@... Subject: java.lang.IllegalArgumentException: no such vertex in graph Hi, I'm in something of a quandary. I am constructing a tree where the nodes are chosen at random from a search space. A path is followed at random through the tree and a new node is added each time. When I get to a depth of 3 or 4 I get the error: java.lang.IllegalArgumentException: no such vertex in graph. A simplified version of my code is: if d.vertexSet().isEmpty(){ >>Create initialNode >>dGraph.addVertex(initialNode); } currentNode = initialNode; Loop while tree depth < 10{ >>// Explore existing tree >>while(currentNode!=null){ >>>>previousNode = currentNode >>>>BranchID = chooseBranch(previousNode ) >>>>If node exists for the chosen branch{ >>>>>>currentNode = (DecisionNode) previousNode.getChildren().get(BranchID) >>>>} >>>>else{ >>>>>>currentNode =null >>>>} >>} >>// Create new node from search space. >> currentNode = Create new node >>dGraph.addVertex(currentNode); >>dGraph.addEdge(previousNode, currentNode); } I have tried using the ParanoidGraph, but the result was the same. Is it my logic or something I can resolve within jgrapht? Any advice would be appreciated. Regards, Charles 