Python code to find Eulerian Tour does not work in one case. Why?

python, recursion

Solution

You have no backtracking mecanism in `getCurPoint()`. This means that your algorithm is taking the first edge found to travel in the graph, building a path that may lead to dead ends without having traversed all nodes.

This is exactly what is happening with your example. Your algorithm will start from node `0` to get to node `1`. This node offer 3 edges to continue your travel (which are `(1, 5)`, `(1, 7)`, `(1, 6)`) , but one of them will lead to a dead end without completing the Eulerian tour. Unfortunately the first edge listed in your graph definition `(1, 5)` is the wrong path and won't let you any occasion to reach nodes `6`, `3`, and `7`.

To check my affirmation, you could try to change the given definition of the graph to invert edges `(1, 5)` with `(1, 7)`, and see how your algorithm will then list all nodes correctly.

How can I help

First, to help you solve yourself these issues, you should always make diagrams (and not only to make Feynman happy), and try to follow your algorithm on the diagram. These cases are easy to draw, and it will become clear that the algorithm is not correct, and you might spot why.

Second, this exercise is about backtracking. Do you know what this is ? If not, you can try googling this word or even search it here in stackoverflow search box, and wikipedia has a good article on that also.

At last, I can give you some advice on your coding style. Please consider them as personal and take what seems to suit your current needs:

When possible:

- avoid `for x in range(len(graph)):` if you'll use only `graph[x]` after. Python offers a very elegant replacement solution `for edge in graph:`. And if you really need the index of the element you are iterating, you could go for the elegant: `for i, edge in enumerate(graph):`

avoid your 3 lines construct (that you've used twice) involving a lonely `if` in a `for`:

for x in criticals[1]:
    if x != point:
        stops.append(x)

prefer explicit, and smaller:

node_a, node_b = critical_edges[1] 
stops += [node_a] if node_b == node else [node_b]

less important code cosmetic style remarks:

- avoid java CamelCase for variable, function name and method names, python has a PEP8 on styling that prefer variable names to use lower case with underscores.

- rename 'point' to 'node' to stick to wider used vocabulary on graph

- rename 'pair' to 'edge' to get a descriptive naming of what is the meaning of your variable rather than its type (although you could think of mixing both info in what is called Hungarian Notation)

Applying the cosmetic remarks, we'll have for example `getCurPoint` renamed to `get_next_nodes`, with:

- variable_with_underscore instead of CamelCase and `Point`-> `nodes` as explained before,

- plural because it will return a list of node

- 'cur' was renamed 'next' because, it's about getting the next nodes.

A sample by rewriting your code in a more pythonic way

Please note that this is only a rewrite, and that the previous bug is always present. Take a look at the `get_next_nodes()` function how it changed:

def get_next_nodes(edges, cur_node):
    connected_edges = [x for x in edges
                       if cur_node in x]
    if connected_edges:
        a, b = connected_edges[0]
        next_node = b if a == cur_node else a
        edges.remove(connected_edges[0])
        return [cur_node] + get_next_nodes(edges, next_node)
    return []

def take_tour(graph):
    start_node = graph[0][0]
    critical_edges = []
    nodes = []
    for edge in graph:
        if start_node in edge and len(critical_edges) < 2:
            critical_edges.append(edge)
        else:
            nodes.append(edge)

    second_node = critical_edges[0][1]
    stops = [start_node] + get_next_nodes(nodes, second_node)

    a, b = critical_edges[1]
    stops += [a] if b == start_node else [b]
    return stops + [start_node]

Now, there are more issues to your algorithm

How should your script react to non Eulerian graph ? Your algorithm will output a broad variety of results, ranging from wrong node list, to confusing exception. A proper non-confusing exception should be raised if exception is not to be avoided. Try your algorithm with these graph:

non-Eulerian:

[(0, 1), (1, 5), (1, 7), (4, 5), (4, 8), (1, 6), (3, 7), (5, 9), (2, 4), (2, 5), (3, 6), (8, 9)]

non-Eulerian: `[(0, 1), (0, 3)]`

- Eulerian: `[(0, 0)]`

- non-Eulerian: `[]`

you are adding by hand 3 nodes in your list in `take_tour`. There is a much more elegant solution, with much less code!

why are you picking a finishing edge in `take_tour` along with the starting edge ? You might pick the wrong one ! you saw that taking the first of multiple choice could be wrong. Try this graph:

- Eulerian: `[(0, 1), (0, 1), (0, 2), (0, 2)]`, the correct result should be `[0, 1, 0, 2, 0]`.

Finaly, let met give you a correct answer

This simple recursive code will answer the initial problem you tried to solve.

Please note how the the initial `getCurPoint` is not far from doing some backtracking. The only addition is the introduction of the `for` loop that will parse in all possible solution instead of blindly taking the first one.

But to allow backtracking, the function must be able to quit current path calculation. This is done by allowing `False` value to be returned in cases where no path are found. `False` will then be repercuted from child function call to parent function, effectively un-tying the recursion until it can try another edge thanks to the `for` loop.

You'll notice that you can merge `getCurPoint` and `take_tour`. This gives the added benefice to have 2 features hidden in the new `take_tour`:

- it'll be able to show you Eulerian path (which are different than Eulerian tour which have to start and end on the same node).

- you can provide a start node if you are curious enough to force another start node to see paths.

Here is the code:

def take_tour(graph, node_start=None, cycle_only=True):
    if len(graph) == 0:
        if node_start is None:
            return []
        return [node_start]

    node_start = graph[0][0] if node_start is None else node_start

    for chosen_edge in [x for x in graph if node_start in x]:
        (node_a, node_b) = chosen_edge
        path = take_tour([e for e in graph if e != chosen_edge],
                         node_b if node_start == node_a else node_a,
                         cycle_only=False)
        if path is not False and (not cycle_only or node_start == path[-1]):
            return [node_start] + path
    return False

If you are look for some other simple exercise, here are 2 easy to medium questions that are left open and that could be answered in one go:

- how would you modify `take_tour` to return a list of all possible tour/paths ?

- and would you be able to transform `take_tour` in an iterator of all possible tour/paths ? (a clever iterator that would compute next path only upon request).

I hope this was didactic enough.

Problem

Original source

Related problems

• Finding a Eulerian Tour