def calc_euler_tour(g, start, end):
    '''Calculates an Euler tour over the graph g from vertex start to vertex end.
    Assumes start and end are odd-degree vertices and that there are no other odd-degree
    vertices.'''
    even_g = nx.subgraph(g, g.nodes())
    if end in even_g.neighbors(start):
        # If start and end are neighbors, remove the edge
        even_g.remove_edge(start, end)
        comps = list(nx.connected_components(even_g))
        # If the graph did not split, just find the euler circuit
        if len(comps) == 1:
            trail = list(nx.eulerian_circuit(even_g, start))
            trail.append((start, end))
        elif len(comps) == 2:
            subg1 = nx.subgraph(even_g, comps[0])
            subg2 = nx.subgraph(even_g, comps[1])
            start_subg, end_subg = (subg1, subg2) if start in subg1.nodes() else (subg2, subg1)
            trail = list(nx.eulerian_circuit(start_subg, start)) + [(start, end)] + list(nx.eulerian_circuit(end_subg, end))
        else:
            raise Exception('Unknown edge case with connected components of size {0}:\n{1}'.format(len(comps), comps))
    else:
        # If they are not neighbors, we add an imaginary edge and calculate the euler circuit
        even_g.add_edge(start, end)
        circ = list(nx.eulerian_circuit(even_g, start))
        try:
            trail_start = circ.index((start, end))
        except:
            trail_start = circ.index((end, start))
        trail = circ[trail_start+1:] + circ[:trail_start]
    return trail

    def test_eulerian_circuit_cycle(self):
        G=nx.cycle_graph(4)

        edges=list(eulerian_circuit(G,source=0))
        nodes=[u for u,v in edges]
        assert_equal(nodes,[0,1,2,3])
        assert_equal(edges,[(0,1),(1,2),(2,3),(3,0)])

        edges=list(eulerian_circuit(G,source=1))
        nodes=[u for u,v in edges]
        assert_equal(nodes,[1,0,3,2])
        assert_equal(edges,[(1,0),(0,3),(3,2),(2,1)])

def tsp_mstheuristic( graph, depot ) :
    # the simple MST heurisitc, should exhibit the right rate of growth at least
    mst = nx.minimum_spanning_tree( graph, weight='weight' )
    gg = nx.MultiGraph()
    gg.add_edges_from( mst.edges_iter() )
    gg.add_edges_from( mst.edges_iter() )
    circuit = nx.eulerian_circuit( gg, depot )
    tour = []
    for i,j in nx.eulerian_circuit( gg, depot ) :
        if i not in tour :
            tour.append( i )
    tour.append( depot )
    return tour

    def test_eulerian_circuit_digraph(self):
        G=nx.DiGraph()
        nx.add_cycle(G, [0, 1, 2, 3])

        edges=list(eulerian_circuit(G,source=0))
        nodes=[u for u,v in edges]
        assert_equal(nodes,[0,1,2,3])
        assert_equal(edges,[(0,1),(1,2),(2,3),(3,0)])

        edges=list(eulerian_circuit(G,source=1))
        nodes=[u for u,v in edges]
        assert_equal(nodes,[1,2,3,0])
        assert_equal(edges,[(1,2),(2,3),(3,0),(0,1)])

def eulerian_path(g, algorithm="Fleury"):
    """Return a Eulerian path for the semi-eulerian graph ``g``.

    Parameters
    ----------
    g : nx.DiGraph, nx.MultiDiGraph
        The input graph. The graph must be semi-Eulerian.
    algorithm : {'Fleury', 'Hierholzer'}, optional
        Which algorithm to use to find the path. Hierholzer is faster
        but has the distinct disadvantage that I haven't implemented
        it yet. =P

    Returns
    -------
    edges_iter : iterator of edges
        An Eulerian path of ``g``.

    Notes
    -----
    An Eulerian path is one that visits every edge in a graph exactly
    once.
    """
    source, sink = _source_and_sink(g)
    g.add_edge(sink, source)
    edges_iter = nx.eulerian_circuit(g, source=source)
    return edges_iter

