Re: [jgrapht-developers] subclassing CrossComponetIterator
Brought to you by:
barak_naveh,
perfecthash
Menu
▾
▴
Re: [jgrapht-developers] subclassing CrossComponetIterator
|
From: John V. S. <js...@gm...> - 2005-07-26 07:39:10
|
Sun's java.util provides classes like AbstractList and AbstractSet to make it very easy to whip up custom implementations of collection classes. You only have to implement a few methods, and the base class does the rest. And this way, if you want, you can optimize the complexity of the size() method, whereas if you only provided an iterator() method, then an algorithm needing the size would be forced to iterate and count. Concerning the edgeSet() and vertexSet() methods of Graph, we have no plans to replace them. The two methods you mention (iterator and size) are exactly the ones you need to override in AbstractSet, so it's already very easy to produce custom implementations. We had two very good reasons for declaring these methods the way they are: 1) In every textbook on graph theory, a graph is defined in terms of a pair (V,E) where V is a set of vertices and E is a set of edges. So, a good graph interface should stick as close as possible to this formalism. Since Sun already provides the Set concept, we use it directly. 2) Sets are useful for other operations such as membership test, union, intersect, set equality test, etc. For example, if we did what you suggested, then we'd have to clutter up the interface with more methods like containsEdge. Even though you don't currently use these methods, other users may (including your future self). I appreciate your critique, and I hope this discussion helps to explain these aspects of the library's design. JVS gu boulmi wrote: > 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 > |
