There's a decent amount of research into functional graph algorithms. The right approach depends on the application, but two interesting ones are inductive grap

There's a decent amount of research into functional graph algorithms. The right approach depends on the application, but two interesting ones are inductive graphs[1] and zippers[2]. I also agree with other commenters that you should make certain you actually need your arbitrarily complicated graph, though. [1]: http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.pdf http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraph... [2]: https://www.cs.tufts.edu/~nr/pubs/zipcfg.pdf https://www.cs.tufts.edu/~nr/pubs/zipcfg.pdf