Algorithm to travel all edges only once

Question

I have a directed, unweighted graph that obeys the following rules:

• The number of nodes and edges is finite
• Each node can eventually be reached from any other node by some path
• Each node has an equal number of incoming and outgoing edges

Like this:

I am trying to develop and algorithm that starts in any node and travels each edge of the map once and only once but I'm struggling to come up with anything.

I've thought about finding an algorithm to hit each node and then following it out and back but this can easily be done without traveling every path. (In the graph above you could go a->d->g->e->b->c->f->c->b->e->g->d->a but never hit the paths connecting d to e or the paths connecting e to f)

I've also tried to come up with something like the corn maze solution where you always take the left most available path, but this too has the potential to leave out large chunks of the graph. (you could go a->d->a and think you were done)

I think in order to do this I probably need to be keeping track of which nodes I've already visited and how many remaining untraveled edges it had and always choose to travel to the node with the max remaining untraveled edges. But I feel like this has errors too where I could trap myself into part of the graph though I haven't found a good example where it does so. Any way to prove the correctness of this or find a counterexample (and in that case maybe thoughts on a new possibility) would be greatly appreciated! I've found a counter example:

Consider the following graph with moves marked in red and remaining count at each node marked in blue, at this point, you are in node b, and can move to either a or c because they are equally weighted, if you move to a, you have effectively cut yourself off from ever traveling the b->c paths.

So now I'm at even more of a loss :/

Answer 1

You are trying to find an Euleran path in a graph.

Observe, that if each node has equal number of incoming and outcoming edges, every time you enter a node using an edge you have not used before, there is an unused outgoing edge. The only vertex that does not have this property is the starting vertex. Therefore, any path that starts in vertex $v$ can either be easily extended or end in $v$, resulting in a cycle.

The only problem we now have to take care about is covering all the edges. After you finish a cycle and can't proceed, take any vertex $t$, which is in your cycle and has some unused edges. Start a new cycle from $t$, obviously using only unused edges. Connect the new cycle with the old one. Iterate until finished.

Answer 2

Though this is from 4 years ago, another way to solve this is by finding the Hamiltonian Path of the Line Graph of G. Just convert each edge to a vertex and connect those vertices if the corresponding edges shared a vertex in G. (Respecting the directions in this case.)

So the line graph would look like this, each vertex is labeled with the direction of the edge in G. So finding the hamiltonian path of this directed graph, gives the Eulerian path of G.