Eulerian paths

[JoeyT1994]

This PR adds algorithms for finding Eulieran paths and Eulerian cycles for the AbstractGraph type.

An Eulerian path is a path from a source vertex to a target vertex which traverses each edge in the graph exactly once. In order to have an Eulerian path the source and target vertex must be of odd degree and all other vertices of even degree. An Eulerian cycle is a path from a source vertex back to itself which traverses each edge in the graph exactly once. In order to have an Eulerian cycle all vertices of the graph must be of even degree.

See: https://en.wikipedia.org/wiki/Eulerian_path for more info.

If such a cycle/ path exists for a graph g, the algorithm implemented here will find it in O(M) where M = length(edges(g)) time.

@mtfishman I think this could be a good base for coming up with a good sweeping plan for DMRG.

1. If a graph has an Eulerian cycle then a reasonable one/two-site sweep plan is simply eulerian_cycle(g) for the first half sweep and then reverse(eulerian_cycle(g)) for the second half.
2. If the graph doesn't have an Eulerian cycle (because it has vertices of odd degree) then it seems reasonable to: i) add "dummy" edges whilst minimising dist(g_original, src(e), dst(e)) until all its vertices have even degree, then ii) construct a corresponding Eulerian cycle starting at one of the extremal vertices of the original graph g and finally iii) if doing a two-site sweep plan, remove any dummy edges from the cycle

Consider: An open boundary 1D chain of L sites. Then a single edge will be added 1 => L to make all the vertices of even degree and the Eulerian cycle will simply start at site 1/L and flow round to site L/1 of the chain and then backwards as is done in typical DMRG.

[mtfishman]

Interesting. Not exactly the same thing but it reminds me of the use of Hilbert curves as 1D paths through a 2D lattice for DMRG in https://arxiv.org/abs/2105.02239. Does it seem like it constructs reasonable iteration paths? For example, how does it compare to doing a DFS?

By the way, I see: https://juliagraphs.org/Graphs.jl/dev/algorithms/traversals/#Graphs.eulerian-Union%7BTuple%7BAbstractGraph%7BT%7D%7D,%20Tuple%7BT%7D,%20Tuple%7BAbstractGraph%7BT%7D,%20T%7D%7D%20where%20T. Can we just wrap that?

[JoeyT1994]

Ah I didn't see that Graphs.jl has this functionality already. I can re-write just to wrap that as that should be fine.

Depth first search currently misses out edges of the graph as it essentially treeifies it. So one would have to take the union of different DFSs to fully cover the edges of the graph. This seems like it could create some discontinuities in the sweep plan which this algorithm would aim to minimise. I can run it on a 2D square lattice to see what it comes up with.

[mtfishman]

Yes, a naive application of DFS would definitely miss some edges, but my conjecture would be that there would be some way to minimally catch those missed edges, say by traversing the DFS tree/path and then updated all edges of each vertex that is visited (say if you are doing a 2-site update). For n-site updates you could start with the same DFS as the "base path" and update some neighborhood around each vertex visited in the path. One would then just need to track which groups of vertices were already visited (say by storing a set of the vertex sets that have been updated) and not update the same edges/vertex sets multiple times as you traverse along the DFS path.

[JoeyT1994]

Yeah that also would be another reasonable option and at least in the 1 / 2-site case is perhaps more straightforward to code. Let me play around with that and if it gives reasonable answers might be good to stick with for now.