graphe-sim.py

# Par exemple pour Fool et Sage vous devez renvoyez le résultat suivant :
# 
# FOOL
# POOL
# POLL
# POLE
# PALE
# SALE
# SAGE
# 
# SOLUTION:

graph = {'A': ['B', 'C'],
  'B': ['C', 'D'],
  'C': ['D'],
  'D': ['C'],
  'E': ['F'],
  'F': ['C']
}

class Graphe(dict):
    def __init__(self, liens, noeuds):
        for v in liens:
            self[v] = set()
        for e in noeuds:
            self.ajout_noeud(e)

    def ajout_lien(self, lien):
        self[lien[0]].add(lien[1])
        self[lien[1]].add(lien[0])

    def ajout_noeud(self, noeud):
        self[noeud] = set()

def simGraphe(mots):
    d = {}
    g = Graphe(mots, [])

    for mot in mots:
        for i in range(len(mot)):
            groupe = mot[:i] + '_' + mot[i+1:]
            if groupe in d:
                d[groupe].append(mot)
            else:
                d[groupe] = [mot]

    for groupe in d.keys():
        for mot1 in d[groupe]:
            for mot2 in d[groupe]:
                if mot1 != mot2:
                    g.ajout_lien([mot1, mot2])
    return g

def chemin(graphe, source, destination, visite=None):

    if source == destination:
        return [destination]
    else:
        visite = visite or set()
        for s in graphe[source]:
                if s not in visite:
                    visite.add(s)
                    print("trace:", source + " > " + s)
                    sous_chemin = chemin(graphe, s, destination, visite)
                    if sous_chemin is not None:
                        return [source] + sous_chemin

print(chemin(simGraphe(["AA", "AB", "BC", "AC", "DD"]), "AA", "BC"))

# ['AA', 'AB', 'AC', 'BC']