How can be found Euler path from a directed graph using hierholzer's algo?

Question

The above graph contains an Euler Path & indegree and outdegree are equal in every node except the starting node 6 (Indeg[6] + 1 == Outdeg[6]) and finishing node 4 (Indeg[4] == Outdeg[4] + 1).

Path: 6->7->8->9->6->3->0->2->1->3->4

If I add an extra edge 4 to 6, then all nodes are balanced.

If I apply Hierholzer's algorithm, output (cycle) can be:

6->3->0->2->1->3->4->6->7>8->9->6

Now, How can I retrieve the actual path?

Answer 1

Firstly, Divide the cycle into two cycles where the edge is connected by the finishing node (4) to the starting node (6). Two cycles are:

1. 6->3->0->2->1->3->4->6
2. 6->7>8->9->6

Now, remove the last node from every cycle and simply connect 2 and 1.

6->7>8->9

+

6->3->0->2->1->3->4

Finally, we get:

6->7>8->9->6->3->0->2->1->3->4

Answer 2

You might be overcomplicating it. Consider the cycle to be an actual cycle:

6302  (arrows implicit, going clockwise)
|  1
9  3
8764

It has no specific beginning or end; we can trace the path starting at any point in the cycle. For instance 1->3->4->6->7->8->9->6->3->0->2 (-> back to 1).

Since in the original graph, there is no cycle and we must terminate on 4, we just pick that rotation of the above cycle which terminates on 4. That's easy; it's the rotation which starts at the successor of 4. 4 has that successor precisely because of the extra edge that had been added.

To find the rotation ending in 4, we can start with 6->3->0->2->1->3->4->6->7>8->9->6 and then follow this algorithm:

while last(cycle) != terminating_node
  pushback(cycle, popfront(cycle))

---

Another way to look at this is that the above cycle is itself a new graph, which is related to the original augmented graph.

Vertices in the original augmented graph correspond to sets of vertices in the cycle graph. For instance, 3 appears twice in the cycle, but the original graph has only one 3. We thus should give the vertices unique names like $3_a$ and $3_b$ to properly represent the cycle as a graph:

$$6_a\rightarrow 3_a\rightarrow 0_a\rightarrow 2_a\rightarrow 1_a\rightarrow 3_b\rightarrow 4_a\rightarrow 6_b\rightarrow 7_a\rightarrow 8_a\rightarrow 9_a\rightarrow 6_a$$

Multiple visits to the same vertex under the Hierholzer algorithm are thus recorded as unique vertices in the cycle graph representing the path, which lets us see the two occurrences of $6$ more clearly as different objects.

In any case, the edges in the cycle graph are in 1:1 correspondence with those in original augmented graph (by definition of what it represents).

The augmented graph has a $4\rightarrow 6$ edge which was added to the original unaugmented graph. This edge object, like all the others, has exactly one counterpart in the cycle graph. That counterpart is the $4_a\rightarrow 6_b$ edge.

If we remove that edge, we open the cycle and our path emerges:

6302
|  1
9  3
8764
   ^ cut here!

6302
|  1
9  3
8  4
76  

The path begins at the only only vertex with no incoming edge, but as a shortcut, we know that if we are deleting the $4_a\rightarrow 6_b$ edge to break the cycle, then $6_b$ must be that vertex.

In other words, what Angina Seng wrote in a comment!