Data.Graph.Indexed.Query.DFS

This modules provides several functions for traversing
graphs in depth-first order and accumulating results in
various ways along the way.

Definitions

limitedDfsWith : IGraph k e n -> List (Fin k) -> (s -> Fin k -> Either s a) -> s -> Fin k -> Either s a

  Traverses the graph in depth-first order from the given
  start node and accumulates the nodes encountered with the
  given function.
  
  This abborts if the function returns a `Right`, otherwise it
  continues with the traversal. The result is either the
  accumulated state or the final result (if any).
  
  Unlike `dfsWith`, this takes a list of nodes that are taboo, that is
  that will already be set to `visited`. This allows us exclude certain
  pathways from our search.

Totality: total
Visibility: export

dfsWith : IGraph k e n -> (s -> Fin k -> Either s a) -> s -> Fin k -> Either s a

  Traverses the graph in depth-first order from the given
  start node and accumulates the nodes encountered with the
  given function.
  
  This abborts if the function returns a `Right`, otherwise it
  continues with the traversal. The result is either the
  accumulated state or the final result (if any).

Totality: total
Visibility: export

limitedDfsWith' : IGraph k e n -> List (Fin k) -> (s -> Fin k -> s) -> s -> Fin k -> s

  Like `dfsWith` but accumulates the whole connected component
  from the given starting node in depth-first order.

Totality: total
Visibility: export

dfsWith' : IGraph k e n -> (s -> Fin k -> s) -> s -> Fin k -> s

  Like `dfsWith` but accumulates the whole connected component
  from the given starting node in depth-first order.

Totality: total
Visibility: export

limitedDfs : IGraph k e n -> List (Fin k) -> Fin k -> SnocList (Fin k)

  Traverses the graph in depth-first order for the given start nodes
  returning the encountered nodes in a `SnocList`.

Totality: total
Visibility: export

dfs : IGraph k e n -> Fin k -> SnocList (Fin k)

  Traverses the graph in depth-first order for the given start nodes
  returning the encountered nodes in a `SnocList`.

Totality: total
Visibility: export

cdfsWith : IGraph k e n -> (s -> Fin k -> s) -> s -> List (Fin k) -> List s

  Traverses the graph in depth-first order for the given
  start nodes and accumulates the nodes encountered with the
  given function.
  
  Unlike with `dfsWith`, results are accumulated component-wise,
  using initial state `init` for every component we encounter.

Totality: total
Visibility: export

cdfsWith' : IGraph k e n -> (s -> Fin k -> s) -> s -> List s

  Traverses the whole graph in depth-first order
  accumulates the nodes encountered with the given function.

Totality: total
Visibility: export

cdfs : IGraph k e n -> List (Fin k) -> List (SnocList (Fin k))

  Traverses the graph in depth-first order for the given start nodes
  returning the encountered nodes in a `SnocList`.

Totality: total
Visibility: export

cdfs' : IGraph k e n -> List (SnocList (Fin k))

  Traverses the whole graph in depth-first order
  returning the encountered nodes in a `SnocList`.

Totality: total
Visibility: export

dffWith : IGraph k e n -> (Fin k -> t) -> List (Fin k) -> Forest t

  Traverses the graph in depth-first order for the given
  start nodes and converts the nodes encountered with the
  given function.
  
  Unlike `dfsWith`, this returns a forest of spanning trees
  of the connected components encountered.

Totality: total
Visibility: export

dffWith' : IGraph k e n -> (Fin k -> t) -> Forest t

  Traverses the whole graph in depth-first order
  converts the nodes encountered with the given function.
  
  Unlike `dfsWith'`, this returns a forest of spanning trees
  of the connected components encountered.

Totality: total
Visibility: export

dff : IGraph k e n -> List (Fin k) -> Forest (Fin k)

  Traverses the graph in depth-first order for the given start nodes
  returning the encountered nodes in a list.
  
  Unlike `dfs`, this returns a forest of spanning trees
  of the connected components encountered.

Totality: total
Visibility: export

dff' : IGraph k e n -> Forest (Fin k)

  Traverses the whole graph in depth-first order
  returning the encountered nodes in a list.
  
  Unlike `dfs'`, this returns a forest of spanning trees
  of the connected components encountered.

Totality: total
Visibility: export

components : IGraph k e n -> List (SnocList (Fin k))

  Collection of connected components

Totality: total
Visibility: export

noComponents : IGraph k e n -> Nat

  Number of connected components

Totality: total
Visibility: export

isConnected : IGraph k e n -> Bool

  Is the graph connected?

Totality: total
Visibility: export