package topological_sort

You can search for identifiers within the package.

in-package search v0.2.0

topological_sort
- Topological_sort
  - Edge
  - Node
  - Traversal_order
  - What

Legend:
Library
Module
Module type
Parameter
Class
Class type

module type Node = sig ... end

module Edge : sig ... end

module Traversal_order : sig ... end

Controls the order in which we begin traversing nodes as entry points into the graph. The earliest nodes with finished traversals are returned last.

module What : sig ... end

val sort : 
  ?traversal_order:Traversal_order.t ->
  ?verbose:Base.Bool.t ->
  ?verify:Base.Bool.t ->
  (module Node with type t = 'node) ->
  what:What.t ->
  nodes:'node Base.List.t ->
  edges:'node Edge.t Base.List.t ->
  'node Base.List.t Base.Or_error.t

sort (module Nodes) ~what ~nodes ~edges returns a list of nodes output satisfying:

output contains one occurrence of every node in nodes when what = Nodes, or one occurrence of every node in nodes and edges when what = Nodes_and_edge_endpoints.
if { from; to_ } is in edges, then from occurs before to_ in output.

sort returns Error if there is a cycle.

traversal_order determines the order in which we processing nodes as entry points into the graph.

verify checks that the sorted output or generated cycle is indeed correct.

val sort_or_cycle : 
  ?traversal_order:Traversal_order.t ->
  ?verbose:Base.Bool.t ->
  ?verify:Base.Bool.t ->
  (module Node with type t = 'node) ->
  what:What.t ->
  nodes:'node Base.List.t ->
  edges:'node Edge.t Base.List.t ->
  ('node Base.List.t, [ `Cycle of 'node Base.List.t ]) Base.Result.t

Same as sort, but returns the cycle if there is one.