Re: [jgrapht-developers] RE : Some contributions

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