Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como implementar BFS e DFS em Python e extrair informações úteis de um grafo, como conectividade, aciclicidade, etc?

+3 votos
3,873 visitas
perguntada Abr 25, 2016 em Ciência da Computação por Saulo (456 pontos)  
Compartilhe

1 Resposta

+4 votos
respondida Abr 25, 2016 por Saulo (456 pontos)  
editado Abr 25, 2016 por Saulo

Esta resposta será estruturada da seguinte forma. Inicialmente, será mostrado o código-fonte em Python utilizado. Em seguida, será feito alguns comentários no código, em especial como extrair informações básicas do grafo usando BFS e DFS. E, por fim, será mostrado como utilizar.

O código-fonte em Python é:

import numpy as np
from collections import deque
from sortedcontainers import SortedSet

class Graph:
    def __init__(self, directedGraph=False):
        self.__V = list()
        self.__directedGraph = directedGraph
        self.__time = 0
        return

    def addVertex(self, v):
        if (not (v in self.__V)):
            v.setIndex(len(self.__V))
            self.__V.append(v)
        return v

    def createVertex(self):
        return self.addVertex(Vertex(self))

    def addEdge(self, u, v):
        if (isinstance(u, Vertex) and isinstance(v, Vertex)):
            if ((u in self.__V) and (v in self.__V)):
                u.addAdjacentVertex(v)

                if (not self.__directedGraph):
                    v.addAdjacentVertex(u)

                return
            else:
                raise("addEdge error. u and v must belong to graph.")
        elif (isinstance(u, int) and isinstance(v, int)):
            self.addEdge(self[u], self[v])
        else:
            raise("addEdge error. u and v must be of class Vertex or integers.")
        return

    def __getitem__(self, k):
        if ((len(self.__V) > 0) and (k >= 0) and (k < len(self.__V))):
            return self.__V[k]
        return None

    def __len__(self):
        return len(self.__V)

    def __str__(self):
        graphStr = str("")
        for index, vertex in enumerate(self.__V):
            graphStr += str(vertex)
            if (index < len(self.__V) - 1):
                graphStr += "\n"
        return graphStr

    def setVertexListAsUnexplored(self):
        for v in self.__V:
            v.setAsUnexplored()
        return

    def BFS(self, source=0, exploreObj=None):
        self.setVertexListAsUnexplored()

        if ((exploreObj is not None) and (source != exploreObj.getInitialVertexIndex())):
            source = exploreObj.getInitialVertexIndex()

        self[source].d = 0
        self[source].explore(exploreObj)

        queue = deque([self[source]])

        while len(queue)!=0:
            v = queue.popleft()

            for adjacentVertex in v.getAdjacentVertexSet():
                if(not adjacentVertex.wasExplored()):
                    adjacentVertex.predecessor = v
                    adjacentVertex.d = v.d + 1
                    adjacentVertex.explore(exploreObj)

                    queue.append(adjacentVertex)

        return exploreObj

    def DFS_Stack(self, exploreObj=None):
        self.setVertexListAsUnexplored()

        self.__time = 0

        for vertex in self.__V:
            if (not vertex.wasExplored()):
                self.__DFS_VISIT_STACK(vertex, exploreObj)

        return exploreObj

    def __DFS_VISIT_STACK(self, initialVertex, exploreObj=None):

        stack = deque([initialVertex])
        while len(stack)!=0:
            vertex = stack.pop()

            if (not vertex.wasExplored()):
                self.__time += 1
                vertex.d = self.__time
                vertex.explore(exploreObj)

                stack.append(vertex)

                for adjacentVertex in reversed(vertex.getAdjacentVertexSet()):
                    if (not adjacentVertex.wasExplored()):
                        adjacentVertex.predecessor = vertex
                        stack.append(adjacentVertex)
            else:
                if (vertex.f == np.inf):
                    self.__time += 1
                    vertex.f = self.__time

        return exploreObj

    def DFS_Rec(self, exploreObj=None):
        self.setVertexListAsUnexplored()

        self.__time = 0

        for vertex in self.__V:
            if (not vertex.wasExplored()):
                self.__DFS_VISIT_REC(vertex, exploreObj)

        return exploreObj

    def __DFS_VISIT_REC(self, vertex, exploreObj=None):

        self.__time += 1
        vertex.d = self.__time
        vertex.explore(exploreObj)

        for adjacentVertex in vertex.getAdjacentVertexSet():
            if(not adjacentVertex.wasExplored()):
                adjacentVertex.predecessor = vertex
                self.__DFS_VISIT_REC(adjacentVertex, exploreObj)

        self.__time += 1
        vertex.f = self.__time

        return exploreObj

    def isConnected(self):

        if (self.__directedGraph):
            for v in self.__V:
                self.setVertexListAsUnexplored()
                self.__DFS_VISIT_REC(v, None)
                for u in self.__V:
                    if (u.d == np.inf):
                        return False
            return True
        else:
            self.BFS(0, None)

            for v in self.__V:
                if (v.d == np.inf):
                    return False

            return True

    def isAcyclic(self):
        if (self.__directedGraph):
            self.DFS_Stack(None)
            for u in self.__V:
                for v in u.getAdjacentVertexSet():
                    if (Edge.isBackEdge(u, v)):
                        return False
            return True
        return False

    def getArticulationPoints(self):
        articulationPoints = list()

        n = len(self.__V)
        for i in range(n):
            vertex = self.__V.pop(0)

            if (not self.isConnected()):
                articulationPoints.append(vertex)

            self.__V.append(vertex)

        return articulationPoints


    def topologicalSort(self):
        if (self.isAcyclic()):
            self.DFS_Stack()

            self.__V = sorted(self.__V, cmp=topological_comparator, reverse=True)
        else:
            raise("Topological sort not possible. Graph is not acyclic.")


