cp_truc_tiep = {
    'a': {'c': 0.2, 'b': 0.1},
    'b': {'c': 0.3, 'd': 0.4},
    'c': {'e': 0.5},
    'd': {'e': 0.6},
}

'''
a -> c, b
b -> c, d
c -> e
d -> e 

a -> e ?

'''

# lay het cac cty trong list
list_cty = set(cp_truc_tiep.keys())
for cty, l in cp_truc_tiep.items():
    list_cty = list_cty.union(set(l.keys()))

cp_all = { }

def sum_so_huu(link_cty):
    result = 1
    for i in range(len(link_cty) - 1):
        from_cty = link_cty[i]
        to_cty = link_cty[i + 1]
        result *= cp_truc_tiep[from_cty][to_cty]
    return result


def tinh_cp(current_cty, init_cty, end_cty, link_cty):
    if current_cty == end_cty:
        sum_link = sum_so_huu(link_cty)
        # print(link_cty)
        # print('So huu = {}'.format(sum_link))
        if init_cty not in cp_all:
            cp_all[init_cty] = {}
        if end_cty not in cp_all[init_cty]:
            cp_all[init_cty][end_cty] = 0
        cp_all[init_cty][end_cty] += sum_link
        return
    if current_cty not in cp_truc_tiep:
        return
    for cty in cp_truc_tiep[current_cty]:
        tinh_cp(cty, init_cty, end_cty, link_cty + [cty])


def list_cp(cty):
    cty1 = cty
    for cty2 in list_cty:
        if cty1 != cty2:
            tinh_cp(cty1, cty1, cty2, [cty1])
            val = cp_all.get(cty1, {}).get(cty2, 0)
            if val != 0:
                print('{} so huu {}: {}'.format(cty1, cty2, val))


list_cp('a')