import networkx as nx
import random


def trace(a, b, G):
    done = []
    next = a
    while True:
        n = list(G.neighbors(a))
        k = 0
        l = None
        for i in n:
            if i in done:
                k += 1
                continue
            elif i == b:
                return False
            else:
                done.append(i)
                l = i
        if k == len(n):
            return True
        next = i
def find(G, v):
    E = init(v)
    while len(E) < len(G.edges()):
        f = []
        for e in G.edges(v):
            if trace(v, e, G):
                continue
            f.append(e) # Nicht brücke
        if len(f) == 0: # Nur brücken
            f = list(G.edges(v))
        e_ = random.choice(f)   # Wähle eine Kante aus
        while e_ in E or e_[1] == E[len(E) - 1][0]:
            f.remove(e_)
            if len(f) == 0:
                raise ValueError("Kein Eulerkreis!")
            e_ = random.choice(f)
        E.append(e_)
        v = e_[1]
    if E[0][0] != E[len(E) - 1][1]:
        raise ValueError("Kein Eulerkreis!")
    return E

def init(v):
    E = []
    f = []
    for e in G.edges(v):
        if trace(v, e, G):
            continue
        f.append(e) # Nicht brücke
    if len(f) == 0: # Nur brücken
        f = list(G.edges(v))
    e_ = list(random.choice(f))
    e_[0], e_[1] = e_[1], e_[0]
    E.append((*e_,))
    return E

G = nx.MultiGraph()
G.add_nodes_from([*"ABCD"])
G.add_edges_from([("A", "C"), ("C", "B"), ("B", "D"), ("D", "A")])
print(find(G, random.choice(list(G.nodes()))))