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

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