Zog.Traversal (Zog v0.4.0)

View Source

Native graph traversal algorithms backed by Zog (Zig) via Zigler.

This module currently provides topological sorting for directed acyclic graphs (DAGs).

Summary

Functions

acyclic?(builder)

Returns true if the directed graph contains no directed cycles.

cyclic?(builder)

Returns true if the directed graph contains at least one directed cycle.

nif_is_acyclic(arg1, arg2, arg3, arg4)
nif_topological_sort(arg1, arg2, arg3, arg4, arg5)
topological_sort(builder, opts \\ [])

Computes a topological ordering of a directed acyclic graph (DAG).

Functions

acyclic?(builder)

@spec acyclic?(Zog.SoA.t()) :: boolean()

Returns true if the directed graph contains no directed cycles.

Empty graphs and graphs with no edges are considered acyclic.

Examples

iex> builder = Zog.directed()
...> |> Zog.add_edge(:a, :b, 1.0)
...> |> Zog.add_edge(:b, :c, 1.0)
iex> Zog.Traversal.acyclic?(builder)
true

iex> builder = Zog.directed()
...> |> Zog.add_edge(:a, :b, 1.0)
...> |> Zog.add_edge(:b, :c, 1.0)
...> |> Zog.add_edge(:c, :a, 1.0)
iex> Zog.Traversal.acyclic?(builder)
false

cyclic?(builder)

@spec cyclic?(Zog.SoA.t()) :: boolean()

Returns true if the directed graph contains at least one directed cycle.

nif_is_acyclic(arg1, arg2, arg3, arg4)

@spec nif_is_acyclic(
  0..18_446_744_073_709_551_615,
  [0..4_294_967_295] | <<_::_*32>>,
  [0..4_294_967_295] | <<_::_*32>>,
  [float()] | <<_::_*64>>
) :: boolean()

nif_topological_sort(arg1, arg2, arg3, arg4, arg5)

@spec nif_topological_sort(
  0..18_446_744_073_709_551_615,
  [0..4_294_967_295] | <<_::_*32>>,
  [0..4_294_967_295] | <<_::_*32>>,
  [float()] | <<_::_*64>>,
  term()
) :: term()

topological_sort(builder, opts \\ [])

@spec topological_sort(
  Zog.SoA.t(),
  keyword()
) :: {:ok, [Zog.SoA.label()]} | {:error, :cycle}

Computes a topological ordering of a directed acyclic graph (DAG).

Returns {:ok, [labels]} where labels is a valid ordering such that every edge goes from an earlier node to a later node. If the graph contains a directed cycle, returns {:error, :cycle}.

Options

  • :algorithm - :dfs (default) or :kahn.

Examples

iex> builder = Zog.directed()
...> |> Zog.add_edge(:a, :b, 1.0)
...> |> Zog.add_edge(:b, :c, 1.0)
iex> {:ok, order} = Zog.Traversal.topological_sort(builder)
iex> order
[:a, :b, :c]

iex> builder = Zog.directed()
...> |> Zog.add_edge(:a, :b, 1.0)
...> |> Zog.add_edge(:b, :c, 1.0)
...> |> Zog.add_edge(:c, :a, 1.0)
iex> Zog.Traversal.topological_sort(builder)
{:error, :cycle}