Eulerian tour
I’m taking Intro to Algorithms, which focuses mostly on graphs, and one of the first topics is about Eulerian paths and tours, you can easily find the theory of these topics in the course or on Wikipedia, let’s write some code.
This is my brute force solution to the challenge in problem set 1: Find Eulerian tour:
# Find Eulerian Tour
#
# Write a function that takes in a graph
# represented as a list of tuples
# and return a list of nodes that
# you would follow on an Eulerian Tour
#
# For example, if the input graph was
# [(1, 2), (2, 3), (3, 1)]
# A possible Eulerian tour would be [1, 2, 3, 1]
import copy
def contains_all_nodes(path, nodes):
= {}
unique for p in path:
= True
unique[p] for node in nodes:
if node not in unique:
return False
return True
def tour(u, graph, visited, path, nodes):
path.append(u)for v in graph[u]:
= (min(u, v), max(u, v))
e if e not in visited:
= copy.deepcopy(visited)
visited_copy = True
visited_copy[e] = copy.deepcopy(path)
path_copy = tour(v, graph, visited_copy, path_copy, nodes)
p if contains_all_nodes(p, nodes):
return p
return path
def find_eulerian_tour(edges):
= {}
graph = {}
nodes for edge in edges:
= edge[0]
u = edge[1]
v = True
nodes[u] = True
nodes[v] if u not in graph:
= []
graph[u]
graph[u].append(v)if v not in graph:
= []
graph[v]
graph[v].append(u)
for n in nodes:
= tour(n, graph, {}, [], nodes)
path if contains_all_nodes(path, nodes):
return path
return []
#edges = [(1, 2), (2, 3), (3, 1)]
= [(0, 1), (1, 5), (1, 7), (4, 5), (4, 8), (1, 6), (3, 7),
edges 5, 9), (2, 4), (0, 4), (2, 5), (3, 6), (8, 9)]
(print find_eulerian_tour(edges)