Pythonで依存関係リゾルバを実装する

回答: def resolve_dependencies(package_definitions, target_package): # パッケージ定義を解析する graph = {} for definition in package_definitions: if ':' not in definition: raise ValueError(f'無効なパッケージ定義: {definition}') name, _, deps_str = definition.partition(':') name = name.strip() deps_str = deps_str.strip() if deps_str: deps = [d.strip() for d in deps_str.split(',')] else: deps = [] graph[name] = deps # 不足しているパッケージを確認する for pkg, deps in graph.items(): for dep in deps: if dep not in graph: raise ValueError(f'次のパッケージ定義が不足しています: {dep}') if target_package not in graph: raise ValueError(f'次のパッケージ定義が不足しています: {target_package}') # DFS を使用したトポロジカルソート。target_package から到達可能なパッケージのみを対象とする # 状態: 0 = 未訪問、1 = 処理中、2 = 完了 state = {} result = [] path = [] # 循環検出のために現在の経路を追跡する def dfs(pkg): if state.get(pkg) == 2: return if state.get(pkg) == 1: # path 内で循環を見つける cycle_start = path.index(pkg) cycle = path[cycle_start:] + [pkg] raise ValueError(f'次を含む循環依存が検出されました: {" -> ".join(cycle)}') state[pkg] = 1 path.append(pkg) for dep in graph[pkg]: dfs(dep) path.pop() state[pkg] = 2 result.append(pkg) dfs(target_package) return result

def resolve_dependencies(package_definitions, target_package): """ target_package の依存関係を解決し、有効なインストール順序を返します。 Args: package_definitions: list[str]、各エントリは 'Package: Dep1, Dep2' または 'Package:' の形式です。 target_package: str Returns: list[str]: target_package で終わるトポロジカルソートされたインストール順序。 Raises: ValueError: 入力形式が無効な場合、パッケージ定義が不足している場合、または循環依存がある場合。 """ def parse_definitions(definitions): graph = {} for entry in definitions: if not isinstance(entry, str): raise ValueError(f"無効なパッケージ定義: {entry}") if ':' not in entry: raise ValueError(f"無効なパッケージ定義: {entry}") package, deps_part = entry.split(':', 1) package = package.strip() if not package: raise ValueError(f"無効なパッケージ定義: {entry}") deps_part = deps_part.strip() if deps_part: deps = [dep.strip() for dep in deps_part.split(',') if dep.strip()] else: deps = [] if package in graph: raise ValueError(f"パッケージ '{package}' の定義が重複しています") graph[package] = deps return graph graph = parse_definitions(package_definitions) if target_package not in graph: raise ValueError(f"パッケージ '{target_package}' の定義が不足しています") order = [] state = {} # 0/未設定 = 未訪問、1 = 訪問中、2 = 訪問済み stack = [] def dfs(package): if package not in graph: raise ValueError(f"パッケージ '{package}' の定義が不足しています") package_state = state.get(package, 0) if package_state == 1: try: start = stack.index(package) cycle_path = stack[start:] + [package] except ValueError: cycle_path = [package, package] raise ValueError( "循環依存が検出されました: " + " -> ".join(cycle_path) ) if package_state == 2: return state[package] = 1 stack.append(package) for dep in graph[package]: if dep not in graph: raise ValueError(f"パッケージ '{dep}' の定義が不足しています") dfs(dep) stack.pop() state[package] = 2 order.append(package) dfs(target_package) return order # 使用例: if __name__ == "__main__": package_definitions = [ 'A: B, C', 'B: D', 'C: D, E', 'D:', 'E:' ] print(resolve_dependencies(package_definitions, 'A')) # 循環例: # print(resolve_dependencies(['A: B', 'B: A'], 'A')) # 不足パッケージ例: # print(resolve_dependencies(['A: B', 'B: C'], 'A'))