Graph possible python paths

Question

I have a dictionary, where the key is a vertex and the value is a list of vertices adjacent to the vertex (key).

dic = {'A':['B,'C'],'B':['A','C','D'],'C':['A','B','D'],'D':['B','C']}

What I want is a matrix of all possible paths (from one vertex to another, for example from 'A' to’D').

I’ve tried so much, I don’t know what else to try. I thought to go through each list of adjacent vertices, starting with the 'A' key (because of the example) and then to each adjacent vertex go through its list of adjacent vertices. I tried to do that, but it gave me a mistake, so I realized I kept walking.

def percorrer(v,vAux,dic):
  for e in dic.get(v):
    while e!=vAux:
        percorrer(e,vAux,dic)

def todosCaminhos(g,v1,v2):
   dicVertices = g.getVertices()
   for v in dicVertices:
       if v != v1:
           if v1 in dicVertices.get(v):
               dicVertices.get(v).remove(v1)
    matriz=[]
    lista=[]
    for v in dicVertices.get(v1):
        while v != v2:
            percorrer(v,v2,dicVertices)
            lista.append(v)
        matriz.append(lista)
    return matriz

Answer 1

The problem with your solution is that the function percorrer does not have access to lista, which is where you store the information about which vertices you have visited. You have to pass on this information from some way for the function that will make the recursion. I joined the functions, put some comments and made a more idiomatic code:

# encoding: utf-8
# A linha anterior permite usar acentos no nosso programa.

def gerar_caminhos(grafo, caminho, final):
    """Enumera todos os caminhos no grafo `grafo` iniciados por `caminho` e que terminam no vértice `final`."""

    # Se o caminho de fato atingiu o vértice final, não há o que fazer.
    if caminho[-1] == final:
        yield caminho
        return

    # Procuramos todos os vértices para os quais podemos avançar…
    for vizinho in G[caminho[-1]]:
        # …mas não podemos visitar um vértice que já está no caminho.
        if vizinho in caminho:
            continue
        # Se você estiver usando python3, você pode substituir o for
        # pela linha "yield from gerar_caminhos(grafo, caminho + [vizinho], final)"
        for caminho_maior in gerar_caminhos(grafo, caminho + [vizinho], final):
            yield caminho_maior

# Exemplo de uso
G = {'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B', 'D'], 'D': ['B', 'C']}
for caminho in gerar_caminhos(G, ['A'], 'D'):
    # "print(caminho)" em python3
    print caminho

(Ideone)

To avoid repetition, I use the operator in from Python, which checks whether an object belongs to a list (or a set, or to the keys of a dictionary) - this means that I ignore the neighbors of the current vertex I’ve passed.

The other thing I do is use the yield in my role - it is easier to illustrate what it does with a simpler example:

def LOST():
    yield 4
    yield 8
    yield 15
    yield 16
    yield 23
    yield 42

for n in LOST():
    print n

The yield works as if it were a return, but thought to be used in a for. The yield, unlike the return, does not interrupt function execution: it returns the value for the for, let the for do his job, and then go back to performing the function from where he left off.

The idea of recursive call to gerar_caminhos(grafo, caminho + [vizinho], final) is that it is permitted to go to vizinho starting from caminho[-1] (the last element of caminho); I seek all the ways that do this, return them to the function-mother (i.e. the function that called me), and repeat this to all neighbors who are no longer in the way (thus avoiding repetition).

Answer 2

Use the search algorithm Depth Dirst Search:

dic = {'A':['B','C'],'B':['A','C','D'],'C':['A','B','D'],'D':['B','C']}

def dfs_caminhos(grafo, inicio, fim):
    pilha = [(inicio, [inicio])]
    while pilha:
        vertice, caminho = pilha.pop()
        for proximo in set(grafo[vertice]) - set(caminho):
            if proximo == fim:
                yield caminho + [proximo]
            else:
                pilha.append((proximo, caminho + [proximo]))

caminhos = list(dfs_caminhos(dic, 'A', 'D'))
print(caminhos)
>>> [['A', 'B', 'D'], ['A', 'B', 'C', 'D'], ['A', 'C', 'D'], ['A', 'C', 'B', 'D']]

Shortest first path:

min(caminhos, key = len)
>>> ['A', 'B', 'D']

You could also use Breadth-first search.