[Haskell-cafe] Navigating Graphs
matthias.goergens at googlemail.com
Tue Feb 9 16:57:32 EST 2010
Using something like zippers it is easy to navigate an acyclic graph
in O(1) operations per arc you follow. Inspired by Chris Okasaki's
work on queues I wondered if there is a similar approach to navigating
If the graph you are navigating is static (i.e. does not have to
support addition or removal of vertices in any reasonable amount of
time), I guess you can get away with "Tying the know"
(http://www.haskell.org/haskellwiki/Tying_the_Knot). But is there a
technique that allows navigation, insertion and removal at focus in
(at least amortised) O(1) operations each?
As a generalisation being able to have multiple points of focus (in an
acyclic graph for a start) would also be interesting.
More information about the Haskell-Cafe