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

DiJrId0u

algoritmo DFS sobre grafos

10 mensagens neste tópico

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora