diagram.tpz
// Diagram compiler. Parses a directed-graph DSL, lays it out in layers (Sugiyama-lite) by longest
// path from a root, and renders an SVG. Written in Topaz. Deterministic and offline.
// Key identifiers: 간선=edge, 세그=segment, 출발=from, 도착=to, 끝=last, 글자정리=escapeChar,
// 줄정리=escapeText, 유효노드=validNode, 보기=view, 줄들=lines, 노드들=nodes, 더미=isDummy,
// 간선들=edges, 세그먼트들=segments, 조각들=parts, 체인=chain, 색인=index, 진입차수=inDegree,
// 층=layer, 대기열=queue, 머리=head, 위상수=topoCount, 현재=current, 실제개수=realCount,
// 총개수=totalCount, 최대층=maxLayer, 층카운트=layerCount, 층내=rowInLayer, 최대행=maxRow,
// 폭=width, 높이=height, 그림=svg.
//
// 다이어그램 컴파일러. 방향 그래프 DSL을 파싱해 층(레이어)으로 배치하고 SVG를 그립니다.
// A directed-graph DSL is parsed, laid out in layers, and rendered as SVG.
// 줄마다 `A -> B -> C` 형태의 간선 사슬을 적고, 노드 하나만 적으면 독립 노드입니다.
// One edge-chain per line like `A -> B -> C`; a lone node is an isolated node.
// 한 층을 넘는 긴 간선은 중간 층마다 더미 노드를 넣어 박스를 비켜 꺾이게 합니다.
// A long edge crossing more than one layer gets a dummy node per intermediate layer so it bends
// around boxes instead of slicing through them.
// 안 하는 것: 무방향 그래프, 힘기반 배치, 상호작용, 곡선/직교 라우팅, 첫 등장 순서를 넘는 교차 최소화.
// Won't do: undirected graphs, force layout, interactivity, curved/orthogonal routing, crossing
// minimization beyond first appearance.
// 순수하며 결정적입니다. 같은 입력은 같은 SVG를 냅니다(시계·난수 없음).
// Pure and deterministic. The same input yields the same SVG (no clock, no randomness).
type 간선 = { 출발: int, 도착: int } // an edge as a pair of node indices
// 닫힌 세그먼트 끝 태그. 노드 라벨은 입력 경계라 string으로 둔다.
// Closed segment-end tag. Node labels stay string at the input boundary.
type 세그끝 = "중간" | "끝"
type 세그 = { 출발: int, 도착: int, 끝: 세그끝 } // a one-layer segment; "끝" gets the arrowhead
// 레코드 리터럴은 문자열 리터럴을 넓히므로 세그먼트 생성은 헬퍼에서 좁힌다.
// Record literals widen string literals, so segment records narrow through this helper.
function 세그만들기(출발: int, 도착: int, 끝: 세그끝) -> 세그 {
{ 출발: 출발, 도착: 도착, 끝: 끝 }
}
function 글자정리(글: string) -> string {
// 사용자 입력(노드 이름)을 SVG에 넣기 전에 HTML 이스케이프합니다.
// HTML-escape user input (node names) before placing it in the SVG.
if 글 == "&" { "&" }
else if 글 == "<" { "<" }
else if 글 == ">" { ">" }
else if 글 == "\"" { """ }
else { 글 }
}
function 줄정리(원문: string) -> string {
let mut 출력 = ""
for 글 in 원문.scalars() { 출력 = 출력 + 글자정리(글) }
출력
}
function 유효노드(이름: string) -> bool {
// 노드 이름은 비어있지 않고, 공백이나 붙임표를 포함하지 않아야 합니다. `<` `>` `&` `"` 같은 글자는
// 라벨로 허용하되 렌더할 때 이스케이프합니다. 화살표 `->`는 이미 split으로 떼어낸 뒤라 여기엔 없습니다.
// A node name is non-empty with no whitespace or hyphen. Characters like `<` `>` `&` `"` are allowed
// as labels and escaped at render time. The `->` arrow is already removed by split before this runs.
let 글자들 = 이름.scalars()
if 글자들.length == 0 { return false }
for 글 in 글자들 {
if 글 == " " || 글 == "\t" || 글 == "-" { return false }
}
true
}
function 순환소속(시작: int, 인접: Array<Array<int>>, 개수: int) -> bool {
// 시작 노드에서 간선을 따라가 다시 시작 노드로 돌아오는 경로(길이 1 이상)가 있으면 순환에 속합니다.
// 순환을 가리키기만 하는 비순환 다리 노드는 자기 자신으로 못 돌아오므로 제외됩니다. 인접 리스트를 써서
// 매 확장이 O(차수)라 BFS 한 번이 O(V+E)입니다.
// A node is on a cycle iff there is a path of length >= 1 from it back to itself. An acyclic bridge
// node that only points into a cycle never returns to itself, so it is excluded. With the adjacency
// list each expansion is O(degree), so one BFS is O(V+E).
let mut 방문: Array<bool> = []
let mut 초기 = 0
while 초기 < 개수 { 방문.push(false); 초기 = 초기 + 1 }
let mut 큐: Array<int> = []
for 다음 in 인접[시작] { 큐.push(다음) }
let mut 머 = 0
while 머 < 큐.length {
let 현 = 큐[머]
머 = 머 + 1
if 현 == 시작 { return true }
if !방문[현] {
방문[현] = true
for 다음 in 인접[현] { 큐.push(다음) }
}
}
false
}
function 보기(입력: string) -> string {
let 줄들 = 입력.split("\n")
let mut 노드들: Array<string> = []
let mut 간선들: Array<간선> = []
let mut 줄번호 = 0
for 줄 in 줄들 {
줄번호 = 줄번호 + 1
let 다듬 = 줄.trim()
if 다듬 != "" {
// `->`로 나누면 빽빽한 `A->B`와 띄어쓴 `A -> B`가 똑같이 처리됩니다.
// Splitting on `->` treats compact `A->B` and spaced `A -> B` the same.
let 조각들 = 다듬.split("->")
let mut 체인: Array<int> = []
let mut 줄오류 = ""
for 조각 in 조각들 {
let 이름 = 조각.trim()
if !유효노드(이름) {
줄오류 = "{줄번호}번째 줄: 노드 이름이 잘못되었습니다. 형식은 A -> B -> C 입니다."
} else {
let 색인 = match 노드들.indexOf(이름) {
case Some(찾음) => 찾음
case None => { 노드들.push(이름); 노드들.length - 1 }
}
체인.push(색인)
}
}
if 줄오류 != "" { return "<div class=\"err\">{줄오류}</div>" }
let mut 칸 = 0
while 칸 + 1 < 체인.length {
let 출 = 체인[칸]
let 도 = 체인[칸 + 1]
// 자기 자신을 가리키는 간선(A -> A)도 간선으로 넣습니다. 1개짜리 순환이라 아래 순환 검사가 잡습니다.
// A self-edge (A -> A) is added as an edge. It is a one-node cycle that the cycle check below reports.
let mut 있음 = false
for 간 in 간선들 { if 간.출발 == 출 && 간.도착 == 도 { 있음 = true } }
if !있음 { 간선들.push({ 출발: 출, 도착: 도 }) }
칸 = 칸 + 1
}
}
}
let 실제개수 = 노드들.length
if 실제개수 == 0 {
return "<div class=\"meta\">그래프를 입력하세요. 예: A -> B -> C</div>"
}
// 위상 정렬(Kahn) + 최장경로 층 배치. 큐가 비었는데 못 넣은 노드가 남으면 순환입니다.
// Topological sort (Kahn) with longest-path layering. Leftover nodes after the queue drains = cycle.
let mut 진입차수: Array<int> = []
let mut 층: Array<int> = []
let mut 준비 = 0
while 준비 < 실제개수 { 진입차수.push(0); 층.push(0); 준비 = 준비 + 1 }
// 인접 리스트를 한 번만 만들어, 순환 검사 BFS가 매 단계 간선 전체를 다시 훑지 않게 합니다.
// Build the adjacency list once so the cycle-check BFS does not rescan all edges each step.
let mut 인접: Array<Array<int>> = []
let mut 인접초기 = 0
while 인접초기 < 실제개수 {
let mut 빈: Array<int> = []
인접.push(빈)
인접초기 = 인접초기 + 1
}
for 간 in 간선들 {
진입차수[간.도착] = 진입차수[간.도착] + 1
let mut 목록 = 인접[간.출발]
목록.push(간.도착)
인접[간.출발] = 목록
}
let mut 대기열: Array<int> = []
let mut 첫 = 0
while 첫 < 실제개수 {
if 진입차수[첫] == 0 { 대기열.push(첫) }
첫 = 첫 + 1
}
let mut 위상수 = 0
let mut 머리 = 0
while 머리 < 대기열.length {
let 현재 = 대기열[머리]
머리 = 머리 + 1
위상수 = 위상수 + 1
// 같은 인접 리스트를 재사용해 노드마다 간선 전체를 훑지 않습니다(Kahn이 O(V+E)).
// Reuse the adjacency list so Kahn does not rescan all edges per node (O(V+E)).
for 도착 in 인접[현재] {
진입차수[도착] = 진입차수[도착] - 1
if 층[도착] < 층[현재] + 1 { 층[도착] = 층[현재] + 1 }
if 진입차수[도착] == 0 { 대기열.push(도착) }
}
}
if 위상수 < 실제개수 {
// 위상 정렬이 모든 노드를 내보내지 못하면 순환이 있습니다. 실제로 순환에 "속한" 노드만 보고하려고
// 각 노드가 자기 자신으로 돌아오는 경로를 가지는지 확인합니다. 순환을 가리키기만 하는 비순환 다리
// 노드는 제외됩니다. 노드 색인은 첫 등장 순서라 보고도 그 순서를 따릅니다.
// The topological sort could not output every node, so there is a cycle. To report only nodes that
// are actually ON a cycle, test whether each node has a path back to itself. An acyclic bridge node
// that merely points into a cycle is excluded. Node indices follow first appearance, so the report
// does too.
let mut 남은 = ""
let mut 검사 = 0
while 검사 < 실제개수 {
// Kahn이 못 내보낸 잔여 노드(진입차수 > 0)만 검사해 호출 수를 줄입니다. 배치된 노드는 순환이 아닙니다.
// Only test residual nodes (진입차수 > 0) Kahn could not place; placed nodes are never on a cycle.
if 진입차수[검사] > 0 {
if 순환소속(검사, 인접, 실제개수) {
if 남은 != "" { 남은 = 남은 + ", " }
남은 = 남은 + 줄정리(노드들[검사])
}
}
검사 = 검사 + 1
}
return "<div class=\"err\">순환이 있어 배치할 수 없습니다: {남은}</div>"
}
// 긴 간선을 중간 층의 더미 노드로 펼쳐, 각 세그먼트가 정확히 한 층만 건너게 만듭니다.
// Expand long edges through dummy nodes at intermediate layers so each segment spans one layer.
let mut 더미: Array<bool> = []
let mut 더미초기 = 0
while 더미초기 < 실제개수 { 더미.push(false); 더미초기 = 더미초기 + 1 }
let mut 세그먼트들: Array<세그> = []
for 간 in 간선들 {
if 층[간.도착] == 층[간.출발] + 1 {
세그먼트들.push(세그만들기(간.출발, 간.도착, "끝"))
} else {
let mut 앞 = 간.출발
let mut 다음층 = 층[간.출발] + 1
while 다음층 < 층[간.도착] {
노드들.push("")
더미.push(true)
층.push(다음층)
let 새더미 = 노드들.length - 1
세그먼트들.push(세그만들기(앞, 새더미, "중간"))
앞 = 새더미
다음층 = 다음층 + 1
}
세그먼트들.push(세그만들기(앞, 간.도착, "끝"))
}
}
let 총개수 = 노드들.length
// 층 안에서의 순서(첫 등장 순)와 층별 개수를 구해 좌표를 정합니다. 더미는 실제 노드 다음 행에 놓입니다.
// Compute within-layer order (first appearance) and per-layer counts. Dummies sit in rows after the
// real nodes of their layer, so a bent long edge clears the boxes above it.
let mut 최대층 = 0
for 값 in 층 { if 값 > 최대층 { 최대층 = 값 } }
let mut 층카운트: Array<int> = []
let mut 초기 = 0
while 초기 <= 최대층 { 층카운트.push(0); 초기 = 초기 + 1 }
let mut 층내: Array<int> = []
let mut 채움 = 0
while 채움 < 총개수 { 층내.push(0); 채움 = 채움 + 1 }
let mut 자리 = 0
while 자리 < 총개수 {
let 이층 = 층[자리]
층내[자리] = 층카운트[이층]
층카운트[이층] = 층카운트[이층] + 1
자리 = 자리 + 1
}
let mut 최대행 = 0
for 칸수 in 층카운트 { if 칸수 > 최대행 { 최대행 = 칸수 } }
let 폭 = (최대층 + 1) * 180 + 40
let 높이 = 최대행 * 70 + 40
// SVG를 만듭니다. 노드 라벨만 사용자 값이라 이스케이프하고, 나머지 좌표는 정수입니다.
// Build the SVG. Only node labels are user values (escaped); the rest are integer coordinates.
let mut 그림 = "<svg class=\"diagram\" viewBox=\"0 0 {폭} {높이}\" width=\"{폭}\" height=\"{높이}\" xmlns=\"http://www.w3.org/2000/svg\">"
그림 = 그림 + "<defs><marker id=\"arrow\" markerWidth=\"9\" markerHeight=\"9\" refX=\"8\" refY=\"3\" orient=\"auto\"><path d=\"M0,0 L8,3 L0,6 Z\" fill=\"#111\"/></marker></defs>"
for 변 in 세그먼트들 {
let 출 = 변.출발
let 도 = 변.도착
// 모든 세그먼트는 한 층 박스의 오른쪽 끝(층x+140)에서 다음 층 박스의 왼쪽 끝(다음층x+20)까지,
// 두 층 사이의 빈 구간에서만 그립니다. 박스는 층 위치에만 있으므로 세그먼트가 박스를 관통할 수 없습니다.
// Every segment is drawn only in the gap between two layers, from a layer box right edge (층x+140)
// to the next layer box left edge (다음층x+20). Boxes sit only at layer positions, so a segment
// can never cross a box interior.
let 가로1 = 층[출] * 180 + 140
let 세로1 = 층내[출] * 70 + 40
let 가로2 = 층[도] * 180 + 20
let 세로2 = 층내[도] * 70 + 40
let 화살촉 = match 변.끝 {
case "끝" => " marker-end=\"url(#arrow)\""
case "중간" => ""
}
그림 = 그림 + "<line x1=\"{가로1}\" y1=\"{세로1}\" x2=\"{가로2}\" y2=\"{세로2}\" stroke=\"#111\" stroke-width=\"1.5\"{화살촉}/>"
}
// 더미는 자기 층의 박스 띠를 가로질러, 들어온 선(왼쪽 끝)과 나가는 선(오른쪽 끝)을 잇습니다.
// 자기 행에 그려지므로 같은 층의 실제 박스(다른 행)와 겹치지 않습니다.
// Each dummy bridges its incoming segment (ends at the left edge) and outgoing segment (starts at
// the right edge) with a horizontal across its layer band, drawn at its own row so it clears the
// real boxes (which are in other rows).
let mut 다리 = 0
while 다리 < 총개수 {
if 더미[다리] {
let 다리왼 = 층[다리] * 180 + 20
let 다리오 = 층[다리] * 180 + 140
let 다리세로 = 층내[다리] * 70 + 40
그림 = 그림 + "<line x1=\"{다리왼}\" y1=\"{다리세로}\" x2=\"{다리오}\" y2=\"{다리세로}\" stroke=\"#111\" stroke-width=\"1.5\"/>"
}
다리 = 다리 + 1
}
let mut 노 = 0
while 노 < 총개수 {
if !더미[노] {
let 가로 = 층[노] * 180 + 20
let 세로 = 층내[노] * 70 + 20
let 글자가로 = 가로 + 60
let 글자세로 = 세로 + 25
그림 = 그림 + "<rect x=\"{가로}\" y=\"{세로}\" width=\"120\" height=\"40\" fill=\"#fff\" stroke=\"#111\"/>"
그림 = 그림 + "<text x=\"{글자가로}\" y=\"{글자세로}\" text-anchor=\"middle\" font-family=\"ui-monospace, monospace\" font-size=\"13\" fill=\"#111\">" + 줄정리(노드들[노]) + "</text>"
}
노 = 노 + 1
}
그림 = 그림 + "</svg>"
"<div class=\"out\">" + 그림 + "</div>"
}
print(보기(input()))