Como o Graph Labs funciona

Um roteiro de dois minutos para conhecer o estúdio usando um grafo pronto:

1. 1.Na aba Construir, clique em Rede ponderada. O grafo é carregado e enquadrado automaticamente.
2. 2.Vá para Executar e escolha Método de Dijkstra, em Caminho mínimo.
3. 3.Em Raiz / origem, selecione A; em Vértice de destino, selecione F.
4. 4.Clique em Executar Dijkstra e use Próximo passo para ver cada vértice ser fechado e cada aresta tensa ser relaxada na tabela dist e pred.
5. 5.No último passo, o caminho mínimo A → C → F, de peso 11, aparece em roxo, e o card de Conclusões resume as distâncias finais.

Apenas uma ferramenta fica ativa por vez, destacada na barra superior. O cursor muda de formato para indicar qual está em uso, e uma dica ao lado da barra explica o que fazer.

• Selecionar e mover

  Ferramenta padrão. Clique em um vértice ou aresta para selecioná-lo, arraste vértices para reposicioná-los e arraste o fundo para mover a visão.

• Adicionar vértice

  Cada clique em um ponto vazio cria um vértice ali. Os rótulos seguem a sequência A, B, C, ..., Z, A1, B1, ..., sempre pulando os já usados.

• Conectar vértices

  Clique no vértice de origem e depois no de destino. Entre os dois cliques, uma linha tracejada acompanha o cursor. Esc cancela.

• Remover elemento

  Clique em um vértice ou aresta para apagá-lo. Remover um vértice remove também todas as arestas ligadas a ele.

• Desfazer

  Volta a última alteração do grafo. Guarda até 60 alterações.

• Refazer

  Reaplica uma alteração desfeita.

• Limpar grafo

  Apaga todos os vértices e arestas. Pode ser desfeito com Desfazer.

• Novas arestas não direcionadas

  As arestas criadas no canvas nascem simples (padrão).

• Novas arestas direcionadas

  As arestas criadas no canvas nascem com seta, da origem para o destino.

• Sugestão de posicionamento

  Quando ligada, cada nova aresta dispara um ajuste fino do desenho. A preferência fica salva.

• Reorganizar agora

  Aplica o ajuste de posicionamento imediatamente, uma única vez.

Arraste o fundo para mover a visão e use a roda do mouse (ou o gesto de pinça no trackpad e no celular) para aproximar e afastar, sempre centrado no ponto sob o cursor. O zoom vai de 30% a 260%. Os botões no canto inferior direito oferecem o mesmo controle:

• Aproximar

  Aumenta o zoom em 25%, mantendo o centro.

• Afastar

  Reduz o zoom em 20%, mantendo o centro.

• Enquadrar grafo

  Ajusta zoom e posição para que o grafo inteiro caiba na tela.

Ao carregar um modelo pronto, o grafo é enquadrado automaticamente. Arestas paralelas entre o mesmo par de vértices, como A → B e B → A, são desenhadas curvas para não se sobreporem.

Depois que um algoritmo é executado, cada vértice e aresta recebe um estado a cada passo. A legenda no canto inferior esquerdo do canvas resume o significado das cores:

• Não explorado

  Estado inicial: o algoritmo ainda não alcançou o elemento.

• Marcado

  Alcançado, mas ainda não processado: está na fila, na pilha ou na fronteira.

• Em análise

  Elemento examinado no passo atual. Vértices em análise pulsam para chamar a atenção.

• Explorado / na solução

  Processamento concluído ou elemento aceito na solução (árvore, ordem, emparelhamento).

• Descartado

  Rejeitado pelo algoritmo, como uma aresta que formaria ciclo. Arestas descartadas ficam tracejadas.

• Caminho

  Resultado destacado no fim: caminho mínimo, caminho aumentante ou trajeto euleriano.

