How to break out a function without return or break in Python

Question

I'm dfs traversing between nodes a and b, however when I break the loop at node b the algorithm continues. Here is my code:

import networkx as nx

def Graph():
    G=nx.Graph()

    k = 30

    G.add_edge(1,2)
    G.add_edge(2,3)
    G.add_edge(1,3)

    for i in range(2,k+1):
        G.add_edge(2*i-2,2*i)
        G.add_edge(2*i-1,2*i)
        G.add_edge(2*i-1,2*i+1)
        G.add_edge(2*i,2*i+1)

    G.add_nodes_from(G.nodes(), color='never coloured')
    G.add_nodes_from(G.nodes(), label = -1)
    G.add_nodes_from(G.nodes(), visited = 'no')

    return G

def dfs(G,a,b,u):
    global i
    G.node[u]['visited'] = 'yes'
    i += 1
    G.node[u]['label'] = i
    print(u)
    print("i", i)
    for v in G.neighbors(u):
        if v == b:
            G.node[v]['visited'] = 'yes'
            i += 1
            G.node[v]['label'] = i
            print("b is ", v)
            print("distance from a to b is ", G.node[v]['label'])
            break### the problem area, doesn't break out the function
        elif v != b:
            if G.node[v]['visited'] == 'no':
                dfs(G,a,b,v)
G=Graph()
a=1
b=19
i = 0
print('Depth-First-Search visited the following nodes of G in this order:')
dfs(G,a,b,a)  ### count the DFS-path from a to b, starting at a
print('Depth-First Search found in G7 a path between vertices', a, 'and', b, 'of length:', G7.node[b]['label'])
print()

I have tried returning out of the for loop, tried using break and also tried try/catch methods. Is there any elegant way to break out this function or will I have to rewrite it as it doesn't recurse through all neighbors of u?

Answer 1

The problem here is not break or return, but that you use recursion and you don't stop the loop in each recursive call. What you need to do is to return a result from your dfs function that tells whether you found your node or not, and then break the loop inside your else block if the recursive call did find it. Something like this:

def dfs(G,a,b,u):
    global i
    G.node[u]['visited'] = 'yes'
    i += 1
    G.node[u]['label'] = i
    print(u)
    print("i", i)
    for v in G.neighbors(u):
        if v == b:
            G.node[v]['visited'] = 'yes'
            i += 1
            G.node[v]['label'] = i
            print("b is ", v)
            print("distance from a to b is ", G.node[v]['label'])
            return True
        elif v != b:
            if G.node[v]['visited'] == 'no':
                found = dfs(G,a,b,v)
                if found:
                    return True
    return False

Note how this propagates the successful result back up through your entire call stack.

Answer 2

As used break breaks for loop.To break the function use return.