def topological_comparator(u, v):
        return u.f - v.f

class Edge:
    @staticmethod
    def isBackEdge(u, v):
        return (v.d <= u.d) and (u.d < u.f) and (u.f <= v.f)

    @staticmethod
    def isTreeEdgeOrForwardEdge(u, v):
        return (u.d < v.d) and (v.d < v.f) and (v.f < u.f)

    @staticmethod
    def isCrossEdge(u, v):
        return (v.d < v.f) and (v.f < u.d) and (u.d < u.f)

class Vertex:
    def __init__(self, parentGraph, index=0):
        self.__parentGraph = parentGraph
        self.__index = index
        self.__adjacentVertexSet = SortedSet()
        self.__explored = False
        self.__name = ""

        self.d = np.inf
        self.f = np.inf
        self.predecessor = None

    def setIndex(self, index):
        self.__index = index

    def getIndex(self):
        return self.__index

    def addAdjacentVertex(self, adjacentVertex):
        if (isinstance(adjacentVertex, Vertex)):
            if (not (adjacentVertex in self.__adjacentVertexSet)):
                self.__adjacentVertexSet.add(adjacentVertex)
        else:
            raise("addAdjacentVertex error. adjacentVertex must be of class Vertex.")
        return

    def setName(self, name):
        self.__name = name
        return self

    def getName(self):
        if (len(self.__name) == 0):
            return str(self.__index)
        return self.__name

    def getAdjacentVertexSet(self):
        return self.__adjacentVertexSet

    def wasExplored(self):
        return self.__explored

    def setAsUnexplored(self):
        self.__explored = False
        self.d = np.inf
        self.f = np.inf
        self.predecessor = None
        return

    def explore(self, exploreObj=None):
        if ((not self.__explored) and (exploreObj is not None)):
            exploreObj.explore(self)

        self.__explored = True

        return

    def vertex2str(self, showCompleteInfo=False):
        vertexStr = str("")
        vertexStr += self.getName()
        if (showCompleteInfo):
            vertexStr += " [d=" + str(self.d) + "][f=" + str(self.f) + "]"
        vertexStr += " -> "

        if (len(self.__adjacentVertexSet) > 0):
            for adjacentVertex in self.__adjacentVertexSet:
                vertexStr += " " + adjacentVertex.getName()

        return vertexStr

    def __lt__(self, other):
        return self.__index < other.__index

    def __gt__(self, other):
        return self.__index > other.__index

    def __str__(self):
        return self.vertex2str()

