Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
DiJrId0u

algoritmo DFS sobre grafos

Recommended Posts

DiJrId0u

boas pessoal!

Estou com sérias duvidas em aplicar o algoritmo depth first search num grafo aciclico orientado, em python.

pretendo utilizar um outro algoritmo, o de ordenação topológica, sobre o grafo e necessito de implementar primeiro o DFS.

o algoritmo é dividido em dois, e tem as seguintes caracteristicas:

procedimento DFS(G: Grafo)

    Para Cada vértice v de G:

        Marque v como não visitado

    Para Cada vértice v de G:

        Se v não foi visitado:

            DFS_VISIT(v)

procedimento DFS_VISIT(v: vértice)

    Marque v como visitado

    Para Cada vértice w adjacente a v:

        Se w não foi visitado:

            DFS_VISIT(w)

se houve alguem que me possa ajudar, agradecia imenso.

cumprimentos a todos e boas programações

Henrique

Share this post


Link to post
Share on other sites
djthyrax

Como tens o grafo representado?


Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Share this post


Link to post
Share on other sites
DiJrId0u

Ora viva.

Para já, está representado da forma abaixo apresentada.

Ja tentei por o algoritmo a funcionar e testa-lo, mas confesso que percebo muito pouco disto e não faço a minima ideia se está bem ou mal encaminhado.

o objectivo do trabalho passa por implementar o DFS no algoritmo de ordenação topológica, e para o mesmo grafo, ordena-lo um determinado numero de vezes, para recolher os tempos de cada ordenação, por forma a elaborar um estudo sobre o comportamento computacional do algoritmo.

# -*- coding: cp1252 -*-
import math
import random
import time
import datetime
import copy
       
#############
# função DFS 
#############
def dfs(graph):
        color = {}
        WHITE = 0
        GRAY = 1
        BLACK = 2
        for i in graph:
                color[i] = WHITE
        
        #print graph
        for k in graph:
                if color[k] == WHITE:
                        print color
                        dfs_visit(graph,k, color)
                
         
###################
# função DFS_VISIT 
###################
def dfs_visit(graph, v, color):

        WHITE = 0
        GRAY = 1
        BLACK = 2

        color[v] = GRAY
        
        for w in graph[v]:
                if color[v] == WHITE:
                        dfs_visit(graph, w, color)
                color[w] = BLACK

                
#############################
# gera numeros de Ramos 1 a 5 
#############################
def gRamos():
    return random.randint(1,5)

#################################################
# gera a ponderação dos ramos numeros de -10 a 20 
#################################################
def gPonder():
    return random.randint(5, 20)

#############################
# Cria um grafo com size nós 
#############################
def newGraph(size):

    graph = {}

    for n in range (size):
        sGraph = {}
        nRamos = gRamos()
        for k in range (nRamos):
            ponder = gPonder()
            temp = random.randint(n , size)
            if temp <> n:
                 vizinho = temp
                 sGraph[vizinho] = ponder
        graph[n] = sGraph

    #print graph
    return graph
        

#################
# Função runProg  
#################
def runProg():
    
    fileDados = open('_GrafoTimes.txt', 'wb')
    
    sizeGraph = 5
    
    graph = newGraph(sizeGraph) #cria um grafo com sizeGraph nós
    print (len(graph))

    for n in range(1): #nº de repetições das ordenações ao grafo

        t1 = time.clock()
        print graph
        
        dfs(graph) #testa a função DFS
        #topological_sort(graph)
        
        t2 = time.clock()
        #print (t2 - t1)
        fileDados.write(str(n+1) + '\t' + str(t2 - t1)+ '\r\n')
    #print graph
    fileDados.close

#################
# MAIN PROG
#################
runProg()

Não querendo abusar muito, mas se me conseguirem dar, também, umas luzes sobre o tolopogical sort, agradeço.

cumprimentos

Share this post


Link to post
Share on other sites
mogers

Tás a seguir o pseudo-código do livro Introduction to Algorithms (também conhecido por CLRS) do MIT Press? Esse livro é muito bom, mas não é fácil de seguir.

Só estás a fazer uma coisa mal na dfs. White significa que o vértice ainda não foi visitado, Gray significa que o vértice já foi visitado e que estás a processar os seus vértices adjacentes e Black significa que o vértice já acabou de ser processado.

Sendo assim, só deves atribuir a cor preta a um vértice 'v' no final da dfs_visit e não a um adjacente 'w'.

def dfs_visit(graph, v, color):

        WHITE = 0
        GRAY = 1
        BLACK = 2

        color[v] = GRAY
       
        for w in graph[v]:
                if color[v] == WHITE:
                        dfs_visit(graph, w, color)
        color[v] = BLACK

Senão estou em erro, podes definir as cores fora das funções e funcionam como variaveis globais. Mas é melhor alguém que saiba python responder-te a isso.

Aconselho-te a veres os artigos de grafos na revista Programar:

http://www.revista-programar.info/front/edition/10  (introdução aos grafos e dfs)

