Copyright	Thodoris Papakonstantinou 2017-2026
License	LGPL-3
Maintainer	dev@tpapak.com
Stability	experimental
Portability	POSIX
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Graph.AdjacencyList.BFS

Contents

BFS result
Running BFS
Utilities

Description

Breadth-first search (BFS) for directed graphs represented as adjacency lists. Provides two entry points:

bfs — BFS on a concrete Graph value
adjBFS — BFS on an implicit graph given as an IntMap [Vertex] adjacency map

Both produce a BFS record containing the level (distance) of every reachable vertex, the BFS parent map, and a topological ordering of the visited vertices.

Used by the Tide algorithm (Pure) in the globalRelabel step to compute vertex heights from distances to the source and sink in the residual graph.

Synopsis

data BFS = BFS {
- frontier :: IntSet
- level :: IntMap Int
- parent :: IntMap Vertex
- maxLevel :: Int
- topSort :: [Vertex]
}
bfs :: Graph -> Vertex -> BFS
adjBFS :: IntMap [Vertex] -> Vertex -> BFS
spanningTree :: BFS -> [Edge]

BFS result

data BFS Source #

Result of a breadth-first search from a single source vertex.

Constructors

BFS

Fields

frontier :: IntSet
Current frontier (vertices at the deepest explored level). Empty when the search is complete.
level :: IntMap Int
Map from vertex to its BFS level (shortest distance from source).
parent :: IntMap Vertex
Map from vertex to its BFS parent. The source vertex has no entry.
maxLevel :: Int
Maximum level reached during the search.
topSort :: [Vertex]
Vertices in BFS visit order. For DAGs this coincides with a topological sort.

Instances

Instances details

Show BFS Source #
Instance details Defined in Data.Graph.AdjacencyList.BFS Methods showsPrec :: Int -> BFS -> ShowS # show :: BFS -> String # showList :: [BFS] -> ShowS #
Eq BFS Source #
Instance details Defined in Data.Graph.AdjacencyList.BFS Methods (==) :: BFS -> BFS -> Bool # (/=) :: BFS -> BFS -> Bool #

Running BFS

bfs :: Graph -> Vertex -> BFS Source #

Run BFS on a Graph from the given source vertex.

Explores all vertices reachable from s via the graph's neighbors function. Returns a BFS record with levels, parents, and visit order.

If s is not in the graph's vertex set, returns the initial (empty) BFS.

adjBFS :: IntMap [Vertex] -> Vertex -> BFS Source #

Run BFS on an implicit graph defined by an adjacency map.

adjBFS neimap s performs BFS from vertex s where the neighbors of each vertex are given by neimap :: IntMap [Vertex]. Vertices not present in neimap are treated as having no outgoing edges.

This is used by residualDistances to run BFS on the residual graph (whose edge set changes each tide) without constructing a full Graph value.

Utilities

spanningTree :: BFS -> [Edge] Source #

Extract the BFS spanning tree as a list of edges.

Each edge (parent, child) in the returned list corresponds to one entry in the parent map.