Leonard Ritter
@lritter@mastodon.gamedev.place  ·  activity timestamp 2 weeks ago
.decl rel_cy(rel:symbol, src:symbol) // transitive closure of cyclical edges rel_cy(a, b) :- rel_dep(a,b), rel_dep_tc(b,a). rel_cy(a, c) :- rel_cy(a, b), rel_cy(b, c). .decl scc(group:number, rel:symbol) // strongly connected components scc(mnx, y) :- rel_cy(_, y), rel_id(y_id, y), mnx = min x_id : { rel_cy(x, y), rel_id(x_id, x), x_id <= y_id }.
.decl rel_cy(rel:symbol, src:symbol) // transitive closure of cyclical edges rel_cy(a, b) :- rel_dep(a,b), rel_dep_tc(b,a). rel_cy(a, c) :- rel_cy(a, b), rel_cy(b, c). .decl scc(group:number, rel:symbol) // strongly connected components scc(mnx, y) :- rel_cy(_, y), rel_id(y_id, y), mnx = min x_id : { rel_cy(x, y), rel_id(x_id, x), x_id <= y_id }.
.decl rel_cy(rel:symbol, src:symbol) // transitive closure of cyclical edges rel_cy(a, b) :- rel_dep(a,b), rel_dep_tc(b,a). rel_cy(a, c) :- rel_cy(a, b), rel_cy(b, c). .decl scc(group:number, rel:symbol) // strongly connected components scc(mnx, y) :- rel_cy(_, y), rel_id(y_id, y), mnx = min x_id : { rel_cy(x, y), rel_id(x_id, x), x_id <= y_id }.
Leonard Ritter
@lritter@mastodon.gamedev.place  ·  activity timestamp 2 weeks ago
.decl rel_cy(rel:symbol, src:symbol) // transitive closure of cyclical edges rel_cy(a, b) :- rel_dep(a,b), rel_dep_tc(b,a). rel_cy(a, c) :- rel_cy(a, b), rel_cy(b, c). .decl scc(group:number, rel:symbol) // strongly connected components scc(mnx, y) :- rel_cy(_, y), rel_id(y_id, y), mnx = min x_id : { rel_cy(x, y), rel_id(x_id, x), x_id <= y_id }.
.decl rel_cy(rel:symbol, src:symbol) // transitive closure of cyclical edges rel_cy(a, b) :- rel_dep(a,b), rel_dep_tc(b,a). rel_cy(a, c) :- rel_cy(a, b), rel_cy(b, c). .decl scc(group:number, rel:symbol) // strongly connected components scc(mnx, y) :- rel_cy(_, y), rel_id(y_id, y), mnx = min x_id : { rel_cy(x, y), rel_id(x_id, x), x_id <= y_id }.
.decl rel_cy(rel:symbol, src:symbol) // transitive closure of cyclical edges rel_cy(a, b) :- rel_dep(a,b), rel_dep_tc(b,a). rel_cy(a, c) :- rel_cy(a, b), rel_cy(b, c). .decl scc(group:number, rel:symbol) // strongly connected components scc(mnx, y) :- rel_cy(_, y), rel_id(y_id, y), mnx = min x_id : { rel_cy(x, y), rel_id(x_id, x), x_id <= y_id }.
Leonard Ritter
@lritter@mastodon.gamedev.place  ·  activity timestamp 2 weeks ago
.decl scc_dep(scc:number, src:number) // SCC dependency edges scc_dep(scc_a, scc_b) :- rel_dep(a, b), scc(scc_a, a), scc(scc_b, b), scc_a != scc_b. // SCC transitive closure .decl scc_dep_tc(scc:number, src:number, dist:number) scc_dep_tc(a, b, 1) :- scc_dep(a, b). scc_dep_tc(a, c, ab + bc) :- scc_dep_tc(a, b, ab), scc_dep_tc(b, c, bc). // topological order of SCC .decl scc_order(index:number, scc:number) scc_order(0, a) :- scc(a, _), !scc_dep(a, _). scc_order(mxi, a) :- scc(a, _), mxi = max i : { scc_dep_tc(a, _, i) }.
.decl scc_dep(scc:number, src:number) // SCC dependency edges scc_dep(scc_a, scc_b) :- rel_dep(a, b), scc(scc_a, a), scc(scc_b, b), scc_a != scc_b. // SCC transitive closure .decl scc_dep_tc(scc:number, src:number, dist:number) scc_dep_tc(a, b, 1) :- scc_dep(a, b). scc_dep_tc(a, c, ab + bc) :- scc_dep_tc(a, b, ab), scc_dep_tc(b, c, bc). // topological order of SCC .decl scc_order(index:number, scc:number) scc_order(0, a) :- scc(a, _), !scc_dep(a, _). scc_order(mxi, a) :- scc(a, _), mxi = max i : { scc_dep_tc(a, _, i) }.
.decl scc_dep(scc:number, src:number) // SCC dependency edges scc_dep(scc_a, scc_b) :- rel_dep(a, b), scc(scc_a, a), scc(scc_b, b), scc_a != scc_b. // SCC transitive closure .decl scc_dep_tc(scc:number, src:number, dist:number) scc_dep_tc(a, b, 1) :- scc_dep(a, b). scc_dep_tc(a, c, ab + bc) :- scc_dep_tc(a, b, ab), scc_dep_tc(b, c, bc). // topological order of SCC .decl scc_order(index:number, scc:number) scc_order(0, a) :- scc(a, _), !scc_dep(a, _). scc_order(mxi, a) :- scc(a, _), mxi = max i : { scc_dep_tc(a, _, i) }.
Leonard Ritter
@lritter@mastodon.gamedev.place  ·  activity timestamp 2 weeks ago
# will produce following topological order and lifetimes: --------------- rel_order =============== 0 i 1 b 1 a 2 c 2 d 3 o =============== --------------- rel_lt =============== 1 i 2 b 2 a 3 o 3 c 3 d =============== struct i (x : s32) struct a (x : s32) struct b (x : s32) struct c (x : s32) struct d (x : s32) struct o (x : s32) a x if (i x) a x if (b x) b x if (a x) c x if (b x) d x if (c x) c x if (d x) o x if (d x)
# will produce following topological order and lifetimes: --------------- rel_order =============== 0 i 1 b 1 a 2 c 2 d 3 o =============== --------------- rel_lt =============== 1 i 2 b 2 a 3 o 3 c 3 d =============== struct i (x : s32) struct a (x : s32) struct b (x : s32) struct c (x : s32) struct d (x : s32) struct o (x : s32) a x if (i x) a x if (b x) b x if (a x) c x if (b x) d x if (c x) c x if (d x) o x if (d x)
# will produce following topological order and lifetimes: --------------- rel_order =============== 0 i 1 b 1 a 2 c 2 d 3 o =============== --------------- rel_lt =============== 1 i 2 b 2 a 3 o 3 c 3 d =============== struct i (x : s32) struct a (x : s32) struct b (x : s32) struct c (x : s32) struct d (x : s32) struct o (x : s32) a x if (i x) a x if (b x) b x if (a x) c x if (b x) d x if (c x) c x if (d x) o x if (d x)
// topological order of relations .decl rel_order(n:number, rel:symbol) rel_order(i,rel) :- Rel(rel), scc(scc_id, rel), scc_order(i, scc_id). // relation lifetime (after which order can we free this relation) .decl rel_lt(n:number, rel:symbol) rel_lt(i,rel) :- Rel(rel), scc(scc_id, rel), !scc_dep(_, scc_id), scc_order(i, scc_id). rel_lt(mxi,rel) :- Rel(rel), scc(scc_id, rel), scc_dep(scc_user, scc_id), mxi = max i : { scc_order(i, scc_user) }.
// topological order of relations .decl rel_order(n:number, rel:symbol) rel_order(i,rel) :- Rel(rel), scc(scc_id, rel), scc_order(i, scc_id). // relation lifetime (after which order can we free this relation) .decl rel_lt(n:number, rel:symbol) rel_lt(i,rel) :- Rel(rel), scc(scc_id, rel), !scc_dep(_, scc_id), scc_order(i, scc_id). rel_lt(mxi,rel) :- Rel(rel), scc(scc_id, rel), scc_dep(scc_user, scc_id), mxi = max i : { scc_order(i, scc_user) }.
// topological order of relations .decl rel_order(n:number, rel:symbol) rel_order(i,rel) :- Rel(rel), scc(scc_id, rel), scc_order(i, scc_id). // relation lifetime (after which order can we free this relation) .decl rel_lt(n:number, rel:symbol) rel_lt(i,rel) :- Rel(rel), scc(scc_id, rel), !scc_dep(_, scc_id), scc_order(i, scc_id). rel_lt(mxi,rel) :- Rel(rel), scc(scc_id, rel), scc_dep(scc_user, scc_id), mxi = max i : { scc_order(i, scc_user) }.
Home Login