ac-library-hs-1.0.0.0: Data structures and algorithms
Safe HaskellNone
LanguageGHC2021

AtCoder.Internal.Csr

Description

Immutable Compresed Sparse Row.

Example

Expand

Create a Csr without edge weights using build:

>>> import AtCoder.Internal.Csr qualified as C
>>> let csr = build' 3 $ VU.fromList @(Int, Int) [(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)]
>>> csr `C.adj` 0
[1,2,3]
>>> csr `C.adj` 1
[2]
>>> csr `C.adj` 2
[3]

Create a Csr with edge weights with build and retrieve edge with edgeW:

>>> import AtCoder.Internal.Csr qualified as C
>>> let csr = build 3 $ VU.fromList @(Int, Int, Int) [(0, 1, 101), (0, 2, 102), (0, 3, 103), (1, 2, 112), (2, 3, 123)]
>>> csr `C.adjW` 0
[(1,101),(2,102),(3,103)]
>>> csr `C.adjW` 1
[(2,112)]
>>> csr `C.adjW` 2
[(3,123)]

Since: 1.0.0

Synopsis

Compressed sparse row

data Csr w #

Comperssed Sparse Row representation of a graph.

Since: 1.0.0

Instances

Instances details
(Show w, Unbox w) => Show (Csr w) #

Since: 1.0.0

Instance details

Defined in AtCoder.Internal.Csr

Methods

showsPrec :: Int -> Csr w -> ShowS #

show :: Csr w -> String #

showList :: [Csr w] -> ShowS #

(Unbox w, Eq w) => Eq (Csr w) #

Since: 1.0.0

Instance details

Defined in AtCoder.Internal.Csr

Methods

(==) :: Csr w -> Csr w -> Bool #

(/=) :: Csr w -> Csr w -> Bool #

Constructor

build :: (HasCallStack, Unbox w) => Int -> Vector (Int, Int, w) -> Csr w #

\(O(n + m)\) Creates Csr.

Since: 1.0.0

build' :: HasCallStack => Int -> Vector (Int, Int) -> Csr () #

\(O(n + m)\) Creates Csr with no weight.

Since: 1.0.0

Accessors

adj :: (HasCallStack, Unbox w) => Csr w -> Int -> Vector Int #

\(O(1)\) Returns adjacent vertices.

Since: 1.0.0

adjW :: (HasCallStack, Unbox w) => Csr w -> Int -> Vector (Int, w) #

\(O(1)\) Returns adjacent vertices with weights.

Since: 1.0.0

eAdj :: (HasCallStack, Unbox w) => Csr w -> Int -> Vector (Int, Int) #

\(O(1)\) Returns a vector of (edgeId, adjacentVertex).

Since: 1.0.0