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
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 :/