Algoritmos em Grafos e Literate Programming na Internet

The philosophy of literate programming is explained fully in the book
Literate Programming, which also contains an extensive bibliography of the subject.
More than 30 example CWEB programs can be found in The Stanford GraphBase.
And I've made several additional programs available for downloading.

Fonte: http://www-cs-staff.Stanford.EDU/~knuth/cweb.html

Abaixo encontra-se uma lista de alguns sítios de Algoritmos em Grafos, Literate Programming e assuntos relacionados. Durante o andamento da disciplina a lista abaixo deve ser atualizada e expandida. Muitos dos links abaixo foram garimpados pelos professores e alunos de edições passadas de MAC0328. Se você encontrar algum sítio de Algoritmos em Grafos (ou de qualquer outra coisa) que você ache interessante, por favor, não deixe de me avisar.

Edições anteriores de MAC0328

Edição 2001, (prof. Paulo Feofiloff), edição 1999 (prof. José Coelho), edição 1998 (prof. José Augusto Ramos).

Literate Programming

Literate Programming FAQ.

Literate Programming

Literate programming is a methodology that combines a programming language with a documentation language, thereby making programs more robust, more portable, more easily maintained, and arguably more fun to write than programs that are written only in a high-level language. The main idea is to treat a program as a piece of literature, addressed to human beings rather than to a computer. The program is also viewed as a hypertext document, rather like the World Wide Web. (Indeed, I used the word WEB for this purpose long before CERN grabbed it!) This book is an anthology of essays including my early papers on related topics such as structured programming, as well as the article in The Computer Journal that launched Literate Programming itself. The articles have been revised, extended, and brought up to date.

Quick introduction to literate programming by Chris Lee

Literate programming is an approach to programming which emphasises that programs should be written to be read by people as well as compilers. From a purist standpoint, a program could be considered a publishable-quality document that argues mathematically for its own correctness. A different approach is that a program could be a document that teaches programming to the reader through its own example. A more casual approach to literate programming would be that a program should be documented at least well enough that someone could maintain the code properly and make informed changes in a reasonable amount of time without direct help from the author. At the most casual level, a literate program should at least make its own workings plain to the author of the program so that at least the author can easily maintain the code over its lifetime.

Programs to Read (by D.E. Knuth)

I write lots of CWEB programs, primarily for my own edification. If there is sufficient interest, I'll make a large subset of them available via the Internet. For now, I'm listing only a few. The first two show (by quite different methods) that exactly 2,432,932 knight's tours are unchanged by 180-degree rotation of the chessboard. The third was used to compute some of the tables in Axioms and Hulls that several people have asked about. The fourth was used in one of my otherwise unpublished lectures in the Computer Musings series. The next few were requested by members of the Academy of Recreational Mathmaticians in Japan. And so on.

Note: Many of my programs, including the first two samples, use the conventions and library of The Stanford GraphBase.

Donald E. Knuth's Home Page

Literate programming

Articles, FAQ, books, and bibliography
Manuals for literate programming tools
Examples of literate programs
The best of comp.programming.literate
Download tools and utilities
Recommendation for literate programming


The Stanford GraphBase: A Platform for Combinatorial Computing

This award-winning book demonstrates the art of literate programming with more than 30 examples. Each example is a programmatic essay: a short story that can be read and enjoyed by human beings as readily as it can be read and interpreted by machines. The programs contain state-of-the-art explanations of many important algorithms and data structures. They also define a workbench for combinatorial computing, and standard sets of data that can be used for benchmark tests of competing methods, as well as demonstration programs and games that make use of the data.

Hundreds of example programs that use The Stanford GraphBase will be distributed electronically as supplements to Volume 4 of The Art of Computer Programming when that volume is available, because Knuth will be using The Stanford GraphBase for many of the examples in that book.

Errata. A list of corrections to all known errors in this book appears in the file With these corrections, the book should be error-free. But (sigh) it probably isn't. Therefore I will gratefully pay $2.56 to the first person who finds and reports anything that remains technically, historically, typographically, or politically incorrect. Please send suggested corrections to, or send snail mail to Prof. D. Knuth, Computer Science Department, Gates Building 4B, Stanford University, Stanford, CA 94305-9045 USA.


The CWEB System of Structured Documentation

CWEB is a version of WEB for documenting C, C++, and Java programs. WEB was adapted to C by Silvio Levy in 1987, and since then both Knuth and Levy have revised and enhanced the system in many ways, notably to support C++ and ANSI C. Thus CWEB combines TeX with today's most widely used professional programming languages.

If you are in the software industry and do not use CWEB but your competitors do, your competitors will soon overtake you---and you'll miss out on a lot of fun besides.

More comments about CWEB can be found in Daniel Mall's website for Literate Programming.

download the latest version of cweb.tar.gz (cweb-3.64.tar.gz)

CWEB Examples