def plot_puzzle_graph(G, pos, diff_degree=2., amp=1., scale=1.5, steps=100, **params):
    """ Turn graph into puzzle, by making a line for each edge
    
    if the edge has an attribute for 'invisible_line' set to True skip
    it and if the edge has an attrible for 'straight_line' set to
    True, don't make a nub
    """
    # add matching on odd degree nodes (with 'blank' as a hacky vtx in
    # the middle to make sure the degree really increases
    odd_nodes = [v for v in G if len(G[v])%2 == 1]
    for u,v in zip(odd_nodes[::2], odd_nodes[1::2]):
        midpt = 'mid_%s_%s' % (u,v)
        G.add_edge(u, midpt, invisible_line=True)
        G.add_edge(midpt, v, invisible_line=True)

    for u, v in nx.eulerian_circuit(G):
        if G[u][v].get('invisible_line'):
            continue

        if G[u][v].get('straight_line'):
            plot_line(pos[u], pos[v], **params)
        else:
            if random.random() > .5:
                plot_nub(pos[u], pos[v], diff_degree, amp, scale, steps, **params)
            else:
                plot_nub(pos[v], pos[u], diff_degree, amp, scale, steps, **params)

 def POSTPROCESS(cls, digraph_eul, A ) :
     """
     This implementation is different than what is specified in FHK.
     It simply returns an ordering of arcs in A.
     The process of moving from arc to arc by shortest paths should be straightforward.
     (Nevertheless, the steps of FHK are written below in comments.)
     """
     # Step 1: Given a set of arcs and edges with associated direction,
     # from which a tour can be constructed, find the tour.
     
     # Step 2: For any series of two or more consecutive edges in the tour,
     # replace them with one edge, thus eliminating intermediate vertices. (???)
     
     # Step 3: For any two vertices vi and vj anchoring an edge in the tour,
     # insert any vertices that would create a shorter path between vi and vj.
     # (Undo Step 2 of PREPROCESS.)
     
     # Step 4: List the tour beginning at vs, the initial vertex, and finishing at vf,
     # the terminal vertex.
     
     # Alternative Method:
     arcs = {}
     for arc in A.edges( keys=True ) :
         arcs.setdefault( arc[:2], [] ).append( arc )
         
     new_walk = []
     for edge in nx.eulerian_circuit( digraph_eul ) :
         if edge in arcs :
             longver = arcs[edge]
             new_walk.append( longver.pop(0) )
             if len( longver ) <= 0 : del arcs[edge]
     return new_walk

def generatePath(G):
    even_v = []
    MST = nx.minimum_spanning_tree(G)
    for v in MST.nodes():
        if len(MST.neighbors(v)) % 2 == 0:
            even_v.append(v)
    O = G.copy()
    for v in even_v:
        O.remove_node(v)
    matching = []
    while len(O.edges()) > 1:
        minEdge = findMinEdge(O)
        O.remove_node(minEdge[0])
        O.remove_node(minEdge[1])
        matching.append(minEdge)
    MST = nx.MultiGraph(MST)
    MST.add_weighted_edges_from(matching)
    eulerTour = list(nx.eulerian_circuit(MST))
    MST = nx.Graph(MST)
    maxEdge = findMaxEdge(MST)
    rudrataPath = findEulerPath(maxEdge, eulerTour) #eulerPath
    swap = nx.Graph()
    swap.add_nodes_from(MST.nodes(data=True))
    swap.add_weighted_edges_from([(u, v, G[u][v]['weight']) for (u, v) in rudrataPath])
    if len(swap.nodes()) > 4:
        swap = double_edge_swap(G, swap, nswap=2000, max_tries=10000)
    path = edgesToPath(swap.edges())
    problems = pathCheck(G, path)
    if problems > 0:
        path = CHEAT(G)
    TSP = ''
    for v in path:
        TSP += str(v) + ' '
    return TSP[:-1] # gets rid of final space

    def twice_around(self, source=None):
        if source is None:
            source = np.random.choice(self.graph.nodes())

        T = self.extract_mst(TSP.MST.PRIM)
        T = nx.MultiGraph(T)

        T.add_edges_from(T.edges(data=True))
        
        eulerian_circuit = nx.eulerian_circuit(T, source)

        visited = []
        hamiltonian_path = []

        for u,v in eulerian_circuit:
            if u not in visited:
                visited.append(u)
                hamiltonian_path.append(u)

        hamiltonian_path.append(hamiltonian_path[0])

        hamiltonian_graph = nx.create_empty_copy(self.graph)

        for i in range(len(hamiltonian_path)-1):
            edge = (hamiltonian_path[i], hamiltonian_path[i+1])
            hamiltonian_graph.add_edge(*edge, self.graph.get_edge_data(*edge))
            
        return (hamiltonian_graph, hamiltonian_path)

