jgrapht-developers

[jgrapht-developers] interface breaking changes

[Barak N. <bar...@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

RE: [jgrapht-developers] interface breaking changes

[gu b. <bou...@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 <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.

Re: [jgrapht-developers] interface breaking changes

[John V. S. <js...@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

[John V. S. <js...@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. S. <js...@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