cs215 ยป

CS215Lesson6

CS215Lesson6 is ...

Code for Lecture 9:

def long_and_simple_path(G,u,v,l):
"""
G: Graph
u: starting node
v: ending node
l: minimum length of path
"""
if not long_and_simple_decision(G,u,v,l):
    return False
for node1 in G:
    neighbors = G[node1].keys()
    for node2 in neighbors:
        G = break_link(G, node1, node2)
        if not long_and_simple_decision(G,u,v,l):
            #need to keep that edge
            G = make_link(G, node1, node2)
path = [u]
node = u
next = (G[node].keys())[0]
while (next != v):
    path.append(next)
    nextnext0 = (G[next].keys())[0]
    nextnext1 = (G[next].keys())[1]
    if nextnext0 == node: (node, next) = (nextnext0, nextnext1)
    else: (node, next) = (next, nextnext0)
return path +[v]