• Anel tracejado na cor principal

  Vértice de partida. A etiqueta acima dele indica RAIZ ou, nos algoritmos de fluxo, FONTE.

• Anel tracejado roxo

  Vértice de chegada: DESTINO, ou SUMIDOURO nos algoritmos de fluxo.

• 1/6

  Etiqueta sob o vértice

  Valor do vértice no passo atual: TD/TT na busca em profundidade, nível na busca em largura, dist em Dijkstra, cor na coloração, s e t no fluxo.

• 3/5

  Rótulo da aresta

  Mostra o peso. Durante a execução pode dar lugar a outro valor, como fluxo/capacidade nos algoritmos de fluxo ou a ordem de travessia em Fleury.

• Contorno colorido

  Agrupa vértices do mesmo conjunto: componentes f-conexos em Kosaraju, árvores da floresta em Kruskal, classes de cor na coloração.

Os modelos reproduzem exemplos usados em aula, cada um pensado para destacar o comportamento de determinados algoritmos. Carregar um modelo substitui o grafo atual (é possível desfazer), limpa a raiz e o destino escolhidos e enquadra o desenho.

• Rede ponderada

  Grafo não direcionado e ponderado, com peso w(e) > 0 em cada aresta: base para AGM (Prim e Kruskal) e para Dijkstra.

  PrimKruskalDijkstra

• Grafo direcionado com circuitos

  Grafo direcionado com três componentes fortemente conexos (f-conexos), para o método de Kosaraju.

  KosarajuDFS

• Rede de fluxo

  Rede de fluxo: grafo direcionado com capacidade u(e) em cada aresta, da fonte s = S ao sumidouro t = T.

  Ford-Fulkerson

• Pesos negativos

  Grafo direcionado com arestas de peso negativo e sem ciclo de peso negativo, para Bellman-Ford e Floyd-Warshall.

  Bellman-FordFloyd-Warshall

• Grafo simples

  Grafo simples não direcionado, sem pesos relevantes: bom para as buscas em largura e em profundidade.

  BFSDFS

• Grafo euleriano

  Exemplo 1 do deck de grafos eulerianos: todos os vértices têm grau par, então existe ciclo euleriano.

  Fleury

• Grafo semi-euleriano

  Exemplo 2 do deck: exatamente dois vértices de grau ímpar (5 e 6), então existe trajeto euleriano aberto.

  Fleury

• Rede com gargalo

  Rede do deck de Edmonds-Karp: duas arestas de capacidade 100 ligadas por uma de capacidade 1, que expõe a fragilidade da escolha arbitrária de caminho.

  Ford-FulkersonEdmonds-KarpDinic

• Precedência de atividades

  Grafo acíclico do deck de ordenação topológica: a fabricação de uma estante, de comprar as tábuas até transportá-la.

  KahnOrd. topológica (BP)

• Emparelhamento com botões

  Grafo genérico com dois ciclos de tamanho ímpar: exige a contração de botões (blossoms) do método de Edmonds.

  Edmonds

• Coloração de vértices

  Grafo com χ(G) = 3 em que a ordem alfabética faz o método guloso gastar 4 cores, enquanto Welsh-Powell encontra 3.

  Coloração gulosaWelsh-Powell

• Contraexemplo de Welsh-Powell

  Grafo bipartido, logo χ(G) = 2, em que Welsh-Powell mesmo assim usa 3 cores. É o contraexemplo do deck de coloração.

  Welsh-PowellColoração gulosa

O card Vértices lista todos os vértices em ordem alfabética, com a contagem total no cabeçalho. O botão Novo cria um vértice no canvas sem precisar trocar de ferramenta; depois é só arrastá-lo para o lugar desejado.

• Renomear: edite o rótulo direto no campo de texto, com até 6 caracteres. A ordem alfabética dos rótulos é a ordem padrão de visita de todos os algoritmos.
• Selecionar: clique no círculo com as iniciais ou no campo de texto para destacar o vértice no canvas.
• Remover: o ícone de lixeira apaga o vértice e todas as arestas incidentes a ele.

