topological_sort.py

"""
拓扑排序模块
Topological Sort Module
"""

from collections import deque
from graph_storage import SocialNetwork


def topological_sort(network):
    """
    拓扑排序，用于确定任务执行顺序
    Topological sort for determining task execution order
    
    Args:
        network (SocialNetwork): 社交网络对象 Social network object
        
    Returns:
        list: 拓扑排序结果，如果存在循环依赖则返回空列表
              Topologically sorted list, or empty list if circular dependency exists
    """
    # 计算每个节点的入度 Calculate in-degree for each node
    in_degree = [0] * network.n
    
    for i in range(network.n):
        neighbors = network.get_following(i)
        for neighbor in neighbors:
            in_degree[neighbor] += 1
    
    # 找到所有入度为0的节点 Find all nodes with in-degree 0
    queue = deque()
    for i in range(network.n):
        if in_degree[i] == 0:
            queue.append(i)
    
    topo_order = []
    
    # 执行Kahn算法 Execute Kahn's algorithm
    while queue:
        node = queue.popleft()
        topo_order.append(node)
        
        # 减少邻居节点的入度 Reduce in-degree of neighbors
        for neighbor in network.get_following(node):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # 如果拓扑排序结果不包含所有节点，说明存在循环依赖
    # If topological sort doesn't include all nodes, there's a circular dependency
    if len(topo_order) != network.n:
        return []  # 循环依赖存在 Circular dependency exists
    
    return topo_order


def has_cycle(network):
    """
    检测图中是否存在循环依赖
    Detect if there's a circular dependency in the graph
    
    Args:
        network (SocialNetwork): 社交网络对象 Social network object
        
    Returns:
        bool: 是否存在循环依赖 Whether circular dependency exists
    """
    # 使用DFS检测循环 Use DFS to detect cycles
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * network.n
    
    def dfs_visit(node):
        if color[node] == GRAY:
            return True  # 发现后向边，存在循环 Found back edge, cycle exists
        if color[node] == BLACK:
            return False  # 已经访问过，无循环 Already visited, no cycle
        
        color[node] = GRAY  # 标记为正在访问 Mark as being visited
        
        # 检查所有邻居节点 Check all neighbor nodes
        for neighbor in network.get_following(node):
            if dfs_visit(neighbor):
                return True
        
        color[node] = BLACK  # 标记为已完成访问 Mark as completely visited
        return False
    
    for i in range(network.n):
        if color[i] == WHITE:
            if dfs_visit(i):
                return True
    
    return False


class TopologicalSortNetwork(SocialNetwork):
    """
    具有拓扑排序功能的社交网络类
    Social Network class with topological sort functionality
    """
    
    def topological_sort(self):
        """
        拓扑排序，用于确定任务执行顺序
        Topological sort for determining task execution order
        
        Returns:
            list: 拓扑排序结果，如果存在循环依赖则返回空列表
                  Topologically sorted list, or empty list if circular dependency exists
        """
        return topological_sort(self)
    
    def has_cycle(self):
        """
        检测图中是否存在循环依赖
        Detect if there's a circular dependency in the graph
        
        Returns:
            bool: 是否存在循环依赖 Whether circular dependency exists
        """
        return has_cycle(self)


# 测试示例
if __name__ == "__main__":
    print("拓扑排序 - 示例运行")
    print("Topological Sort - Example Run")
    
    # 创建一个拓扑排序网络 Create a topological sort network
    network = TopologicalSortNetwork(6, directed=True, storage_type="adj_list")
    
    # 添加一些边形成有向无环图 Add some edges to form a DAG
    edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5)]
    for u, v in edges:
        network.add_edge(u, v)
    
    print(f"添加了 {len(edges)} 条边形成有向无环图")
    print(f"Added {len(edges)} edges to form a DAG")
    
    # 检查是否有循环 Check for cycles
    cycle_exists = network.has_cycle()
    print(f"图中是否存在循环: {cycle_exists}")
    print(f"Does the graph have cycles: {cycle_exists}")
    
    # 执行拓扑排序 Perform topological sort
    topo_order = network.topological_sort()
    print(f"拓扑排序结果: {topo_order}")
    print(f"Topological sort result: {topo_order}")
    
    # 创建一个带循环的图 Create a graph with a cycle
    print(f"\n创建一个带循环的图...")
    print(f"Creating a graph with a cycle...")
    
    cycle_network = TopologicalSortNetwork(4, directed=True, storage_type="adj_list")
    cycle_edges = [(0, 1), (1, 2), (2, 3), (3, 1)]  # 包含1->2->3->1的循环 Contains cycle 1->2->3->1
    for u, v in cycle_edges:
        cycle_network.add_edge(u, v)
    
    print(f"添加了 {len(cycle_edges)} 条边形成循环")
    print(f"Added {len(cycle_edges)} edges to form a cycle")
    
    # 检查循环 Check for cycle
    cycle_exists = cycle_network.has_cycle()
    print(f"图中是否存在循环: {cycle_exists}")
    print(f"Does the graph have cycles: {cycle_exists}")
    
    # 尝试拓扑排序 Try topological sort
    topo_order = cycle_network.topological_sort()
    print(f"拓扑排序结果 (应为空列表): {topo_order}")
    print(f"Topological sort result (should be empty list): {topo_order}")