11.64 srfi.234 - Topological sorting ¶

Module: srfi.234 ¶

This module implements topological sort algorithm.

The SRFI is an enhancement of Gauche’s util.toposort module (see util.toposort - Topological sort). As this SRFI is finalized, we encourage new code to use this for richer features and portability. Original util.toposort has become a thin wrapper of this module.

Function: topological-sort graph :optional eq node-array ¶

[SRFI-234]{srfi.234} Returns a list of node, ordered to satisfy the dependency graph represented by graph.

Graph represents a directed acyclic graph (DAG) by a list of connections, where each connection is the form

(<node> <downstream> <downstream2> ...)

that means a node <node> is connected to other nodes <downstream> etc. <node> can be arbitrary object. Their equality is compared by a procedure eq, which is equal? by default.

If the graph contains cycles, #f is returned.

(topological-sort '((shirt tie belt)
                    (tie jacket)
                    (belt jacket)
                    (watch)
                    (pants shoes belt)
                    (undershorts pants shoes)
                    (socks shoes)))
 ⇒ (socks undershorts watch shirt tie pants belt jacket shoes)

If the optional node-array is given and not #f, it must be a vector of nodes, and graph uses integer indices of the nodes in place of nodes themselves. The comparison predicate eq is applied on the indices. Once the nodes are sorted, they are looked up from node-array, and a list of nodes is returned.

Function: topological-sort/details graph :optional eq node-array ¶

[SRFI-234]{srfi.234} Like topological-sort, but returns three values for further information. The meanings of arguments are the same as topological-sort.

If nodes can be topologically sorted, the first return value is a sorted list of nodes, and the second and the third values are #f.

If nodes cannot be topologically sorted, the first return value is #f, the second return value is an error message, and the third value is a list of nodes that provides information of at least one cycle.

Function: edgelist->graph edgelist :optional retriever ¶

[SRFI-234]{srfi.234} Converts a list of edges edgelist to a graph acceptable by topolocial-sort. Each edge is a list of two nodes, representing a directed edge (from-node to-node). The returned graph is a list of (from-node downstream-node downstream-node2 …).

The optional argument retriever is called as (retriever from-node graph) to get a graph entry starting with from-node. When omitted, assoc is used. If you need to compare nodes in a special way different from equal?, you can give a customized procedure.

(edgelist->graph '((a b) (a c) (b e) (c b)))
 ⇒ ((a b c) (b e) (c b))

Function: edgelist/inverted->graph edgelist :optional retriever ¶

[SRFI-234]{srfi.234} Like edgelist->graph, but take each edge entry as (to-node from-node).

(edgelist/inverted->graph '((a b) (a c) (b e) (a e)))
 ⇒ ((b a) (c a) (e b a))

Function: graph->edgelist graph ¶

[SRFI-234]{srfi.234} Given graph, which is a list of (from-node downstream-node downstream-node1 …), returns a list of edges, each of which being (from-node to-node). This is an inverse operation of edgelist->graph.

Function: graph->edgelist/inverted graph ¶

[SRFI-234]{srfi.234} Given graph, which is a list of (from-node downstream-node downstream-node1 …), returns a list of edges, each of which being (to-node from-node). This is an inverse operation of edgelist/inverted->graph.

Function: connected-components graph ¶

[SRFI-234]{srfi.234} Returns a list of node lists, where each list of nodes consists of a connected component of a directed graph graph. The format of graph argument is the same as topological-sort, i.e. ((node downstream …) …).

A connected component is a group of nodes such that from any node in the group can reach any other nodes in the same group.

(connected-components '((1 2 3) (2 1) (3 4) (4 3)))
  ⇒ ((4 3) (1 2))

Note: The order of result list, and the order of each node group in the list, don’t matter. Mathematically, they should be sets instead of lists.