# __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) ```