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, 줄정리=escapeText,
// 유효노드=validNode, 보기=view, 줄들=lines, 노드들=nodes, 노드색인=nodeIndex, 더미=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).
record 간선 { 출발: int, 도착: int } // an edge as a pair of node indices
// 닫힌 세그먼트 끝 태그를 enum으로 둔다. 노드 라벨은 입력 경계라 string으로 둔다.
// Segment-end tag as a closed enum. Node labels stay string at the input boundary.
enum 세그끝 { 중간, 끝 }
record 세그 { 출발: int, 도착: int, 끝: 세그끝 } // a one-layer segment; 세그끝.끝 gets the arrowhead
function 줄정리(원문: string) -> string {
// 사용자 입력(노드 이름)을 SVG에 넣기 전에 HTML 이스케이프합니다. `&`를 먼저 바꿔야 새로 만든
// `&`를 다시 이스케이프하지 않습니다.
// HTML-escape user input (node names) before placing it in the SVG. Replace `&` first so the
// `&` it introduces is not escaped again.
원문.replace("&", "&").replace("<", "<").replace(">", ">").replace("\"", """)
}
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>>) -> 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 방문: Set<int> = Set.of()
let mut 큐: Array<int> = []
for 다음 in 인접[시작] { 큐.push(다음) }
let mut 머 = 0
while 머 < 큐.length {
let 현 = 큐[머]
머 += 1
if 현 == 시작 { return true }
if !(현 in 방문) {
방문.add(현)
for 다음 in 인접[현] { 큐.push(다음) }
}
}
false
}
function 보기(입력: string) -> string {
let 줄들 = 입력.split("\n")
let mut 노드들: Array<string> = []
// 노드 이름 -> 색인. 노드들이 첫 등장 순서(배치용)를 담고, 이 맵이 O(1) 인터닝을 맡습니다.
// Node name -> index. 노드들 holds first-appearance order (for layout); this map interns in O(1).
let mut 노드색인: Map<string, int> = Map.new()
let mut 간선들: Array<간선> = []
// 이미 넣은 간선 키("출->도") 집합으로 중복 간선을 O(1)에 걸러냅니다. 순서는 간선들이 유지합니다.
// Set of edge keys ("출->도") already added, to reject duplicate edges in O(1). 간선들 keeps order.
let mut 본간선: Set<string> = Set.of()
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 노드색인.get(이름) {
case Some(찾음) => 찾음
case None => { 노드들.push(이름); let 새 = 노드들.length - 1; 노드색인.insert(이름, 새); 새 }
}
체인.push(색인)
}
}
if 줄오류 != "" { return "<div class=\"err\">{줄오류}</div>" }
for 칸 in 0..<(체인.length - 1) {
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 키 = "{출}->{도}"
if !(키 in 본간선) {
본간선.add(키)
간선들.push(간선 { 출발: 출, 도착: 도 })
}
}
}
}
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> = []
for _ in 0..<실제개수 { 진입차수.push(0); 층.push(0) }
// 인접 리스트를 한 번만 만들어, 순환 검사 BFS가 매 단계 간선 전체를 다시 훑지 않게 합니다.
// Build the adjacency list once so the cycle-check BFS does not rescan all edges each step.
let mut 인접: Array<Array<int>> = []
for _ in 0..<실제개수 {
let mut 빈: Array<int> = []
인접.push(빈)
}
for 간 in 간선들 {
진입차수[간.도착] += 1
인접[간.출발].push(간.도착)
}
let mut 대기열: Array<int> = []
for 첫 in 0..<실제개수 {
if 진입차수[첫] == 0 { 대기열.push(첫) }
}
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 남은 = ""
for 검사 in 0..<실제개수 {
// Kahn이 못 내보낸 잔여 노드(진입차수 > 0)만 검사해 호출 수를 줄입니다. 배치된 노드는 순환이 아닙니다.
// Only test residual nodes (진입차수 > 0) Kahn could not place; placed nodes are never on a cycle.
if 진입차수[검사] > 0 {
if 순환소속(검사, 인접) {
if 남은 != "" { 남은 += ", " }
남은 += 줄정리(노드들[검사])
}
}
}
return "<div class=\"err\">순환이 있어 배치할 수 없습니다: {남은}</div>"
}
// 긴 간선을 중간 층의 더미 노드로 펼쳐, 각 세그먼트가 정확히 한 층만 건너게 만듭니다.
// Expand long edges through dummy nodes at intermediate layers so each segment spans one layer.
let mut 더미: Array<bool> = []
for _ in 0..<실제개수 { 더미.push(false) }
let mut 세그먼트들: Array<세그> = []
for 간 in 간선들 {
if 층[간.도착] == 층[간.출발] + 1 {
세그먼트들.push(세그 { 출발: 간.출발, 도착: 간.도착, 끝: 세그끝.끝 })
} else {
let mut 앞 = 간.출발
for 다음층 in (층[간.출발] + 1)..<층[간.도착] {
노드들.push("")
더미.push(true)
층.push(다음층)
let 새더미 = 노드들.length - 1
세그먼트들.push(세그 { 출발: 앞, 도착: 새더미, 끝: 세그끝.중간 })
앞 = 새더미
}
세그먼트들.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 최대층 = 층.reduce(0, (최대, 값) => if 값 > 최대 { 값 } else { 최대 })
let mut 층카운트: Array<int> = []
for _ in 0..<(최대층 + 1) { 층카운트.push(0) }
let mut 층내: Array<int> = []
for _ in 0..<총개수 { 층내.push(0) }
for 자리 in 0..<총개수 {
let 이층 = 층[자리]
층내[자리] = 층카운트[이층]
층카운트[이층] += 1
}
let 최대행 = 층카운트.reduce(0, (최대, 칸수) => if 칸수 > 최대 { 칸수 } else { 최대 })
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).
for 다리 in 0..<총개수 {
if 더미[다리] {
let 다리왼 = 층[다리] * 180 + 20
let 다리오 = 층[다리] * 180 + 140
let 다리세로 = 층내[다리] * 70 + 40
그림 += "<line x1=\"{다리왼}\" y1=\"{다리세로}\" x2=\"{다리오}\" y2=\"{다리세로}\" stroke=\"#111\" stroke-width=\"1.5\"/>"
}
}
for 노 in 0..<총개수 {
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>"
}
}
그림 += "</svg>"
"<div class=\"out\">" + 그림 + "</div>"
}
input() |> 보기 |> print