# Path: clrs/_src/algorithms/graphs.py
# def dfs(A: _Array) -> _Out:
# def bfs(A: _Array, s: int) -> _Out:
# def topological_sort(A: _Array) -> _Out:
# def articulation_points(A: _Array) -> _Out:
# def bridges(A: _Array) -> _Out:
# def strongly_connected_components(A: _Array) -> _Out:
# def mst_kruskal(A: _Array) -> _Out:
#   def mst_union(u, v, in_mst, probes):
# def mst_prim(A: _Array, s: int) -> _Out:
# def bellman_ford(A: _Array, s: int) -> _Out:
# def dijkstra(A: _Array, s: int) -> _Out:
# def dag_shortest_paths(A: _Array, s: int) -> _Out:
# def floyd_warshall(A: _Array) -> _Out:
# def bipartite_matching(A: _Array, n: int, m: int, s: int, t: int) -> _Out:
#   D = np.copy(A)


from absl.testing import absltest
from clrs._src.algorithms import graphs
import numpy as np
BIPARTITE = np.array([
    [0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
])

BIPARTITE_2 = np.array([
    [0, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 1, 0, 0],
    [0, 0, 0, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0],
])


class GraphsTest(absltest.TestCase):

  def test_dfs(self):
    expected_directed = np.array([0, 0, 2, 4, 1, 2])

# Path: clrs/_src/algorithms/graphs.py
# def dfs(A: _Array) -> _Out:
# def bfs(A: _Array, s: int) -> _Out:
# def topological_sort(A: _Array) -> _Out:
# def articulation_points(A: _Array) -> _Out:
# def bridges(A: _Array) -> _Out:
# def strongly_connected_components(A: _Array) -> _Out:
# def mst_kruskal(A: _Array) -> _Out:
#   def mst_union(u, v, in_mst, probes):
# def mst_prim(A: _Array, s: int) -> _Out:
# def bellman_ford(A: _Array, s: int) -> _Out:
# def dijkstra(A: _Array, s: int) -> _Out:
# def dag_shortest_paths(A: _Array, s: int) -> _Out:
# def floyd_warshall(A: _Array) -> _Out:
# def bipartite_matching(A: _Array, n: int, m: int, s: int, t: int) -> _Out:
#   D = np.copy(A)


# Path: clrs/_src/algorithms/graphs_test.py
from absl.testing import absltest
from clrs._src.algorithms import graphs
import numpy as np

BIPARTITE = np.array([
    [0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
])

BIPARTITE_2 = np.array([
    [0, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 1, 0, 0],
    [0, 0, 0, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0],
])


class GraphsTest(absltest.TestCase):

  def test_dfs(self):
    expected_directed = np.array([0, 0, 2, 4, 1, 2])

    out, _ = graphs.dfs(DIRECTED)