[jgrapht-developers] JGraphT Version 0.7.1 Released

[John V. Sichi <jsichi@gm...>]

This is a maintenance release which includes a number of bugfixes and
contributions which have accumulated since the 0.7.0 release.

Many thanks to all who have contributed code, tests, bugs, bugfixes,
questions, and answers!

JVS

Re: [jgrapht-developers] RE : Some contributions

[John V. Sichi <jsichi@gm...>]

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

Re: [jgrapht-developers] GraphML and DOT exporters

[Trevor Harmon <trevor@vo...>]

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

Re: [jgrapht-developers] EdgeNameProvider

[Trevor Harmon <trevor@vo...>]

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

Re: [jgrapht-developers] EdgeNameProvider

[John V. Sichi <jsichi@gm...>]

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

Re: [jgrapht-developers] GraphML and DOT exporters

[John V. Sichi <jsichi@gm...>]

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

[jgrapht-developers] EdgeNameProvider

[Trevor Harmon <trevor@vo...>]

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

[jgrapht-developers] GraphML and DOT exporters

[Trevor Harmon <trevor@vo...>]

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

Re: [jgrapht-developers] RE : Some contributions

[John V. Sichi <jsichi@gm...>]

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

[jgrapht-developers] RE : Some contributions

[gu boulmi <boulmigu@ya...>]

[jgrapht-developers] EdgeReversedGraph and JGraphT class collaboration patterns

[John V. Sichi <jsichi@gm...>]

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

Re: [jgrapht-developers] [jgrapht-users] DFS Question

[John V. Sichi <jsichi@gm...>]

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

Re: [jgrapht-developers] [jgrapht-users] all against all shortest path

[Aaron Harnly <aaron@li...>]

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
> jgrapht-users@...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

Re: [jgrapht-developers] all against all shortest path

[John V. Sichi <jsichi@gm...>]

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

[jgrapht-developers] JGraphT Version 0.7.0 Released

[John V. Sichi <jsichi@gm...>]

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

Re: [jgrapht-developers] interface breaking changes

[John V. Sichi <jsichi@gm...>]

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

[jgrapht-developers] preparing for 0.7 release

[John V. Sichi <jsichi@gm...>]

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

Re: [jgrapht-developers] interface breaking changes

[John V. Sichi <jsichi@gm...>]

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

Re: [jgrapht-developers] interface breaking changes

[John V. Sichi <jsichi@gm...>]

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

RE: [jgrapht-developers] interface breaking changes

[gu boulmi <boulmigu@ya...>]

  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 <barak_naveh@...> 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
jgrapht-developers@...
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.

[jgrapht-developers] Re: [jgrapht - Users] RE: Graph.edgesOf() return type

[John V. Sichi <jsichi@gm...>]

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

[jgrapht-developers] interface breaking changes

[Barak Naveh <barak_naveh@us...>]

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

[jgrapht-developers] RE: [jgrapht - Users] RE: Graph.edgesOf() return type

[Barak Naveh <barak_naveh@us...>]

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:nobody@...] On Behalf Of
> SourceForge.net
> Sent: Monday, May 08, 2006 01:33
> To: noreply@...
> 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

[jgrapht-developers] breaking interface changes made/planned for 0.7

[John V. Sichi <jsichi@gm...>]

FYI:

http://sourceforge.net/forum/message.php?msg_id=3718040

JVS

Re: [jgrapht-developers] RandomGraphGenerator behavior

[John V. Sichi <jsichi@gm...>]

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 <cfry@...>/* 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
>     jgrapht-developers@...
>     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 
>  >