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: Sat, 8 Oct 2022 20:13:48 +0200 [thread overview]
Message-ID: <26f63a49-ad17-865b-8ad3-43bf6e76389b@telenet.be> (raw)
In-Reply-To: <7e5cff81-debc-bc04-6cc0-9d88c5ea1d9b@telenet.be>
[-- Attachment #1.1.1: Type: text/plain, Size: 377 bytes --]
I found a solution: change the depth-first traversal to a breadth-first
traversal -- it uses (pfds hamts) from guile-pfds instead of (guix
sets)/(ice-9 vlist), so will need some small changes for use in Guix
(unless the additional dependency is considered acceptable), but it
should at least unblock the workspace implementation in antioxidant.
Greetings,
Maxime.
[-- Attachment #1.1.2: topological-sort.scm --]
[-- Type: text/x-scheme, Size: 2812 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)
#:use-module ((srfi srfi-69) #:select (hash))
#:use-module ((ice-9 match) #:select (match))
#:use-module (pfds hamts))
(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.
(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))
(match current-unexpanded-nodes
((first . current-unexpanded-nodes)
(if (hamt-ref visited (node-name first) #false)
;; Already visisted, nothing to do!
(inner-loop current-unexpanded-nodes
later-unexpanded-nodes result visited)
;; 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))))
(() ;; All nodes on the current level are expanded, descend!
(loop later-unexpanded-nodes result visited)))))))
[-- 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-08 18:14 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 [this message]
2022-10-12 12:34 ` Maxime Devos
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=26f63a49-ad17-865b-8ad3-43bf6e76389b@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.