Re: [jgrapht-developers] subclassing CrossComponetIterator

[gu b. <bou...@ya...>]

Why not, but if I want the returned list to be
coherent, I must implement not only the #iterator()
method but also the others methods of the List
interface such that #size() whose complexity would
become O(size of the list) because we would have to
iterate over all elements to know the size.

Furthermore the complexity of Graph#vertexSet and
Graph#edgeSet would become O(number of vertices) and
O(number of edges) for the same reason.


Concerning the Graph#edgeSet() method, what about
replacing it by 2 methods #edgeIterator and
#getNbEdges ? Actually, from my point of view I use
the edgeSet() method either to know the number of
edges or to iterate ver them.
With this modification if someone wants to store the
edges differently, it would be easier to implement
only these 2 methods instead of implementing all the
methods of the Set interface.


Best regards

Guillaume


--- "John V. Sichi" <js...@gm...> a écrit :

> If the complexity of edgesOf is your concern, that's
> easy to address. 
> Instead of returning a standard implementation such
> as ArrayList, your 
> custom Subgraph class can return a custom List
> implementation which 
> defers the filtering process to its Iterator
> implementation.
> 
> JVS
> 
> gu boulmi wrote:
> > Why not, it seems easy.
> > Nevertheless I think it will be slow.
> > Indeed, whereas the complexity of
> > AbstractBaseGraph#edgesOf is O(1), the complexity
> of
> > Subgraph#edgesOf is O(number of outgoing edges in
> the
> > super-graph) and I care about time consuming.
> > 
> > A method edgesOfIterator (to iterate over outgoing
> > edges like an Iterator) in Graph could allow us to
> > save time when iterating over edges of a vertex.
> > 
> > Furthermore, it is not exactly what I want because
> > "forbidden vertices" are not vertices that are not
> in
> > the subgraph. In contrary they are in the graph
> but
> > such that I do not want any path to cross them
> when
> > using a CrossComponentIterator : a vertex could
> not be
> > reached via a forbidden vertex (except if the
> > forbidden vertex is the source vertex).
> > 
> > I will appreciate any help.
> > Thanks.
> > 
> > 
> > 
> > --- "John V. Sichi" <js...@gm...> a écrit :
> > 
> > 
> >>Instead of subclassing the iterator, have you
> >>considered using a 
> >>Subgraph instead?  It sounds like that's really
> what
> >>you want. 
> >>Subclassing the iterator would be clumsy, because
> >>there are already 
> >>subclasses for the various traversal types (DFS,
> >>BFS, CFS).
> >>
> >>The existing Subgraph implementation is "additive"
> >>in the sense that you 
> >>give it an underlying graph and a mask for which
> >>vertices and edges you 
> >>want to see.  For your purposes, it sounds like a
> >>"subtractive" subgraph 
> >>might be more appropriate; you would give it a
> mask
> >>for which vertices 
> >>and edges you DON'T want to see.
> >>
> >>JVS
> >>
> >>gu boulmi wrote:
> >>
> >>>  Hi,
> >>>
> >>>I want to subclass CrossComponetIterator in order
> >>
> >>to
> >>
> >>>take into account forbidden vertices and
> forbidden
> >>>edges.
> >>>
> >>>Actually, here what I want :
> >>>- I do not want to change the structure of the
> >>
> >>graph
> >>
> >>>via removeVertex and remmoveEdge because it is
> >>
> >>slow
> >>
> >>>(regarding to CPU time).
> >>>- I want to prevent somme edges from being
> >>
> >>traversed
> >>
> >>>and I say "this edge is forbidden".
> >>>- For some vertices I do not want at all to
> >>
> >>examine
> >>
> >>>its edges ant I say "this vertex is forbidden".
> >>>
> >>>Here ideas I have to tackle this matter (but it
> >>
> >>will
> >>
> >>>need to modify few lines of the core jgrapht
> >>
> >>source
> >>
> >>>code) :
> >>>- for the 3d point : let the method
> >>>addUnseenChildrenOf be protected (instead of
> >>
> >>private)
> >>
> >>>such that I could override it like that : "if
> >>
> >>vertex
> >>
> >>>is forbidden then do nothing else
> >>>super.addUnseenChildrenOf".
> >>>- for the 2d point : add a protected method
> >>>"edgesOfIterator(Vertex)" and a graph member
> >>
> >>instead
> >>
> >>>of "Specifics" classes (each time we used
> >>
> >>Specifics,
> >>
> >>>it is to iterate over the edges of a vertex
> >>
> >>depending
> >>
> >>>on the directed/undirected feature of the graph).
> >>
> >>Thus
> >>
> >>>I would have to override this "edgesOfIterator"
> >>
> >>and
> >>
> >>>ignore forbidden edges when returning the "next"
> >>
> >>edge.
> >>
> >>>What do you think about it ?
> >>>If you agree with me, I would appreciate if these
> >>>changes could be in the next 0.6 release.
> >>>
> >>>Thanks
> >>>
> >>>Guillaume
> >>>
> >>>
> >>>	
> >>>
> >>>	
> >>>		
> >>>
> >>
> >
>
___________________________________________________________________________
> > 
> >>>Appel audio GRATUIT partout dans le monde avec le
> >>
> >>nouveau Yahoo! Messenger 
> >>
> >>>Téléchargez cette version sur
> >>
> >>http://fr.messenger.yahoo.com
> >>
> >>>
> >>>
> >
>
-------------------------------------------------------
> > 
> >>>SF.Net email is sponsored by: Discover Easy Linux
> >>
> >>Migration Strategies
> >>
> >>>from IBM. Find simple to follow Roadmaps,
> >>
> >>straightforward articles,
> >>
> >>>informative Webcasts and more! Get everything you
> >>
> >>need to get up to
> >>
> >>>speed, fast.
> >>
> >
>
http://ads.osdn.com/?ad_id=7477&alloc_id=16492&op=click
> > 
> >>>_______________________________________________
> >>>jgrapht-developers mailing list
> >>>jgr...@li...
> >>>
> >>
> >
>
https://lists.sourceforge.net/lists/listinfo/jgrapht-developers
> 
=== message truncated ===



	

	
		
___________________________________________________________________________ 
Appel audio GRATUIT partout dans le monde avec le nouveau Yahoo! Messenger 
Téléchargez cette version sur http://fr.messenger.yahoo.com