pythongraphdepth-first-searchbrute-forcefunction-calls

how can i print out the generator object without using the shell?


Came across this example online, its a dfs function which finds all the cycles within a graph.

I'm trying to add the cycle part into the function so i don't have to use the shell to get the results. I'm new to generator objects so I'm not sure how to display cycles.

version which uses the shell:

def dfs(graph, start, end):
    fringe = [(start, [])]
    while fringe:
        state, path = fringe.pop()
        if path and state == end:
            yield path
            continue
    for next_state in graph[state]:
        if next_state in path:
            continue
        fringe.append((next_state, path+[next_state]))

>>> graph = { 1: [2, 3, 5], 2: [1], 3: [1], 4: [2], 5: [2] }
>>> cycles = [[node]+path  for node in graph for path in dfs(graph, node, node)]
>>> len(cycles)
7
>>> cycles
[[1, 5, 2, 1], [1, 3, 1], [1, 2, 1], [2, 1, 5, 2], [2, 1, 2], [3, 1, 3], [5, 2, 1, 5]]

Here is my attempt:

def dfs(g, start, end):
    fringe = [(start, [])]
    while fringe:
        state, path = fringe.pop()
        if path and state == end:
            yield path
            continue
    for next_state in g[state]:
        if next_state in path:
            continue
        fringe.append((next_state, path+[next_state]))
    cycles = (list([node]+path for node in g for path in dfs(g, node, node)))
    print("cycles",cycles)
return path

dfs(graph, 1, 1)

tried several different start and end nodes all the same result.

my graph is the same as above,

 graph = { 1: [2, 3, 5], 2: [1], 3: [1], 4: [2], 5: [2] }

output = generator object dfs at 0x000001D9CB846EB8

Any ideas?


Solution

  • Is this what you are looking for?

    def dfs(g, start, end):
        fringe = [(start, [])]
        while fringe:
            state, path = fringe.pop()
            if path and state == end:
    
                yield path
                continue
            for next_state in g[state]:
                if next_state in path:
                    continue
                fringe.append((next_state, path+[next_state]))
    
    
    graph = {1: [2, 3, 5], 2: [1], 3: [1], 4: [2], 5: [2]}
    cycles = [[node]+path for node in graph for path in dfs(graph, node, node)]
    print(cycles)
    

    you dont need a return in a generator so you can just loop through it using a list comprehension or a regular loop.