Amazing-Python-Scripts

1
'''
2
------------------------------------- Fleury's Algorithm -------------------------------------
3

4
Approach:-
5
1. Start with any vertex in the graph.
6

7
2. While there are unused edges in the graph, do the following steps:
8
    a. Choose any unused edge connected to the current vertex. It doesn't matter which one you choose.
9
    b. If removing the chosen edge doesn't disconnect the graph, go to the vertex at the other end of the chosen edge.
10
    c. If removing the chosen edge disconnects the graph, backtrack to the previous vertex that still has unused edges and choose a different edge.
11
    d. Repeat steps (a) to (c) until you can no longer choose any unused edges from the current vertex.
12

13
3. The algorithm terminates when you have traversed all the edges of the graph.
14

15
4. If all the vertices in the graph have even degrees, you will end up with an Eulerian circuit, which is a closed path that visits each edge exactly once.
16

17
5. If exactly two vertices in the graph have odd degrees, you will end up with an Eulerian path, which is a path that starts and ends at different vertices and visits each edge exactly once.
18
'''
19

20
# Program Starts
21
from collections import defaultdict
22

23

24
class Graph:
25

26
    def __init__(self, vertices):
27
        self.V = vertices  # No. of vertices
28
        self.graph = defaultdict(list)
29
        self.Time = 0
30

31
    # function to add an edge to graph
32
    def addEdge(self, source, destination):
33
        self.graph[source].append(destination)
34
        self.graph[destination].append(source)
35

36
    # This function removes edge source-destination from graph
37
    def removeEdge(self, source, destination):
38
        for index, key in enumerate(self.graph[source]):
39
            if key == destination:
40
                self.graph[source].pop(index)
41
        for index, key in enumerate(self.graph[destination]):
42
            if key == source:
43
                self.graph[destination].pop(index)
44

45
    # A DFS based function to count reachable vertices from destination
46
    def DFSCount(self, destination, visited):
47
        count = 1
48
        visited[destination] = True
49
        for i in self.graph[destination]:
50
            if visited[i] == False:
51
                count = count + self.DFSCount(i, visited)
52
        return count
53

54
    # The function to check if edge source-destination can be considered as next edge in Euler Trail
55
    def isValidNextEdge(self, source, destination):
56
        # The edge source-destination is valid in one of the following two cases:
57

58
        # 1) If destination is the only adjacent vertex of source
59
        if len(self.graph[source]) == 1:
60
            return True
61
        else:
62
            '''
63
            2) If there are multiple adjacents, then source-destination is not a bridge
64
                    Do following steps to check if source-destination is a bridge
65

66
            2.a) count of vertices reachable from source'''
67
            visited = [False]*(self.V)
68
            count1 = self.DFSCount(source, visited)
69

70
            '''2.b) Remove edge (source, destination) and after removing the edge, count
71
				vertices reachable from source'''
72
            self.removeEdge(source, destination)
73
            visited = [False]*(self.V)
74
            count2 = self.DFSCount(source, visited)
75

76
            # 2.c) Add the edge back to the graph
77
            self.addEdge(source, destination)
78

79
            # 2.d) If count1 is greater, then edge (source, destination) is a bridge
80
            return False if count1 > count2 else True
81

82
    # Print Euler Trail starting from vertex source
83

84
    def printEulerUtil(self, source):
85
        # Recur for all the vertices adjacent to this vertex
86
        for destination in self.graph[source]:
87
            # If edge source-destination is not removed and it's a a valid next edge
88
            if self.isValidNextEdge(source, destination):
89
                print("%d-%d " % (source, destination)),
90
                self.removeEdge(source, destination)
91
                self.printEulerUtil(destination)
92

93
    '''The main function that print Eulerian Trail. It first finds an odd
94
degree vertex (if there is any) and then calls printEulerUtil()
95
to print the path '''
96

97
    def printEulerTrail(self):
98
        # Find a vertex with odd degree
99
        source = 0
100
        for i in range(self.V):
101
            if len(self.graph[i]) % 2 != 0:
102
                source = i
103
                break
104
        # Print Trail starting from odd vertex
105
        print("\n")
106
        self.printEulerUtil(source)
107

108

109
# Driver program
110
V = int(input("\nEnter the number of vertices in the graph: "))
111

112
g = Graph(V)
113

114
E = int(input("\nEnter the number of edges in the graph: "))
115

116
# Taking input from the user
117
print("\nEnter the edges in the format (source destination)")
118
for i in range(E):
119
    source = int(input(f"Source {i+1}: "))
120
    destination = int(input(f"Destination {i+1}: "))
121
    g.addEdge(source, destination)
122

123
# Printing the final result after analysing
124
print("\nResult of Fleury Algorithm: ", end="")
125
g.printEulerTrail()
126
print()
127