234: Topological Sorting

This SRFI has complex authorship. The original specification and corresponding implementation were written by Shiro Kawai for Gauche. This SRFI was written by John Cowan, but its design is based on the Gauche specification. The implementation was written principally by Arvydas Silanskas based on the Gauche implementation, and then modified further by John Cowan to match this SRFI.

Status

This SRFI is currently in draft status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-234@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Abstract

Topological sorting is an algorithm that takes a graph consisting of nodes and other nodes that depend on them, forming a partial order, and returns a list representing a total ordering of the graph. If the graph is cyclic, the topological sort will fail, and an error will be signaled.

Issues

None at present.

Rationale

Consider the following graph representing steps to be performed:

example graph described below

This graph means that (among other things) steps 5 and 7 must be performed before step 11, and step 11 must be performed before steps 2, 9, and 10. By topologically sorting this graph, we get one possible total ordering of the steps that satisfies the partial order.

Specification

(topological-sort graph)
(topological-sort graph =)

Topologically sorts graph, which is a list of connections. Each connection is a list of the form (node dependency dependency ...), meaning that dependencies are dependent on node. The optional argument = specifies the identity relation between nodes; it defaults to eqv?.

It is an error if the same node (in the sense of =) appears in more than one connection.

If graph is circular, an error satisfying circular-graph? is signaled.

The graph shown above can be represented as ((5 11) (7 11 8) (3 8 10) (11 2 9 10) (8 9)). One possible result of applying `topological-sort` to this graph is the list (3 7 5 11 2 8 10 9), meaning that performing steps 3, 7, 5, ..., 10, 9 in that order will satisfy the partial ordering of the graph.

Implementation

The sample implementation is available in the SRFI 234 repository repository.

Acknowledgements

Credit is due to the members of the SRFI 234 mailing list.

The graph is in the public domain and is available at https://upload.wikimedia.org/wikipedia/commons/0/03/Directed_acyclic_graph_2.svg.

© 2022 John Cowan, Arvydas Silanskas, Shiro Kawai.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.


Editor: Arthur A. Gleckler