I need to cover all the edges of a graph with the minimum number of paths. I read that the Eulerian path method is needed here. I tried to reproduce it, but it doesn't work correctly.
def split_graph(graph, n):
stack = []
path = []
some_list = []
for i in range(n):
some_list .append(sum(graph[i]))
cur = 0
while (len(stack) > 0 or sum(graph[cur]) != 0):
if (sum(graph[cur]) == 0):
path.append(cur+1)
cur = stack[-1]
del stack[-1]
else:
for i in range(n):
if (graph[cur][i] == 1):
stack.append(cur)
graph[cur][i] = 0
graph[i][cur] = 0
cur = i
print(path)
if __name__ == '__main__':
graph = [[0, 1, 0, 1, 0, 0],
[1, 0, 1, 1, 0, 0],
[0, 1, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 1, 0]]
n = len(graph)
split_graph(graph, n)
Required output (There may be several options, this is one of them):
[6, 7, 4, 1, 2, 3]
[2,4]
[7, 5]
My output:
[3, 5, 6, 1, 4, 2]
How can this be fixed?