O formulário no topo do card cria arestas com precisão, o que é útil para grafos grandes ou para copiar um exercício: escolha os vértices De e Para, informe o Peso e o Tipo (simples ou direcionada) e clique em Adicionar aresta. O cabeçalho mostra o total de arestas e quantas são de cada tipo.

Cada aresta da lista pode ser editada sem ser recriada:

• o campo numérico altera o peso, e apagá-lo deixa a aresta sem peso;
• o selo alterna a direção com um clique: simples / direcionada
• clicar nos rótulos seleciona a aresta no canvas;
• a lixeira remove a aresta.

O card Algoritmo agrupa os métodos por tópico, na ordem da disciplina. Cada opção mostra o nome, a complexidade e um resumo da estratégia. O algoritmo selecionado fica destacado e define o conteúdo do card Parâmetros logo abaixo.

O cabeçalho do card repete o nome e a complexidade do método, seguidos pelos requisitos do grafo em forma de selos. Os campos de vértice só aparecem quando o algoritmo os utiliza:

Quando um campo obrigatório ainda não foi escolhido, o estúdio usa o primeiro vértice em ordem alfabética (e, para o sumidouro, o primeiro diferente da fonte). Os vértices escolhidos ganham um anel tracejado no canvas com a etiqueta RAIZ, DESTINO, FONTE ou SUMIDOURO.

Muitos algoritmos precisam decidir qual vizinho examinar primeiro. Por padrão a decisão segue a ordem alfabética dos rótulos, que é a convenção usada em sala. Quando o exercício pede outra ordem, monte-a em Sequência de visita:

• clique nos vértices na ordem desejada para acrescentá-los à sequência;
• o primeiro vértice escolhido vira a raiz quando nenhuma for definida acima (nos algoritmos de fluxo, ele é o primeiro vizinho tentado na busca);
• clique em um vértice da sequência para retirá-lo;
• os vértices que ficarem de fora seguem em ordem alfabética, depois dos escolhidos;
• o botão Padrão volta à ordem alfabética.

Os requisitos são verificados a cada alteração do grafo ou dos parâmetros. Se estiver tudo certo, aparece uma confirmação em verde; caso contrário, cada problema é listado em vermelho com a correção sugerida, e o botão Executar fica desabilitado.

O cabeçalho indica o algoritmo e a posição atual (por exemplo, Passo 4 de 23), com uma barra de progresso logo abaixo. Os controles são:

• Primeiro passo

  Volta ao estado inicial.

• Passo anterior

  Recua uma iteração.

• Reproduzir / pausar

  Avança sozinho no ritmo escolhido. No fim, recomeça do primeiro passo.

• Próximo passo

  Avança uma iteração.

• Último passo

  Pula para o resultado final.

• Limpar

  Descarta a execução e devolve o canvas às cores originais.

O controle deslizante salta direto para qualquer passo. Qualquer navegação manual pausa a reprodução automática. As velocidades disponíveis são:

O card principal traz o título da decisão tomada (por exemplo, “Aresta tensa (A, C): relaxada”), a justificativa com os valores envolvidos e, quando faz sentido, métricas como a ordem de visita, a iteração corrente ou o valor do fluxo. Abaixo dele aparecem as estruturas auxiliares do algoritmo.

As tabelas reproduzem as do quadro: dist e pred, tempos de descoberta e término, matrizes de Floyd-Warshall, fluxo e capacidades residuais, entre outras. Linhas coloridas indicam o papel de cada entrada no passo atual:

No último passo surge o card Conclusões, em verde, que interpreta o resultado: distâncias finais e caminho recuperado, peso total da árvore geradora, valor do fluxo máximo e o corte correspondente, componentes encontrados, ordem topológica, número de cores usadas. É o resumo para conferir com a sua resposta.