toposort

lib.lists.toposort

Docs pulled from | This Revision | about 1 hour ago

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

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: list:
    let
      dfsthis = listDfs true before list;
      toporest = toposort before (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.cycle ] ++ dfsthis.visited);
                  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; };