Re: [jgrapht-developers] subclassing CrossComponetIterator
Brought to you by:
barak_naveh,
perfecthash
From: John V. S. <js...@gm...> - 2005-06-25 03:15:05
|
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 > >> >> > ------------------------------------------------------- > >>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 > |