Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.Extra.Graph

Contents

Re-export of CSR
CSR helpers
Graph search

Description

Re-export of the Csr module and generic graph search functions.

Since: 1.1.0.0

Synopsis

module AtCoder.Internal.Csr
swapDupe :: Unbox (Int, Int, w) => Vector (Int, Int, w) -> Vector (Int, Int, w)
swapDupe' :: Unbox (Int, Int) => Vector (Int, Int) -> Vector (Int, Int)
scc :: Csr w -> Vector (Vector Int)
topSort :: Int -> (Int -> Vector Int) -> Vector Int
blockCut :: Int -> (Int -> Vector Int) -> Csr ()
blockCutComponents :: Int -> (Int -> Vector Int) -> Vector (Vector Int)

Re-export of CSR

The Csr data type and all the functions such as build or adj are re-exported.

module AtCoder.Internal.Csr

CSR helpers

swapDupe :: Unbox (Int, Int, w) => Vector (Int, Int, w) -> Vector (Int, Int, w) Source #

\(O(n)\) Converts non-directed edges into directional edges. This is a convenient function for making an input to build.

Example

Expand

swapDupe duplicates each edge reversing the direction:

>>> import AtCoder.Extra.Graph qualified as Gr
>>> import Data.Vector.Unboxed qualified as VU
>>> Gr.swapDupe $ VU.fromList [(0, 1, ()), (1, 2, ())]
[(0,1,()),(1,0,()),(1,2,()),(2,1,())]

Create a non-directed graph:

>>> let gr = Gr.build 3 . Gr.swapDupe $ VU.fromList [(0, 1, ()), (1, 2, ())]
>>> gr `Gr.adj` 0
[1]

>>> gr `Gr.adj` 1
[0,2]

>>> gr `Gr.adj` 2
[1]

Since: 1.1.0.0

swapDupe' :: Unbox (Int, Int) => Vector (Int, Int) -> Vector (Int, Int) Source #

\(O(n)\) Converts non-directed edges into directional edges. This is a convenient function for making an input to build'.

Example

Expand

swapDupe' duplicates each edge reversing the direction:

>>> import AtCoder.Extra.Graph qualified as Gr
>>> import Data.Vector.Unboxed qualified as VU
>>> Gr.swapDupe' $ VU.fromList [(0, 1), (1, 2)]
[(0,1),(1,0),(1,2),(2,1)]

Create a non-directed graph:

>>> let gr = Gr.build' 3 . Gr.swapDupe' $ VU.fromList [(0, 1), (1, 2)]
>>> gr `Gr.adj` 0
[1]

>>> gr `Gr.adj` 1
[0,2]

>>> gr `Gr.adj` 2
[1]

Since: 1.1.0.0

scc :: Csr w -> Vector (Vector Int) Source #

\(O(n + m)\) Returns the strongly connected components.

Example

Expand

>>> import AtCoder.Extra.Graph qualified as Gr
>>> import Data.Vector.Unboxed qualified as VU
>>> -- 0 == 1 -> 2    3
>>> let gr = Gr.build' 4 $ VU.fromList [(0, 1), (1, 0), (1, 2)]
>>> Gr.scc gr
[[3],[0,1],[2]]

Since: 1.1.0.0

Graph search

topSort :: Int -> (Int -> Vector Int) -> Vector Int Source #

\(O(n \log n + m)\) Returns the lexicographically smallest topological ordering of the given graph.

Constraints

The graph must be a DAG.

Example

Expand

>>> import AtCoder.Extra.Graph qualified as Gr
>>> import Data.Vector.Unboxed qualified as VU
>>> let n = 5
>>> let gr = Gr.build' n $ VU.fromList [(1, 2), (4, 0), (0, 3)]
>>> Gr.topSort n (gr `Gr.adj`)
[1,2,4,0,3]

Since: 1.1.0.0

blockCut :: Int -> (Int -> Vector Int) -> Csr () Source #

\(O(n + m)\) Returns a block cut tree where super vertices represent each biconnected component.

Example

Expand

>>> import AtCoder.Extra.Graph qualified as Gr
>>> import Data.Vector.Unboxed qualified as VU
>>> -- 0---3---2
>>> -- +-1-+
>>> let n = 4
>>> let gr = Gr.build' n . Gr.swapDupe' $ VU.fromList [(0, 3), (0, 1), (1, 3), (3, 2)]
>>> let bct = blockCut n (gr `Gr.adj`)
>>> bct
Csr {nCsr = 6, mCsr = 5, startCsr = [0,0,0,0,0,2,5], adjCsr = [3,2,0,3,1], wCsr = [(),(),(),(),()]}

>>> V.generate (Gr.nCsr bct - n) ((bct `Gr.adj`) . (+ n))
[[3,2],[0,3,1]]

Since: 1.1.1.0

blockCutComponents :: Int -> (Int -> Vector Int) -> Vector (Vector Int) Source #

\(O(n + m)\) Returns a blocks (biconnected comopnents) of the graph.

Example

Expand

>>> import AtCoder.Extra.Graph qualified as Gr
>>> import Data.Vector.Unboxed qualified as VU
>>> -- 0---3---2
>>> -- +-1-+
>>> let n = 4
>>> let gr = Gr.build' n . Gr.swapDupe' $ VU.fromList [(0, 3), (0, 1), (1, 3), (3, 2)]
>>> Gr.blockCutComponents n (gr `Gr.adj`)
[[3,2],[0,3,1]]

Since: 1.1.1.0