CSR (compressed sparse row) representation of a graph, weightened or unweightened.

\(O(N)\) Builds an non-weightned SparseGraph.

\(O(N)\) Builds an non-weightned SparseGraph.

\(O(N)\) Builds a weightned SparseGraph.

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

\(O(1)\) Returns (EdgeId, Vertex) pairs. Hardly used.

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

\(O(V+E)\) Collects reachable vertices from source points.

\(O(V+E)\) DFS that paints connnected components. Returns (vertexToComponentId, components). Works on a non-directed graph only.

\(O(V+E)\) Depth-first search. Returns a vector of distances to each vertex. Unreachable vertices are given distance of `-1`.

\(O(N N!)\) Depth-first search that finds the longest path. Just a template!

Typical problems

• ABC 317 C - Remembering the Days

\(O(V+E)\) Breadth-first search. Unreachable vertices are given distance of -1.

\(O(V+E)\) 01-BFS. Unreachable vertices are given distance of -1.

\(O((E+V) \log {V})\) Dijkstra's algorithm.

>>> let gr = buildWSG 4 (U.fromList [(0, 1, 1 :: Int), (1, 2, 1), (1, 3, 100), (2, 3, 1)])
>>> djSG gr (-1 :: Int) (U.singleton 0)
[0,1,2,3]

\(O(V+E)\) depth-first search. Returns a vector of parents. The source vertex or unrechable vertices are given `-1` as their parent. Note that it doesn't return the shortest path.

\(O(V+E)\) breadth-first search. Returns a vector of distances and parents. The source vertex or unrechable vertices are given `-1` as their parent.

>>> bfsTreeSG (buildSG 4 (U.fromList [(0, 1), (1, 2), (1, 3), (2, 3)])) 0 (-1)
([0,1,2,2],[-1,0,1,1])

Retrieve a shortest path: >>> let (_, ps) = bfsTreeSG (buildSG 4 (U.fromList [(0, 1), (1, 2), (1, 3), (2, 3)])) 0 (-1) >>> restorePath ps 3 [0,1,3]

\(O((E+V) \log {V})\) Dijkstra's algorithm with path restoration information.

Tries to paint the whole graph (possible not connected) as a digraph.

let DigraphInfo isFailure vertColors vertComps compInfos = paintDigraphSG gr

Typical problems

• ABC 282 D - Make Bipartite 2
• PAST 10 O - 3-順列

\(O(V+E)\) Tries to paint the whole graph (possible not connected) as a digraph. Works on non-directed graphs only.

\(O(V+E)\) Topological sort

Upstream (not referenced) vertices come first:

>>> let !gr = buildSG 5 $ U.fromList ([(0, 1), (0, 2), (2, 3)] :: [(Int, Int)])
>>> topSortSG gr
[4,0,2,3,1]

\(O(V+E)\) Creates a reverse graph.

\(O(V+E)\) Partial running of topSccSG over topologically sorted vertices, but for some connected components only.

\(O(V+E)\) Collectes strongly connected components, reverse topologically sorted (referenced SCCs come first).

Downstream vertices come first, e.g., [v1 == v2 == v3] <- [v4 == v5] <- [v6].

• *TODO: Faster.**

\(O(V+E)\) Collectes strongly connected components, reverse topologically sorted (not referenced SCCs come first).

\(O(E)\) Kruscal's algorithm. Returns edges for building a minimum spanning tree.

NOTE: User ia assumed to not duplicate the edges.

If you need to detect if the tree spans all the vertices, be sure to check the length of the edges equals to the number of vertices minus one. Do not try to count the vertices directly, e.g., o-o o-o contains four connected vertices, but only has two edges. It's apparently not a spanning tree.

Typical problems

• Typica 49 - Flip Digits 2

\(O(E)\) Kruscal's algorithm. Returns a minimum spanning tree.

NOTE: User ia assumed to not duplicate the edges.

\(O(V+E)\) Finds a cycle in a directed graph and collects their vertices. Embed edge information to the weight if necessary.

\(O(V+E)\) Finds a cycle in an undirected graph and collects their vertices. Embed edge information to the weight if necessary.

\(O(E)\) (Internal) Auxiliary function to `fincCycleUndirectedSG. Detects self-loop edges and multiple edges.

TODO: efficient implementation (findMap? and two of them in one loop?)

\(O(V+E)\) Finds a cycle in a directed or undirected graph and collects their vertices.

• revEdgeIsCycle: Reports reverse edge as a cycle on True. It's set to False@ for undirected graphs where edges are duplicated.

<https://drken1215.hatenablog.com/entry/2023/05/20/200517z.