SGB book cover

Stanford GraphBase

O Stanford GraphBase, ou SGB, é uma plataforma para computação combinatória desenvolvida por Donald Knuth na Universidade de Stanford.  Veja o extended abstract preparado por Knuth.   O SGB é um pacote de software que contém dois tipos de módulos (chame-os de programas se preferir):

  1. módulos que geram grafos muito variados e interessantes;
  2. módulos que resolvem certos problemas combinatórios sobre alguns dos grafos gerados pelos módulos do tipo 1.

Todos os módulos foram escritos em CWEB (veja minha página sobre o CWEB). Essa linguagem permite preparar programas em C integrados com detalhada documentação.

O SGB está descrito no livro The Stanford GraphBase: A Platform for Combinatorial Computing de Donald Knuth (ACM Press e Addison-Wesley, 1993).  O capítulo How to read CWEB programs (veja minha tradução livre) explica como ler os programas.

Módulos do tipo 1

Cada módulo do tipo 1 define uma função geradora de grafos. Alguns dos módulos definem várias funções geradoras inter-relacionadas. Cada função geradora tem parâmetros que permitem especificar o tamanho e outras características do grafo. Eis alguns exemplos de funções:

FUNÇÃO DESCRIÇÃO MÓDULO
words Cada vértice é uma palavra de 5 letras em inglês. Há um arco entre duas palavras se elas diferem em exatamente uma das 5 posições. O usuário pode selecionar n das palavras, com base em diversos critérios. GB_WORDS
miles Gera grafos baseados nas distâncias rodoviárias entre um certo conjunto de cidades dos EUA e Canadá. Vértices são cidades; os arcos ligam cidades próximas. GB_MILES
games Gera grafos baseados nos jogos de college football (não confunda com futebol) americano da temporada de 1990. Cada vértice representa um time e os arcos representam os jogos. GB_GAMES
econ Gera grafos baseados no desempenho da economia americana em 1985. Cada vértice é um setor da economia. Arcos representam fluxo de bens e serviços entre setores. GB_ECON
books Gera grafos baseados em cinco livros famosos: Anna Karenina, David Copperfield, Ilíada, Huckleberry Finn e Os miseráveis. Cada vértice é um personagem do livro (você pode se restringir, de várias maneiras, a apenas alguns dos personagens). Um arco liga dois personagens se eles se encontram no livro. GB_BOOKS
random_graph Gera grafos (pseudo-) aleatórios de muitos tipos. Os parâmetros permitem escolher o tipo de grafo gerado. GB_RAND
board Os vértices são as casas de um tabuleiro de xadrez n-por-n. Arcos correspondem a movimentos de peças do jogo de xadrez. Você pode permitir vários tipos de movimentos que as regras usuais do xadrez proíbem. GB_BASIC
subsets Os vértices são subconjuntos de um certo tamanho do conjunto 1, 2, … , n. Há um arco ligando dois desses subconjuntos se a intersecção tem uma certa cardinalidade. GB_BASIC
binary Grafos baseados em rotações de árvores binárias. Os vértices são árvores binárias com n nós e altura limitada por h; duas árvores são ligadas por um arco se uma é o resultado da rotação da outra. GB_BASIC

Se o seu programa C usa alguma das funções definidas no SGB, ele deve incluir os header files apropriados. Por exemplo, se o seu programa usa as funções econ e subsets, ele deve ter as linhas

#include "gb_graph.h"
#include "gb_econ.h"
#include "gb_basic.h"

Módulos do tipo 2

Os módulos do tipo 2 também são conhecidos como programas de demonstração (demo programs).  Cada módulo é um programa executável:  basta digitar o nome do módulo seguido das eventuais opções.  Eis alguns exemplos:

MÓDULO DESCRIÇÃO
LADDERS Calcula um caminho mínimo entre quaisquer duas palavras de um grafo gerado por words.  A documentação é muito detalhada.
WORD_COMPONENTS Calcula os componentes conexos de um grafo gerado por words.  O módulo é curto e simples.
BOOK_COMPONENTS Calcula os bicomponentes (ou seja, 2-conexos) de um grafo gerado por books.
MILES_SPAN Encontra uma árvore geradora mínima de um grafo gerado por miles.
FOOTBALL Procura um caminho simples de peso máximo de um vértice dado a outro em um grafo gerado por games.
ECON_ORDER Procura um minimum feedback arc set em um grafo gerado por econ.

Os programas de demonstração não foram escritos para uso industrial, mas para ilustrar as possibilidades e o potencial do SGB.

Exercícios

. . . pleasure has probably been the main goal all along. But I hesitate to admit it, because computer scientists want to maintain their image as hard-working individuals who deserve high salaries. Sooner or later society will realise that certain kinds of hard work are in fact admirable even though they are more fun than just about anything else.
—D.E. Knuth

  1. Brinque com o SGB:  digite  ladders,  depois  order,  depois  chaos,  e veja o que acontece.
  2. Brinque com o SGB:  digite  football,  depois  Stanford,  depois  Harvard,  e veja o que acontece.
  3. Escreva uma versão brasileira do LADDERS.  Tenho um enorme arquivo com todas as palavras do português falado no Brasil. O arquivo foi gerado pelo prof. Yoshiharu Kohayakawa a partir do trabalho de Ricardo Ueda. Ele pode ser usado e copiado desde que as condições do GNU Public License sejam respeitadas.

Lista de todos os módulos

Segue a lista de todos os módulos do SGB. O link sob o nome de cada módulo leva à documentação do módulo. Já o link sob o .w leva ao arquivo .w que contém o código CWEB do módulo. É desse arquivo que o programa C e a documentação do módulo são extraídos.

Módulos de apoio:

Módulos do tipo 1 (geradores):

Módulos do tipo 2 (programas de demonstração):

Todos esse pacote pode ser obtido no servidor ftp da Universidade de Stanford (veja o arquivo sgb.tar.gz).

Uso do SGB numa instalação Linux

Ao compilar um módulo do SGB, ou algum programa C que usa o SGB, é preciso dizer ao compilador onde estão os vários header files e as funções da biblioteca do SGB  (a não ser, é claro, que essas informações já estejam no PATH).  Eis onde essas coisas estão no Linux:

Portanto, para que o gcc compile o seu programa xxx que usa funções do SGB você pode dizer

gcc -I/usr/include -L. -L/usr/lib xxx.c -o xxx -lgb

É claro que você pode acrescentar outros parâmetros, como -Wall, -pedantic, -ansi, etc.   Para automatizar o processo todo, você pode usar um Makefile.

Outros assuntos:   Projeto de Algoritmos em C  |  Livro Algoritmos em C  |  Desenvolvimento de Algoritmos  |  Estruturas de Dados  |  Literate Programming & CWEB  |  O que é uma prova?  |  Uma Introdução Sucinta à Teoria dos Grafos  |  Exercícios de Teoria dos Grafos  |  Graph Theory Exercises  |  Digrafos  |  Algoritmos em Grafos com Stanford GraphBase  |  Algoritmos para Grafos via Sedgewick  |  Curso Avançado de Teoria dos Grafos  |  Análise de Algoritmos  |  Minicurso de Análise de Algoritmos  |  Algoritmos de Programação Linear  |  Otimização Combinatória  |  Algoritmos de Aproximação