logo

oasis-root

Compiled tree of Oasis Linux based on own branch at <https://hacktivis.me/git/oasis/> git clone https://anongit.hacktivis.me/git/oasis-root.git

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
  38.     a a
  39.     a b
  40.     a c
  41.     a c
  42.     a d
  43.     b c
  44.     c b
  45.     e f
  47. or equivalently
  49.     a a a b a c a c a d
  50.     b c c b e f
  52. represents the graph
  54.               ┌─┐
  55.               ↓ │
  56.              ┏━━━┓
  57.       ┌──────┃ a ┃──────┐
  58.       │      ┗━━━┛      │
  59.       │       │ │       │
  60.       ↓       ↓ ↓       ↓
  61.     ┏━━━┓───→┏━━━┓    ┏━━━┓
  62.     ┃ b ┃    ┃ c ┃    ┃ d ┃
  63.     ┗━━━┛←───┗━━━┛    ┗━━━┛
  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.