강한 연결 요소 편집하기 (부분)

== 구현 소스코드 ==
아래는 SCC를 구하고 DAG까지 산출해주는 소스코드이다. 코르사주를 기반으로 하고 있지만 코르사주 알고리즘을 철저히 따르진 않고 좀 더 계량된 버전이다. 순수한 코르사주 알고리즘을 보고 싶다면 해당 문서를 참고하면 된다.<syntaxhighlight lang="python3">
from collections import defaultdict

# Step 1: Reverse Graph Function
def reverse_graph(graph):
    """Reverse the directed graph"""
    rev_graph = defaultdict(list)
    for u in graph:
        for v in graph[u]:
            rev_graph[v].append(u)
    return rev_graph

# Step 2: DFS for Reckless Ranking
def dfs_rank(graph, node, visited, stack):
    """DFS to determine finishing times (Reckless Ranking)"""
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_rank(graph, neighbor, visited, stack)
    stack.append(node)  # Store nodes in finishing order

# Step 3: DFS for SCC Computation
def dfs_scc(graph, node, visited, component):
    """DFS to extract strongly connected components"""
    visited.add(node)
    component.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_scc(graph, neighbor, visited, component)

# SCC Driver using iRank order
def scc_driver(graph, iRank):
    """Compute SCCs by running DFS on G in iRank order"""
    visited = set()
    sccs = []

    while iRank:
        node = iRank.pop()  # Process nodes in decreasing finishing order
        if node not in visited:
            component = []
            dfs_scc(graph, node, visited, component)
            sccs.append(component)

    return sccs

# Kosaraju-Sharir SCC Algorithm
def find_sccs(graph):
    """Compute SCCs using Kosaraju-Sharir Algorithm with iRank"""
    rev_graph = reverse_graph(graph)
    
    # Step 2: Reckless Ranking (DFS on G_rev to get finishing times)
    visited = set()
    stack = []
    for node in graph:
        if node not in visited:
            dfs_rank(rev_graph, node, visited, stack)

    # Step 3: SCC Computation using SCC Driver (DFS on G in iRank order)
    sccs = scc_driver(graph, stack)
    return sccs

# Step 4: Compute Reduced Graph G^c
def build_reduced_graph(graph, sccs):
    """Build the reduced graph G^c where each SCC is treated as a single node"""
    scc_map = {node: i for i, scc in enumerate(sccs) for node in scc}
    reduced_graph = defaultdict(set)

    for u in graph:
        for v in graph[u]:
            if scc_map[u] != scc_map[v]:  # Only keep inter-SCC edges
                reduced_graph[scc_map[u]].add(scc_map[v])
    
    return reduced_graph, scc_map

# Corrected Graph Definition (G9)
graph_G9 = {
    "a": ["d"],
    "b": ["a", "c"],
    "c": ["b"],
    "d": ["g", "h"],
    "e": ["a", "b", "h", "i"],
    "f": ["c", "e"],
    "g": ["h"],
    "h": ["a"],
    "i": ["f", "h"]
}

# Execute SCC Algorithm with iRank
sccs = find_sccs(graph_G9)
reduced_graph, scc_map = build_reduced_graph(graph_G9, sccs)

# Print SCC Results
print("\n📌 Strongly Connected Components (SCCs):")
for i, scc in enumerate(sccs, 1):
    print(f"  SCC {i}: {scc}")

# Print Reduced Graph
print("\n📌 Corrected Reduced Graph (G^c):")
for scc_id, neighbors in reduced_graph.items():
    print(f"  SCC {sccs[scc_id]} → { [sccs[n] for n in neighbors] }")
</syntaxhighlight>실행 결과
 📌 Strongly Connected Components (SCCs):
   SCC 1: ['a', 'd', 'g', 'h']
   SCC 2: ['b', 'c']
   SCC 3: ['f', 'e', 'i']
 
 📌 Corrected Reduced Graph (G^c):
   SCC ['b', 'c'] → <nowiki>[['a', 'd', 'g', 'h']]</nowiki>
   SCC ['f', 'e', 'i'] → [['a', 'd', 'g', 'h'], ['b', 'c']]