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:

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:

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.

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:

• os header files  (gb_graph.h, gb_words.h, etc.)  estão no diretório  /usr/include/
• a biblioteca de funções  libgb.a  do SGB  (que contém as funções miles, words, etc.)  está em  /usr/lib/
• o código executável dos programas de demonstração do SGB  (ladders, football, miles_span, etc.)  está em  /usr/bin/

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.