From: Maxime Devos <maximedevos@telenet.be>
To: 58198@debbugs.gnu.org
Subject: bug#58198: topological-sort does not sort topologically in case of diamonds
Date: Wed, 12 Oct 2022 14:34:19 +0200 [thread overview]
Message-ID: <77b74931-cf0a-580b-b558-461ec8d5c2ef@telenet.be> (raw)
In-Reply-To: <26f63a49-ad17-865b-8ad3-43bf6e76389b@telenet.be>
[-- Attachment #1.1.1: Type: text/plain, Size: 239 bytes --]
On 08-10-2022 20:13, Maxime Devos wrote:
> I found a solution: [...]
It's buggy, it doesn't handle situations like
libnewsboat
/ |
| regex-rs
| |
strprintf.
Revised module is attached.
[-- Attachment #1.1.2: topological-sort.scm --]
[-- Type: text/x-scheme, Size: 4339 bytes --]
;;; GNU Guix --- Functional package management for GNU
;;; Copyright © 2019 Ludovic Courtès <ludo@gnu.org>
;;; Copyright © 2022 Maxime Devos <maximedevos@telenet.be>
;;;
;;; This file is part of GNU Guix.
;;;
;;; GNU Guix is free software; you can redistribute it and/or modify it
;;; under the terms of the GNU General Public License as published by
;;; the Free Software Foundation; either version 3 of the License, or (at
;;; your option) any later version.
;;;
;;; GNU Guix is distributed in the hope that it will be useful, but
;;; WITHOUT ANY WARRANTY; without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
;;; GNU General Public License for more details.
;;;
;;; You should have received a copy of the GNU General Public License
;;; along with GNU Guix. If not, see <http://www.gnu.org/licenses/>.
;; To be used by the implementation of workspaces.
;; Extracted from (guix import utils), and changed from (guix sets)
;; to a guile-pfds equivalent.
(define-module (topological-sort)
#:export (topological-sort topological-sort*)
#:use-module (srfi srfi-1)
#:use-module ((srfi srfi-69) #:select (hash))
#:use-module ((ice-9 match) #:select (match))
;; XXX: Cuirass compiles even build-side only modules.
#:autoload (pfds hamts) (make-hamt hamt-ref hamt-set))
(define (topological-sort nodes
node-dependencies
node-name)
"Perform a breadth-first traversal of the graph rooted at NODES, a list of
nodes, and return the list of nodes sorted in topological order. Call
NODE-DEPENDENCIES to obtain the dependencies of a node, and NODE-NAME to
obtain a node's uniquely identifying \"key\"."
;; It is important to do a breadth-first traversal instead of a depth-first
;; traversal -- a simpler depth-first traversal has caused failures in the
;; past.
(define (is-dependency? potential-dependency potential-dependents)
(member (node-name potential-dependency)
(map node-name
(append-map node-dependencies potential-dependents))))
(let loop ((unexpanded-nodes nodes)
(result '()) ; in reverse topological order
;; Identical to 'result', except for using a different data
;; structure.
(visited (make-hamt hash equal?)))
(if (null? unexpanded-nodes)
(reverse result) ; done!
(let inner-loop ((current-unexpanded-nodes unexpanded-nodes)
(later-unexpanded-nodes '())
(result result)
(visited visited)
(progress? #false))
(match current-unexpanded-nodes
((first . current-unexpanded-nodes)
(cond ((hamt-ref visited (node-name first) #false)
;; Already visisted, nothing to do!
(inner-loop current-unexpanded-nodes
later-unexpanded-nodes result visited
#true))
;; XXX: would be nice to not recompute
;; 'node-dependencies'.
((is-dependency? first current-unexpanded-nodes)
;; The node was a dependency of something on the previous
;; level, but also of something of the current level.
;; Delay it for later.
(inner-loop current-unexpanded-nodes
(cons first later-unexpanded-nodes)
result
visited
progress?))
(#true
;; Expand 'first', putting dependencies in
;; 'later-unexpanded-nodes'.
(inner-loop current-unexpanded-nodes
(append (node-dependencies first)
later-unexpanded-nodes)
(cons first result)
(hamt-set visited (node-name first) #true)
#true))))
(()
;; All nodes on the current level are expanded, descend!
;; But first check for a cycle.
(if progress?
(loop later-unexpanded-nodes result visited)
(error "cycle"))))))))
(define (topological-sort* nodes node-dependencies node-name)
"Like TOPOLOGICAL-SORT, but don't assume that NODES are roots. Instead,
consider all nodes in the closure of NODES."
(define artificial-root (make-symbol "root")) ; uninterned, fresh symbol
(define nodes* (list artificial-root))
(define (node-dependencies* node*)
(if (eq? node* artificial-root)
nodes
(node-dependencies node*)))
(define (node-name* node*)
(if (eq? node* artificial-root)
artificial-root
(node-name node*)))
(define (proper-node? node*)
(not (eq? node* artificial-root)))
(filter proper-node?
(topological-sort nodes* node-dependencies* node-name*)))
[-- Attachment #1.1.3: OpenPGP public key --]
[-- Type: application/pgp-keys, Size: 929 bytes --]
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 236 bytes --]
next prev parent reply other threads:[~2022-10-12 12:39 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-09-30 18:10 bug#58198: topological-sort does not sort topologically in case of diamonds Maxime Devos
2022-10-05 8:42 ` Maxime Devos
2022-10-08 18:13 ` Maxime Devos
2022-10-12 12:34 ` Maxime Devos [this message]
2022-10-17 19:01 ` Maxime Devos
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=77b74931-cf0a-580b-b558-461ec8d5c2ef@telenet.be \
--to=maximedevos@telenet.be \
--cc=58198@debbugs.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/guix.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.