Math.Grads.Algo.Traversals

Module providing various kinds of graph traversals and their modifications.

Documentation

type BFSState = [(Int, (Int, Int))]

List of (level, (edgeIdx, vertexIdx)).

bfsState :: (Ord v, Eq e, Show v, Show e, Graph g) => g v e -> EdgeList e -> BFSState -> BFSState -> BFSState

Bfs algorithm that takes graph, its EdgeList, BFSState corresponding to already visited vertices and BFSState that corresponds to starting point of traversal and returns BFSState as a result.

dfsCycle :: Array Int [Int] -> [Int] -> [Int] -> [Int]

Dfs a simple cycle.

dfs :: EdgeList e -> Int -> EdgeList e

Classic dfs.

getComps :: Ord v => GenericGraph v e -> [GenericGraph v e]

Get connected components of graph. Note that indexation will be CHANGED.

getCompsWithReindex :: Ord v => GenericGraph v e -> [(Bimap Int Int, GenericGraph v e)]

Get graph components and mapping from old indices to new indices of resulting graph components.

getCompsIndices :: Ord v => GenericGraph v e -> [[Int]]

Get indices of vertices that belong to different connected components.