class CExplore:
    def __init__(self, graph = None):
        self._graph = graph
        self.__initialVertexIndex = 0
        self._indexVertex1 = -1
        self._indexVertex2 = -1
        return

    def check(self, indexVertex1, indexVertex2):
        if (isinstance(indexVertex1, Vertex) and isinstance(indexVertex2, Vertex)):
            return self.check(indexVertex1.getIndex(), indexVertex2.getIndex())

        elif (isinstance(indexVertex1, int) and isinstance(indexVertex2, int)):
            self._indexVertex1 = indexVertex1

            self._indexVertex2 = indexVertex2

            self.setInitialVertexIndex(indexVertex1)

            self._makeCalculations()

        else:
            raise("Error! u and v must be of class Vertex or integers.")

        return self

    def _makeCalculations(self):
        return self

    def setInitialVertexIndex(self, index):
        self.__initialVertexIndex = index
        return

    def getInitialVertexIndex(self):
        return self.__initialVertexIndex

    def explore(self, vertex):
        print "Exploring vertex ", vertex.getIndex(), " d=", vertex.d

class CShortestPath(CExplore):
    def __init__(self, graph):
        CExplore.__init__(self, graph)

        self.__shortestPath = np.inf

        self.__path = list()

        return

    def _makeCalculations(self):
        self.__shortestPath = np.inf

        self.__path = list()

        self._graph.BFS(self._indexVertex1, self)

        return self

    def explore(self, vertex):

        if (self._indexVertex2 == vertex.getIndex()):
            self.__shortestPath = vertex.d

            v = vertex
            while (v is not None):
                self.__path.insert(0, v.getIndex())
                v = v.predecessor

        return

    def getShortestPath(self):
        return self.__shortestPath

    def getPathVertexList(self):
        return self.__path

    def __str__(self):
        shortestPathStr = str("Shortest path: ")
        shortestPathStr += str(self.getPathVertexList())
        shortestPathStr += " -> "
        shortestPathStr += str(self.getShortestPath())
        return shortestPathStr

O código-fonte possui algumas classes principais:
1) "Graph", que representa o grafo. Ele possui uma lista de vértices e uma variável indica se o grafo é direcionado ou não.
2) "Vertex", que representa o vértice.
3) "CExplore", que representa uma classe para explorar o nó. Pode-se estender esta classe para realizar qualquer tarefa de exploração. Um exemplo é a classe "CShortestPath", que é usada para calcular o caminho mínimo.

O algoritmo BFS (método "Graph.BFS") utilizado encontra-se em [1, p. 595]. A estrutura principal é uma fila. Note que, neste algoritmo, armazena-se em cada vértice a informação de distância na variável "d".

O algoritmo DFS utilizado encontra-se em [1, p. 604], que usa recursão (método "Graph.DFS_Rec"). Mas também é possível obter o mesmo resultado usando uma pilha (método "Graph.DFS_Stack"). Armazena-se em cada vértice a informação de timestamp, sendo "d" o início e "f" o fim.

O BFS pode ser usado para calcular o caminho mínimo, conforme mostrado no Teorema 22.5 de [1, p. 599]. O caminho mínimo de um vértice s a outro vértice v pode ser descoberto usando os predecessores de v.

A conectividade (método "Graph.isConnected") de um grafo não-direcionado pode ser verificada tanto pelo BFS, quanto pelo DFS. Apenas aplica-se o algoritmo em um vértice inicial e verifica-se se todos os vértices foram visitados. Em grafos direcionados, não é tão simples assim. Uma possível solução é rodar o DFS em cada vértice, verificando se todos os outros vértices foram visitados. Veja a discussão em:
http://www.geeksforgeeks.org/connectivity-in-a-directed-graph/

Para verificar aciclicidade, podemos utilizar o lema 22.11: "A directed graph G is acyclic if and only if a depth-first search of G yields no back edges" [1, p. 614]. A definição de um "back edge" pode ser obtida em [1, p. 609], sendo que [2, p. 123] dá uma melhor intuição. Para verificar se uma aresta é um "back edge", usaremos o fato que "edge \( (u, v) \) is a back edge if and only if \(v.d \leq u.d < u.f \leq v.f \)" [1, p. 611].

