Safe Haskell	None
Language	Haskell2010

Math.Grads.Algo.Traversals

Description

Module providing various kinds of graph traversals and their modifications.

Synopsis

type BFSState = [(Int, (Int, Int))]
bfsState :: (Ord v, Eq e, Show v, Show e, Graph g) => g v e -> EdgeList e -> BFSState -> BFSState -> BFSState
dfsCycle :: Array Int [Int] -> [Int] -> [Int] -> [Int]
dfs :: EdgeList e -> Int -> EdgeList e
getComps :: Ord v => GenericGraph v e -> [GenericGraph v e]
getCompsWithReindex :: Ord v => GenericGraph v e -> [(Bimap Int Int, GenericGraph v e)]
getCompsIndices :: Ord v => GenericGraph v e -> [[Int]]

Documentation

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

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

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

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] Source #

Dfs a simple cycle.

dfs :: EdgeList e -> Int -> EdgeList e Source #

Classic dfs.

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

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

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

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

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

Get indices of vertices that belong to different connected components.