Graph possible paths python

Question

Graph possible paths python

Navigation

#1 by (2 votes)
#2 by (0 votes)

4

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 an array of all possible paths (from one vertex to another, for example from 'A' to 'D').

I've tried so much, I do not know what to try anymore. I thought of going through each list of adjacent vertices, starting with the 'A' key (because of the example) and then for each adjacent vertex going through its list of adjacent vertices. I tried to do this, 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

python lista grafo

asked by anonymous 05.06.2015 / 01:57

2 answers

SQL Server - Doubt update and relationship between tables Problem loading image in HTML (Performance)

score 2 · Answer 1

The problem with your solution is that the percorrer function does not have access to lista , which is where you store information about which vertices you have already visited. You have to pass this information somehow to the function that will do the recursion. I added 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 in operator of 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 vertex current one I've been through.

The other thing I do is use yield in my function - it's 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 for . The yield , unlike return , does not interrupt the execution of the function: it returns the value for for , lets for do its service, and then returns to execute the function where it stopped .

The idea of the recursive call to gerar_caminhos(grafo, caminho + [vizinho], final) is that it is allowed to go to vizinho from caminho[-1] (the last element of caminho ); I look for all the paths that do this, I return them to the parent function (i.e. the function that called me), and I repeat this for all the neighbors that are no longer in the path (thus avoiding repetition).

score 0 · 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']]

First shortest path:

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

You could also use Breadth-first search .