toposort

lib.lists.toposort

Docs pulled from | This Revision | 26 minutes ago

Nixpkgs manual

Sort a list based on a partial ordering using DFS. This implementation is O(N^2), if your ordering is linear, use sort instead.

before a b == true means that b should be after a in the result.

Inputs

before: 1. Function argument
list: 2. Function argument

Type

toposort :: (a -> a -> Bool) -> [a] -> ({ result :: [a]; } | { cycle :: [a]; loops :: [a]; })

Examples

`lib.lists.toposort` usage example

toposort hasPrefix [ "/home/user" "other" "/" "/home" ]
  == { result = [ "/" "/home" "/home/user" "other" ]; }

toposort hasPrefix [ "/home/user" "other" "/" "/home" "/" ]
  == { cycle = [ "/home/user" "/" "/" ]; # path leading to a cycle
       loops = [ "/" ]; }                # loops back to these elements

toposort hasPrefix [ "other" "/home/user" "/home" "/" ]
  == { result = [ "other" "/" "/home" "/home/user" ]; }

toposort (a: b: a < b) [ 3 2 1 ] == { result = [ 1 2 3 ]; }

Noogle detected

Aliases

lib.toposort

Implementation

The following is the current implementation of this function.

toposort =
    before:
    let
      dfs = listDfs true before;
      recurse =
        list:
        let
          dfsthis = dfs list;
          toporest = recurse (dfsthis.visited ++ dfsthis.rest);
        in
        if length list < 2 then
          # finish
          { result = list; }
        else if dfsthis ? cycle then
          # there's a cycle, starting from the current vertex, return it
          {
            cycle = reverseList dfsthis.visited ++ [ dfsthis.cycle ];
            inherit (dfsthis) loops;
          }
        else if toporest ? cycle then
          # there's a cycle somewhere else in the graph, return it
          toporest
        # Slow, but short. Can be made a bit faster with an explicit stack.
        else
          # there are no cycles
          { result = [ dfsthis.minimal ] ++ toporest.result; };
    in
    recurse;