grafos

Biblioteca de grafos não-direcionados e ponderados em C99, sem nenhuma dependência além da biblioteca padrão. Você joga a descrição de um grafo na entrada padrão e ela responde sete perguntas sobre ele: quantos vértices e arestas tem, em quantos pedaços ele se parte, se dá para colorir com duas cores, qual o diâmetro de cada pedaço, quais vértices e quais arestas, se removidos, partem o grafo em dois.

$ make
$ ./teste < exemplos/teste5.in
grafo: Desordenado
10 vertices
7 arestas
4 componentes
não bipartido
diâmetros: 0 2 10 13
vértices de corte: a zzz
arestas de corte: 1 2 3 a aaa zzz abc zzz

---

Contexto: por que isto existe

Trabalho de disciplina de teoria dos grafos. O enunciado veio como código: o primeiro commit do repositório traz grafo.h, teste.c, o makefile e cinco pares exemplos/*.in / exemplos/*.out — a interface, o programa que a exercita e a saída que ela precisa produzir. Tudo o que veio depois é grafo.c, as 537 linhas que fazem as dez funções do cabeçalho existirem.

Isso muda o tipo de exercício. A assinatura não é negociável — diametros() devolve uma char * com os diâmetros separados por brancos em ordem não decrescente, e ponto. Não há espaço para "eu preferia devolver um vetor de int". O trabalho inteiro é escolher estruturas e algoritmos por trás de uma fronteira que já estava desenhada, e devolver exatamente as strings que os .out esperam, na ordem que eles esperam.

O makefile também é do enunciado, e ele briga: são 35 flags de aviso ligadas ao mesmo tempo — -Wconversion, -Wshadow, -Wcast-qual, -Wstrict-overflow=5, -Wunsafe-loop-optimizations, -fstack-protector-all. Os casts explícitos para size_t espalhados pelo código são resposta direta a -Wconversion; num projeto compilado com -Wall de rotina eles não estariam ali.

---

O que está implementado

As dez funções de grafo.h, todas em grafo.c. Nenhuma é stub:

Função	O que faz	Como
le_grafo	monta o grafo a partir de um FILE *	leitura linha a linha, aresta inserida nos dois sentidos
destroi_grafo	libera vértices e listas de adjacência	percurso da lista encadeada
nome	devolve o nome do grafo	campo da struct
n_vertices	conta vértices	percorre a lista de vértices
n_arestas	conta arestas	soma os graus e divide por 2
n_componentes	número de componentes conexas	BFS a partir de cada vértice ainda não visitado
bipartido	1 se o grafo é bipartido	BFS de 2-coloração; devolve 0 no primeiro par adjacente de mesma cor
diametros	diâmetro de cada componente, em ordem não decrescente	duplo Dijkstra (double sweep) por componente
vertices_corte	pontos de articulação, em ordem alfabética	DFS com tin/low (Tarjan)
arestas_corte	pontes, em ordem alfabética	DFS com tin/low, condição low[v] > tin[u]

Duas observações que o resultado torna visíveis:

• O peso importa. diametros soma pesos, não arestas. No teste1.in, o triângulo tem lados 12, 24 e 41, e o diâmetro sai 36 — o caminho um → dois → quatro é mais curto que a aresta direta de peso 41. Aresta sem peso na entrada vale 1.
• Vértice isolado tem diâmetro 0, e entra na lista como qualquer outra componente (é o 0 do diâmetros: 0 36).

---

A decisão que estrutura tudo: lista de adjacência

A escolha clássica em grafos é lista de adjacência contra matriz de adjacência. Aqui é lista — e não a versão de livro, o que tem consequências que vale a pena explicitar em vez de esconder.

O grafo é uma lista encadeada de vértices; cada vértice tem uma lista encadeada de arestas; e cada aresta guarda o vizinho pelo nome:

typedef struct aresta_t {
    char destino[MAX_NAME];   // o vizinho por NOME, não por ponteiro nem índice
    int peso;
    struct aresta_t *prox;
} aresta_t;

O que essa escolha compra. Memória proporcional a V + E, não a V²: um grafo esparso de mil vértices e mil arestas não paga um milhão de células vazias. E, principalmente, ela dispensa a etapa que a matriz obrigaria — mapear nome de vértice para índice antes de qualquer coisa. Como a entrada identifica vértices por string arbitrária (zzz, aaa, 1, sozinho) e não por número, a matriz exigiria uma tabela nome→índice construída na leitura. Guardar o nome dentro da aresta faz a leitura ficar direta: leu a linha, criou o que faltava, ligou.

O que ela custa. Caminhar de um vértice para o vizinho não é dereferenciar um ponteiro: é varrer a lista de vértices comparando strings até achar aquele nome. Cada travessia de aresta custa O(V) comparações. Isso muda a complexidade de todo mundo:

Operação	Com esta representação	Com índice/ponteiro direto
le_grafo	O(V·E)	O(E) com hash nome→índice
n_componentes, bipartido	O(V·E)	O(V + E)
vertices_corte, arestas_corte	O(V·E)	O(V + E)
diametros (por componente)	O(V² + V·E)	O(E log V) com heap

O Dijkstra, além da busca por nome, seleciona o mínimo por varredura linear — sem fila de prioridade —, o que já valeria O(V²) sozinho.

O que eu faria diferente. O consenso é que a lista está certa para grafo esparso; o erro é a aresta apontar para um nome. Duas correções, em ordem de retorno:

1. Guardar o índice do vizinho (ou o ponteiro vertice_t *) na aresta, e resolver nome→índice uma única vez, na leitura, com uma tabela hash. Sozinha, essa mudança derruba o fator O(V) de toda travessia e devolve BFS e DFS ao seu O(V + E) de livro.
2. Trocar a seleção linear do Dijkstra por um heap binário.

Nada disso muda uma linha de grafo.h: é exatamente o tipo de reforma que a fronteira fixa do enunciado permitia — e não fazer foi decisão de prazo, não descoberta posterior.

A segunda decisão: diâmetro por heurística, não exato

Diâmetro exato pede todos os pares de caminhos mínimos: Floyd-Warshall em O(V³), ou um Dijkstra por vértice. O código faz duplo Dijkstra: parte de um vértice qualquer, acha o mais distante u, roda de novo a partir de u e devolve a maior distância encontrada. São dois Dijkstras por componente em vez de V.

O preço é honesto e precisa ser dito: o double sweep é exato em árvore, e no grafo com ciclo é apenas um limite inferior. Como ele sempre devolve a distância entre dois vértices que existem de fato, nunca superestima — mas pode ficar abaixo do diâmetro verdadeiro. Nos cinco exemplos do enunciado o valor bate; isso não é prova de nada além dos cinco exemplos.

---

Formato de entrada

O grafo é lido de stdin, no formato descrito em grafo.h:

• a primeira linha útil é o nome do grafo;
• linhas iniciadas por // são comentários e são ignoradas; linhas em branco também;
• uma aresta é xxx -- yyy ppp, onde ppp é um inteiro opcional (o peso); sem peso, a aresta vale 1;
• um vértice sozinho na linha é um vértice isolado;
• vértice que aparece numa aresta não precisa ser declarado antes.

// o nome do grafo
triângulo_com_vértice

// uma lista com três arestas e seus pesos
um -- dois 12
dois -- quatro 24
quatro -- um 41

// um vértice isolado
três

O cabeçalho é explícito quanto a isto: a entrada é suposta bem formada e não há validação. Entrada torta é comportamento indefinido, por especificação — não por esquecimento.

---

Como compilar e rodar

Só precisa de um compilador C e make:

make                          # gera o executável ./teste
./teste < exemplos/teste1.in  # roda sobre um exemplo
make clean                    # remove ./teste e os .o

Para conferir contra a saída esperada que veio com o enunciado:

for f in exemplos/*.in; do
  diff <(./teste < "$f") "${f%.in}.out" > /dev/null \
    && echo "ok   $f" \
    || echo "FALHA $f"
done

Os cinco .in cobrem casos diferentes de propósito: triângulo com vértice isolado, caminho P5 (todo mundo é ponte), grafo enterrado em comentários e linhas vazias, K4 completo (nenhuma ponte, nenhum ponto de articulação) e um grafo desordenado com quatro componentes de formatos distintos.

---

Por dentro dos algoritmos

Componentes e bipartição são a mesma BFS com propósitos diferentes. A bipartição pinta o vértice inicial com a cor 1 e todo vizinho com a cor oposta; achou dois adjacentes da mesma cor, existe ciclo ímpar e o grafo não é bipartido — retorna 0 na hora, sem terminar a varredura. Componentes conta quantas vezes precisou recomeçar a BFS de um vértice ainda não visitado.

Vértices de corte e pontes saem da mesma ideia de Tarjan: uma DFS que anota, para cada vértice, o tempo de descoberta tin[u] e o low[u] — o menor tin alcançável descendo pela subárvore e subindo por no máximo uma aresta de retorno. A diferença entre os dois resultados é uma comparação:

• low[v] >= tin[u] e u não é raiz → u é ponto de articulação (a raiz é caso à parte: é articulação se tiver mais de um filho na árvore DFS);
• low[v] > tin[u] → a aresta u—v é ponte (estrito: não há nenhum desvio de volta).

Ordenação da saída. Vértices e arestas de corte saem alfabéticos via qsort, e o par de cada ponte é ordenado internamente antes de virar string, para que {z, a} sempre apareça como a z. Os diâmetros são ordenados por um par de laços aninhados — ordenação O(n²) sobre uma lista que tem uma entrada por componente.

---

Limitações conhecidas

• Teto de 1024 vértices, e sem verificação. MAX_VERTICES é 1024, as filas de BFS são vertice_t *fila[1024] e os vetores de tin/low/visitado têm esse tamanho fixo. Passar disso não dá erro: transborda.
• Nome de vértice até 127 caracteres, também sem verificação — a leitura usa %s sem largura sobre buffers de 128 bytes.
• arestas_corte aloca ~134 MB de uma vez. O buffer de saída é MAX_VERTICES * MAX_VERTICES * MAX_NAME bytes, dimensionado para um caso que não pode acontecer (um grafo simples com V=1024 tem no máximo V−1 pontes). Uma matriz de adjacência int de 1024×1024 ocuparia 4 MB — trinta vezes menos que o buffer temporário desta função. É o ponto mais indefensável do código.
• vertices_corte estima 64 bytes por nome (malloc(n_cortes * 64)) enquanto o nome pode ter 128. Nomes longos estouram o buffer. E, quando não há nenhum vértice de corte — caso real, teste1, teste3 e teste4 — o malloc(0) é seguido de escrita do terminador em res[0].
• Arestas paralelas quebram a detecção de pontes. A DFS ignora o vizinho pelo vértice pai (if (v == parent) continue), não pela aresta percorrida. Com duas arestas entre u e v, nenhuma das duas é ponte, mas o código as reporta como se fossem.
• Pesos negativos não são suportados. O cabeçalho especifica peso inteiro não negativo, o parser aceita %d sem checar sinal, e Dijkstra dá resposta errada em silêncio se um negativo entrar.
• O nome do grafo é lido num buffer de 128 bytes enquanto a especificação admite linhas de até 2047 caracteres; e o teste de comentário dessa leitura específica rejeita qualquer linha cujo segundo caractere seja /, então um grafo chamado a/b seria descartado como comentário.
• destroi_grafo libera o grafo, não as strings. As char * devolvidas por diametros, vertices_corte e arestas_corte são do chamador — teste.c as libera uma a uma, e quem usar a biblioteca precisa fazer o mesmo.
• Grafo dirigido não é suportado, por decisão de escopo: le_grafo insere toda aresta nos dois sentidos.

---

Estrutura

.
├── grafo.h        interface e especificação do formato de entrada (veio do enunciado)
├── grafo.c        a implementação inteira — 537 linhas
├── teste.c        programa de teste: lê stdin, imprime as oito linhas de saída
├── makefile       C99 sob 35 flags de aviso
├── readme.txt     o README original entregue com o trabalho
└── exemplos/      cinco pares .in / .out (entrada e saída esperada)