STUDIO HAZE · jeniapp

Topaz source

Open by house policy. Topaz is our own language.

Topaz 5.20.2 · 63 files

apps/diagram/diagram.tpz

Topaz · 11292 B · Original file

// 다이어그램. 화살표로 적은 방향 그래프를 위상 정렬해 최장 경로 기준으로 층을 나누고 SVG 로 그립니다.

// 입력은 줄마다 `A -> B -> C` 같은 간선 사슬이고 노드 하나만 적은 줄은 독립 노드입니다. 노드 이름에는 공백과 붙임표를 쓸 수 없습니다.

// 출력은 SVG 를 담은 HTML 조각이고, 순환이 있으면 순환에 속한 노드를 첫 등장 순으로 적은 오류 조각입니다.

4// 같은 입력이면 인터프리터와 웹 빌드에서 바이트까지 같은 출력을 냅니다.

// 무방향 그래프, 힘 기반 배치, 곡선 연결선, 첫 등장 순서를 넘는 교차 줄이기는 하지 않습니다.

6// Diagram: layers a directed graph by longest path and renders it as SVG.

8record 그래프 { 노드들: Array<string>, 간선들: Array<간선> }

9record 선분 { 출발: int, 도착: int, 화살촉: bool }

10record 층배치 { 층들: Array<int>, 행들: Array<int>, 선분들: Array<선분>, 층수: int, 행수: int }

12let 빈입력안내 = "<div class=\"meta\">그래프를 입력하세요. 예: A -> B -> C</div>"

13let 화살촉표시 = " marker-end=\"url(#arrow)\""

// 공용 도우미 시작 (이스케이프 오류알림 간선 위상정렬결과 인접목록 위상정렬하기 순환소속인가 결과풀기)

// 여러 도구가 같은 원본을 씁니다. 여기서 고치지 않고 원본에서 고친 뒤 다시 생성합니다.

18// 사용자 입력을 HTML 에 넣기 전에 반드시 거칩니다.

