christofides.py 文件源码

def Euler_Tour(multigraph):
    """ Uses Fleury's algorithm to find the Euler Tour of the MultiGraph.

    """
    tour = []
    temp_graph = nx.MultiGraph()
    graph_nodes = nx.nodes(multigraph)
    current_node = graph_nodes[0]
    tour.append(current_node)
    while nx.number_of_edges(multigraph) > 0:   
        for edge in multigraph.edges(current_node):
            temp_graph = copy.deepcopy(multigraph)
            temp_graph.remove_edge(edge[0], edge[1], key=None)
            if nx.is_connected(temp_graph):
                tour.append(edge[1])
                current_node = edge[1]
                multigraph.remove_edge(edge[0], edge[1], key=None)
                break
        else:
            tour.append(edge[1])
            current_node = edge[1]
            multigraph.remove_edge(edge[0], edge[1], key=None)
            multigraph.remove_nodes_from(nx.isolates(multigraph))
    return tour