;============================================================
;  アルゴリズム 21〜25: グラフ
;    21. Dijkstra (最短経路)
;    22. Bellman-Ford (負辺対応)
;    23. Floyd-Warshall (全点対最短路)
;    24. Union-Find + Kruskal (MST)
;    25. Topological Sort (Kahn)
;============================================================

#include "hsp3cl_net_64.as"

; ----- 21. Dijkstra (隣接行列版 O(V^2)) -----
#module
#deffunc dijkstra array _mat, int _n, int _src, array _dist, \
	local _i, local _u, local _min_d, local _INF, local _w, local _it
	_INF = 0x7FFFFFFF
	dim _dist, _n
	dim _done, _n
	repeat _n : _dist(cnt) = _INF : loop
	_dist(_src) = 0
	repeat _n
		_u = -1 : _min_d = _INF
		repeat _n
			_i = cnt
			if _done(_i) == 0 : if _dist(_i) < _min_d : _min_d = _dist(_i) : _u = _i
		loop
		if _u == -1 : break
		_done(_u) = 1
		repeat _n
			_i = cnt
			_w = _mat(_u * _n + _i)
			if _w > 0 : if _done(_i) == 0 : if _dist(_u) + _w < _dist(_i) : _dist(_i) = _dist(_u) + _w
		loop
	loop
	return
#global

; ----- 22. Bellman-Ford -----
#module
#deffunc bellman_ford array _u, array _v, array _w, int _m, int _n, int _src, array _dist, \
	local _i, local _j, local _INF
	_INF = 0x7FFFFFFF
	dim _dist, _n
	repeat _n : _dist(cnt) = _INF : loop
	_dist(_src) = 0
	repeat _n - 1
		repeat _m
			_j = cnt
			if _dist(_u(_j)) != _INF : if _dist(_u(_j)) + _w(_j) < _dist(_v(_j)) : _dist(_v(_j)) = _dist(_u(_j)) + _w(_j)
		loop
	loop
	return
#global

; ----- 23. Floyd-Warshall -----
#module
#deffunc floyd_warshall array _d, int _n, \
	local _k, local _i, local _j, local _INF, local _via
	_INF = 0x7FFFFFFF
	repeat _n
		_k = cnt
		repeat _n
			_i = cnt
			repeat _n
				_j = cnt
				if _d(_i * _n + _k) != _INF : if _d(_k * _n + _j) != _INF {
					_via = _d(_i * _n + _k) + _d(_k * _n + _j)
					if _via < _d(_i * _n + _j) : _d(_i * _n + _j) = _via
				}
			loop
		loop
	loop
	return
#global

; ----- 24. Union-Find + Kruskal -----
#module
#deffunc uf_init array _par, int _n, local _i
	dim _par, _n
	repeat _n : _par(cnt) = cnt : loop
	return

#defcfunc uf_find array _par, int _x, local _r, local _t, local _x2
	_r = _x
	repeat
		if _par(_r) == _r : break
		_r = _par(_r)
	loop
	_x2 = _x
	repeat
		if _par(_x2) == _r : break
		_t = _par(_x2) : _par(_x2) = _r : _x2 = _t
	loop
	return _r

#defcfunc uf_union array _par, int _x, int _y, local _a, local _b
	_a = uf_find(_par, _x) : _b = uf_find(_par, _y)
	if _a == _b : return 0
	_par(_a) = _b
	return 1

#deffunc kruskal array _w, array _u, array _v, int _m, int _n, var _total, var _picked, \
	local _i, local _j, local _idx, local _tmp, local _par_work
	dim _ord, _m
	repeat _m : _ord(cnt) = cnt : loop
	; selection sort by weight
	repeat _m - 1
		_i = cnt
		repeat _m - 1 - _i
			_j = _i + 1 + cnt
			if _w(_ord(_i)) > _w(_ord(_j)) : _tmp = _ord(_i) : _ord(_i) = _ord(_j) : _ord(_j) = _tmp
		loop
	loop
	uf_init _par_work, _n
	_total = 0
	_picked = 0
	repeat _m
		_idx = _ord(cnt)
		if uf_union(_par_work, _u(_idx), _v(_idx)) {
			_total += _w(_idx)
			_picked++
		}
	loop
	return
