Finding an Euler cycle using the backtracking algorithm

The backtracking algorithm is, although expensive, a fairly universal method. It is connected with enumerating the vertices of the graph. The question arises: can edges be interpreted as vertices? This idea is being implemented.

The code allows you to find, taking into account the starting vertex, an Euler cycle or at least its route (semi-Eulerian). In fact, in this interpretation, a vertex is taken to be the set of two neighboring vertices. Implemented in dict_to_setEdge. As for dfs, this is a standard implementation of depth-first traversal with backtracking.

# не Эйлер
G1 = {
    1: [2, 3, 5],
    2: [1, 4, 5],
    3: [1, 4, 5],
    4: [2, 3, 5],
    5: [1, 2, 3, 4]
}

# полу-Эйлер
G2 = {
    1: [2, 3, 5],
    2: [1, 4, 5, 6],
    3: [1, 4, 5],
    4: [2, 3, 5, 6],
    5: [1, 2, 3, 4],
    6: [2, 4]
}

# Эйлер
G3 = {
    1: [2, 3, 5, 7],
    2: [1, 4, 5, 6],
    3: [1, 4, 5, 7],
    4: [2, 3, 5, 6],
    5: [1, 2, 3, 4],
    6: [2, 4],
    7: [1, 3]
}

def dfs(g, v, path):
    #print("path =", path)
    if len(path)-1 == len(edgeSet): 
        return path
    for w in g[v]:
        if not {v, w} in path: 
            path.append({v, w})
            newpath = dfs(g, w, path) 
            if newpath: 
                return newpath 
    path.pop()
   
def dict_to_setEdge(G):
    s = []
    for v in G:
        for z in G[v]:
            if not {v, z} in s:
                s.append({v, z})
    return s

   
v = [1, 2]

for i,g in enumerate([G1, G2, G3]):
    edgeSet = dict_to_setEdge(g)
    print("==== граф ===", i+1)
    for s in v:
        print(" для вершины =", s)
        p = dfs(g, s, [{s, None}])
        if not p:
            print("Эйлер и полу-Эйлер не найдены")
        elif len({s, None}.intersection(p[-1])):
            print("Эйлер найден", p[1:])
        else: print("Полу-Эйлер найден", p[1:])
        print()

Now we modify the data format so that it is possible to process multi-graphs. To do this, first, we'll add named edges. Secondly, to two adjacent vertices (3,7) we add one more edge (for G5) or two more edges (for G4). Accordingly, G4 will remain an Euler graph.

# Эйлер
G4 = {
    1: [(2,1), (3,1), (5,1), (7,1)],
    2: [(1,1), (4,1), (5,1), (6,1)],
    3: [(1,1), (4,1), (5,1), (7,1), (7,2), (7,3)],
    4: [(2,1), (3,1), (5,1), (6,1)],
    5: [(1,1), (2,1), (3,1), (4,1)],
    6: [(2,1), (4,1)],
    7: [(1,1), (3,1), (3,2), (3,3)]
}

# не Эйлер
G5 = {
    1: [(2,1), (3,1), (5,1), (7,1)],
    2: [(1,1), (4,1), (5,1), (6,1)],
    3: [(1,1), (4,1), (5,1), (7,1), (7,2)],
    4: [(2,1), (3,1), (5,1), (6,1)],
    5: [(1,1), (2,1), (3,1), (4,1)],
    6: [(2,1), (4,1)],
    7: [(1,1), (3,1), (3,2)]
}

def dfs(g, v, path):
    #print("path =", path)
    if len(path)-1 == len(edgeSet):
        return path
    
    for w in g[v]:
        if not ({v, w[0]}, w[1]) in path: 
            path.append(({v, w[0]}, w[1]))
            newpath = dfs(g, w[0], path) 
            if newpath: 
                return newpath 
    path.pop()
   
def dict_to_setEdge(G):
    s = []
    for v in G:
        for z in G[v]:
            if not ({v, z[0]}, z[1]) in s:
                s.append(({v, z[0]}, z[1]))
    return s

    
v = [1, 2]

for i,g in enumerate([G4, G5]):
    edgeSet = dict_to_setEdge(g)
    #print(edgeSet); input()
    print("\n==== граф ===", i+1)
    for s in v:
        print("для вершины =", s)
        p = dfs(g, s, [{s, None}])
        if not p:
            print("Эйлер и полу-Эйлер не найден")
        elif len({s, None}.intersection(p[-1][0])):
            print("Эйлер найден", p[1:])
        else: print("Полу-Эйлер найден", p[1:])
        print()