http://www.revista-programar.info/front/edition/16  (fala um pouco mais de dfs )

Não há nenhum artigo sobre ordenação topologica, mas se tás a seguir aquele livro, tens la a explicação. Senão eu posso ajudar.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
DiJrId0u

Sim, estou a seguir esse livro, por aconselhamento "forçado" :wallbash: do meu professor. no entanto, pelo que pude constatar, é muito bom... :thumbsup:

Com o DFS a funcionar, e para que consiga preceder com a ordenação topológica, basta que à medida que um nó passe a black (ou seja, foi visitado) faça um append deste nó à lista que irá conter os resultados.

no final, essa lista deverá conter a ordenação que pretendo.

ou seja, crio uma lista nova que vai adicionando à lista todos os nós que passarem a black. certo?

Esta lista pode ser criada dentro do DFS_VISIT...?

###################
# função DFS_VISIT 
###################
def dfs_visit(graph, v, color):

        listOrd = {} #lista que irá conter a ordenação

        WHITE = 0
        GRAY = 1
        BLACK = 2

        color[v] = GRAY
        
        for w in graph[v]:
                if color[v] == WHITE:
                        dfs_visit(graph, w, color)
        color[v] = BLACK

        #instrução para adicionar o nó black à lista

sendo assim, caso a minha lógica esteja certa, só preciso mm de adicionar à lista os nós que entretanto ficaram a pretos. qual é a instrução em python que faz o que pretendo? tentei com listOrd.append(graph[v]) mas dá erro.

cumprimentos

Share this post


Link to post
Share on other sites
mogers

Pelo que sei, uma lista em python é definida por  listOrd = []        o {} é um "map"

O ideal seria adicionares ao inicio da lista tal como manda o livro, mas não sei fazer isso em python. Podes manter o append e depois invertes a lista.

Percebeste porque é que o algoritmo funciona? Eu aprendi outro algoritmo para fazer o mesmo, até desconhecia este...


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
DiJrId0u

sim, penso que percebi. estava era com problemas em traduzi-lo para código, pois a experiencia neste tipo de problemas é pouca, e às tantas, começo a baralhar-me.

Acho que ja consegui impelmentar a lista e adicionar-lhe os valores dos nós pretos. julgo não ser necessário fazer a operação de inversão, pq o que se pretende no trabalho é só recolher o tempo de execução do algoritmo e estudar a sua complexidade computacional. basta-me recolher tempos para grafos com 1000, 5000 e 15000 nós, e ver como evolui o algoritmo perante estes.

no entanto, e perante testes ja efectuados, o tempo é maior consoante o nº de nós do grafo, mas a diferencia é de centesimas e décimas. será possivel?

eis os testes que fiz:

num de nós / segundos

1000            0,0018357

10000       0,019484981

20000       0,038512278

50000       0,0976501

por curiosidade, qual é o algoritmo que usas para o fazer?

Share this post


Link to post
Share on other sites
mogers

Sim, é normal porque o algoritmo é muito rápido - uma simples dfs tem um exempo de execução linear O(V+E). Para veres diferenças maiores vais ter de aumentar muito o número de nós. 200 000 para cima. Mas como o tempo de execução é linear, espera-se que os tempos evoluam linearmente.

O algoritmo que uso, é pena um dos recursos que o explica não está disponível no momento, consiste em analisar o indegree de cada vértice, ou seja, o número de arestas que partem de outros vértices e têm como destino esse vértice.

Assim, adicionam-se os vértices com indegree = 0 a uma fila.

Posto isto, processam-se os elementos da fila por ordem (first-in, first-out). Ao processar um vértice v, percorre-se a sua lista de adjacências e "remove-se" este vértice do grafo. Para isso, reduz-se o indegree de todos os vértices w adjacentes de v. Se indegree[w ] = 0 significa que não existe mais nenhum vértice a precedê-lo e adicionamos esse vértice ao fim da fila.

O processo continua até todos os vértices serem processados. O tempo de execução é o mesmo O(V+E) porque cada vértice é adicionado à fila e são percorridas todas as arestas ao processar as listas de adjacencias dos vértices.

edit: se a fila se esgotar e não tiveres processado todos os vértices, é porque existe um ciclo no grafo. Exemplo:  1->2 , 2-> 3 , 3->4 , 4->2


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
DiJrId0u

Começo a achar alguma piada sobre o tema. Quando esse recurso estiver disponivel, manda o link.

Obrigado pela ajuda. Creio que sem ela, nao teria resolvido o meu problema.

Parabéns ao forum. Não conhecia, e ja reparei que é bastante rico em tudo o que é programação.

Encontramo-nos por outros posts  :P

tnks :P

Share this post


Link to post
Share on other sites
mogers

O meu professor parece que já tirou os slides da página da cadeira onde se falou nisso. De qualquer modo podes ver em http://paginas.fe.up.pt/~ei05053/grafos1.pdf  página 6, slide 11

Dispõe :P


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.