GNU bug report logs - #58198
topological-sort does not sort topologically in case of diamonds

Previous Next

To reply to this bug, email your comments to 58198 AT debbugs.gnu.org.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Maxime Devos <maximedevos <at> telenet.be>
To: bug-guix <bug-guix <at> gnu.org>
Subject: topological-sort does not sort topologically in case of diamonds
Date: Fri, 30 Sep 2022 20:10:09 +0200

[Message part 1 (text/plain, inline)]

Consider the following DAG (arrows are implicitly downwards):

top -> left, right
left,right -> bottom.

Or in ASCII art:

     top
    /    \
left      right
    \    /
     bottom

Currently, they are sorted incorrectly with topological-sort -- the 
exact resulting order depends on the order in which the dependencies are 
passed to 'topological-sort' (from (guix import utils)), but you can get 
the following:

right bottom left top

'bottom' and 'right' need to be switched.

(Background)
I would like to use a copy of 'topological-sort' for determining the 
order in which 'workspace' members need to be built in antioxidant, but 
currently it produces bogus results (at least for 'greetd').

Theoretically, it would also impact recursive imports (unverified) 
(topological-sort is used to emit them in topological order).

Code to reproduce the bug:

(use-modules (guix sets) (ice-9 match) (srfi srfi-1))

(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\"."
  (let loop ((nodes nodes)
             (result '())
             (visited (set)))
    (match nodes
      (()
       result)
      ((head . tail)
       (if (set-contains? visited (node-name head))
           (loop tail result visited)
           (let ((dependencies (node-dependencies head)))
             (loop (append dependencies tail)
                   (cons head result)
                   (set-insert (node-name head) visited))))))))

(define %dependencies
  '((top left right)
    (left bottom)
    (right bottom)
    (bottom)))
(define root-nodes '(top))
(define (node-dependencies node)
  (assoc-ref %dependencies node))
(define node-name identity)
(define sorted (topological-sort root-nodes node-dependencies node-name))
(write sorted)

;; Verify the dependencies have smaller indices
(define (node-index node)
  (list-index (lambda (x) (equal? node x)) sorted))
(define (check node)
  (unless (<= (apply max 0 (map node-index (node-dependencies node)))
	      (node-index node))
    (pk node)
    (error "incorrectly sorted!")))
(for-each check (map car %dependencies))


Greetings,
Maxime.

[OpenPGP_0x49E3EE22191725EE.asc (application/pgp-keys, attachment)]

[OpenPGP_signature (application/pgp-signature, attachment)]

Message #8 received at 58198 <at> debbugs.gnu.org (full text, mbox):

From: Maxime Devos <maximedevos <at> telenet.be>
To: 58198 <at> debbugs.gnu.org
Subject: Re: topological-sort does not sort topologically in case of diamonds
Date: Wed, 5 Oct 2022 10:42:10 +0200

[Message part 1 (text/plain, inline)]

Currently trying out https://srfi.schemers.org/srfi-234/srfi-234.html, 
let's see how that works out.

Greetings,
Maixme.

[OpenPGP_0x49E3EE22191725EE.asc (application/pgp-keys, attachment)]

[OpenPGP_signature (application/pgp-signature, attachment)]

Message #11 received at 58198 <at> debbugs.gnu.org (full text, mbox):

From: Maxime Devos <maximedevos <at> telenet.be>
To: 58198 <at> debbugs.gnu.org
Subject: Re: topological-sort does not sort topologically in case of diamonds
Date: Sat, 8 Oct 2022 20:13:48 +0200

[Message part 1 (text/plain, inline)]

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.

[topological-sort.scm (text/x-scheme, attachment)]

[OpenPGP_0x49E3EE22191725EE.asc (application/pgp-keys, attachment)]

[OpenPGP_signature (application/pgp-signature, attachment)]

Message #14 received at 58198 <at> debbugs.gnu.org (full text, mbox):

From: Maxime Devos <maximedevos <at> telenet.be>
To: 58198 <at> debbugs.gnu.org
Subject: Re: topological-sort does not sort topologically in case of diamonds
Date: Wed, 12 Oct 2022 14:34:19 +0200

[Message part 1 (text/plain, inline)]

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.

[topological-sort.scm (text/x-scheme, attachment)]

[OpenPGP_0x49E3EE22191725EE.asc (application/pgp-keys, attachment)]

[OpenPGP_signature (application/pgp-signature, attachment)]

Message #17 received at 58198 <at> debbugs.gnu.org (full text, mbox):

From: Maxime Devos <maximedevos <at> telenet.be>
To: 58198 <at> debbugs.gnu.org
Subject: Re: topological-sort does not sort topologically in case of diamonds
Date: Mon, 17 Oct 2022 21:01:50 +0200

[Message part 1 (text/plain, inline)]

The revised module is _also_ broken (in case of nushell's member graph). 
 Will wait with posting the revised² module until it has seen more 
testing ...

[OpenPGP_0x49E3EE22191725EE.asc (application/pgp-keys, attachment)]

[OpenPGP_signature (application/pgp-signature, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.