jgrapht-developers Mailing List for JGraphT (Page 2)
Brought to you by:
barak_naveh,
perfecthash
You can subscribe to this list here.
2003 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
|
Aug
|
Sep
(4) |
Oct
(4) |
Nov
|
Dec
|
---|---|---|---|---|---|---|---|---|---|---|---|---|
2004 |
Jan
|
Feb
|
Mar
|
Apr
|
May
(1) |
Jun
|
Jul
|
Aug
|
Sep
(18) |
Oct
(3) |
Nov
|
Dec
|
2005 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
(5) |
Jul
(7) |
Aug
(5) |
Sep
(7) |
Oct
|
Nov
|
Dec
(14) |
2006 |
Jan
(6) |
Feb
(1) |
Mar
(3) |
Apr
(6) |
May
(7) |
Jun
(1) |
Jul
(4) |
Aug
(1) |
Sep
(1) |
Oct
|
Nov
|
Dec
(2) |
2007 |
Jan
|
Feb
|
Mar
(8) |
Apr
|
May
|
Jun
(2) |
Jul
(1) |
Aug
|
Sep
(4) |
Oct
(2) |
Nov
(3) |
Dec
|
2008 |
Jan
(1) |
Feb
|
Mar
|
Apr
|
May
(2) |
Jun
|
Jul
(2) |
Aug
|
Sep
(1) |
Oct
|
Nov
|
Dec
|
2009 |
Jan
(2) |
Feb
|
Mar
|
Apr
(2) |
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
2010 |
Jan
|
Feb
|
Mar
(2) |
Apr
|
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
2011 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
|
Aug
|
Sep
(1) |
Oct
|
Nov
|
Dec
|
2018 |
Jan
|
Feb
|
Mar
|
Apr
|
May
(1) |
Jun
|
Jul
|
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
2019 |
Jan
(1) |
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
2020 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
(1) |
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
From: John V. S. <js...@gm...> - 2007-03-17 08:53:38
|
Finally getting around to the questions below...answers inline. For the contributions, I need someone to send me an updated version against the latest Subversion, plus unit tests. gu boulmi wrote: > --------------------- > - Running time (#list if allowingLoops) is missing for methods > AbstractBaseGraph#degreeOf Do you have a suggestion for the comment which should be added? None of the other methods have running times advertised, do they? > http://www.jgrapht.org/javadoc/org/jgrapht/alg/BellmanFordShortestPath.html > the link "Bellman-Ford algorithm" points at > http://www.nist.gov/dads/HTML/shortestpath.html instead of > http://www.nist.gov/dads/HTML/bellmanford.html I just fixed it, thanks. > 2. Code design > --------------------- > - Why not add a default constructor to graphs (with no parameter) > where the edge-class would be java.lang.Object ? There's no way to get this to work lint-free with generics. We tried for a long time and had to give up. An alternative would be to make one extra non-edge-generic class per graph type; I considered it, but the maintenance effort didn't seem worth it. > - Why not push down methods Graph#addEdge, Graph#addVertex, > Graph#removeEdge, Graph#removeVertexModifiableGraph in a > ModifiableGraph interface (extending the Graph interface). In this > way it would become much easier to extend Graph with a new concrete > graph class. Actually none of the algorithms of JGraphT require > these modify-methods. This has been proposed. I think the last conclusion on this was that we shouldn't do it because it doesn't follow the java.util pattern, where there is no statically checked "const correctness" split between modifiable and unmodifiable objects; instead, everything is dynamically checked (throw UnsupportedOperationException isn't that much work). > - Why not add a contructor to ConnectivityInspector with Graph as > parameter type ? Edge direction would be ignored if the passed graph > is not an instance of > DirectedGraph. The two current constructors would become useless. AsUndirectedGraph wants a DirectedGraph as parameter, so the distinction is required (lint again). > - Methods Graph#containsVertex and #containsEdge are redundant with > Graph#vertexSet().contains and Graph#edgeSet().contains and should > be removed Not true. contains takes Object as parameter (Sun has a twisted rationale somewhere), whereas containsVertex and containsEdge are typesafe-generic. > - Add a method DijkstraShortestPath#findPathBetween without the > radius parameter It looks like this already exists? > - The constructor DijkstraShortestPath checks wether the graph > contains start vertex but does not check for the end vertex I just fixed it; not much point searching for something which isn't there :) > - The dijkstra algorithm constructs a shortest-paths tree from the > start vertex thus it would be usefull (from a running time point of > view) to add the endVertex parameter to methods getLength(endVertex) > and getPathEdgeList(endVertex). The endVertex parameter of the > constructor would become useless. DijkstraShortestPath is really just a convenience class for pairwise searches; use ClosestFirstIterator directly for anything else. Or we can factor out a new convenience class DijkstraShortestPathTree for handling multiple endpoints. > - Classes ConnectivityInspector and StringConnectivityInspector > should have quite the same usage. > why ConnectivityInspector#isGraphConnected is not named > #isConnected as StrongConnectivityInspector#isStronglyConnected ? > why ConnectivityInspector#getGraph does not exist as in > StrongConnectivityInspector ? > why ConnectivityInspector#connectedSubgraphs does not exist as > in StrongConnectivityInspector ? > why StrongConnectivityInspector#stronglyConnectedSetOf does not > exist as in ConnectivityInspector ? > why StrongConnectivityInspector#pathExists does not exist as in > ConnectivityInspector ? Hmmm...sounds like we need a JGraphT Standards Committee :) If I give you Subversion access, would you like to be the chairman for a future release? We can follow the policy of leaving the inconsistencies behind with @deprecated, and eventually get rid of them. > 3. Coding conventions > --------------------- > - BellmanFordShortestPath#getCost should be renamed #getPathLength > as DijkstraShortestPath##getPathLength More work for the standards committee. > - Attribute AbstractPathElement#nHops should be renamed #nbHops as > "number of hops" and thus method AbstractPathElement#getHopCount > should be renamed > #getNbHops according to java-beans getter convention I usually use the convention nLumps to mean "number of lumps". I don't think we're following java-beans getter convention anywhere in JGraphT; to me, getHopCount is much more meaningful than getNbHops. > - Is it a java coding convention to append "Listener" at the end of > as listener-class name ? In this cas NeighborIndex should be renmed > NeighborIndexListener I don't think it's necessary. In a case like this, a class can implement a Listener interface as an implementation detail; it doesn't need to advertise that fact in its name (except as a means of attaching itself to the graph). > 4. Web site > --------------------- > - The web site http://www.dis.uniroma1.it/~challenge9/ tackles about > implementations of shortest paths algorithm and it could be useful > to add a link. Thanks; I've added this to a new page: http://jgrapht.wikispaces.org/RelatedProjects Feel free to add on more. > - On the wiki site > http://jgrapht.wikispaces.com/CollaborationPatterns several times > EdgeDirectedGraph is used instead of EdgeReversedGraph. It's fixed now. JVS |
From: Trevor H. <tr...@vo...> - 2007-03-12 23:55:08
|
On Mar 8, 2007, at 12:35 AM, John V. Sichi wrote: > Trevor Harmon wrote: >> I noticed that the repository has a new GMLExporter class that >> will likely be included in the next JGraphT release. I've >> written exporters for two other graph formats: DOT and GraphML. >> They're not quite ready for submission yet, but I hope to clean >> them up and submit them about a month from now. Would that be in >> time to include them in the next official release of JGraphT? > > At my current snail's pace, it seems likely that they would be > included :) So that I don't forget, I went ahead and cleaned them up and submitted them. They're in the Patch tracker as #1679428 and #1679430. Trevor |
From: Trevor H. <tr...@vo...> - 2007-03-12 09:36:40
|
On Mar 8, 2007, at 12:44 AM, John V. Sichi wrote: > Trevor Harmon wrote: >> I use the VertexNameProvider classes a lot, and I recently had a >> need to provide names for the edges in my graph, too. I was >> surprised to find that there don't seem to be any >> EdgeNameProvider classes. Is there some technical reason for >> this, or is it simply that nobody's gotten around to writing name >> provider code for edges? > > The latter. Okay, I just submitted an implementation as patch #1678818. Trevor |
From: John V. S. <js...@gm...> - 2007-03-08 08:44:17
|
Trevor Harmon wrote: > I use the VertexNameProvider classes a lot, and I recently had a need > to provide names for the edges in my graph, too. I was surprised to > find that there don't seem to be any EdgeNameProvider classes. Is > there some technical reason for this, or is it simply that nobody's > gotten around to writing name provider code for edges? The latter. > I assume it's the latter case, so I plan to write one myself and > submit it to the JGraphT project. For the design, I'm thinking there > will be an interface called EdgeNameProvider and two implementing > classes, IntegerEdgeNameProvider and StringEdgeNameProvider. Sound > about right? Right. The getEdgeName method in the interface should only take (E edge), with no info about the source and target. If someone needs to derive the edge name based on the source/target, they can do that in their implementation of the interface by giving their constructor a reference to a specific graph and calling to that graph to get the source and target from getEdgeName. JVS |
From: John V. S. <js...@gm...> - 2007-03-08 08:35:56
|
Trevor Harmon wrote: > I noticed that the repository has a new GMLExporter class that will > likely be included in the next JGraphT release. I've written > exporters for two other graph formats: DOT and GraphML. They're not > quite ready for submission yet, but I hope to clean them up and > submit them about a month from now. Would that be in time to include > them in the next official release of JGraphT? At my current snail's pace, it seems likely that they would be included :) JVS |
From: Trevor H. <tr...@vo...> - 2007-03-07 20:51:21
|
I use the VertexNameProvider classes a lot, and I recently had a need to provide names for the edges in my graph, too. I was surprised to find that there don't seem to be any EdgeNameProvider classes. Is there some technical reason for this, or is it simply that nobody's gotten around to writing name provider code for edges? I assume it's the latter case, so I plan to write one myself and submit it to the JGraphT project. For the design, I'm thinking there will be an interface called EdgeNameProvider and two implementing classes, IntegerEdgeNameProvider and StringEdgeNameProvider. Sound about right? Trevor |
From: Trevor H. <tr...@vo...> - 2007-03-07 20:49:18
|
I noticed that the repository has a new GMLExporter class that will likely be included in the next JGraphT release. I've written exporters for two other graph formats: DOT and GraphML. They're not quite ready for submission yet, but I hope to clean them up and submit them about a month from now. Would that be in time to include them in the next official release of JGraphT? Trevor |
From: John V. S. <js...@gm...> - 2006-12-21 07:42:44
|
gu boulmi wrote: > It seems that .zip extension is blocked. That's why I've renamed the zip > file with .zip2 extension and I retry to send my mail above. Thanks, got it. I'll respond as soon as I get some time. I notice that you're still referring to org._3pq.jgrapht; the package got renamed to org.jgrapht as part of the 0.7.0 release. It would help if all files sent were baselined against the subversion head, or at least 0.7.0, since there have been many changes. JVS |
From: John V. S. <js...@gm...> - 2006-09-17 07:52:51
|
I've checked a new EdgeReversedGraph view into Subversion. This allows you to create a view of a directed graph with all of the edges reversed, without having to pay the cost of copying the graph and flipping the edges. This is useful in combination with iterators (e.g. reverse-topological-sort, or reverse DFS/BFS). On the general topic of how various classes in JGraphT can be combined (and the pattern for adding new classes and methods), I've written up a wiki page with some of the philosophy I've been trying to live: http://jgrapht.wikispaces.com/CollaborationPatterns JVS |
From: John V. S. <js...@gm...> - 2006-08-27 09:18:43
|
John V. Sichi wrote: > I'll see if I can come up with something efficient when I fix it > permanently in 0.7.1. There have been requests to keep track of the > discovery and finish time, so I can probably kill two birds with one > stone by keeping this info in the "seen data" and using it to know > whether something is still on the stack or not without linear search. I've checked a more efficient fix into Subversion. DepthFirstIterator now keeps track of the standard WHITE/GRAY/BLACK vertex visit states, and uses them to provide a finish event via TraversalListener. No timestamps yet. Code review by anyone who has time would be appreciated; maybe someone can enhance BreadthFirstIterator to publish vertex finish events in the same way. Khanh Vu also reported a problem with CycleDetector, which I fixed. It is now using StrongConnectivityInspector for one of the cases; it should probably be using it for more of them; I'll see about that as part of changing StrongConnectivityInspector to use DepthFirstIterator. I'm going to take care of a few of the other recent requests and then put out 0.7.1. JVS |
From: Aaron H. <aa...@li...> - 2006-07-24 23:13:25
|
Hmm, for a sparse graph, which I'd wager your 1% graph could be considered, doing an iterated Dijkstra will be more efficient than the Floyd-Warshall -- O(N E log N) vs O(N^3), if I remember right. Other than that I don't have a clear intuition beyond John's good idea... good luck! -A -- Aaron Harnly Center for Computational Learning Systems Columbia University http://harnly.net On Jul 21, 2006, at 3:35 PM, John V. Sichi wrote: > Muhamad Abu-Much wrote: >> i have a undirected weighted graph, i want to find a shortest >> path which contains the given set of nodes, or as many as possible >> of the given >> set. >> >> any idea would be appreciated >> >> i have implemented warshall algorithm but the all pairs solution >> but it is time consuming since my graph is a littile bit large >> 5552 vertices and 235222 edges. >> >> which iterator should i use ?, the shortest path is based on the >> weight of the edge. > > There's probably a standard algorithm for this if you check a graph > theory book. Off the top of my head, maybe you could start from the > desired "waypoint" set and for each member, find a shortest path to > the > source and target independently. Link up the two halves, do that for > each vertex in the waypoint set, and then score them based on combined > pathlength and number of other waypoint vertices included, > weighting the > two in whatever way makes sense for your application. > > Whatever you come up with, please consider contributing it (and your > all-pairs implementation) to JGraphT if it can be expressed > generically. > > JVS > > ---------------------------------------------------------------------- > --- > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to > share your > opinions on IT & business topics through brief surveys -- and earn > cash > http://www.techsay.com/default.php? > page=join.php&p=sourceforge&CID=DEVDEV > _______________________________________________ > jgrapht-users mailing list > jgr...@li... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users |
From: John V. S. <js...@gm...> - 2006-07-21 19:35:27
|
Muhamad Abu-Much wrote: > i have a undirected weighted graph, i want to find a shortest path which contains the given set of nodes, or as many as possible of the given > set. > > any idea would be appreciated > > i have implemented warshall algorithm but the all pairs solution but it is time consuming since my graph is a littile bit large > 5552 vertices and 235222 edges. > > which iterator should i use ?, the shortest path is based on the weight of the edge. There's probably a standard algorithm for this if you check a graph theory book. Off the top of my head, maybe you could start from the desired "waypoint" set and for each member, find a shortest path to the source and target independently. Link up the two halves, do that for each vertex in the waypoint set, and then score them based on combined pathlength and number of other waypoint vertices included, weighting the two in whatever way makes sense for your application. Whatever you come up with, please consider contributing it (and your all-pairs implementation) to JGraphT if it can be expressed generically. JVS |
From: John V. S. <js...@gm...> - 2006-07-03 08:29:44
|
Or should I say JGraphT<V,E>? Generics are here, and there are a lot of interface-breaking changes in this release, so it will be the bumpiest upgrade yet, but it should be well worth it to anyone interested in type-safety. I have also created a wiki for the JGraphT community (free/ad-supported hosting courtesy of wikispaces.com): http://wiki.jgrapht.org Join now and let us know how you're using the project! JVS |
From: John V. S. <js...@gm...> - 2006-07-03 05:08:26
|
Notes on resolutions below, since I'm about to wrap up 0.7.0. Also, Eclipse and I went on a Ctrl-Alt-R purge last night and all the m_'s are gone forever! (Cue maniacal laughter...) Barak Naveh wrote: > Since 0.7.0 will anyway involves some interface-breaking changes, it might > be a good chance to consider fixing a few flaws were left lurking in Graph > -- probably due my fault... > > 1. Edge factory > ---------------------------- > The inclusion of the edge factory was a pre-Java 5.0 attempt to provide some > crude type-safety for edges. Now after generics have been applied, there > seem to be no strong need for the edge factory. The Graph interface can be > simplified by eliminating the edge factory. Consequently, addEdge(V,V) will > become obsolete and could be eliminate as well. Turns out edge factory is still required, because new E() doesn't work in Java generics. The default implementation is now ClassBasedEdgeFactory, which uses a class object to create new instances. > 2. NullPointerException -> IllegalArgumentException > --------------------------------------------------- > Some methods throw new NullPointerException. It might be better if they > throw new IllegalArgumentException to avoid confusion with the > NullPointerExceptions that the virtual machine may throw. See > http://pmd.sf.net/rules/strictexception.html for more on that. I disagree with PMD here. I think a NullPointerException is more natural than an IllegalArgumentException in this context, and java.util agrees (grep the src and you'll see them throwing many NPE's); since java.util has always been the model we follow, I think we should stick with the existing behavior. > 3. edgesOf(V v) > ------------- > Contract clarification: what if v is null? What if v doesn't exist in the > graph? Probably should through IllegalArgumentException. The code already throws NPE/IAE from getEdgeContainer, so I am just going to add that specification to the Javadoc; no behavior change. JVS |
From: John V. S. <js...@gm...> - 2006-06-26 09:29:17
|
I spent the weekend on a lot of cleanup work in preparation for the release: - purging a lot of obsolete code in experimental, and getting the rest buildable again - eliminating all lint warnings except for experimental and test code - moving isomorphism code to experimental (needs more work for generics and some other things before it's ready for prime time) - standardizing file headers and Subversion keyword expansion - fixing all Javadoc errors/warnings - fixing Eclipse warnings It would be helpful if anyone who has the time could pull the latest code from Subversion and test it out, in particular on Windows since I do all of my development on Linux. I still have the items below to take care of before release: - fix/suppress warnings in experimental and test - run Jalopy - test out retroweaver - figure out how to rework CVS tags support in build.xml to target Subversion instead - update release notes, wiki, sample code, etc. JVS |
From: John V. S. <js...@gm...> - 2006-05-30 05:35:47
|
OK, the bomb has dropped, the dust has settled, and there's no looking back. I have committed a massive change to Subversion, getting rid of the Edge package entirely and moving all of the connectivity/weight info to the Graph interface. It should now be possible to create views such as edge-reversals and different weightings on the same underlying graph. Details are at a new wiki I just created (free ad-supported hosting from wikispaces.com) for JGraphT: http://jgrapht.wikispaces.com/MigrationTo0.7 I'm sure there's lots of cleanup needed (e.g. generating various serialVersionUUID's), and now we should be able to get rid of a lot more of the lint warnings. Try it out and send me suggestions if you see something that doesn't look right. The experimental package build is temporarily broken as a result of my changes, because I didn't fix all of the dependencies in there. Notes: - Edges which inherit from the new DefaultEdge use an "IntrusiveEdge" mechanism so that the connectivity info is really still inside of the edge, but hidden away. For other edge types, a HashMap is used to go from edge object to connectivity info. - Edge factories are still there, but now there's a way to get one based on YourEdge.class. For type-safety, you now have to supply an edge factory in all cases; with generics, there's no way to make edge construction happen automatically, and I didn't want to get rid of the addEdge(V,V) method, because it's very convenient when you aren't using a custom edge class. This is a minor annoyance at the time of graph instantiation. I considered introducing another level of classes to provide correct defaults for this case, but this would have required a companion class for every single one of the "gallery" classes in org.jgrapht.graph, and there are so many of those already! JVS |
From: John V. S. <js...@gm...> - 2006-05-16 21:02:29
|
Thanks Guillaume. I'll go over these together with the ones raised by Barak. Here's an answer to the only easy one: gu boulmi wrote: > Why ModifiableInteger does not extend the java.lang.Integer class ? Because java.lang.Integer is final. JVS |
From: gu b. <bou...@ya...> - 2006-05-15 08:48:35
|
Hi, I agree with Barak about the three changes, specially the 1st point. By the way I will seize the opportunity of suggesting other changes. 1. AbstractBaseGraph ---------------------------- The constructor contains line : edgefactory.createEdge( new Object( ), new Object( ) ). That is to say all edge-factories must allow Object parameters, even if we wanted a factory that creates only edges whose vertices are of a specified type. Anyway if the edge factory is eliminated from the graph interface, as suggested by Barak, this problem will disappear. 2. Modifiable graph ---------------------------- Because the top-interface Graph contains add/remove methods (addVertex, removeVertex, addEdge, removeEdge), when creating an alternative implementation we must implement these modify-methods, although most graph-theory algorithms (at least those in JGraphT at the present time) do not need to modify the graph. Why not create a "ModifiableGraph" sub-interface of Graph (all modify-methods pushed down) ? It could be very easier for alternative implementations. 3. Dijkstra http://en.wikipedia.org/wiki/Dijkstra's_algorithm ---------------------------- The only constructor has a "raduis" argument. Why not create a second constructor without this argument ? Furthermore because Dijkstra algorithm computes the shortest paths between a starting vertex and each other vertex in a directed graph why not create a constructor with the star-vertex but without the end-vertex and pass the end- vertex argument to methods getLength(endVertex) and getPathEdgeList(endVertex) ? 4. ModifiableInteger ---------------------------- Why ModifiableInteger does not extend the java.lang.Integer class ? 5. Complexity ---------------------------- Generally the complexity of the methods are not mentioned. However it is very useful from an algorithmic point of view. For instance I have noticed that the dijkstra complexity is not mentioned as well as AbstractBaseGraph#degreeOf (which is O(#list), not O(1)). 6. DirEdge ---------------------------- What is the interest in discriminating between directed-edge and undirected-edge ? Is it not enough to consider that an edge is directed/undirected regarding a graph ? If the graph is a DirectedGraph, edges are directed, and otherwise edges are undirected. Anyway, at he present time for the graph classes in JGraphT, edges of a graph are either all directed or all undirected. 7. Graph#containsVertex ---------------------------- Two methods should be deleted in the Graph interface : Graph#containsEdge and Graph#containsVertex. They are redundant because of Graph#vertexSet().contains and Graph#edgeSet().contains. Best regards, Guillaume Barak Naveh <bar...@us...> a écrit : Since 0.7.0 will anyway involves some interface-breaking changes, it might be a good chance to consider fixing a few flaws were left lurking in Graph -- probably due my fault... 1. Edge factory ---------------------------- The inclusion of the edge factory was a pre-Java 5.0 attempt to provide some crude type-safety for edges. Now after generics have been applied, there seem to be no strong need for the edge factory. The Graph interface can be simplified by eliminating the edge factory. Consequently, addEdge(V,V) will become obsolete and could be eliminate as well. 2. NullPointerException -> IllegalArgumentException --------------------------------------------------- Some methods throw new NullPointerException. It might be better if they throw new IllegalArgumentException to avoid confusion with the NullPointerExceptions that the virtual machine may throw. See http://pmd.sf.net/rules/strictexception.html for more on that. 3. edgesOf(V v) ------------- Contract clarification: what if v is null? What if v doesn't exist in the graph? Probably should through IllegalArgumentException. Barak ------------------------------------------------------- Using Tomcat but need to do more? Need to support web services, security? Get stuff done quickly with pre-integrated technology to make your job easier Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo http://sel.as-us.falkag.net/sel?cmd=lnk&kid0709&bid&3057&dat1642 _______________________________________________ jgrapht-developers mailing list jgr...@li... https://lists.sourceforge.net/lists/listinfo/jgrapht-developers --------------------------------- Faites de Yahoo! votre page d'accueil sur le web pour retrouver directement vos services préférés : vérifiez vos nouveaux mails, lancez vos recherches et suivez l'actualité en temps réel. Cliquez ici. |
From: John V. S. <js...@gm...> - 2006-05-08 15:52:24
|
Barak, thanks for the perspective. My comments inline below. Barak Naveh wrote: > For many graph applications and algorithms, there is significance for the > *order* of the edges attached to each vertex. Although the original > implementation didn't give powerful tools to manipulate that order, it at > least respected the order in which edges were added. One could always > remove edges and add them back in a desired order. The implementation > wasn't necessarily efficient, but the Graph interface was still open for > alternative implementations that could offer better control on the edge > order with higher efficiency. If the interface is just changed from List to > Set, it closes the lid on implementations that require edge order. Actually, we changed it a while back even for vertices (where Set has been used from the beginning) to preserve edge order for the default graph implementations (via LinkedHashMap). However, we don't require it, as it may not be practical for all graph implementations; it's an optional contract. So, we continue to support this for edges after the interface change, and now we have (a) consistency across edge and vertex and (b) faithfulness to the mathematical definition of a graph, which has always been an important part of JGraphT. > One can say that the edge order could be maintained externally to the > graph. Although true, I don't think it's convenient. For huge graphs it > will probably also be inefficient memory-wise. On the other hand, List > might be inefficient CPU-wise for high-degree vertices –- also not good. Note that even though we used List for the edge interface, it has never actually been possible to use that to manipulate edge order post-addition. Why? Because we return unmodifiable lists from user-level calls. That's not to say users may not have wanted to. Hartmut responded to my forum post asking about exactly that. To address these desires, we can add an additional OrderableGraph interface which allows direct manipulation of edge list and vertex list order. But I don't think this belongs on the main Graph interface (for the same reason that java.util discriminates between Collection and List). > The simplest solution could be to keep the List interface but in the > implementation use an adaptive EdgeContainer. The EdgeContainer implements > List and maintains a Map<Edge,Integer> index that enable fast access edges > within the list. The graph implementation can use a simple ArrayList-based > container to contain the edges, but if the number of edges exceeds a certain > threshold, say 10 edges, the container is replaced with EdgeContainer. > Since EdgeContainer implements List, such runtime replacements can happen > behind the Graph interface, private to the implementation. > > Another approach could be to completely externalize the edge container > from Graph by introducing an additional generic parameter: > > Graph<V, E extends Edge<V>, EC extends Collection<E>> We actually addressed this one a while back too. We added an EdgeListFactory interface (which I just renamed to EdgeSetFactory). The default implementation produces ArrayList (now ArrayUnenforcedSet), but users can override it with something that returns LinkedHashSet directly, or an adaptive container. There's a unit test for it which uses LinkedHashSet. I think Christian and Hartmut will both agree that accepting additional generic parameters on the Graph interface will require extensive justification! So we'll stick with the factory pattern here. JVS |
From: Barak N. <bar...@us...> - 2006-05-08 13:15:53
|
Since 0.7.0 will anyway involves some interface-breaking changes, it = might be a good chance to consider fixing a few flaws were left lurking in = Graph -- probably due my fault... 1. Edge factory ---------------------------- The inclusion of the edge factory was a pre-Java 5.0 attempt to provide = some crude type-safety for edges. Now after generics have been applied, = there seem to be no strong need for the edge factory. The Graph interface can = be simplified by eliminating the edge factory. Consequently, addEdge(V,V) = will become obsolete and could be eliminate as well. 2. NullPointerException -> IllegalArgumentException --------------------------------------------------- Some methods throw new NullPointerException. It might be better if they throw new IllegalArgumentException to avoid confusion with the NullPointerExceptions that the virtual machine may throw. See http://pmd.sf.net/rules/strictexception.html for more on that. 3. edgesOf(V v) ------------- Contract clarification: what if v is null? What if v doesn't exist in = the graph? Probably should through IllegalArgumentException. Barak=20 |
From: Barak N. <bar...@us...> - 2006-05-08 11:40:11
|
Hi John, Regardless of the historical reasons, I still think it's a mistake to = just change the return type of edgesOf() from List to Set. I think that if nothing else is done, returning List makes a better Graph interface and = I'll try to defend my point. However, since I'm no longer actively involved = in the development, I might be seriously out of sync and talking rubbish as = a result. Please be forgiving if this is the case :) For many graph applications and algorithms, there is significance for = the *order* of the edges attached to each vertex. Although the original implementation didn't give powerful tools to manipulate that order, it = at least respected the order in which edges were added. One could always remove edges and add them back in a desired order. The implementation wasn't necessarily efficient, but the Graph interface was still open for alternative implementations that could offer better control on the edge order with higher efficiency. If the interface is just changed from = List to Set, it closes the lid on implementations that require edge order.=20 One can say that the edge order could be maintained externally to the graph. Although true, I don't think it's convenient. For huge graphs = it will probably also be inefficient memory-wise. On the other hand, List might be inefficient CPU-wise for high-degree vertices =96- also not = good. So, what to do? The simplest solution could be to keep the List interface but in the implementation use an adaptive EdgeContainer. The EdgeContainer = implements List and maintains a Map<Edge,Integer> index that enable fast access = edges within the list. The graph implementation can use a simple = ArrayList-based container to contain the edges, but if the number of edges exceeds a = certain threshold, say 10 edges, the container is replaced with EdgeContainer. Since EdgeContainer implements List, such runtime replacements can = happen behind the Graph interface, private to the implementation. Another approach could be to completely externalize the edge container from Graph by introducing an additional generic parameter: =20 Graph<V, E extends Edge<V>, EC extends Collection<E>> where EC is the edge container type. EC can either be a List for graphs that care about edge order or Set for graphs that don't. Of course, the graph must ensure that NO duplicate edges are ever added to the edge container (EC). =20 Opinions? Barak > -----Original Message----- > From: Nobody [mailto:no...@sc...] On Behalf Of > SourceForge.net > Sent: Monday, May 08, 2006 01:33 > To: no...@so... > Subject: [jgrapht - Users] RE: Graph.edgesOf() return type >=20 >=20 > Read and respond to this message at: > https://sourceforge.net/forum/message.php?msg_id=3D3718040 > By: perfecthash >=20 > I have gone ahead with the breaking interface change in Subversion, > replacing > List with Set. >=20 > Turns out there's no need to worry about assert/non-assert, because = the > graph > already takes care of edge uniqueness at a higher-level, so no safety = is > sacrificed > by always using ArrayUnenforcedSet (the new collection class I added). >=20 > I'm thinking about going ahead with a much bigger breaking change: = making > it > so that only Graph knows about connectivity, so to get a source or = target > of > an edge (or an attribute like weighting), you have to ask the Graph. = This > has > been requested repeatedly in the past as a way of making new graph = views > (e.g. > ReversedGraph) practical. The symmetry it would bring between Vertex = and > Edge > would probably also resolve a lot of the problems with generics > encountered > by Hartmut. >=20 > JVS >=20 >=20 > ______________________________________________________________________ > You are receiving this email because you elected to monitor this = forum. > To stop monitoring this forum, login to SourceForge.net and visit: > https://sourceforge.net/forum/unmonitor.php?forum_id=3D296039 |
From: John V. S. <js...@gm...> - 2006-05-07 22:38:04
|
FYI: http://sourceforge.net/forum/message.php?msg_id=3718040 JVS |
From: John V. S. <js...@gm...> - 2006-04-30 07:07:19
|
The proposal from Charles sounds good to me. JVS assaf lehr wrote: > It sounds like a possible feature. If it will be decided to allow it > ,the changes should be minor: > change documentation > change resetRandomSeed to be public (and rename it to a better public name) > delete the call to it in the generateGraph method. > > However , you will destory the behaviour of tests/code which use it , so > make sure to update tests and make it clear to the community that such > change will effect thier code and that whoever uses it , must fix their > code. > I do not know what is the policy about API change of this code , which > is not officialy released , John V. Sichi might answer that. > > about changing it to interface , I got no particular issues. > > > > */Charles Fry <cf...@us...>/* wrote: > > It seems to me that the RandomGraphGenerator specification is incorrect. > It currently generates the same graph over and over on subsequent calls > to generateGraph(), and I argue that it should rather produce (probably) > different graphs on each call to generateGraph(). I don't recall any > discussion about the class, but it may have occured before I joined the > group. In any case, I need to extend RandomGraphGenerator, and I would > very much like to see its specification improved. :-) > > The closest parallels that I can find in Java itself are Random and > SecureRandom, which generate random numbers as opposed to random graphs. > Their model is to construct a single instance of Random, and then to > generate a (probably) different random number on each subsequent method > invocation. It is possible to reseed the random number generator (or to > seed the constructor) to obtain duplicible results. > > I argue that RandomGraphGenerator should do the same. It should be > possible to construct an instance either with or without specifying a > seed, and then to reseed the instance at will. But between reseedings, > succesive calls to generateGraph should create (probably) different > graphs. > > I also propose that RandomGraphGenerator be turned into an interface > (following the specification outlined above, which I would be glad to > turn into code), which could then be implemented by the current > generator, as well as the currently experimental > UniformRandomGraphGenerator and PartiteRandomGraphGenerator (shouldn't > that be Bipartite?), in addition to some new RandomGraphGenerators that > I plan to write (RegularRandomGraphGenerator and > MOutRandomGraphGenerator to begin with, though > PreferentialAttachmentRandomGraphGenerator would be nice, if not > verbosely named). > > Charles > > -- > My job is > Keeping faces clean > And nobody knows > De stubble > I've seen > Burma-Shave > http://burma-shave.org/jingles/1950/my_job_is > > > ------------------------------------------------------- > Using Tomcat but need to do more? Need to support web services, > security? > Get stuff done quickly with pre-integrated technology to make your > job easier > Download IBM WebSphere Application Server v.1.0.1 based on Apache > Geronimo > http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642 > _______________________________________________ > jgrapht-developers mailing list > jgr...@li... > https://lists.sourceforge.net/lists/listinfo/jgrapht-developers > > > ------------------------------------------------------------------------ > Get amazing travel prices for air and hotel in one click on Yahoo! > FareChase > <http://farechase.yahoo.com/;_ylc=X3oDMTFpMnJnZ3IxBF9TAzk3NDA3NTg5BHNlYwNtYWlsLXRhZ2xpbmVzBHNsawNmYXJlY2hhc2UtMDQyNzA2 > > |
From: assaf l. <ass...@ya...> - 2006-04-29 18:55:22
|
It sounds like a possible feature. If it will be decided to allow it ,the changes should be minor: change documentation change resetRandomSeed to be public (and rename it to a better public name) delete the call to it in the generateGraph method. However , you will destory the behaviour of tests/code which use it , so make sure to update tests and make it clear to the community that such change will effect thier code and that whoever uses it , must fix their code. I do not know what is the policy about API change of this code , which is not officialy released , John V. Sichi might answer that. about changing it to interface , I got no particular issues. Charles Fry <cf...@us...> wrote: It seems to me that the RandomGraphGenerator specification is incorrect. It currently generates the same graph over and over on subsequent calls to generateGraph(), and I argue that it should rather produce (probably) different graphs on each call to generateGraph(). I don't recall any discussion about the class, but it may have occured before I joined the group. In any case, I need to extend RandomGraphGenerator, and I would very much like to see its specification improved. :-) The closest parallels that I can find in Java itself are Random and SecureRandom, which generate random numbers as opposed to random graphs. Their model is to construct a single instance of Random, and then to generate a (probably) different random number on each subsequent method invocation. It is possible to reseed the random number generator (or to seed the constructor) to obtain duplicible results. I argue that RandomGraphGenerator should do the same. It should be possible to construct an instance either with or without specifying a seed, and then to reseed the instance at will. But between reseedings, succesive calls to generateGraph should create (probably) different graphs. I also propose that RandomGraphGenerator be turned into an interface (following the specification outlined above, which I would be glad to turn into code), which could then be implemented by the current generator, as well as the currently experimental UniformRandomGraphGenerator and PartiteRandomGraphGenerator (shouldn't that be Bipartite?), in addition to some new RandomGraphGenerators that I plan to write (RegularRandomGraphGenerator and MOutRandomGraphGenerator to begin with, though PreferentialAttachmentRandomGraphGenerator would be nice, if not verbosely named). Charles -- My job is Keeping faces clean And nobody knows De stubble I've seen Burma-Shave http://burma-shave.org/jingles/1950/my_job_is ------------------------------------------------------- Using Tomcat but need to do more? Need to support web services, security? Get stuff done quickly with pre-integrated technology to make your job easier Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642 _______________________________________________ jgrapht-developers mailing list jgr...@li... https://lists.sourceforge.net/lists/listinfo/jgrapht-developers --------------------------------- Get amazing travel prices for air and hotel in one click on Yahoo! FareChase |
From: Charles F. <cf...@us...> - 2006-04-28 19:35:29
|
Indeed, this seems to be exactly the methodology followed by JUNG: http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/random/generators/SimpleRandomGenerator.html Speaking of which they have a number of random grpah generators, but don't use a single backing interface. Perhaps I'll give them a shot... Charles -----Original Message----- > From: Charles Fry <cf...@us...> > Subject: [jgrapht-developers] RandomGraphGenerator behavior > Date: Fri, 28 Apr 2006 14:43:47 -0400 > To: jgr...@li... > > It seems to me that the RandomGraphGenerator specification is incorrect. > It currently generates the same graph over and over on subsequent calls > to generateGraph(), and I argue that it should rather produce (probably) > different graphs on each call to generateGraph(). I don't recall any > discussion about the class, but it may have occured before I joined the > group. In any case, I need to extend RandomGraphGenerator, and I would > very much like to see its specification improved. :-) > > The closest parallels that I can find in Java itself are Random and > SecureRandom, which generate random numbers as opposed to random graphs. > Their model is to construct a single instance of Random, and then to > generate a (probably) different random number on each subsequent method > invocation. It is possible to reseed the random number generator (or to > seed the constructor) to obtain duplicible results. > > I argue that RandomGraphGenerator should do the same. It should be > possible to construct an instance either with or without specifying a > seed, and then to reseed the instance at will. But between reseedings, > succesive calls to generateGraph should create (probably) different > graphs. > > I also propose that RandomGraphGenerator be turned into an interface > (following the specification outlined above, which I would be glad to > turn into code), which could then be implemented by the current > generator, as well as the currently experimental > UniformRandomGraphGenerator and PartiteRandomGraphGenerator (shouldn't > that be Bipartite?), in addition to some new RandomGraphGenerators that > I plan to write (RegularRandomGraphGenerator and > MOutRandomGraphGenerator to begin with, though > PreferentialAttachmentRandomGraphGenerator would be nice, if not > verbosely named). > > Charles > > -- > My job is > Keeping faces clean > And nobody knows > De stubble > I've seen > Burma-Shave > http://burma-shave.org/jingles/1950/my_job_is > > > ------------------------------------------------------- > Using Tomcat but need to do more? Need to support web services, security? > Get stuff done quickly with pre-integrated technology to make your job easier > Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo > http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642 > _______________________________________________ > jgrapht-developers mailing list > jgr...@li... > https://lists.sourceforge.net/lists/listinfo/jgrapht-developers -- Every shaver Now can snore Six more minutes Than before By using Burma-Shave http://burma-shave.org/jingles/1943/every_shaver |