Idiomas:
Representação da estrutura de dados grafo por meio de lista de adjacência.
Estrutura implementada inteiramente em Dart com métodos de inserção e exclusão de vértices e arestas para criação e manipulação de grafos orientados e não orientados.
Conteúdo
Um grafo é uma estrutura de dados composta por dois elementos, um conjunto de vértices (ver definição) e um conjunto de arestas (ver definição). Podem ser do tipo orientado (ver definição) ou não orientado (ver definição).
Grafos orientados, também conhecidos por digrafos, são aqueles nos quais as suas arestas possuem um sentido definido, ou seja, de um vértice u pode-se chegar em v mas oposto não ocorre, não há uma relação simétrica. Graficamente podem ser representados da seguinte forma:
Já que possuem um sentido definido, podem os seus vértices podem ter arestas que saem e chegam neles mesmos:
Grafos não orientados são aqueles nos quais as suas arestas não possuem um sentido definido, pode-se ir tanto de u para v quanto de v para u, ou seja, ocorre a relação de simetria. Graficamente podem ser representados da seguinte forma:
Um vértice, também conhecido por nó, e a unidade fundamental para a composição de um grafo. A partir das suas composições com arestas muitos problemas podem ser resolvidos através da sua modelagem. No caso da implementação deste package, um vértice possui um identificador para diferenciá-lo dos demais, representado pelo atributo label. Pode armazenar um valor numérico em value e possui uma lista de arestas nos quais indica com quais outros vértices este está conectado.
Caso um value não seja definido inicialmente, nesta implementação ele terá o valor 0.
Uma aresta tem a função de conectar dois vértices além de definir de qual tipo um grafo será, orientado ou não orientado.
Arestas orientadas possuem um sentido definido, ou seja, há somente um caminho a ser seguido:
Arestas não orientadas não possuem um sentido definido, podendo conectar dois vértices no sentido de ida e volta:
Em ambos os tipos, as arestas podem armazenar um peso numérico:
Caso um peso não seja passado, nesta implementação ele será nulo.
Tanto grafos orientados quanto os não orientados possuem atributos e métodos em comum. A partir disso, muitas funcionalidades presentes neste Package estão implementadas para os dois tipos de estrutura, mostradas nesta sessão.
Este método consiste em buscar um vértice no grafo através do seu identificador. Caso exista, ele será retornado, caso contrário, será lançado um [StateError].
final myGraph = OrientedGraph();
myGraph.addVertex(newVertex: Vertex(label: '1'), connectedTo: ['2', '3']);
myGraph.addVertex(newVertex: Vertex(label: '2'));
myGraph.addVertex(newVertex: Vertex(label: '3'));
myGraph.getV('1'); // return Vertex(label: '1')
myGraph.getV('w'); // throw `[StateError]`
Como a estrutura padrão para grafos são listas, então adicionando novos vértices e arestas a elas, o grafo será modelado. Um primeiro método para isso consiste em primeiramente adicionar os vértices necessários ao grafo:
final myGraph = OrientedGraph();
myGraph.vertices.add(Vertex(label: 'u'));
myGraph.vertices.add(Vertex(label: 'v'));
myGraph.vertices.add(Vertex(label: 'y'));
myGraph.vertices.add(Vertex(label: 'x'));
myGraph.vertices.add(Vertex(label: 'w'));
myGraph.vertices.add(Vertex(label: 'z')); Após todos os vértices serem definidos, as suas arestas precisam ser adicionadas. Para isso em cada vértice e preciso chamar a função addEdge para que a conexão entre eles seja feita. Recomenda-se utilizar o método getV para encontrar o vértice desejado para uma melhor leitura do código, entre o vértice de origem e o de destino.
myGraph.getV('u').addEdge(connectedTo: myGraph.getV('v'));
myGraph.getV('u').addEdge(connectedTo: myGraph.getV('x'));
myGraph.getV('v').addEdge(connectedTo: myGraph.getV('y'));
myGraph.getV('y').addEdge(connectedTo: myGraph.getV('x'));
myGraph.getV('x').addEdge(connectedTo: myGraph.getV('v'));
myGraph.getV('w').addEdge(connectedTo: myGraph.getV('y'));
myGraph.getV('w').addEdge(connectedTo: myGraph.getV('z'));
myGraph.getV('z').addEdge(connectedTo: myGraph.getV('z')); Vale ressaltar que, como aqui todos os vértices são feitos de maneira manual, caso seja um grafo não orientado, e necessário fazer as arestas de volta também, para que a estrutura computacional corresponda a modelagem.
Uma segunda maneira de se povoar um grafo e através do método addVertex. Esta função consiste em encapsular toda a criação de um vértice e criação das suas arestas para outros vértices mesmo que eles ainda não tenham sido criados.
final myGraph = OrientedGraph();
myGraph.addVertex(newVertex: Vertex(label: 'u'), connectedTo: ['v', 'x']);
myGraph.addVertex(newVertex: Vertex(label: 'v'), connectedTo: ['y']);
myGraph.addVertex(newVertex: Vertex(label: 'y'), connectedTo: ['x']);
myGraph.addVertex(newVertex: Vertex(label: 'x'), connectedTo: ['v']);
myGraph.addVertex(newVertex: Vertex(label: 'w'), connectedTo: ['y', 'z']);
myGraph.addVertex(newVertex: Vertex(label: 'z'), connectedTo: ['z']); No exemplo acima, quando o vértice u e criado, tanto o vértice v quando x ainda não existem no grafo, mas este método os armazena em uma lista de espera, até que eles sejam definitivamente criados, assim as arestas necessárias serão criadas e o grafo seguir a modelagem desejada.
Além de definir as conexões com arestas baseados em connectedTo, também e possível passar pesos para as arestas através do parâmetro edgeWeight. Este parâmetro consiste em uma lista de valores para os pesos, dessa forma, posicionalmente com a lista connectedTo, as arestas terão um peso definido a cada uma. O valor null também pode ser atribuído a peso de arestas.
final myGraph = OrientedGraph();
myGraph.addVertex(newVertex: Vertex(label: 'u'), connectedTo: ['v', 'x'], edgeWeight: [null, 2]);
myGraph.addVertex(newVertex: Vertex(label: 'v'), connectedTo: ['y'], edgeWeight: []);
myGraph.addVertex(newVertex: Vertex(label: 'y'), connectedTo: ['x'], edgeWeight: [null]);
myGraph.addVertex(newVertex: Vertex(label: 'x'), connectedTo: ['v']);
myGraph.addVertex(newVertex: Vertex(label: 'w'), connectedTo: ['y', 'z'], edgeWeight: [6]);
myGraph.addVertex(newVertex: Vertex(label: 'z'), connectedTo: ['z'], edgeWeight: [8]); No exemplo acima existem 4 maneiras de atribuir valores nulos para o peso de arestas: não utilizando o parâmetro edgeWeight (linha 6), utilizando uma lista vazia (linha 4), utilizando explicitamente null (linhas 3 e 5) e omitindo o valor do ultimo peso (linha 7)
Dentre as vantagens que este método possui em relação ao básico, pode-se citar principalmente a redução na quantidade de código, principalmente em grafos não orientados, pois neles a adição de arestas é sempre dobrada, como mostra o exemplo abaixo:
final myGraph = NotOrientedGraph();
myGraph.vertices.add(Vertex(label: 'u'));
myGraph.vertices.add(Vertex(label: 'v'));
myGraph.vertices.add(Vertex(label: 'y'));
myGraph.vertices.add(Vertex(label: 'x'));
myGraph.vertices.add(Vertex(label: 'w'));
myGraph.vertices.add(Vertex(label: 'z'));
myGraph.getV('u').addEdge(connectedTo: myGraph.getV('v'));
myGraph.getV('v').addEdge(connectedTo: myGraph.getV('u'));
myGraph.getV('u').addEdge(connectedTo: myGraph.getV('x'));
myGraph.getV('x').addEdge(connectedTo: myGraph.getV('u'));
myGraph.getV('v').addEdge(connectedTo: myGraph.getV('y'));
myGraph.getV('y').addEdge(connectedTo: myGraph.getV('v'));
myGraph.getV('y').addEdge(connectedTo: myGraph.getV('x'));
myGraph.getV('x').addEdge(connectedTo: myGraph.getV('v'));
myGraph.getV('x').addEdge(connectedTo: myGraph.getV('y'));
myGraph.getV('v').addEdge(connectedTo: myGraph.getV('x'));
myGraph.getV('w').addEdge(connectedTo: myGraph.getV('y'));
myGraph.getV('y').addEdge(connectedTo: myGraph.getV('w'));
myGraph.getV('w').addEdge(connectedTo: myGraph.getV('z'));
myGraph.getV('z').addEdge(connectedTo: myGraph.getV('w'));
final myGraph2 = NotOrientedGraph();
myGraph2.addVertex(newVertex: Vertex(label: 'u'), connectedTo: ['v', 'x']);
myGraph2.addVertex(newVertex: Vertex(label: 'v'), connectedTo: ['y', 'x']);
myGraph2.addVertex(newVertex: Vertex(label: 'y'), connectedTo: ['x', 'w']);
myGraph2.addVertex(newVertex: Vertex(label: 'x'));
myGraph2.addVertex(newVertex: Vertex(label: 'w'), connectedTo: ['z']);
myGraph2.addVertex(newVertex: Vertex(label: 'z'));
myGraph == myGraph2; // trueOutra vantagem que este método possui é a legibilidade do código, pois em um mesmo comando sabe qual vértice está sendo criado, para quais outros ele possui uma aresta e os pesos declarados para cada aresta.
Exclui um vértice do grafo pelo seu identificador juntamente com as arestas que saem e chegam nele.
final myGraph = NotOrientedGraph();
myGraph.addVertex(newVertex: Vertex(label: 'u'), connectedTo: ['v', 'x'], edgeWeight: [null, 2]);
myGraph.addVertex(newVertex: Vertex(label: 'v'), connectedTo: ['y'], edgeWeight: []);
myGraph.addVertex(newVertex: Vertex(label: 'y'), connectedTo: ['x'], edgeWeight: [null]);
myGraph.addVertex(newVertex: Vertex(label: 'x'), connectedTo: ['v']);
myGraph.addVertex(newVertex: Vertex(label: 'w'), connectedTo: ['y', 'z'], edgeWeight: [6]);
myGraph.addVertex(newVertex: Vertex(label: 'z'), connectedTo: ['z'], edgeWeight: [8]);
print(myGraph);
// (u) - [ (v) (x) ]
// (v) - [ (y) ]
// (y) - [ (x) ]
// (x) - [ (v) ]
// (w) - [ (y) (z) ]
// (z) - [ (z) ]
myGraph.excludeVertex(vertexLabel: 'v');
print(myGraph);
// (u) - [ (x) ]
// (y) - [ (x) ]
// (x) - [ ]
// (w) - [ (y) (z) ]
// (z) - [ (z) ] Caso o vértice não seja encontrado no grafo, uma mensagem de erro será mostrada:
Para mais informações sobre o erro ocorrido, execute a sua aplicação no modo debug e um log abaixo desta mensagem de erro também será mostrado, com informações sobre a exceção lançada e o estado atual da pilha de chamadas (StackTrace).
Retorna o primeiro vértice da lista de vértices do grafo.
final myGraph = NotOrientedGraph();
myGraph.addVertex(newVertex: Vertex(label: 'u'), connectedTo: ['v', 'x'], edgeWeight: [null, 2]);
myGraph.addVertex(newVertex: Vertex(label: 'v'), connectedTo: ['y'], edgeWeight: []);
myGraph.addVertex(newVertex: Vertex(label: 'y'), connectedTo: ['x'], edgeWeight: [null]);
myGraph.addVertex(newVertex: Vertex(label: 'x'), connectedTo: ['v']);
myGraph.addVertex(newVertex: Vertex(label: 'w'), connectedTo: ['y', 'z'], edgeWeight: [6]);
myGraph.addVertex(newVertex: Vertex(label: 'z'), connectedTo: ['z'], edgeWeight: [8]);
myGraph.first // Vertex(label: 'u')
Retorna o ultimo vértice da lista de vértices do grafo.
final myGraph = NotOrientedGraph();
myGraph.addVertex(newVertex: Vertex(label: 'u'), connectedTo: ['v', 'x'], edgeWeight: [null, 2]);
myGraph.addVertex(newVertex: Vertex(label: 'v'), connectedTo: ['y'], edgeWeight: []);
myGraph.addVertex(newVertex: Vertex(label: 'y'), connectedTo: ['x'], edgeWeight: [null]);
myGraph.addVertex(newVertex: Vertex(label: 'x'), connectedTo: ['v']);
myGraph.addVertex(newVertex: Vertex(label: 'w'), connectedTo: ['y', 'z'], edgeWeight: [6]);
myGraph.addVertex(newVertex: Vertex(label: 'z'), connectedTo: ['z'], edgeWeight: [8]);
myGraph.last // Vertex(label: 'z')
Método que retorna verdadeiro se houver algum ciclo no grafo.
final myGraph = NotOrientedGraph();
myGraph.addVertex(newVertex: Vertex(label: 'u'), connectedTo: ['v', 'x'], edgeWeight: [null, 2]);
myGraph.addVertex(newVertex: Vertex(label: 'v'), connectedTo: ['y'], edgeWeight: []);
myGraph.addVertex(newVertex: Vertex(label: 'y'), connectedTo: ['x'], edgeWeight: [null]);
myGraph.addVertex(newVertex: Vertex(label: 'x'), connectedTo: ['v']);
myGraph.addVertex(newVertex: Vertex(label: 'w'), connectedTo: ['y', 'z'], edgeWeight: [6]);
myGraph.addVertex(newVertex: Vertex(label: 'z'), connectedTo: ['z'], edgeWeight: [8]);
myGraph.hasCycle // true
Busca em largura em um grafo consiste em calcular a distância para todos os vértices alcançáveis a partir de um vértice de origem. Esse método causa um efeito colateral no grafo, gerando uma árvore de busca em largura.
A árvore resultante e definida através do parâmetro ancestor em cada vértice, no qual armazena o vértice anterior e a distância calculada e guardada em value. Conforme o algoritmo percorre o grafo, o parâmetro visited em cada vértice se torna verdadeiro.
Busca em profundidade em um grafo consiste em, a cada vértice do grafo, explorar o quanto for possível as suas listas de adjacência até ir para o próximo vértice não visitado. Esse método causa um efeito colateral no grafo, gerando uma floresta de busca em profundidade, ou seja, contém várias árvores de busca em profundidade.
Os parâmetros value, ancestor e visited armazenam a distância calculada, o vértice anterior e a identificação de visitado respectivamente.
Grafos orientados possuem características e métodos exclusivos de sua estrutura, nas quais serão mostradas nesta sessão.
Retorna o número de arestas presentes em um grafo orientado, somando a quantidade de arestas presente em cada vértice.
Retorna uma lista com todas as arestas presentes em um grafo orientado.
Verifica se o grafo orientado é fortemente conexo, ou seja, se para cada par de vértices (u,v), v e acessível a partir de u
Verifica se o grafo é um DAG (grafo acíclico orientado)
Método no qual mostra uma versão simplificada do grafo na linha de comando utilizando listas de adjacência.
print(myGraph.toString());
(1) -> [ (2) (3) ]
(2) -> [ ]
(3) -> [ ] Omitindo a chamada do método toString() dentro de print também funciona:
print(myGraph);
(1) -> [ (2) (3) ]
(2) -> [ ]
(3) -> [ ]
Método mais robusto para mostrar o conteúdo de um grafo orientado na linha de comando. Mostra utilizando listas de adjacência com alguns parâmetros opcionais. Valores nulos não são mostrados.
print(myGraph.printGraph());
(1) -----> (2)
-----> (3)
(2)
(3) -----> (3) Os valores associados a cada vértice podem ser mostrados com o parâmetro vertexValue, seguindo o padrão (label:value):
print(myGraph.printGraph(vertexValue: true));
(1:5) -----> (2:4)
-----> (3:10)
(2:4)
(3:10) -----> (3:10) Os pesos de cada aresta também podem ser mostrados com o parâmetro edgeWeight:
print(myGraph.printGraph(edgeWeight: true));
(1) --1--> (2)
--2--> (3)
(2)
(3) --8--> (3)
Grafos não orientados possuem características e métodos exclusivos de sua estrutura, nas quais serão mostradas nesta sessão.
Retorna o número de arestas presentes em um grafo não orientado, seguindo a equação abaixo:
numero_total_de_vertices ~/ 2pois para grafos não orientados, as arestas repetidas mas com sentido oposto são consideradas as mesmas.
Retorna uma lista com todas as arestas presentes em um grafo não orientado orientado, incluindo arestas de ida e de volta.
Verifica se um grafo não orientado e conexo, ou seja, se a partir de um vértice pode-se chegar a todos os outros.
Verifica se um grafo não orientado é acíclico e conexo.
Verifica se um grafo é não orientado e acíclico
Método no qual mostra uma versão simplificada do grafo na linha de comando utilizando listas de adjacência.
print(myGraph.toString());
(1) -- [ (2) (3) ]
(2) -- [ (1) ]
(3) -- [ (1) ] Omitindo a chamada do método toString() dentro de print também funciona:
print(myGraph);
(1) -- [ (2) (3) ]
(2) -- [ (1) ]
(3) -- [ (1) ]
Método mais robusto para mostrar o conteúdo de um grafo não orientado na linha de comando. Mostra utilizando listas de adjacência com alguns parâmetros opcionais. Valores nulos não são mostrados.
print(myGraph.printGraph());
(1) ----- (2)
----- (3)
(2) ----- (1)
(3) ----- (1) Os valores associados a cada vértice podem ser mostrados com o parâmetro vertexValue, seguindo o padrão (label:value):
print(myGraph.printGraph(vertexValue: true));
(1:5) ----- (2:4)
----- (3:10)
(2:4) ----- (1:5)
(3:10) ----- (1:5) Os pesos de cada aresta também podem ser mostrados com o parâmetro edgeWeight:
print(myGraph.printGraph(edgeWeight: true));
(1) --1-- (2)
--2-- (3)
(2) --5-- (1)
(3) --10-- (1)
Métodos exclusivos de um vértice, alguns deles podem ser somente para grafos orientados e, caso sejam utilizados em grafos não orientados, uma mensagem de erro será retornada.
Cria uma nova aresta e a adiciona na lista de arestas daquele vértice.
final myGraph = OrientedGraph();
myGraph.vertices.add(Vertex(label: 'u'));
myGraph.vertices.add(Vertex(label: 'v'));
myGraph.getV('u').addEdge(connectedTo: myGraph.getV('v')); A nova aresta pode ser criada com peso, caso não seja passado, será null.
myGraph.getV('u').addEdge(connectedTo: myGraph.getV('v'), weight: 5); Se a aresta já existir, a exceção EdgeAlreadyExistsException será levantada.
EdgeAlreadyExistsException(
'Edge between $label and ${connectedTo.label} already exists',
);
Remove uma aresta da lista de arestas deste vértice pelo identificador do vértice de destino.
final myGraph = OrientedGraph();
myGraph.vertices.add(Vertex(label: 'u'));
myGraph.vertices.add(Vertex(label: 'v'));
myGraph.getV('u').addEdge(connectedTo: myGraph.getV('v'));
myGraph.getV('u').excludeEdge('v');Caso a aresta não seja encontrada no vértice, a seguinte exceção será lançada:
EdgeNotFoundException(
'Edge between (vertex $label) and (vertex $destinyLabel) not found!!!!!!',
);
Retorna a lista de adjacência do vértice a partir da edgesList.
final myGraph = OrientedGraph();
myGraph.addVertex(newVertex: Vertex(label: 'u'), connectedTo: ['v', 'x']);
myGraph.getV('u').verticesOfEdgesList //[Vertex(label: 'v'), Vertex(label: 'x')]
Verifica se naquele vértice há somente arestas que chegam nele, ou seja, não há arestas saindo. Válido somente para grafos orientados.
final myGraph = OrientedGraph();
myGraph.addVertex(newVertex: Vertex(label: '1'), connectedTo: ['2', '3']);
myGraph.addVertex(newVertex: Vertex(label: '2'));
myGraph.addVertex(newVertex: Vertex(label: '3'));
myGraph.getV('2').isSinkhole; // true
myGraph.getV('3').isSinkhole; // true
Verifica se naquele vértice há somente arestas que saem dele, ou seja, não há arestas chegando. Válido somente para grafos orientados.
final myGraph = OrientedGraph();
myGraph.addVertex(newVertex: Vertex(label: '1'), connectedTo: ['2', '3']);
myGraph.addVertex(newVertex: Vertex(label: '2'));
myGraph.addVertex(newVertex: Vertex(label: '3'));
myGraph.getV('1').isSinkhole; // true
Número de arestas que entram no vértice.
final myGraph = OrientedGraph();
myGraph.addVertex(newVertex: Vertex(label: '1'), connectedTo: ['2', '3']);
myGraph.addVertex(newVertex: Vertex(label: '2'));
myGraph.addVertex(newVertex: Vertex(label: '3'));
myGraph.getV('1').entryDegree; // 0
Número de arestas que saem do vértice.
final myGraph = OrientedGraph();
myGraph.addVertex(newVertex: Vertex(label: '1'), connectedTo: ['2', '3']);
myGraph.addVertex(newVertex: Vertex(label: '2'));
myGraph.addVertex(newVertex: Vertex(label: '3'));
myGraph.getV('1').entryDegree; // 2