go-sgb

Donald Knuth의 Stanford GraphBase (SGB)를 한글 GWEB 문학적 프로그램으로 옮겨 Go로 짜는 프로젝트다. .w 문서가 일차 산출물이고, 여기서 gtangle로 Go 소스를, gweave+luatex로 한글 PDF 문서를 뽑아낸다.

구조

SGB는 세 층으로 구성되고, 이식도 그 구조를 따른다.

층	패키지/디렉터리	비고
커널	gbflip	난수
	gbio	데이터 파일 입출력
	gbgraph	그래프 자료구조
	gbsort	연결 리스트 정렬
생성기·유틸리티	gbbasic	표준 그래프 여섯 생성기
	gbbooks	문학 작품 인물 관계 그래프
	gbecon	미국 경제 부문 간 흐름 그래프
	gbgames	미식축구 점수 그래프
	gbgates	논리 회로(RISC·곱셈기) 게이트 그래프
	gblisa	모나리자 픽셀 행렬·평면·이분 그래프
	gbmiles	북아메리카 도시 간 거리 그래프
	gbplane	델로네 삼각분할 기반 평면 그래프
	gbraman	Ramanujan 그래프(사원수 기반)
	gbrand	무작위 그래프
	gbroget	Roget 유의어 사전 그래프
	gbsave	그래프 저장·복원
	gbwords	다섯 글자 낱말 그래프
	gbdijk	Dijkstra 최단경로 + 우선순위 큐
데모	demos/assign_lisa	배정 문제(헝가리 알고리즘)
	demos/book_components	이중연결 성분
	demos/econ_order	경제 부문 준삼각 순서
	demos/football	팀 사이 승리 사슬 찾기
	demos/girth	Ramanujan 그래프의 둘레·지름
	demos/ladders	낱말 사다리
	demos/miles_span	최소 신장 트리
	demos/multiply	곱셈 회로로 큰 수 곱하기
	demos/queen	퀸의 행마
	demos/roget_components	Roget 그래프의 강한 성분
	demos/take_risc	RISC 회로로 곱셈·나눗셈
설치 검증	test_sample	모든 생성기 표본 (저장소 루트)
	demos/word_components	낱말 그래프 연결 성분

패키지 디렉터리 이름은 패키지명과 같다(gbflip/gbflip.w → package gbflip). 각 패키지 .w는 본문(패키지.go)과 시험(패키지_test.go)을 함께 뽑는다 — demos/의 시연 프로그램에는 시험이 없다. 공유하는 GWEB 서식 힌트는 루트 gbtypes.w에 모아 @i로 끌어와 쓴다.

라이브러리 패키지(위 표의 gb…)의 tangle 산출물 .go·_test.go는 go get이 되도록 저장소에 함께 커밋한다. 그 밖의 산출물 — 데모와 루트 검증 프로그램의 .go, 그리고 모든 .tex·.pdf — 은 커밋하지 않는다(.gitignore 참고). 일차 산출물은 어디까지나 .w이고, gb…/*.go는 언제든 그 .w에서 다시 뽑아낼 수 있다.

설치와 사용

라이브러리로 바로 가져다 쓸 수 있다. gb… 패키지의 .go가 저장소에 들어 있어, 받는 쪽에서 GWEB 도구는 필요 없다. 쓸 패키지를 go get으로 받는다:

go get github.com/sjnam/go-sgb/gbgraph@latest

import (
    "github.com/sjnam/go-sgb/gbgraph"
    "github.com/sjnam/go-sgb/gbwords"
)

모듈 전체를 의존성에 더하려면 go get github.com/sjnam/go-sgb@latest를 쓴다.

빌드

GWEB 문학적 프로그래밍 도구(gtangle, gweave)와 한글 조판용 luatex(kotexgweb)가 설치되어 있어야 한다.

make            # tangle + go vet + go test
make tangle     # 각 .w -> .go (패키지는 + _test.go)
make test       # go vet + go test
make doc        # 각 .w를 조판해 .pdf로
make clean      # 생성물 삭제 (.w 원본과 data/는 남김)

표준 Go 도구도 그대로 쓸 수 있다. 라이브러리 패키지의 .go는 이미 들어 있고, 데모까지 빌드하려면 먼저 make tangle로 그 .go를 생성한다:

go build ./...
go test ./...
go test ./<pkg> -run TestName
go vet ./...

검증

데모 출력은 Knuth가 발표한 값과 cweb-sgb/test.correct, cweb-sgb/sample.correct에 대조해 확인한다. 루트의 test_sample은 거의 모든 생성기를 불러 그 표준 출력이 sample.correct와 바이트 단위로 일치하고, 부차 산출물 test.gb도 test.correct와 바이트 단위로 일치함을 확인했다(자료는 /usr/local/sgb/data에서 읽는다).

원본이 gb_typed_alloc으로 만들어 정점 배열 바로 뒤(vertices[7])에 얹는 stray 정점("Testing")은, gbgraph에 AllocVertex(SGB의 gb_typed_alloc에 대응)를 두어 재현했다. NewGraph가 정점 슬라이스에 여분 용량을 잡아 두므로 이 정점이 제자리로 이어 붙어, 기존 정점·호 포인터를 깨지 않으면서 Index로 참조되고 gbsave가 함께 저장한다.