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.