Perhaps something like that in ConcreteBidirectional be implemented for general Digraph so predecessors can be accessed in O(1)? If I am not mistaken, that will double the storage and running time of most of the operations. This implementation could be added as an additional variant without modifying existing code.
Kevin Cheung. > From: ri...@happyleptic.org >> > What you're asking is similar to the problem of finding the >> predecessor >> > of an arbitrary node in a singly-linked-list. You have no option but >> to >> > scan the whole list to find its predecessor. If you had a >> > doubly-linked-list, predecessor lookups would work easily, but that's >> a >> > different data structure, with much more overhead. >> >> Much more overhead, really ? >> So this is for performance reasons that all functionnal languages >> promote singly-linked lists, while for instance in Linux every list >> is implemented with a doubly linked list for purely ideological reasons >> ? >> >> :-) > > Yes indeed, much more overhead. But the source is not the fact you > have to maintain backlinks, but their impact on the GC. > With a GC, any modification on existing values has a cost, since you > have to keep track of them independently of the value itself. > Since linux has no GC, using doubly linked lists has only a very > limited cost, mostly related to the extra space needed. > By the way, BSD uses lots of singly-linked lists, probably because it > comes from a time when there was not so much memory. > > Jacques Garrigue > > _______________________________________________ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > _______________________________________________ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
