sbase

suckless unix tools
git clone git://git.suckless.org/sbase
Log | Files | Refs | README | LICENSE

tsort.1 (1467B)


      1 .Dd 2016-02-16
      2 .Dt TSORT 1
      3 .Os sbase
      4 .Sh NAME
      5 .Nm tsort
      6 .Nd topological sort
      7 .Sh SYNOPSIS
      8 .Nm
      9 .Op Ar file
     10 .Sh DESCRIPTION
     11 .Nm
     12 topologically sorts a graph.
     13 The graph is read either from
     14 .Ar file
     15 or from standard input.
     16 The result is not optimized for any particular usage.
     17 Loops are detected and reported to standard error, but does not stop the
     18 sort.
     19 .Pp
     20 The input is a list of edges (vertex pairs), where
     21 the edge is directed from the first vertex to the
     22 second vertex.
     23 .Sh OPTIONS
     24 None.
     25 .Sh EXIT STATUS
     26 .Bl -tag -width Ds
     27 .It 0
     28 The graph as successfully sorted.
     29 .It 1
     30 The graph as successfully sorted, but contained loops.
     31 .It > 1
     32 An error occurred.
     33 .El
     34 .Sh EXAMPLES
     35 .Bd -literal -offset left
     36 The input
     37 
     38     a a
     39     a b
     40     a c
     41     a c
     42     a d
     43     b c
     44     c b
     45     e f
     46 
     47 or equivalently
     48 
     49     a a a b a c a c a d
     50     b c c b e f
     51 
     52 represents the graph
     53 
     54               ┌─┐
     55               ↓ │
     56              ┏━━━┓
     57       ┌──────┃ a ┃──────┐
     58       │      ┗━━━┛      │
     59       │       │ │       │
     60       ↓       ↓ ↓       ↓
     61     ┏━━━┓───→┏━━━┓    ┏━━━┓
     62     ┃ b ┃    ┃ c ┃    ┃ d ┃
     63     ┗━━━┛←───┗━━━┛    ┗━━━┛
     64 
     65     ┏━━━┓    ┏━━━┓
     66     ┃ e ┃───→┃ f ┃
     67     ┗━━━┛    ┗━━━┛
     68 .Ed
     69 .Sh STANDARDS
     70 The
     71 .Nm
     72 utility is compliant with the
     73 .St -p1003.1-2013
     74 specification.