Para obter os pontos de articulação, podemos usar a própria definição. Um ponto de articulação é aquele que, se for removido, desconecta o grafo [1, p. 621], [2, p. 125].

Um algoritmo para ordenação topológica pode ser obtido em [1, p. 613], [2, p. 140]. É válido ressaltar que somente é possível fazer a ordenação topológica em grafos direcionados e acíclicos, pois, se o grafo contém um ciclo, não é possível fazer a ordenação linear. Para fazer a ordenação topológica, basta rodar um DFS e ordenar de forma decrescente pela variável "f" do vértice. Existem outros algoritmos para a ordenação topológica, que usam técnicas de dividir e conquistar, como em [2, p. 141].

Vamos para os exemplos. Considere o seguinte grafo:

    N = 8
    for i in range(0, N):
        graph.createVertex()

    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 3)
    graph.addEdge(2, 4)
    graph.addEdge(3, 5)
    graph.addEdge(4, 5)
    graph.addEdge(6, 7)

Para usar o BFS ou DFS, basta usar algum dos métodos abaixo. A classe "CExplore" apenas está sendo usada para imprimir a execução, sendo que ela não é necessária.

    print "Graph"
    print graph

    print "BFS"
    graph.BFS(CExplore())

    print "DFS Stack"
    graph.DFS_Stack(CExplore())

    print "DFS_Recursive"
    graph.DFS_Rec(CExplore())

Para verificar o menor caminho:

    vertexPairs = {(0, 0), (0, 1), (1, 2), (5, 0), (0, 6)}
    shortestPathObj = CShortestPath(graph)

    for vertexPair in vertexPairs:
        shortestPathObj.check(vertexPair[0], vertexPair[1])

        print shortestPathObj
        print ""

Para verificar a conectividade e aciclicidade é diretamente pela chamada do métodos "isConnected" e "isAcyclic"

    print "Connected? ", graph.isConnected()

    print "Acyclic? ", graph.isAcyclic()

Pontos de articulação:

    print "Articulation points"
    for articulationPoint in graph.getArticulationPoints():
        print articulationPoint

Ordenação topológica. Esse exemplo é o mesmo da figura 22.7 de [1, p. 613].

    clothingGraph = Graph(True)
    vertex_undershorts = clothingGraph.createVertex().setName("undershorts")
    vertex_pants = clothingGraph.createVertex().setName("pants")
    vertex_belt = clothingGraph.createVertex().setName("belt")
    vertex_shirt = clothingGraph.createVertex().setName("shirt")
    vertex_tie = clothingGraph.createVertex().setName("tie")
    vertex_jacket = clothingGraph.createVertex().setName("jacket")
    vertex_socks = clothingGraph.createVertex().setName("socks")
    vertex_shoes = clothingGraph.createVertex().setName("shoes")
    vertex_watch = clothingGraph.createVertex().setName("watch")

    clothingGraph.addEdge(vertex_undershorts, vertex_pants)
    clothingGraph.addEdge(vertex_undershorts, vertex_shoes)

    clothingGraph.addEdge(vertex_pants, vertex_shoes)
    clothingGraph.addEdge(vertex_pants, vertex_belt)

    clothingGraph.addEdge(vertex_belt, vertex_jacket)

    clothingGraph.addEdge(vertex_shirt, vertex_belt)
    clothingGraph.addEdge(vertex_shirt, vertex_tie)

    clothingGraph.addEdge(vertex_tie, vertex_jacket)

    clothingGraph.addEdge(vertex_socks, vertex_shoes)

    clothingGraph.topologicalSort()

    print clothingGraph

Referências:
[1] Cormen, T. H.; Leiserson, C. E.; Rivest, R.; Stein, C. "Introduction to Algorithms". MIT Press, 2009. 3 ed.
[2] Levitin, A. "Introduction to the design and analysis of algorithms". Pearson, 2011. 3 ed.

...