Graph Utility
(byslib/graph/utility.py)

• View this file on GitHub
• Last update: 2022-04-18 22:29:22+09:00

Verified with

• tests/graph/dijkstra.test.py

Code

# @title Graph Utility
from typing import List, Tuple

from .depth_first_search import DepthFirstSearch
from .graph import LilMatrix


def restore_path(prev: List[int], to: int) -> List[int]:
    res = []
    while to != -1:
        res.append(to)
        to = prev[to]
    return res[::-1]


def rooted_tree(graph: LilMatrix, root: int) -> LilMatrix:
    dfs = DepthFirstSearch(graph)
    res = LilMatrix.empty(len(graph))
    for now in dfs.pre_order(root):
        for dest, weight in graph[now]:
            if dest != dfs.prev[now]:
                res.add_edge(now, dest, weight)
    return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.4/x64/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir], 'release': True}).decode()
  File "/opt/hostedtoolcache/Python/3.10.4/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/python.py", line 80, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page