toposort

lib.lists.toposort

Docs pulled from | This Revision | 10 minutes 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; };