exercise-13-2.py

from dataclasses import dataclass, field


@dataclass
class AdjMat:
    rep: list[list[int]] = field(default_factory=lambda: [])


@dataclass
class AdjLst:
    rep: dict[int, list[int]] = field(default_factory=lambda: {})


def mat2lst(graph: AdjMat) -> AdjLst:
    """
    O(n^2)
    """
    adj_lst = AdjLst()
    for i, v in enumerate(graph.rep):
        adj_lst.rep.setdefault(i, [j for j, x in enumerate(v) if x])

    return adj_lst


def lst2mat(graph: AdjLst) -> AdjMat:
    """
    O(v * e)

    or more generally,

    O(n^2)
    """
    adj_mat = AdjMat()

    for _, neighbours in graph.rep.items():
        adj_mat.rep.append(
            [1 if x in neighbours else 0 for x in range(len(graph.rep.keys()))]
        )

    return adj_mat


def f(some_graph: AdjMat | AdjLst) -> bool:  # pyright: ignore
    some_complex_algorithm = lambda: True
    return some_complex_algorithm() == True


def f_prime(graph: AdjMat | AdjLst) -> bool:
    """
    F'(X) = 1 iff x represents a graph via the adjacency matrix repr.
    such that F(G) == 1
    """
    if type(graph) is not AdjMat:
        return False

    return f(graph)


def f_prime_prime(graph: AdjMat | AdjLst) -> bool:
    if not isinstance(graph, AdjLst):
        return False

    return f(graph)


if __name__ == "__main__":
    """
    💡 Proof:
    Given a graph in either Adjacency Matrix or Adjacency List representation,
    we can trivially convert between representations in polynomial time.
    see `mat2lst` or `lst2mat`.

    Due to this ease of conversion, If F'' exists in P, F' must also exist in P
    since we can just layer an additional conversion from AdjLst -> AdjMat via
    `lst2mat`.

    All in all, we have:
    `polynomial time algo f + polynomial time conversion algo lst2mat
    which ultimately yields a polynomial time algorithm`
    """
    G = AdjLst({0: [1], 1: [0, 2], 2: [1]})
    assert G == mat2lst(lst2mat(G))
    result = f_prime_prime(G)
    assert result == True
    # do polynomial time conversion
    G = lst2mat(G)
    result = f_prime(G)
    assert result == True

    print("✅")