def christofides(graph_x, subset_graph):  
    t0 = time.clock() 
    subset_n = neighbours(subset_graph)
    graph_comp = makecomplete(subset_n, graph_x)
    newEdges = missing_edges(subset_n)
    simp = simplify_complete(graph_comp,newEdges)
 
    perfect_matching = call_blossom(subset_n,simp)
    subset_plus_comp = subset_n.copy()
    allGraph = nx.MultiGraph(subset_plus_comp)
    for edge in perfect_matching:
        allGraph.add_weighted_edges_from([(edge[0],edge[1],
            graph_comp[edge[0]][edge[1]]['weight'])])
	
    mst_edges = match_components(subset_n,simp,graph_x)
    final = allGraph.copy()
    for edge in mst_edges:
	final.add_weighted_edges_from([(edge[0],edge[1],
            graph_comp[edge[0]][edge[1]]['weight'])])
	final.add_weighted_edges_from([(edge[0],edge[1],
            graph_comp[edge[0]][edge[1]]['weight'])])

    tour = list(nx.eulerian_circuit(final))
    t1 = time.clock()
    results = list()
    results.append(tour_cost(tour, graph_comp))
    runtime = t1 - t0
    results.append(runtime)
    results.append(tour_cost(tour, graph_comp))
    results.append(runtime)
    results.append(check_solution(tour,graph_x,subset_graph))
    print(tour)
    print(results)
    return results

def eulerian_circuit(graph):
    circuit = list(nx.eulerian_circuit(graph))
    nodes = []
    for u, v in circuit:
        nodes.append(u)
    # Close the loop
    nodes.append(circuit[0][0])
    return nodes

def ROUTEINSPECTION( graph, weight_attr='length' ) :
    """
    input graph should be a roadmap, i.e., a weighted multi-digraph;
    however, the algorithm assumes no one-way roads
    """
    workgraph = nx.MultiGraph()
    
    # add an original copy of every edge to the workgraph
    for u, v, key in graph.edges_iter( keys=True ) :
        workgraph.add_edge( u, v, (ORIGINAL,key) )
        
    # if non-Eulerian, add joining paths between odd-degree vertices
    T = ODDNODES( graph )
    # metric graph
    met = nx.Graph()
    for s in T :
        for t in T :
            if t == s : continue
            path = nx.shortest_path( graph, s, t, weight=weight_attr )
            pathlen = PATHLEN( path, graph, weight_attr )
            # use weight attribute for matching, want min cost!
            met.add_edge( s, t, weight=-pathlen, path=path )
    match = nx.max_weight_matching( met, maxcardinality=True )
    
    extras = itertools.count()
    while len( match ) > 0 :
        s, t = match.iteritems().next()
        del match[s]
        del match[t]    # have to kill both ends
        
        path = met.get_edge_data(s,t).get('path')
        for u,v in zip( path[:-1], path[1:] ) :
            #edgekey = SHORTESTEDGE(u,v, graph, weight_attr )
            #idx = len( extras )
            #extras.append(edgekey)
            idx = extras.next()
            workgraph.add_edge(u,v, (EXTRA,idx) )
            
    #return workgraph

    # traverse
    walk = []
    
    for u, v in nx.eulerian_circuit( workgraph ) :
        edge_data = workgraph.get_edge_data(u,v)
        which, key = datakey = edge_data.iterkeys().next()
        workgraph.remove_edge(u,v, datakey )
        
        if which == ORIGINAL :
            edge_key = key
        elif which == EXTRA :
            edge_key = SHORTESTEDGE(u,v, graph, weight_attr )
        
        if not len( walk ) > 0 :
            walk.append(u)
        walk.extend([edge_key,v])
        
    return walk

 def test_eulerian_circuit_multigraph(self):
     G=nx.MultiGraph()
     nx.add_cycle(G, [0, 1, 2, 3])
     G.add_edge(1,2)
     G.add_edge(1,2)
     edges=list(eulerian_circuit(G,source=0))
     nodes=[u for u,v in edges]
     assert_equal(nodes,[0,3,2,1,2,1])
     assert_equal(edges,[(0,3),(3,2),(2,1),(1,2),(2,1),(1,0)])

