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