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

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