Data.Graph.Indexed.Ring.Relevant.ShortestPath

This module provides utilities used to compute families of relevant cycles
as described by Vismara et al in "Union of all the minimum cycle bases of a graph"
(The Electronic Journal of Combinatorics 4 (1997)).

In particular, it computes the number of shortest paths between a root
node and all other nodes in a graph.

Please note that this is internal stuff. The algorithm is not suitable
as a general shortest path algorithm, as it computes only paths up
to half the graph order in length.

Reexports

Definitions

smaller : Fin o -> Nat -> ISubgraph o k e Nat -> Fin o -> Bool

  `True` if node `n` is "smaller" than `root`. This is
  the ordering "pi" used in the paper.

Totality: total
Visibility: export

toDegs : Subgraph k e n -> Subgraph k e Nat

  Converts a subgraph to hold the degree of each node as its label.

Totality: total
Visibility: export

shortestPaths : ISubgraph o k e Nat -> Fin o -> List (Path o)

  Computes the shortest paths to all nodes reachable from
  the given starting node.
  
  Note: This is not a general shortest paths algorithm but a utility
  for computing relevant cycles. Since paths are later merged to cycles,
  only paths of length up to half the graph order are computed.

Totality: total
Visibility: export