Look for non-loop path in a graph

graph.py

# Author  : Go Frendi Gunawan
# Purpose : Comparing Greedy & BruteForce Algorithm

'''
Graph Structures
'''
START, END  = 'A', 'E'
COORDINATE  = {
        'A' : [0,1],
        'B' : [2,0],
        'C' : [0,5],
        'D' : [4,1],
        'E' : [5,1]
    }
EDGE        = {
        'A' : ['B','C','D'],
        'B' : ['D','E','A'],
        'C' : ['B','A'],
        'D' : ['B','A'],
        'E' : ['B']
    }

'''
Function to calculate euclidean distance. 
If actual parameter set to be True (which is default), 
then it will return None if the path is not exits
'''
def distance(node_1, node_2, actual=True):
    if actual and node_1 in EDGE and node_2 not in EDGE[node_1]:
        return None
    x1, y1 = COORDINATE[node_1]
    x2, y2 = COORDINATE[node_2]
    return ( ((x1-x2)**2) + ((y1-y2)**2) ) ** 0.5

'''
Function to calculate path route length
'''
def path_distance(nodes):
    total = 0
    for i in range(len(nodes)-1):
        dist = distance(nodes[i],nodes[i+1])
        if dist == None:
            return None
        total += dist
    return total

'''
Function to get all path from start with no loop
(i.e: A-B-A-B-A-B-E has loop)
'''
def nonloop_path(previous_path = [START]):
    current_node  = previous_path[-1]
    new_path_list = []
    for next_node in EDGE[current_node]:
        new_path = previous_path[:]        
        if next_node not in new_path:
            new_path.append(next_node)
            new_path_list.append(new_path)
            next_new_path_list = nonloop_path(new_path)
            for next_new_path in next_new_path_list:
                new_path_list.append(next_new_path)            
    return new_path_list

'''
Function go get all path from start to end with no loop
'''
def valid_nonloop_path(previous_path = [START], end = END):
    return [x for x in nonloop_path(previous_path) if x[-1] == END]

'''
Brute Force
'''
def brute_force(start=START, end=END):
    path_list = valid_nonloop_path([start], end)
    if len(path_list)>0:
        # sort path list based on actual path distances
        path_list = sorted(path_list, key = lambda x: path_distance(x))
        # the first one is the best
        min_path  = path_list[0]
        min_distance = path_distance(min_path)
        return min_path, min_distance
    return None

'''
Function to calculate approximation.
g is the already passed path distance, h is heuristic distance
'''
def greed_value(path, end = END):
    g = path_distance(path)
    h = distance(path[-1], end, False)
    if g == None or h == None:
        return None
    return g + h

def greedy(start=START, end=END):
    path_list = valid_nonloop_path([start], end)
    margin = 2
    while len(path_list)>1:
        path_list = sorted(path_list, key = lambda x: greed_value(x[:margin]))
        min_val = greed_value(path_list[0][:margin])
        for path in path_list:
            if greed_value(path[:margin]) > min_val:
                path_list.remove(path)
        margin += 1
    if len(path_list)>0:
        min_path = path_list[0]
        return min_path, path_distance(min_path)
    return None        

print('Brute Force : ' + str(brute_force()) )
print('Greedy      : ' + str(greedy()) )