๐พ Archived View for siiky.srht.site โบ programming โบ transitive-reduction.gmi captured on 2024-02-05 at 09:33:45. Gemini links have been rewritten to link to archived content
โฌ ๏ธ Previous capture (2023-05-24)
-=-=-=-=-=-=-
siiky
2023/03/04
2023/03/04
en
There's this operation on graphs/relations called "transitive reduction" (I didn't learn its name until very recently). It can be used on a graph/relation to compute another (possibly smaller) graph/relation that has no redundant edges (assuming transitivity). And I've been thinking about how to do it for about two years (dam), because I needed it for some POSet things (Scheme ยง poset). Some weeks ago I was walking home, not thinking about anything in particular, and an algorithm just popped into my brain out of nowhere!
gemini://gemi.dev/cgi-bin/wp.cgi/view/en?Transitive_reduction
../wiki/transitive_reduction.gmi
https://git.sr.ht/~siiky/experiments/tree/main/item/transitive-reduction.scm
The idea is so simple that I'm flabbergasted I didn't come up with it two years ago, when I was kinda obsessed. (Though I haven't proven it works, intuitively I think it does).
Let's say `a โ b` means that node 'b' is directly reachable from node 'a' ("directly" means there are no intermediate nodes); and let's say `a โ* b` means that node 'b' is reachable from node 'a', possibly through intermediate nodes (e.g. if `a โ b โ c`, we could say `a โ* c`).
We'll call our graph G=(V, E), where V is the set of all nodes, and E is the relation `a โ* b` (a, b โ V). We're looking to compute an E' from E that is the relation `a โ b`.
And here it is at last: โa, c โ V: (a โ* c โง โb โ V: bโ c โง `a โ b` โง `b โ* c`) โ remove `a โ* c` from E.
There's one caveat with this algorithm: it only works for acyclic graphs (aka DAGs, graphs with no cycles). That's not a problem for me (I wanted it for POSets after all; see ยง "Alternative definitions") so I didn't bother to think about the matter further, but beware.
gemini://gemi.dev/cgi-bin/wp.cgi/view/en?Directed_acyclic_graph
The implementation is also simple enough (see the ~siiky/experiments for previous versions):
(import (srfi 42)) (define (reachable? E s d) (memq d (alist-ref s E))) (define (transitive-reduction E) (list-ec (:list s*sE E) (:let s (car s*sE)) (:let sE (cdr s*sE)) (cons s (list-ec (:list d sE) (if (not (any?-ec (:list c sE) (and (not (eq? c d)) (reachable? E c d))))) d))))
Very important note: this implementation assumes that E is the transitive closure! It may not compute the correct result otherwise. I just made this choice to KISS: this way I don't have to recursively check reachability. When I apply it to the posets experiment I'll be sure to change that.
I like how it turned out. SRFI 42 made it pretty.
A recursive `reachable?` could be something like this:
(define (reachable? E s d) (let ((sE (alist-ref s E))) (or (memq d sE) (any?-ec (:list c sE) (reachable? E c d)))))