def euler_path(graph: nx.DiGraph, func=genome_path_string) -> list:
    edge = balance_graph(graph)
    if not nx.is_eulerian(graph):
        raise ValueError("Not Eulerian: {0}".format(graph))

    circuit = list(nx.eulerian_circuit(graph, edge[1]))
    #print("asdf {0}".format(circuit))
    #return [ func(x) for x in circuit ]
    return [x[0] for x in circuit] + [ circuit[0][0] ]

 def test_multigraph_with_keys(self):
     G = nx.MultiGraph()
     nx.add_cycle(G, [0, 1, 2, 3])
     G.add_edge(1, 2)
     G.add_edge(1, 2)
     edges = list(eulerian_circuit(G, source=0, keys=True))
     nodes = [u for u, v, k in edges]
     assert_equal(nodes, [0, 3, 2, 1, 2, 1])
     assert_equal(edges[:2], [(0, 3, 0), (3, 2, 0)])
     assert_count_equal(edges[2:5], [(2, 1, 0), (1, 2, 1), (2, 1, 2)])
     assert_equal(edges[5:], [(1, 0, 0)])

def eulerian_circuit_verbose( multidigraph, source=None ) :
    registry = dict()
    for u,v,key in multidigraph.edges_iter( keys=True ) :
        pair = u,v
        id = u,v,key
        if not pair in registry : registry[pair] = []
        registry[ pair ].append( id )
        
    for pair in nx.eulerian_circuit( multidigraph, source ) :
        options = registry[ pair ]
        yield options.pop(0)

def christofides(graph_x, subset_graph):
    t0 = time.clock()
    # ******* PHASE 1 ********
    # Make graph_x complete with shortest path between nodes for missing edges
    graph_comp = make_complete(subset_graph, graph_x)
    new_edges = missing_edges(subset_graph)
    simplified = simplify_complete(graph_comp,new_edges)

    # ******* PHASE 2 *******
    matching_edges = match_components(subset_graph, simplified, graph_x)
    # Add component matching edges to Gr
    subset_plus_comp = subset_graph.copy()
    for edge in matching_edges:
        subset_plus_comp.add_weighted_edges_from([(edge[0],edge[1],
            simplified[edge[0]][edge[1]]['weight'])])

    perfect_matching = call_blossom(subset_plus_comp,graph_x)
    final = nx.MultiGraph(subset_plus_comp)


    for edge in perfect_matching:

        # If edge exists in original graph:
        if graph_x.has_edge(*edge):
            final.add_weighted_edges_from([(edge[0],edge[1], 
                graph_x[edge[0]][edge[1]]['weight'])])
        # Else get shortest path between them and replace
        else:
            final.add_weighted_edges_from(shortest_path_edges(edge[0],edge[1],graph_x))

    if nx.is_eulerian(final):
        tour = list(nx.eulerian_circuit(final))
        t1 = time.clock()
        results = list()
        results.append(tour_cost(tour, graph_comp))
        runtime = t1 - t0
        results.append(runtime)
        results.append(tour_cost(tour, graph_comp))
        results.append(runtime)
        results.append(check_solution(tour,graph_x,subset_graph))
        print(tour)
        print(results)
    else:
	results = list()
	t1 = time.clock()
        results.append(0)
        runtime = t1 - t0
        results.append(runtime)
        results.append(0)
        results.append(runtime)
        results.append(False)
    return results

def eulerian_circuit(graph):
    """
    Given an Eulerian graph, find one eulerian circuit. Returns the circuit as a list of nodes, with the first and
    last node being the same.
    """

    circuit = list(nx.eulerian_circuit(graph))
    nodes = []
    for u, v in circuit:
        nodes.append(u)
    # Close the loop
    nodes.append(circuit[0][0])
    return nodes

def DOUBLETOUR( roadnet ) :
    eulerian = nx.MultiDiGraph()
    for u,v, road in roadnet.edges_iter( keys=True ) :
        eulerian.add_edge( u,v, label=traversal( road, True ) )
        eulerian.add_edge( v,u, label=traversal( road, False ) )
        
    tour = []
    walk = [ u for u in nx.eulerian_circuit( eulerian ) ]
    for u, v in walk :
        edges = eulerian.edge[u][v]
        key = edges.keys()[0]       # get key of the some (e.g., first) edge from u, v
        data = eulerian.get_edge_data( u, v, key )
        tour.append( data.get('label') )
        eulerian.remove_edge( u, v, key )
        
    return tour

def twice_around(G):
    mst = mst_prim(G)
    di_mst = mst.to_directed()
    euler = nx.eulerian_circuit(di_mst,random.randint(0, len(G.nodes())-1)) # o problema está aqui
    edges = list(euler)

    weight = 0
    for i in edges:
        weight += G.edge[i[0]][i[1]]['weight']

    path = []
    for i in list(edges):
        if i[0] not in path:
            path.append(i[0])
        if i[1] not in path:
            path.append(i[1])
    return weight, path