Pesquisas - search

grafos.search.bellmanFord(self, node=0)

Obtém o caminho mínimo do grafo, considerando o peso das arestas como indicador.

Utiliza o algoritmo de Bellman Ford, que permite que as arestas possuam pesos negativos.

Args:

node (int): nó inicial para o percurso do grafo (default: 0)

Returns:

info (dictionary): Estrutura de dados que armazena dois numpy arrays ( dt e previous) e um boolean (negativeCycle), que indicam a distância percorrida no caminho mínimo, os nós anteriores e a presença de um ciclo negativo, respectivamente.

Raises:

None

grafos.search.breadthFirstSearch(self, node=0)

Gerencia as estruturas de dados responsáveis por armazenar os dados gerados na busca em largura.

Args:

node (int): nó de início da busca em largura (default: 0).

Returns:

info (dictionary): dicionário que armazena três listas: visitedNodes, que armazena a sequência de vértices visitados na busca; visitedEdges, que armazena as arestas percorridas na sequência de visitas dos nós; e nftEdges (not from tree edges), que armazena as arestas que não fazem parte da árvore de busca em largura.

Raises:

None

grafos.search.breadthSearch(self, node, visitedNodes, visitedEdges)

Algoritmo para realizar a busca em largura em um grafo.

Args:

node (int): nó de início da busca em largura. visitedNodes (list): lista vazia a ser preenchida com os nós visitados. visitedEdges (list): lista vazia a ser preenchida com as arestas visitadas.

Returns:

None

Raises:

None

grafos.search.depthFirstSearch(self, node=0)

Gerencia as estruturas de dados responsáveis por armazenar os dados gerados na busca em profundidade.

Args:

node (int): nó de início da busca em profunidade (default: 0).

Returns:

info (dictionary): dicionário que armazena três listas: returnEdges, que armazena as arestas de retorno da árvore de busca em profundidade; visitedEdges, que armazena as arestas percorridas na sequência de visita dos nós; e connectedComponents, que armazena listas que contém os vértices que compõem as componentes conexas do grafo.

Raises:

None

grafos.search.depthSearch(self, node, visitedNodes, visitedEdges, returnEdges)

Algoritmo para realizar a busca em profundidade em um grafo.

Args:

node (int): nó de início da busca em largura. visitedNodes (list): lista a ser preenchida com os nós visitados. visitedEdges (list): lista a ser preenchida com as arestas visitadas. returnEdges (list): lista a ser preenchida com as arestas de retorno.

Returns:

None

Raises:

None

grafos.search.hasNegativeCircuit(self)

Verifica a presença de um circuito negativo no grafo.

Utiliza o campo “negativeCycle” obtido através do conjunto de informações geradas pela execução do algoritmo de Bellman Ford no grafo.

Args:

None

Returns:

boolean: True se o grafo possui um circuito negativo; False caso contrário.

Raises:

None

grafos.search.isBipartite(self, node=0)

Verifica se um grafo é bipartido através de coloração.

Define duas cores válidas e colore os grafos presentes na fila de nós, enquanto existirem. Se um nó de uma cor estiver ligado a um nó cuja cor é igual, o grafo não poderá ser considerado bipartido.

Args:

node (int): nó inicial para o percurso do grafo (default: 0)

Returns:

boolean: True se o grafo for bipartido; False caso contrário.

Raises:

None