__author__ pasha usr bin python Find Eulerian Tour Write function that

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
__author__ = 'pasha'
#!/usr/bin/python
# 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), (3, 2), (1, 3)]
# A possible Eulerian tour would be [1, 2, 3, 1]
# Example_graph = [
# (0, 1), (1, 5), (1, 7), (4, 5), (4, 8),
# (1, 6), (3, 7), (5, 9), (2, 4), (0, 4),
# (2, 5), (3, 6), (8, 9)
# ]
def get_node_list(graph):
"""
Make list of nodes from adjacency edge list.
:rtype : list
Example:
> get_node_list([(0, 1), (1, 5), (1, 7)])
> [0, 1, 5, 7]
"""
node_list = []
for edge in graph:
for node in edge:
if node not in node_list:
node_list.append(node)
return node_list
def get_adjacent_edges(vertex, graph):
"""
Make list of adjacent edges from specific vertex.
Example:
> get_adjacent_edges(2, [(0, 2), (2, 5), (1, 7)])
> [(0, 2), (2, 5)]
"""
return filter(lambda (x, y): x == vertex or y == vertex, graph)
def find_starting_node(graph):
"""
Function will return starting vertex for eulerian path.
Example:
> find_starting_node([(1, 2), (2, 3), (1, 3)])
> 1
"""
even = []
odd = []
for node in get_node_list(graph):
if len(get_adjacent_edges(node, graph)) % 2 == 0:
even.append(node)
else:
odd.append(node)
if len(odd) == 0:
return even[0]
else:
return odd[0]
def find_cycle(s_node, graph, cycle):
"""
Recursive gunction that will search and return cycles in graph, it also returns unused edges.
Example:
> find_cycle(1, [(2, 1), (3, 2), (1, 3)], [])
> ([1, 2, 3, 1], [])
"""
possible_edge_list = filter(lambda (x, y): x == s_node or y == s_node, graph)
cycle.append(s_node)
for edge in possible_edge_list:
if edge in graph:
graph.remove(edge)
if edge.index(s_node) == 0:
find_cycle(edge[1], graph, cycle)
else:
find_cycle(edge[0], graph, cycle)
if cycle[0] == cycle[-1]:
return cycle, graph
def merge_cycles(cycle_one, cycle_two):
"""
Function for merging two cycles with common vertex. Accepts two list of vertexes, and will return one list.
Example:
> merge_cycles([4, 8, 9, 5, 2, 4], [1, 0, 4, 5, 1, 7, 3, 6, 1])
> [1, 0, 4, 5, 9, 8, 4, 2, 5, 1, 7, 3, 6, 1]
"""
common_nodes = []
common_nodes += filter(lambda x: x in cycle_one, cycle_two)
index_one = cycle_one.index(common_nodes[0])
index_two = cycle_two.index(common_nodes[0])
#print cycle_two[0:index_two + 1]
#print cycle_one[0:index_one][::-1]
#print cycle_one[index_one:-1][::-1]
#print cycle_two[index_two + 1:]
return \
cycle_two[0:index_two + 1] +\
cycle_one[0:index_one][::-1] +\
cycle_one[index_one:-1][::-1] +\
cycle_two[index_two + 1:]
def search_and_merge(graph, final_path):
"""
Recursive function that will search for cycles in graph until in contains unused edges
and returns list of visited edges.
"""
s_node = find_starting_node(graph)
cycle = []
(cycle, graph) = find_cycle(s_node, graph, cycle)
if len(final_path) == 0:
final_path += cycle
else:
final_path = merge_cycles(final_path, cycle)
if len(graph) > 0:
search_and_merge(graph, final_path)
elif len(graph) == 0:
print merge_cycles(final_path, cycle)
return merge_cycles(final_path, cycle)
graph = [(0, 1), (1, 5), (1, 7), (4, 5), (4, 8), (1, 6), (3, 7), (5, 9), (2, 4), (0, 4), (2, 5), (3, 6), (8, 9)]
final_path = []
print search_and_merge(graph, final_path)