A literate programming language is intended to improve the documentation abilities of the native programming language. Literate programming is the combination of documentation and source code together in a fashion suited for reading by human beings. Donald Knuth is the inventor of literate programming and a typesetting language named TeX. CWEB is a combination of C++, TeX, and CWEB. CWEB demonstrates the ideals of the literate programming approach.


Graph Theory
Página bastante rica de teoria dos grafos do prof. Stephen Locke na Florida Atlantic University. [Stephen meu colega na U. of Waterloo.]

An Overview of Graph Theory
Página de teoria dos grafos do Laboratório Leibnitz na França.

Graph Theory Lessons
Página do prof. Christopher Mawata na Universidade de Tennessee.  Inclui o programa Petersen que permite manipular grafos.

Units in Discrete Mathematics (SciMath Minnesota).

Graph Theory Tutorials
Sítio de ensino programado de teoria dos grafos do prof. Chris Caldwell na University of Tennessee at Martin.

Disciplina "Applied Graph Theory" do Prof. Bill Cherowitzo na Universidade do Colorado em Denver.

Teoria dos Grafos
Página do prof. Antonio Mariani na Universidade Federal de Sta Catarina.

Teoria dos Grafos
Página das profs. Graça Pimentel e Maria Cristina na USP de São Carlos. [Infelizmente escreve dígrafos, com acento, no lugar de grafos dirigidos.]

Algoritmos e Teoria dos Grafos
Página da disciplina CI065-A, ministrada por Michel Gagnon na Universidade Federal do Paraná.

Algoritmo de Dijkstra
Java applet que faz animação do célebre algoritmo do caminho mínimo. O programa foi escrito por Carla Laffra.

Programa IBM/PC para manipulação de grafos.  Criado por Dan Ashlock na Iowa State University. [Acho que não é atualizado desde 1996.]

Mais sítios

Eis uma lista adicional, de sítios provavelmente menos relevantes. Muitos dos links abaixo foram garimpados por alunos da edição 2000 de MAC328.

Disciplina de pós-graduação em Teoria dos Grafos. Segundo semestre de 2000.

Stony Brook Algorithms Repository
Repositório de algoritmos de Steven Skiena em Nova Iorque. Não é bem um sítio de teoria dos grafos, mas pode ser interessante para MAC328.  A propósito, veja o que Skiena diz do Stanford GraphBase.

Web Sites for Teaching Undergraduate Combinatorics/GraphTheory
Links para diversas disciplinas de matemática discreta (algumas já citadas acima).
Navegação no mapa da cidade de São Paulo. Encontra caminho mínimo entre dois pontos da cidade. 

Ecossistemas e Políticas Públicas 
O livro usa grafos [de maneira não muito sofisticada, eu acho] para modelar ecossistemas.

Graph Theory Resources
Mantido por Daniel Sanders. Parece ser mais voltado a pesquisadores que a estudantes. Parece que não está sendo atualizado.
Mantido por Jonathan Gross and Jay Yellen, autores do livro Graph Theory and Its Applications, (CRC Press, 1998). Parece que é o sítio do livro e nada mais.

Underworld of Graph Theory and Combinatorics
Página de Jörg Zuther na Universidade Técnica de Berlin.

World Combinatorics Exchange
Sítio conjunto com o Electronic Journal of Combinatorics.

Graph Theory
Página de não-sei-bem-quem não-sei-bem-onde. Inclui applet que permite desenhar grafos, determinar caminhos mínimos, coloração de vértices, etc.

Introdução à Teoria dos Grafos
Página do prof. Marcelo H. de Carvalho na Universidade Federal de Mato Grosso do Sul. 

Graph Template Library (GTL):
Biblioteca de classes C++ para algoritmos sobre grafos. An Extension of the STL (Standard Template Library) with C++ datastructures for graphs.

GDToolkit (Graph Drawing Toolkit)
Ferramenta para desenho e layout de grafos. Usa LEDA.

Library of Efficient Data Structures and Algorithms: a Platform for Combinatorial and Geometric Computing. Pacote profissional de estruturas de dados em C++; inclui estrutura de dados para grafos.
Cópia do manual na rede Unix do IME.

novo Boost Graph Library
"A fairly new C++ library for graph algorithms, called the Boost Graph Library (BGL). The BGL is novel among C++ graph libraries because it applies generic programming principles (like the Standard Template Library) to acheive more flexibility. The BGL itself includes the typical elementary algorithm, and a few more advanced algorithms. We hope that others find the BGL interface framework useful and build more algorithms using this approach." Veja livro The Boost Graph Library de Jeremy Siek, Lie-Quan Lee, e Andrew Lumsdaine.

XXI Congresso da Sociedade Brasileira de Computação. Veja, em particular, o CTIC-2001 (Concurso de Trabalhos de Iniciação Científica).

Página principal de Algoritmos em Grafos.
Last modified: Thu Feb 13 14:22:57 EDT 2003