Careful with Transitive Reductions of Directed Graphs

General
1

Already this paper had it, that many economical
representations of directed graphs do exist:

The Transitive Reduction of a Directed Graph
Aho, Garey & Ullman - 1972
https://dl.acm.org/doi/abs/10.1137/0201008

In particular I had high hopes that term_factorized/3,
can be used for a top-level, so that instead of this here:

/* SWI-Prolog 9.3.25 */
?- X = f(f(X)), Y = f(f(f(Y))).
X = Y, Y = f(f(f(Y))).

?- X = f(f(f(X))), Y = f(f(Y)).
X = Y, Y = f(f(Y)).

We would get this here:

?- X = f(f(X)), Y = f(f(f(Y))).
X = Y, Y = f(Y).

?- X = f(f(f(X))), Y = f(f(Y)).
X = Y, Y = f(Y).

But then I noticed that term_factorized/3
does a little bit too much:

/* SWI-Prolog 9.3.25 */
?- X=a(X), Y=b(X,X), term_factorized(Y,T,L).
T = b(_A, _A),
L = [_A=a(_A)].

?- X=a(Z), Y=b(X,X), term_factorized(Y,T,L).
T = b(_A, _A),
L = [_A=a(Z)].

But a top-level probably only wants:

/* SWI-Prolog 9.3.25 */
?- X=a(X), Y=b(X,X).
X = a(X),
Y = b(X, X).

?- X=a(Z), Y=b(X,X).
X = a(Z),
Y = b(a(Z), a(Z)).

The problem is, term_factorized/3 also decomposes
acyclic parts of the given term, if there is some sharing.

So term_factorized/3 has probably other niche applications
than the answer substitution display I had in mind.

2

I already closed this ticket from 2023:

Stack overflow in term_factorized/3
https://github.com/SWI-Prolog/swipl-devel/issues/1162

I will close this new ticket opened 18 hours ago as well.

I had some progress with a hand rolled new predicate acyclic_decompose/3:

?- X=a(X), Y=b(X,X), acyclic_decompose(Y,T,L).
T = b(_B, _B), L = [_B = a(_B)].

?- X=a(Z), Y=b(X,X), acyclic_decompose(Y,T,L).
T = b(a(Z), a(Z)), L = [].

It can also do the X=f(X) problem:

?- X=f(f(f(X))), Y=f(f(Y)), acyclic_decompose([X,Y],T,L).
T = [_B, _B], L = [_B = f(_B)]

?- X=f(f(X)), Y=f(f(f(Y))), acyclic_decompose([X,Y],T,L).
T = [_B, _B], L = [_B = f(_B)]