AtCoder.Internal.Csr

Immutable Compresed Sparse Row. It is re-exported from the AtCoder.Extra.Graph module with additional functionalities.

Example

Create a Csr without edge weights using build' and retrieve the edges with adj:

>>> 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 using build and retrieve the edges with adjW:

>>> 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.0

Compressed sparse row

data Csr w

Comperssed Sparse Row representation of a graph.

Since: 1.0.0.0

Constructors

Csr

Fields

• nCsr :: !Int

  The number of vertices.

  Since: 1.1.0.0

• mCsr :: !Int

  The number of edges.

  Since: 1.1.0.0

• startCsr :: !(Vector Int)

  Starting indices.

  Since: 1.1.0.0

• adjCsr :: !(Vector Int)

  Adjacent vertices.

  Since: 1.1.0.0

• wCsr :: !(Vector w)

  Edge weights.

  Since: 1.1.0.0

Instances

(Show w, Unbox w) => Show (Csr w)

Since: 1.0.0.0

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.0

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 a Csr.

Since: 1.0.0.0

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

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

Since: 1.0.0.0

build1 :: HasCallStack => Int -> Vector (Int, Int) -> Csr Int

\(O(n + m)\) Creates a Csr with 1 as edge weights.

Since: 1.1.0.0

Accessors

adj :: HasCallStack => Csr w -> Int -> Vector Int

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

Since: 1.0.0.0

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

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

Since: 1.0.0.0

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

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

Since: 1.0.0.0