19function 이스케이프(원문: string) -> string {

20 원문.replace("&", "&").replace("<", "<").replace(">", ">").replace("\"", """)

21}

23// 문구는 고정 문장이거나 이미 이스케이프한 값이어야 합니다.

24function 오류알림(문구: string) -> string {

25 "<div class=\"err\">{문구}</div>"

26}

28type 간선 = { 출발: int, 도착: int }

// 순서는 Kahn 대기열 순서, 층은 최장 경로 길이입니다. 남은 진입차수가 0 보다 큰 노드는 순환 때문에 놓지 못한 노드입니다.

31type 위상정렬결과 = { 순서: Array<int>, 층들: Array<int>, 남은진입차수: Array<int> }

// 한 번 만들어 두면 위상 정렬과 순환 검사가 노드마다 간선 전체를 다시 훑지 않습니다. 행 안의 순서는 간선 순서입니다.

34function 인접목록(노드수: int, 간선들: Array<간선>) -> Array<Array<int>> {

35 let mut 인접: Array<Array<int>> = [for i in 0..<노드수 => []]

36 for 연결 in 간선들 { 인접[연결.출발].push(연결.도착) }

37 인접

38}

40function 위상정렬하기(인접: Array<Array<int>>) -> 위상정렬결과 {

41 let n = 인접.length

42 let mut 진입차수 = [for i in 0..<n => 0]

43 for 도착들 in 인접 {

44 for 도착 in 도착들 { 진입차수[도착] += 1 }

45 }

46 let mut 층들 = [for i in 0..<n => 0]

47 let mut 대기열 = [for i in 0..<n if 진입차수[i] == 0 => i]

48 let mut 머리 = 0

49 while 머리 < 대기열.length {

50 let 현재 = 대기열[머리]

51 머리 += 1

52 for 도착 in 인접[현재] {

53 진입차수[도착] -= 1

54 층들[도착] = 층들[도착].atLeast(층들[현재] + 1)

55 if 진입차수[도착] == 0 { 대기열.push(도착) }

56 }

57 }

58 { 순서: 대기열, 층들: 층들, 남은진입차수: 진입차수 }

59}

// 순환을 가리키기만 하는 노드도 위상 정렬에서 남으므로 길이 1 이상의 경로로 자기 자신에게 돌아오는지 따로 봅니다.

62function 순환소속인가(시작: int, 인접: Array<Array<int>>) -> bool {

63 let mut 방문: Set<int> = Set.of()

64 // 인접 목록의 행에 직접 넣지 않도록 복사해서 시작합니다.

65 let mut 대기열 = 인접[시작].slice(0, 인접[시작].length)

66 let mut 머리 = 0

67 while 머리 < 대기열.length {

68 let 현재 = 대기열[머리]

69 머리 += 1

70 if 현재 == 시작 { return true }

71 if !(현재 in 방문) {

72 방문.add(현재)

73 for 다음 in 인접[현재] { 대기열.push(다음) }

74 }

75 }

76 false

77}

// 성공 값과 안내가 모두 바로 보여 줄 HTML 조각일 때 진입점에서 한 번 풉니다. 토파즈 과제 'Result 오류 쪽 변환과 풀기' 의 우회입니다.

80function 결과풀기(값: Result<string, string>) -> string {

81 match 값 {

82 case Ok(결과) => 결과

83 case Err(안내) => 안내

84 }

85}

87// 공용 도우미 끝

// 공백인가와 달리 CR 은 막지 않습니다. `<`, `&`, `"` 는 이름으로 받고 그릴 때 이스케이프합니다.

90function 노드이름인가(이름: string) -> bool {

91 이름 != "" && 이름.scalars().filter(글자 => 글자 == " " || 글자 == "\t" || 글자 == "-").length == 0

92}

// 빈 줄은 노드가 없는 사슬입니다. `->` 로 나누므로 붙여 쓴 `A->B` 와 띄어 쓴 `A -> B` 가 같습니다.

95function 사슬읽기(입력줄: string, 줄번호: int) -> Result<Array<string>, string> {

96 let 다듬은줄 = 입력줄.trim()

97 if 다듬은줄 == "" { return Ok([]) }

98 let 이름들 = 다듬은줄.split("->").map(조각 => 조각.trim())

99 if 이름들.filter(이름 => !노드이름인가(이름)).length > 0 {

100

    return Err(오류알림("{줄번호}번째 줄: 노드 이름이 잘못되었습니다. 형식은 A -> B -> C 입니다."))

101 }

102 Ok(이름들)

103}

104

105

// 노드 색인은 첫 등장 순서이고 층 안의 배치와 순환 보고가 이 순서를 따릅니다. 같은 간선은 한 번만 넣습니다.

106// 자기 자신을 가리키는 간선도 넣어 노드 하나짜리 순환으로 알립니다.

107function 그래프읽기(입력: string) -> Result<그래프, string> {

108 let 줄목록 = 입력.split("\n")

109 let mut 노드들: Array<string> = []

110 let mut 노드색인: Map<string, int> = Map.new()

111 let mut 간선들: Array<간선> = []

112 let mut 넣은간선: Set<string> = Set.of()

113 for 줄번호 in 0..<줄목록.length {

114 let 이름들 = 사슬읽기(줄목록[줄번호], 줄번호 + 1)?

115 let mut 사슬: Array<int> = []

116 for 이름 in 이름들 {

117 let 색인 = match 노드색인.get(이름) {

118 case Some(찾음) => 찾음

119 case None => {

120 노드색인.insert(이름, 노드들.length)

121 노드들.push(이름)

122 노드들.length - 1

123 }

124 }

125 사슬.push(색인)

126 }

127 for i in 1..<사슬.length {

128 let 키 = "{사슬[i - 1]}->{사슬[i]}"

129 if !(키 in 넣은간선) {

130 넣은간선.add(키)

131 간선들.push({ 출발: 사슬[i - 1], 도착: 사슬[i] })

132 }

133 }

134 }

135 Ok(그래프 { 노드들: 노드들, 간선들: 간선들 })

136}

137

138

// 한 층을 넘는 간선은 중간 층마다 가상 노드를 넣어 선분이 한 층씩만 건너게 합니다. 가상 노드는 실제 노드 뒤에 색인을 받습니다.

139

// 층 안의 행은 색인 순이라 가상 노드는 같은 층 실제 노드들 아래 행에 놓여 박스를 비켜 갑니다.

140function 배치하기(간선들: Array<간선>, 층들: Array<int>) -> 층배치 {

141 let mut 노드층들 = 층들.slice(0, 층들.length)

142 let mut 선분들: Array<선분> = []

143 for 연결 in 간선들 {

144 let mut 앞 = 연결.출발

145 for 중간층 in (층들[연결.출발] + 1)..<층들[연결.도착] {

146 노드층들.push(중간층)

147 선분들.push(선분 { 출발: 앞, 도착: 노드층들.length - 1, 화살촉: false })

148 앞 = 노드층들.length - 1

149 }

150 선분들.push(선분 { 출발: 앞, 도착: 연결.도착, 화살촉: true })

151 }

152 let 층수 = 노드층들.reduce(0, (최대, 층) => 최대.atLeast(층)) + 1

153 let mut 층별개수 = [for i in 0..<층수 => 0]

154 let mut 행들: Array<int> = []

155 for 노드층 in 노드층들 {

156 행들.push(층별개수[노드층])

157 층별개수[노드층] += 1

158 }

159 층배치 {

160 층들: 노드층들,

161 행들: 행들,

162 선분들: 선분들,

163 층수: 층수,

164 행수: 층별개수.reduce(0, (최대, 개수) => 최대.atLeast(개수)),

165 }

166}

167

168

// 층마다 가로 180, 행마다 세로 70 입니다. 박스는 층 칸의 20부터 140까지라 선분은 층 사이 빈 곳에서만 그려집니다.

169function 박스왼쪽(층: int) -> int {

170 층 * 180 + 20

171}

172

173function 박스오른쪽(층: int) -> int {

174 층 * 180 + 140

175}

176

177function 행가운데(행: int) -> int {

178 행 * 70 + 40

179}

180

181function 선그리기(x1: int, y1: int, x2: int, y2: int, 끝표시: string) -> string {

182 "<line x1=\"{x1}\" y1=\"{y1}\" x2=\"{x2}\" y2=\"{y2}\" stroke=\"#111\" stroke-width=\"1.5\"{끝표시}/>"

183}

184

185function 선분그리기(구간: 선분, 층들: Array<int>, 행들: Array<int>) -> string {

186 let 끝표시 = if 구간.화살촉 { 화살촉표시 } else { "" }

187

  선그리기(박스오른쪽(층들[구간.출발]), 행가운데(행들[구간.출발]), 박스왼쪽(층들[구간.도착]), 행가운데(행들[구간.도착]), 끝표시)

188}

189

190function 상자그리기(이름: string, x: int, y: int) -> string {

191 [

192 "<rect x=\"{x}\" y=\"{y}\" width=\"120\" height=\"40\" fill=\"#fff\" stroke=\"#111\"/>",

193

    "<text x=\"{x + 60}\" y=\"{y + 25}\" text-anchor=\"middle\" font-family=\"ui-monospace, monospace\" font-size=\"13\" fill=\"#111\">{이스케이프(이름)}</text>",

194 ].join("")

195}

196

197function 그리기(노드들: Array<string>, 배치: 층배치) -> string {

198 let 층들 = 배치.층들

199 let 행들 = 배치.행들

200 let 연결선들 = 배치.선분들.map(구간 => 선분그리기(구간, 층들, 행들))

201

  // 가상 노드는 자기 층의 박스 띠를 가로지르는 선으로 들어온 선분과 나가는 선분을 잇습니다.

202

  let 이음선들 = [for i in 노드들.length..<층들.length => 선그리기(박스왼쪽(층들[i]), 행가운데(행들[i]), 박스오른쪽(층들[i]), 행가운데(행들[i]), "")]

203

  let 상자들 = [for i in 0..<노드들.length => 상자그리기(노드들[i], 박스왼쪽(층들[i]), 행들[i] * 70 + 20)]

204 let 폭 = 배치.층수 * 180 + 40

205 let 높이 = 배치.행수 * 70 + 40

206 let 조각들 = [

207

    "<svg class=\"diagram\" viewBox=\"0 0 {폭} {높이}\" width=\"{폭}\" height=\"{높이}\" xmlns=\"http://www.w3.org/2000/svg\">",

208

    "<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>",

209 연결선들.join(""),

210 이음선들.join(""),

211 상자들.join(""),

212 "</svg>",

213 ]

214 "<div class=\"out\">" + 조각들.join("") + "</div>"

215}

216

217function 다이어그램(입력: string) -> Result<string, string> {

218 let 입력그래프 = 그래프읽기(입력)?

219 if 입력그래프.노드들.length == 0 { return Err(빈입력안내) }

220 let 인접 = 인접목록(입력그래프.노드들.length, 입력그래프.간선들)

221 let 정렬결과 = 위상정렬하기(인접)

222 let 못놓은노드들 = [for i in 0..<인접.length if 정렬결과.남은진입차수[i] > 0 => i]

223 if 못놓은노드들.length > 0 {

224

    let 순환노드들 = 못놓은노드들.filter(노드 => 순환소속인가(노드, 인접)).map(노드 => 이스케이프(입력그래프.노드들[노드]))

225 return Err(오류알림("순환이 있어 배치할 수 없습니다: {순환노드들.join(", ")}"))

226 }

227 Ok(그리기(입력그래프.노드들, 배치하기(입력그래프.간선들, 정렬결과.층들)))

228}

229

230input() |> 다이어그램 |> 결과풀기 |> print

231

SHA256 dfe5d027fb8ce398e5bd75b285e14aa6e5fbcb178a41aed48abc6d3e37634f0a