cos 242 · teoria dos grafos · ufrj 2026/2

graphman.

Lucas Pacheco·Rogério Santana

representações · BFS e DFS · componentes · diâmetro

Rust 2024
WebAssembly
WebGPU · vgpu
Next.js
Vercel

01

Arquitetura

entrada

grafo.txt

n, depois uma aresta por linha

EdgeListordenada, sem laços, sem duplicatas

graphman// um crate Rust, sem dependências no núcleo

AdjacencyListO(n + m) palavras
AdjacencyMatrixO(n²) bits
Csrdois arrays

BFS·DFS·distância·componentes·diâmetro

// escritos uma vez sobre o trait Graph, o usuário escolhe o armazenamento

graphman-clios estudos de caso

graphman-wasmo observatório

02

Decisões

01
Normalizar uma vez
// laços e duplicatas saem na leitura
02
Buscas observáveis
// um visitor para a busca no meio do nível
03
Nada alocado duas vezes
// o reset só toca o que a última busca acendeu
04
Orçamento, não crash
// 17,6 GB virou um erro tipado e uma célula
05
Diâmetro de quatro jeitos
// as BFS que cada método gastou no Grafo 4

03

Benchmark

lista de adjacência
matriz de bits
CSR

GrafoTamanhoMemóriaBFS médiaDFS médiaComp.Diâmetro

Grafo 110.0K vértices109.9K arestas2.4 MB13.2 MB2.1 MB386 µs1.65 ms206 µs564 µs2.25 ms516 µs15

Grafo 249.9K vértices1.30M arestas13.6 MB299.2 MB11.7 MB914 µs11.58 ms749 µs2.33 ms16.36 ms2.35 ms1020

Grafo 3375.0K vértices765.6K arestas19.1 MBprecisa de 16.37 GB11.4 MB4.14 ms·3.54 ms9.25 ms·7.06 ms222

Grafo 4375.0K vértices8.19M arestas78.9 MBprecisa de 16.37 GB68.0 MB21.31 ms·18.82 ms31.53 ms·27.99 ms25

Grafo 54.84M vértices13.2M arestas258.5 MBprecisa de 2.67 TB157.2 MB95.18 ms·86.19 ms303 ms·225 ms559

Grafo 64.84M vértices46.5M arestas519.5 MBprecisa de 2.67 TB411.4 MB192 ms·163 ms332 ms·270 ms519

Apple M5, 16.00 GB. Footprint do processo após carregar; média de 100 buscas de raízes distintas, sem leitura nem escrita. ≥ marca um limite inferior.

Abrir os estudos de caso

04

Teste no seu navegador

graphman-ufrj.vercel.app

graphman.

aponte a câmera

graphman-ufrj.vercel.app