#global

; ----- 25. Topological Sort (Kahn 法) -----
#module
#deffunc topo_sort array _edges, int _m, int _n, array _order, var _ok, \
	local _i, local _front, local _rear, local _u, local _v, local _k
	dim _indeg, _n
	repeat _m
		_v = _edges(cnt * 2 + 1)
		_indeg(_v)++
	loop
	dim _order, _n
	dim _q, _n
	_front = 0 : _rear = 0
	repeat _n
		_i = cnt
		if _indeg(_i) == 0 : _q(_rear) = _i : _rear++
	loop
	_k = 0
	repeat
		if _front >= _rear : break
		_u = _q(_front) : _front++
		_order(_k) = _u : _k++
		repeat _m
			if _edges(cnt * 2) == _u {
				_v = _edges(cnt * 2 + 1)
				_indeg(_v)--
				if _indeg(_v) == 0 : _q(_rear) = _v : _rear++
			}
		loop
	loop
	_ok = (_k == _n)
	return
#global

; ===== デモ =====
	mes "=== Dijkstra ==="
	N = 4
	dim mat, N * N
	mat(0) = 0 : mat(1) = 5 : mat(2) = 0 : mat(3) = 1
	mat(4) = 0 : mat(5) = 0 : mat(6) = 2 : mat(7) = 0
	mat(8) = 0 : mat(9) = 0 : mat(10)= 0 : mat(11)= 0
	mat(12)= 0 : mat(13)= 0 : mat(14)= 3 : mat(15)= 0
	dijkstra mat, N, 0, dist
	repeat N : mes strf("dist[%d] = %d", cnt, dist(cnt)) : loop

	mes ""
	mes "=== Bellman-Ford (含負辺) ==="
	dim bu, 4 : bu = 0, 0, 1, 2
	dim bv, 4 : bv = 1, 2, 2, 3
	dim bw, 4 : bw = 4, 5, -3, 4
	bellman_ford bu, bv, bw, 4, 4, 0, bdist
	repeat 4 : mes strf("bdist[%d] = %d", cnt, bdist(cnt)) : loop

	mes ""
	mes "=== Floyd-Warshall ==="
	INF = 0x7FFFFFFF
	M = 3
	dim fm, M * M
	fm(0) = 0   : fm(1) = 3   : fm(2) = INF
	fm(3) = INF : fm(4) = 0   : fm(5) = 1
	fm(6) = 7   : fm(7) = INF : fm(8) = 0
	floyd_warshall fm, M
	repeat M
		mes strf("[%d]: %d %d %d", cnt, fm(cnt * 3), fm(cnt * 3 + 1), fm(cnt * 3 + 2))
	loop

	mes ""
	mes "=== Kruskal MST ==="
	KM = 5 : KN = 4
	dim kw, KM : kw = 1, 3, 4, 2, 5
	dim ku, KM : ku = 0, 0, 1, 2, 2
	dim kv, KM : kv = 1, 2, 2, 3, 1
	kruskal kw, ku, kv, KM, KN, total, picked
	mes strf("MST total = %d (picked %d edges)", total, picked)

	mes ""
	mes "=== Topological Sort ==="
	; 0->1, 0->2, 1->3, 2->3
	dim tedges, 8 : tedges = 0,1, 0,2, 1,3, 2,3
	topo_sort tedges, 4, 4, order, tok
	sdim tline, 64
	tline = "topo order: "
	repeat 4 : tline += "" + order(cnt) + " " : loop
	tline += "(ok=" + tok + ")"
	mes tline
	end 0