SGB book cover

Stanford GraphBase

 

O Stanford GraphBase (SGB) é uma plataforma para computação combinatória desenvolvida por Donald E. 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 uma grande variedade de grafos 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; fiz uma tradução livre do capítulo How to read CWEB programs do livro que descreve o SGB.

A título de curiosidade, veja a página SGB do Stony Brook Algorithms Repository, que Steven Skiena mantém em Nova Iorque.

 

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 COMENTÁRIOS 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 ou 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. 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 o header file apropriado. 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.

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

 

MÓDULO COMENTÁRIOS
LADDERS Determina um caminho mínimo entre quaisquer duas palavras de um grafo gerado por words.  A documentação é muito detalhada.
WORD_COMPONENTS Determina os componentes conexos de um grafo gerado por words.  O módulo é curto e simples.
BOOK_COMPONENTS Determina os bicomponentes (= componentes 2-conexos) de um grafo gerado por books.
MILES_SPAN Determina 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.

 

Lista de todos os módulos

Módulos de apoio


GB_GRAPH  [.w]
GB_FLIP  [.w]
GB_SORT  [.w]
GB_DIJK   [.w]
GB_IO  [.w]
GB_SAVE  [.w]
TEST_SAMPLE  [.w]

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


QUEEN  [.w
LADDERS  [.w]
MILES_SPAN  [.w]
BOOK_COMPONENTS  [.w]
WORD_COMPONENTS  [.w
ROGET_COMPONENTS  [.w]
ECON_ORDER  [.w]
FOOTBALL  [.w]
ASSIGN_LISA  [.w]
GIRTH  [.w]
MULTIPLY  [.w]
TAKE_RISC  [.w]

Módulos do tipo 1 (geradores)


GB_BASIC  [.w]
GB_RAND  [.w]  [errata]
GB_WORDS  [.w]
GB_ROGET  [.w]
GB_BOOKS  [.w]
GB_MILES  [.w]
GB_ECON  [.w]
GB_GAMES  [.w]
GB_GATES  [.w]
GB_LISA  [.w]
GB_PLANE  [.w]
GB_RAMAN  [.w]

 


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 a partir do trabalho de Ricardo Ueda. Ele pode ser usado e copiado desde que as condições do GNU Public License sejam respeitadas.

 


O livro

O SGB está detalhadamente descrito no livro

Donald E. Knuth,
The Stanford GraphBase: A Platform for Combinatorial Computing,
ACM Press e Addison-Wesley, 1993.

O livro contém o código fonte de todos os módulos do SGB, escrito em CWEB.  Fiz uma cópia local da errata do livro em janeiro de 2001; também copiei o adendo à errata que aparece na homepage do livro. O software correspondente já foi corrigido. (A propósito, o uso da linguagem C merece alguns esclarecimentos técnicos.)

 


Cópias do software

O software do SGB pode ser obtido no servidor ftp da Universidade de Stanford (veja arquivo sgb.tar.gz).

 


Uso do SGB na rede UNIX do IME

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 na rede UNIX do IME:

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

gcc -I/usr/local/sgb/include -L. -L/usr/local/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.

 

Uso do SGB na rede Linux do IME

Na rede Linux do IME, os vários arquivos do SGB estão nos seguintes diretórios:

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.   Você também pode automatizar o processo todo usando um Makefile.

 


Last modified: Thu Apr 19 08:03:49 BRT 2018
Paulo Feofiloff
IME-USP

Valid HTML 4.01 Transitional    Valid CSS!

Outros assuntos:   Análise de Algoritmos  |  Minicurso de Análise de Algoritmos  |  Algoritmos de Aproximação  |  Projeto de Algoritmos em C  |  Estruturas de Dados  |  Uma Introdução Sucinta à Teoria dos Grafos  |  Exercícios de Teoria dos Grafos  |  Fluxo em Redes  |  Digrafos  |  Algoritmos em Grafos com Stanford GraphBase  |  Algoritmos para Grafos via Sedgewick  |  Algoritmos de Programação Linear  |  Literate Programming & CWEB  |  O que é uma prova?  |  Opiniões e notícias