Algs graph (strongly connected components) variant 17
from __future__ import annotations


class Graph:
    __matrix: list[list[int]]
    __vertex: list[str]

    def __init__(self):
        self.__matrix = []
        self.__vertex = []

    def __find_index_by_mark(self, mark: str) -> int:
        for index, vertex in enumerate(self.__vertex):
            if vertex == mark:
                return index

        return -1

    def first(self) -> str:
        if not len(self.__vertex):
            raise Exception(f'Graph is empty')

        return self.__vertex[0]

    def next(self, v: str):
        index_v = self.__find_index_by_mark(v)
        if index_v == -1:
            raise Exception(f'Vertex {v} not found!')

        for index_w, col in enumerate(self.__matrix[index_v]):
            if col == 1:
                yield self.__vertex[index_w]

    def vertex(self):
        pass

    def add_v(self, mark: str):
        self.__vertex.append(mark)

        for row in self.__matrix:
            row.append(0)

        new_size_rows = len(self.__matrix) + 1
        self.__matrix.append([0] * new_size_rows)

    def add_e(self, v: str, w: str):
        v_index = self.__find_index_by_mark(v)
        if v_index == -1:
            raise Exception(f'Vertex {v} not found!')

        w_index = self.__find_index_by_mark(w)
        if w_index == -1:
            raise Exception(f'Vertex {w} not found!')

        self.__matrix[v_index][w_index] = 1

    def del_v(self):
        pass

    def del_e(self):
        pass

    def edit_v(self):
        pass

    def edit_e(self):
        pass

    def get_transpose_graph(self) -> Graph:
        result = Graph()
        for vertex in self.__vertex:
            result.add_v(vertex)

        for row_index, row in enumerate(self.__matrix):
            for col_index, col in enumerate(row):
                if col == 0:
                    continue

                v = self.__vertex[col_index]
                w = self.__vertex[row_index]

                result.add_e(v, w)

        return result

graph.py
leoska/bsbo-0809-2022-algs-1
from graph import Graph
from utils import dfs, dfs_transpose


GRAPH_VERTEX_NAMES = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
GRAPH_VERTEX_COUNT = 8
GRAPH_VERTEX_EDGES = [
    {'v': 'A', 'w': 'B'},  # A -> B
    {'v': 'B', 'w': 'E'},  # B -> E
    {'v': 'B', 'w': 'F'},  # B -> F
    {'v': 'B', 'w': 'C'},  # B -> C
    {'v': 'C', 'w': 'G'},  # C -> G
    {'v': 'C', 'w': 'D'},  # C -> D
    {'v': 'D', 'w': 'C'},  # D -> C
    {'v': 'D', 'w': 'H'},  # D -> H
    {'v': 'E', 'w': 'A'},  # E -> A
    {'v': 'E', 'w': 'F'},  # E -> F
    {'v': 'F', 'w': 'G'},  # F -> G
    {'v': 'G', 'w': 'F'},  # G -> F
    {'v': 'H', 'w': 'G'},  # H -> G
    {'v': 'H', 'w': 'D'},  # H -> D
]


def _init_graph(g: Graph):
    for i in range(GRAPH_VERTEX_COUNT):
        g.add_v(GRAPH_VERTEX_NAMES[i])

    for edge in GRAPH_VERTEX_EDGES:
        g.add_e(**edge)


def _init_used() -> dict[str, bool]:
    result = {}

    for vertex in GRAPH_VERTEX_NAMES:
        result[vertex] = False

    return result


if __name__ == '__main__':
    graph = Graph()
    _init_graph(graph)

    used = _init_used()
    order = []

    for v in graph.next(graph.first()):
        if not used[v]:
            dfs(v, order, used, graph)

    graph_transpose = graph.get_transpose_graph()
    used = _init_used()
    component = []

    for i in range(GRAPH_VERTEX_COUNT):
        v = order[GRAPH_VERTEX_COUNT - i - 1]

        if not used[v]:
            dfs_transpose(v, component, used, graph_transpose)

            print(', '.join(component))

            component.clear()

main.py
leoska/bsbo-0809-2022-algs-1
from graph import Graph


def dfs(v: str, order: list[str], used: dict[str, bool], g: Graph):
    used[v] = True

    for vertex in g.next(v):
        if not used[vertex]:
            dfs(vertex, order, used, g)

    order.append(v)


def dfs_transpose(v, component: list[str], used: dict[str, bool], g: Graph):
    used[v] = True
    component.append(v)

    for vertex in g.next(v):
        if not used[vertex]:
            dfs_transpose(vertex, component, used, g)

utils.py
leoska/bsbo-0809-2022-algs-1