Re: [jgrapht-developers] subclassing CrossComponetIterator

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

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
> > 
> 
> 
>
-------------------------------------------------------
> 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
> 



	

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