[Haskell-cafe] Navigating Graphs

[Matthias Görgens]

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
cyclic graphs.

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.

Any thoughts?