Data.Graph.Indexed.Query.BFS

Definitions

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

  Traverses the graph in breadth-first order for the given
  start nodes and accumulates the nodes encountered with the
  given function.
  
  Unlike `bfsWith`, 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.
  
  One use case is to find the shortest cycle containing a given
  edge or sequence of edges.

Totality: total
Visibility: export

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

  Traverses the graph in breadth-first order for the given
  start nodes and accumulates the nodes encountered with the
  given function.

Totality: total
Visibility: export

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

  Tries to find a shortest path between the two nodes.

Totality: total
Visibility: export

bfs : IGraph k e n -> Fin k -> Fin k -> Maybe (SnocList (Fin k))

  Tries to find a shortest path between the two nodes.

Totality: total
Visibility: export

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

  Traverses the graph in breadth-first order for the given
  start nodes and accumulates the nodes encountered with the
  given function.

Totality: total
Visibility: export

distancesToNode : IGraph k e n -> Fin k -> List (Nat, Fin k)

Totality: total
Visibility: export

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

  Computes the shortest paths to all nodes reachable from
  the given starting node. This is a simplified version of
  Dijkstra's algorithm for unweighted edges.
  
  Runs in O(n+m) time and O(n) memory.

Totality: total
Visibility: export