__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
__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.
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]
"""
if len(cycle_one) == 0:
return cycle_two
if len(cycle_two) == 0:
return cycle_one
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])
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.
Example:
> search_and_merge([(1, 2), (3, 2), (1, 3)], [])
> [1, 2, 3, 1]
"""
cycle = []
s_node = find_starting_node(graph)
(cycle, graph) = find_cycle(s_node, graph, cycle)
final_path = merge_cycles(final_path, cycle)
if len(graph) == 0:
return final_path
else:
return search_and_merge(graph, final_path)