social_network_analysis.py

"""
社交媒体网络分析系统
Social Network Analysis System
"""

import heapq
from collections import defaultdict, deque
import random


class SocialNetwork:
    """
    社交网络分析系统类
    Social Network Analysis System Class
    
    该类实现了社交媒体平台的网络分析功能，包括影响力传播、社区发现、最短路径计算等功能。
    This class implements network analysis functions for social media platforms, 
    including influence propagation, community detection, shortest path calculation, etc.
    
    图存储结构分析 Graph Storage Structure Analysis:
    1. 邻接表 (Adjacency List):
       - 空间复杂度 Space Complexity: O(V + E)，其中V是顶点数，E是边数
       - 查找邻居时间复杂度 Time Complexity for finding neighbors: O(degree of vertex)
       - 添加边时间复杂度 Time Complexity for adding edge: O(1) 平均
       - 适用于稀疏图 Suitable for sparse graphs
    
    2. 邻接矩阵 (Adjacency Matrix):
       - 空间复杂度 Space Complexity: O(V^2)
       - 查找邻居时间复杂度 Time Complexity for finding neighbors: O(V)
       - 添加边时间复杂度 Time Complexity for adding edge: O(1)
       - 适用于稠密图 Suitable for dense graphs
    """
    
    def __init__(self, n, directed=True, storage_type="adj_list"):
        """
        初始化图结构
        Initialize graph structure
        
        Args:
            n (int): 节点数量 Number of nodes
            directed (bool): 是否是有向图 Whether the graph is directed
            storage_type (str): 存储类型 ("adj_list" 或 "adj_matrix") Storage type
        """
        self.n = n  # 用户数量 Number of users
        self.directed = directed  # 是否有向 Whether directed
        self.storage_type = storage_type  # 存储类型 Storage type
        
        # 存储用户属性的数据结构 Data structures for user attributes
        self.user_attributes = {}
        for i in range(n):
            self.user_attributes[i] = {
                'id': i,
                'followers': 0,  # 粉丝数 Number of followers
                'posts': 0,      # 发帖数 Number of posts
                'label': i       # 标签 Label (for community detection)
            }
        
        # 根据存储类型初始化图结构 Initialize graph structure based on storage type
        if storage_type == "adj_list":
            # 邻接表 Adjacency list
            self.graph = defaultdict(list)
            self.in_edges = defaultdict(list)  # 反向边，用于计算粉丝列表 Reverse edges for calculating followers
        elif storage_type == "adj_matrix":
            # 邻接矩阵 Adjacency matrix
            self.graph = [[0 for _ in range(n)] for _ in range(n)]
            self.in_edges = None  # 邻接矩阵不需要反向边结构 No reverse edge structure needed for adjacency matrix
        else:
            raise ValueError("存储类型必须是 'adj_list' 或 'adj_matrix'")
    
    def add_edge(self, u, v):
        """
        添加关注关系
        Add following relationship
        
        Args:
            u (int): 关注者 Follower
            v (int): 被关注者 Followee
        """
        if self.storage_type == "adj_list":
            # 在邻接表中添加边 Add edge to adjacency list
            if v not in self.graph[u]:
                self.graph[u].append(v)
            if self.directed:
                # 对于有向图，v的粉丝数加1 For directed graph, increment v's follower count
                self.user_attributes[v]['followers'] += 1
                # 同时记录反向边 Also record reverse edge
                if u not in self.in_edges[v]:
                    self.in_edges[v].append(u)
        else:  # adj_matrix
            # 在邻接矩阵中添加边 Add edge to adjacency matrix
            self.graph[u][v] = 1
            if self.directed:
                # 对于有向图，v的粉丝数加1 For directed graph, increment v's follower count
                self.user_attributes[v]['followers'] += 1
    
    def remove_edge(self, u, v):
        """
        移除关注关系
        Remove following relationship
        
        Args:
            u (int): 关注者 Follower
            v (int): 被关注者 Followee
        """
        if self.storage_type == "adj_list":
            # 从邻接表中移除边 Remove edge from adjacency list
            if v in self.graph[u]:
                self.graph[u].remove(v)
            if self.directed:
                # 更新粉丝数 Update follower count
                self.user_attributes[v]['followers'] -= 1
                if u in self.in_edges[v]:
                    self.in_edges[v].remove(u)
        else:  # adj_matrix
            # 从邻接矩阵中移除边 Remove edge from adjacency matrix
            self.graph[u][v] = 0
            if self.directed:
                # 更新粉丝数 Update follower count
                self.user_attributes[v]['followers'] -= 1
    
    def has_edge(self, u, v):
        """
        检查是否存在边
        Check if edge exists
        
        Args:
            u (int): 起始节点 Start node
            v (int): 目标节点 Target node
            
        Returns:
            bool: 是否存在边 Whether edge exists
        """
        if self.storage_type == "adj_list":
            return v in self.graph[u]
        else:  # adj_matrix
            return self.graph[u][v] == 1
    
    def get_followers(self, user):
        """
        获取指定用户的粉丝列表
        Get followers list for a specific user
        
        Args:
            user (int): 用户ID User ID
            
        Returns:
            list: 粉丝列表 Followers list
        """
        if self.storage_type == "adj_list":
            return self.in_edges[user][:]
        else:  # adj_matrix
            # 在邻接矩阵中查找所有指向该用户的节点 Find all nodes pointing to this user in adjacency matrix
            followers = []
            for i in range(self.n):
                if self.graph[i][user] == 1:
                    followers.append(i)
            return followers
    
    def get_following(self, user):
        """
        获取指定用户的关注列表
        Get following list for a specific user
        
        Args:
            user (int): 用户ID User ID
            
        Returns:
            list: 关注列表 Following list
        """
        if self.storage_type == "adj_list":
            return self.graph[user][:]
        else:  # adj_matrix
            # 在邻接矩阵中查找该用户指向的所有节点 Find all nodes this user points to in adjacency matrix
            following = []
            for i in range(self.n):
                if self.graph[user][i] == 1:
                    following.append(i)
            return following
    
    def get_degree(self, user):
        """
        获取用户的总度数（关注数+粉丝数）
        Get total degree of user (following + followers)
        
        Args:
            user (int): 用户ID User ID
            
        Returns:
            int: 总度数 Total degree
        """
        following = len(self.get_following(user))
        followers = self.user_attributes[user]['followers']
        return following + followers
    
    def get_node_density(self):
        """
        计算图的密度
        Calculate graph density
        
        Returns:
            float: 图的密度 Graph density
        """
        total_possible_edges = self.n * (self.n - 1) if self.directed else self.n * (self.n - 1) // 2
        
        if total_possible_edges == 0:
            return 0.0
            
        if self.storage_type == "adj_list":
            actual_edges = sum(len(self.graph[node]) for node in range(self.n))
        else:  # adj_matrix
            actual_edges = sum(sum(row) for row in self.graph)
            
        return actual_edges / total_possible_edges
    
    def k_step_influence(self, start, k):
        """
        计算k步内影响力传播范围
        Calculate influence spread within k steps
        
        Args:
            start (int): 起始用户ID Start user ID
            k (int): 传播步数 Number of steps
            
        Returns:
            int: k步内能影响的用户数 Number of users influenced within k steps
            list: 受影响的用户列表 List of influenced users
        """
        # 使用广度优先搜索实现 k 步影响力传播
        # Implement k-step influence propagation using breadth-first search
        visited = set()  # 记录访问过的节点 Track visited nodes
        queue = deque([(start, 0)])  # 队列保存 (节点, 步数) Queue stores (node, step)
        visited.add(start)
        
        influenced_users = [start]  # 受影响的用户列表 List of influenced users
        
        while queue:
            current_node, current_step = queue.popleft()
            
            # 如果当前步数达到k，则停止传播 If current step reaches k, stop propagation
            if current_step >= k:
                continue
                
            # 获取当前节点的邻居 Get neighbors of current node
            neighbors = self.get_following(current_node)
            
            for neighbor in neighbors:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, current_step + 1))
                    influenced_users.append(neighbor)
        
        return len(influenced_users), influenced_users
    
    def bfs_shortest_path(self, start, end):
        """
        使用BFS计算两点间的最短路径
        Calculate shortest path between two points using BFS
        
        Args:
            start (int): 起始节点 Start node
            end (int): 结束节点 End node
            
        Returns:
            list: 最短路径节点列表 Shortest path node list
        """
        if start == end:
            return [start]
            
        visited = set()
        queue = deque([(start, [start])])
        visited.add(start)
        
        while queue:
            current_node, path = queue.popleft()
            
            for neighbor in self.get_following(current_node):
                if neighbor == end:
                    return path + [neighbor]
                    
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, path + [neighbor]))
        
        return []  # 无路径 No path
    
    def select_seed_users_greedy(self, k_steps, target_coverage, max_seeds=None):
        """
        使用贪心算法选择种子用户以最大化影响力覆盖
        Use greedy algorithm to select seed users to maximize influence coverage
        
        Args:
            k_steps (int): 传播步数 Number of propagation steps
            target_coverage (int): 目标覆盖用户数 Target number of users to cover
            max_seeds (int): 最大种子用户数 Maximum number of seed users (optional)
            
        Returns:
            list: 选择的种子用户列表 Selected seed users list
        """
        if max_seeds is None:
            max_seeds = self.n  # 默认最多选择所有节点 Default to selecting all nodes if needed
            
        selected_seeds = []
        covered_nodes = set()
        
        # 贪心算法：每一步选择能覆盖最多未覆盖节点的用户
        # Greedy algorithm: At each step, select the user that covers the most uncovered nodes
        for _ in range(max_seeds):
            if len(covered_nodes) >= target_coverage:
                break
                
            best_user = None
            best_coverage = -1
            
            # 遍历所有可能的种子用户 Iterate through all possible seed users
            for user in range(self.n):
                # 如果用户已经在种子列表中，跳过 Skip if user is already in seed list
                if user in selected_seeds:
                    continue
                    
                # 计算该用户k步内的影响力 Calculate influence of this user within k steps
                _, influenced_users = self.k_step_influence(user, k_steps)
                
                # 计算该用户能新增覆盖的节点数 Calculate additional nodes this user can cover
                newly_covered = set(influenced_users) - covered_nodes
                new_coverage = len(newly_covered)
                
                # 更新最佳用户 Update best user if this one covers more
                if new_coverage > best_coverage:
                    best_coverage = new_coverage
                    best_user = user
            
            # 如果没有找到能增加覆盖的用户，结束 If no user increases coverage, end
            if best_user is None or best_coverage == 0:
                break
                
            # 将最佳用户加入种子列表 Add best user to seed list
            selected_seeds.append(best_user)
            
            # 更新已覆盖节点 Update covered nodes
            _, influenced_users = self.k_step_influence(best_user, k_steps)
            covered_nodes.update(influenced_users)
        
        return selected_seeds
    
    def community_detection(self, algorithm='lpa', iterations=100):
        """
        社区发现算法
        Community Detection Algorithm
        
        Args:
            algorithm (str): 算法类型 ('lpa' for Label Propagation Algorithm)
            iterations (int): 最大迭代次数 Maximum number of iterations
            
        Returns:
            dict: 社区划分结果，键为社区标签，值为属于该社区的节点列表
                  Community partitioning result, key is community label, value is list of nodes in that community
        """
        if algorithm == 'lpa':
            return self._label_propagation_algorithm(iterations)
        else:
            raise ValueError(f"不支持的算法类型: {algorithm}")
    
    def _label_propagation_algorithm(self, iterations):
        """
        基于标签传播的社区发现算法
        Label Propagation Algorithm for Community Detection
        
        Args:
            iterations (int): 最大迭代次数 Maximum number of iterations
            
        Returns:
            dict: 社区划分结果 Community partitioning result
        """
        # 初始化每个节点的标签 Initialize labels for each node
        labels = {i: i for i in range(self.n)}
        
        # 迭代更新标签 Iterate to update labels
        for iteration in range(iterations):
            # 随机打乱节点顺序 Randomly shuffle node order
            nodes = list(range(self.n))
            random.shuffle(nodes)
            
            unchanged = True
            
            for node in nodes:
                # 获取邻居节点 Get neighbor nodes
                neighbors = self.get_following(node)
                
                # 统计邻居节点的标签频率 Count frequency of neighbor labels
                label_counts = defaultdict(int)
                for neighbor in neighbors:
                    label_counts[labels[neighbor]] += 1
                
                # 如果没有邻居，跳过 If no neighbors, skip
                if not label_counts:
                    continue
                
                # 选择出现频率最高的标签 Select the most frequent label
                max_count = max(label_counts.values())
                candidates = [label for label, count in label_counts.items() if count == max_count]
                
                # 随机选择一个标签（如果有多个最高频率的标签）Randomly select a label if multiple have max frequency
                new_label = min(candidates)  # 使用min确保结果一致性 Use min for consistent results
                
                # 更新标签 Update label if different
                if labels[node] != new_label:
                    labels[node] = new_label
                    unchanged = False
            
            # 如果没有标签发生变化，提前结束 If no labels changed, end early
            if unchanged:
                break
        
        # 将相同标签的节点分组 Group nodes with the same label
        communities = defaultdict(list)
        for node, label in labels.items():
            communities[label].append(node)
        
        return dict(communities)
    
    def floyd_warshall_all_pairs_shortest_path(self):
        """
        使用Floyd-Warshall算法计算所有节点对之间的最短路径
        Calculate all-pairs shortest paths using Floyd-Warshall algorithm
        
        Returns:
            list: 二维数组，dist[i][j]表示从节点i到节点j的最短距离
                  2D array where dist[i][j] represents the shortest distance from node i to node j
        """
        # 初始化距离矩阵 Initialize distance matrix
        INF = float('inf')
        dist = [[INF for _ in range(self.n)] for _ in range(self.n)]
        
        # 设置初始距离 Set initial distances
        for i in range(self.n):
            dist[i][i] = 0  # 自己到自己的距离为0 Distance from node to itself is 0
        
        # 添加直接相连的边 Add directly connected edges
        for i in range(self.n):
            neighbors = self.get_following(i)
            for j in neighbors:
                dist[i][j] = 1  # 直接相连的距离为1 Distance for directly connected nodes is 1
        
        # Floyd-Warshall算法 Floyd-Warshall algorithm
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        
        return dist
    
    def compute_betweenness_centrality(self):
        """
        计算每个节点的介数中心性（Betweenness Centrality）
        Compute betweenness centrality for each node
        
        Returns:
            dict: 每个节点的介数中心性值 Dictionary of betweenness centrality values for each node
        """
        betweenness = {i: 0.0 for i in range(self.n)}
        
        # 对每个节点计算它在多少最短路径上 For each node, calculate how many shortest paths it lies on
        for s in range(self.n):
            # 使用BFS计算从s出发的最短路径 Use BFS to calculate shortest paths from s
            stack = []
            predecessors = {i: [] for i in range(self.n)}
            shortest_paths_num = {i: 0 for i in range(self.n)}
            distance = {i: -1 for i in range(self.n)}
            
            queue = deque([s])
            distance[s] = 0
            shortest_paths_num[s] = 1
            
            while queue:
                v = queue.popleft()
                stack.append(v)
                
                # 遍历v的邻居节点 Iterate through neighbors of v
                for w in self.get_following(v):
                    if distance[w] == -1:  # w未被访问过 w hasn't been visited
                        queue.append(w)
                        distance[w] = distance[v] + 1
                    
                    if distance[w] == distance[v] + 1:  # w在最短路径上 w is on shortest path
                        shortest_paths_num[w] += shortest_paths_num[v]
                        predecessors[w].append(v)
            
            # 计算依赖度 Calculate dependencies
            delta = {i: 0.0 for i in range(self.n)}
            
            # 从栈顶开始计算 Calculate from top of stack
            while stack:
                w = stack.pop()
                for v in predecessors[w]:
                    delta[v] += (shortest_paths_num[v] / shortest_paths_num[w]) * (1 + delta[w])
                
                if w != s:
                    betweenness[w] += delta[w]
        
        # 标准化介数中心性 Normalize betweenness centrality
        for node in betweenness:
            betweenness[node] /= 2  # 因为图是有向的，但我们在计算无向图的中心性 Because the graph is directed, but we're calculating undirected graph centrality
        
        return betweenness
    
    def topological_sort(self):
        """
        拓扑排序，用于确定任务执行顺序
        Topological sort for determining task execution order
        
        Returns:
            list: 拓扑排序结果，如果存在循环依赖则返回空列表
                  Topologically sorted list, or empty list if circular dependency exists
        """
        # 计算每个节点的入度 Calculate in-degree for each node
        in_degree = [0] * self.n
        
        for i in range(self.n):
            neighbors = self.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(self.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 self.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) != self.n:
            return []  # 循环依赖存在 Circular dependency exists
        
        return topo_order
    
    def has_cycle(self):
        """
        检测图中是否存在循环依赖
        Detect if there's a circular dependency in the graph
        
        Returns:
            bool: 是否存在循环依赖 Whether circular dependency exists
        """
        # 使用DFS检测循环 Use DFS to detect cycles
        WHITE, GRAY, BLACK = 0, 1, 2
        color = [WHITE] * self.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 self.get_following(node):
                if dfs_visit(neighbor):
                    return True
            
            color[node] = BLACK  # 标记为已完成访问 Mark as completely visited
            return False
        
        for i in range(self.n):
            if color[i] == WHITE:
                if dfs_visit(i):
                    return True
        
        return False


class HashTable:
    """
    哈希表实现，用于快速查询
    Hash Table implementation for fast queries
    
    哈希函数采用除法散列，冲突解决使用链地址法
    Hash function uses division method, collision resolution uses chaining
    """
    
    def __init__(self, size=1000):
        """
        初始化哈希表
        Initialize hash table
        
        Args:
            size (int): 哈希表大小 Hash table size
        """
        self.size = size
        self.table = [[] for _ in range(size)]  # 使用链地址法处理冲突 Use chaining to handle collisions
        self.count = 0  # 元素数量 Number of elements
    
    def _hash(self, key):
        """
        哈希函数
        Hash function
        
        Args:
            key: 键 Key
            
        Returns:
            int: 哈希值 Hash value
        """
        if isinstance(key, str):
            # 字符串哈希：使用多项式滚动哈希 Use polynomial rolling hash for strings
            hash_value = 0
            for char in key:
                hash_value = (hash_value * 31 + ord(char)) % self.size
            return hash_value
        else:
            # 数字哈希：使用除法散列 Use division hashing for numbers
            return hash(key) % self.size
    
    def insert(self, key, value):
        """
        插入键值对
        Insert key-value pair
        
        Args:
            key: 键 Key
            value: 值 Value
        """
        index = self._hash(key)
        bucket = self.table[index]
        
        # 检查键是否已存在 Check if key already exists
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # 更新现有键 Update existing key
                return
        
        # 添加新的键值对 Add new key-value pair
        bucket.append((key, value))
        self.count += 1
    
    def search(self, key):
        """
        搜索键对应的值
        Search for value corresponding to key
        
        Args:
            key: 键 Key
            
        Returns:
            值或None Value or None if not found
        """
        index = self._hash(key)
        bucket = self.table[index]
        
        for k, v in bucket:
            if k == key:
                return v
        
        return None  # 未找到 Not found
    
    def delete(self, key):
        """
        删除键值对
        Delete key-value pair
        
        Args:
            key: 键 Key
            
        Returns:
            bool: 是否删除成功 Whether deletion was successful
        """
        index = self._hash(key)
        bucket = self.table[index]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.count -= 1
                return True
        
        return False  # 键不存在 Key doesn't exist


class MaxHeap:
    """
    最大堆实现，用于维护Top-K排名
    Max Heap implementation for maintaining Top-K rankings
    """
    
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left_child(self, i):
        return 2 * i + 1
    
    def right_child(self, i):
        return 2 * i + 2
    
    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    
    def insert(self, value):
        """
        插入元素
        Insert element
        """
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)
    
    def _heapify_up(self, i):
        """
        向上调整堆
        Heapify up
        """
        while i != 0 and self.heap[self.parent(i)][0] < self.heap[i][0]:
            self.swap(i, self.parent(i))
            i = self.parent(i)
    
    def extract_max(self):
        """
        提取最大元素
        Extract maximum element
        """
        if not self.heap:
            return None
        
        if len(self.heap) == 1:
            return self.heap.pop()
        
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        
        return root
    
    def _heapify_down(self, i):
        """
        向下调整堆
        Heapify down
        """
        largest = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        if left < len(self.heap) and self.heap[left][0] > self.heap[largest][0]:
            largest = left
        
        if right < len(self.heap) and self.heap[right][0] > self.heap[largest][0]:
            largest = right
        
        if largest != i:
            self.swap(i, largest)
            self._heapify_down(largest)
    
    def peek(self):
        """
        查看堆顶元素
        Peek at root element
        """
        return self.heap[0] if self.heap else None
    
    def size(self):
        """
        返回堆大小
        Return heap size
        """
        return len(self.heap)


class MinHeap:
    """
    最小堆实现，用于维护Top-K排名
    Min Heap implementation for maintaining Top-K rankings
    """
    
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left_child(self, i):
        return 2 * i + 1
    
    def right_child(self, i):
        return 2 * i + 2
    
    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    
    def insert(self, value):
        """
        插入元素
        Insert element
        """
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)
    
    def _heapify_up(self, i):
        """
        向上调整堆
        Heapify up
        """
        while i != 0 and self.heap[self.parent(i)][0] > self.heap[i][0]:
            self.swap(i, self.parent(i))
            i = self.parent(i)
    
    def extract_min(self):
        """
        提取最小元素
        Extract minimum element
        """
        if not self.heap:
            return None
        
        if len(self.heap) == 1:
            return self.heap.pop()
        
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        
        return root
    
    def _heapify_down(self, i):
        """
        向下调整堆
        Heapify down
        """
        smallest = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        if left < len(self.heap) and self.heap[left][0] < self.heap[smallest][0]:
            smallest = left
        
        if right < len(self.heap) and self.heap[right][0] < self.heap[smallest][0]:
            smallest = right
        
        if smallest != i:
            self.swap(i, smallest)
            self._heapify_down(smallest)
    
    def peek(self):
        """
        查看堆顶元素
        Peek at root element
        """
        return self.heap[0] if self.heap else None
    
    def size(self):
        """
        返回堆大小
        Return heap size
        """
        return len(self.heap)


class OptimizedSocialNetwork(SocialNetwork):
    """
    优化的社交网络类，使用哈希表加速查询
    Optimized Social Network class that uses hash tables to accelerate queries
    """
    
    def __init__(self, n, directed=True, storage_type="adj_list"):
        super().__init__(n, directed, storage_type)
        
        # 创建哈希表用于快速查询 Create hash tables for fast queries
        self.user_info_table = HashTable(size=max(1000, n // 10))  # 用户信息表 User info table
        self.edge_query_table = HashTable(size=max(2000, n // 5))   # 边查询表 Edge query table
        self.label_query_table = HashTable(size=max(1000, n // 10)) # 标签查询表 Label query table
        
        # 初始化用户信息表 Initialize user info table
        for i in range(n):
            self.user_info_table.insert(i, self.user_attributes[i])
    
    def add_edge(self, u, v):
        """
        添加关注关系（重写父类方法以更新哈希表）
        Add following relationship (override parent method to update hash tables)
        """
        super().add_edge(u, v)
        
        # 更新用户信息表 Update user info table
        self.user_info_table.insert(u, self.user_attributes[u])
        self.user_info_table.insert(v, self.user_attributes[v])
        
        # 更新边查询表 Update edge query table
        edge_key = (u, v)
        self.edge_query_table.insert(edge_key, True)
    
    def remove_edge(self, u, v):
        """
        移除关注关系（重写父类方法以更新哈希表）
        Remove following relationship (override parent method to update hash tables)
        """
        super().remove_edge(u, v)
        
        # 更新用户信息表 Update user info table
        self.user_info_table.insert(u, self.user_attributes[u])
        self.user_info_table.insert(v, self.user_attributes[v])
        
        # 更新边查询表 Update edge query table
        edge_key = (u, v)
        self.edge_query_table.delete(edge_key)
    
    def quick_user_lookup(self, user_id):
        """
        快速用户信息查询
        Quick user information lookup
        
        Args:
            user_id (int): 用户ID User ID
            
        Returns:
            dict: 用户信息 User information
        """
        return self.user_info_table.search(user_id)
    
    def quick_edge_check(self, u, v):
        """
        快速检查两个用户之间是否存在关注关系
        Quickly check if there's a following relationship between two users
        
        Args:
            u (int): 起始用户ID Start user ID
            v (int): 目标用户ID Target user ID
            
        Returns:
            bool: 是否存在关注关系 Whether following relationship exists
        """
        edge_key = (u, v)
        result = self.edge_query_table.search(edge_key)
        return result is not None
    
    def quick_label_search(self, label):
        """
        快速检索具有相同标签的用户
        Quickly retrieve users with the same label
        
        Args:
            label: 标签 Label
            
        Returns:
            list: 具有相同标签的用户列表 List of users with the same label
        """
        # 遍历所有用户来查找具有特定标签的用户
        # Iterate through all users to find those with specific label
        users_with_label = []
        for user_id in range(self.n):
            user_info = self.quick_user_lookup(user_id)
            if user_info and user_info.get('label') == label:
                users_with_label.append(user_id)
        
        return users_with_label
    
    def get_top_k_by_followers(self, k):
        """
        获取粉丝数前K名的用户
        Get top K users by number of followers
        
        Args:
            k (int): 前K名 Top K
            
        Returns:
            list: 前K名用户列表 List of top K users
        """
        # 使用最小堆维护Top-K列表
        # Use min heap to maintain Top-K list
        min_heap = MinHeap()
        
        for user_id in range(self.n):
            followers_count = self.user_attributes[user_id]['followers']
            
            if min_heap.size() < k:
                # 堆未满，直接插入 Heap not full, insert directly
                min_heap.insert((followers_count, user_id))
            elif followers_count > min_heap.peek()[0]:
                # 当前用户粉丝数比堆顶多，替换堆顶 Current user has more followers than heap top, replace heap top
                min_heap.extract_min()
                min_heap.insert((followers_count, user_id))
        
        # 提取结果 Extract results
        result = []
        temp_list = []
        
        # 将堆中元素取出并按粉丝数降序排列 Extract elements from heap and sort by followers in descending order
        while min_heap.size() > 0:
            followers_count, user_id = min_heap.extract_min()
            temp_list.append((followers_count, user_id))
        
        # 按粉丝数降序排列 Sort by followers in descending order
        temp_list.sort(reverse=True)
        
        for followers_count, user_id in temp_list:
            result.append((user_id, followers_count))
        
        return result
    
    def get_top_k_by_posts(self, k):
        """
        获取发帖数前K名的用户
        Get top K users by number of posts
        
        Args:
            k (int): 前K名 Top K
            
        Returns:
            list: 前K名用户列表 List of top K users
        """
        # 使用最小堆维护Top-K列表
        # Use min heap to maintain Top-K list
        min_heap = MinHeap()
        
        for user_id in range(self.n):
            posts_count = self.user_attributes[user_id]['posts']
            
            if min_heap.size() < k:
                # 堆未满，直接插入 Heap not full, insert directly
                min_heap.insert((posts_count, user_id))
            elif posts_count > min_heap.peek()[0]:
                # 当前用户发帖数比堆顶多，替换堆顶 Current user has more posts than heap top, replace heap top
                min_heap.extract_min()
                min_heap.insert((posts_count, user_id))
        
        # 提取结果 Extract results
        result = []
        temp_list = []
        
        # 将堆中元素取出并按发帖数降序排列 Extract elements from heap and sort by posts in descending order
        while min_heap.size() > 0:
            posts_count, user_id = min_heap.extract_min()
            temp_list.append((posts_count, user_id))
        
        # 按发帖数降序排列 Sort by posts in descending order
        temp_list.sort(reverse=True)
        
        for posts_count, user_id in temp_list:
            result.append((user_id, posts_count))
        
        return result
    
    def update_user_posts(self, user_id, posts_count):
        """
        更新用户发帖数并更新相关数据结构
        Update user post count and update related data structures
        
        Args:
            user_id (int): 用户ID User ID
            posts_count (int): 新的发帖数 New post count
        """
        if 0 <= user_id < self.n:
            self.user_attributes[user_id]['posts'] = posts_count
            # 更新哈希表 Update hash table
            self.user_info_table.insert(user_id, self.user_attributes[user_id])


def get_top_k_with_heap(data, k, max_heap=True):
    """
    使用堆获取前K个元素
    Get top K elements using heap
    
    Args:
        data (list): 数据列表 Data list
        k (int): 前K个 Top K
        max_heap (bool): 是否使用最大堆 Whether to use max heap
        
    Returns:
        list: 前K个元素列表 List of top K elements
    """
    if max_heap:
        heap = MaxHeap()
    else:
        heap = MinHeap()
    
    for value in data:
        if heap.size() < k:
            heap.insert(value)
        elif max_heap and value[0] > heap.peek()[0]:
            heap.extract_max()
            heap.insert(value)
        elif not max_heap and value[0] < heap.peek()[0]:
            heap.extract_min()
            heap.insert(value)
    
    result = []
    while heap.size() > 0:
        if max_heap:
            result.append(heap.extract_max())
        else:
            result.append(heap.extract_min())
    
    # 如果使用的是最小堆，需要反转结果 If using min heap, reverse the result
    if not max_heap:
        result.reverse()
    
    return result


def quicksort(arr, key_func=None, ascending=True):
    """
    快速排序算法
    QuickSort algorithm
    
    Args:
        arr (list): 待排序数组 Array to sort
        key_func (function): 提取比较键的函数 Function to extract comparison key
        ascending (bool): 是否升序排列 Whether to sort in ascending order
        
    Returns:
        list: 排序后的数组 Sorted array
    """
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    pivot_key = key_func(pivot) if key_func else pivot
    
    # 分割数组 Partition array
    if key_func:
        left = [x for x in arr if (key_func(x) < pivot_key) if ascending else (key_func(x) > pivot_key)]
        middle = [x for x in arr if key_func(x) == pivot_key]
        right = [x for x in arr if (key_func(x) > pivot_key) if ascending else (key_func(x) < pivot_key)]
    else:
        left = [x for x in arr if (x < pivot_key) if ascending else (x > pivot_key)]
        middle = [x for x in arr if x == pivot_key]
        right = [x for x in arr if (x > pivot_key) if ascending else (x < pivot_key)]
    
    # 递归排序并合并 Recursively sort and merge
    return quicksort(left, key_func, ascending) + middle + quicksort(right, key_func, ascending)


def mergesort(arr, key_func=None, ascending=True):
    """
    归并排序算法
    MergeSort algorithm
    
    Args:
        arr (list): 待排序数组 Array to sort
        key_func (function): 提取比较键的函数 Function to extract comparison key
        ascending (bool): 是否升序排列 Whether to sort in ascending order
        
    Returns:
        list: 排序后的数组 Sorted array
    """
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = mergesort(arr[:mid], key_func, ascending)
    right = mergesort(arr[mid:], key_func, ascending)
    
    # 合并两个有序数组 Merge two sorted arrays
    return merge(left, right, key_func, ascending)


def merge(left, right, key_func=None, ascending=True):
    """
    合并两个有序数组
    Merge two sorted arrays
    
    Args:
        left (list): 左侧有序数组 Left sorted array
        right (list): 右侧有序数组 Right sorted array
        key_func (function): 提取比较键的函数 Function to extract comparison key
        ascending (bool): 是否升序排列 Whether to sort in ascending order
        
    Returns:
        list: 合并后的有序数组 Merged sorted array
    """
    result = []
    i = j = 0
    
    # 比较并合并 Compare and merge
    while i < len(left) and j < len(right):
        left_val = key_func(left[i]) if key_func else left[i]
        right_val = key_func(right[j]) if key_func else right[j]
        
        if (left_val <= right_val) if ascending else (left_val >= right_val):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 添加剩余元素 Add remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result


def binary_search(arr, target, key_func=None):
    """
    二分查找算法
    Binary search algorithm
    
    Args:
        arr (list): 已排序数组 Sorted array
        target: 目标值 Target value
        key_func (function): 提取比较键的函数 Function to extract comparison key
        
    Returns:
        int: 目标值索引，若未找到返回-1 Index of target value, -1 if not found
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        mid_val = key_func(arr[mid]) if key_func else arr[mid]
        
        if mid_val == target:
            return mid
        elif mid_val < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1


def binary_search_range(arr, target, key_func=None):
    """
    二分查找变种：查找目标值的范围
    Binary search variant: find range of target values
    
    Args:
        arr (list): 已排序数组 Sorted array
        target: 目标值 Target value
        key_func (function): 提取比较键的函数 Function to extract comparison key
        
    Returns:
        tuple: (起始索引, 结束索引) 或 (-1, -1) (start index, end index) or (-1, -1)
    """
    def find_first():
        left, right = 0, len(arr) - 1
        result = -1
        while left <= right:
            mid = (left + right) // 2
            mid_val = key_func(arr[mid]) if key_func else arr[mid]
            
            if mid_val == target:
                result = mid
                right = mid - 1  # 继续向左找 Keep searching to the left
            elif mid_val < target:
                left = mid + 1
            else:
                right = mid - 1
        return result
    
    def find_last():
        left, right = 0, len(arr) - 1
        result = -1
        while left <= right:
            mid = (left + right) // 2
            mid_val = key_func(arr[mid]) if key_func else arr[mid]
            
            if mid_val == target:
                result = mid
                left = mid + 1  # 继续向右找 Keep searching to the right
            elif mid_val < target:
                left = mid + 1
            else:
                right = mid - 1
        return result
    
    first = find_first()
    if first == -1:
        return (-1, -1)
    
    last = find_last()
    return (first, last)


def linear_search_multiple_conditions(arr, conditions):
    """
    多条件线性搜索
    Multi-condition linear search
    
    Args:
        arr (list): 搜索数组 Search array
        conditions (dict): 条件字典，键为属性名，值为条件值 Condition dictionary
        
    Returns:
        list: 满足条件的元素列表 List of elements satisfying conditions
    """
    result = []
    
    for item in arr:
        match = True
        for attr, condition_val in conditions.items():
            item_val = getattr(item, attr) if hasattr(item, attr) else item.get(attr) if isinstance(item, dict) else item[attr] if isinstance(item, list) else item
            if item_val != condition_val:
                match = False
                break
        
        if match:
            result.append(item)
    
    return result


class SocialNetworkWithSorting(OptimizedSocialNetwork):
    """
    支持排序和搜索的社交网络类
    Social Network class with sorting and searching capabilities
    """
    
    def sort_users_by_attribute(self, attribute, ascending=True):
        """
        按指定属性对用户进行排序
        Sort users by a specific attribute
        
        Args:
            attribute (str): 属性名 Attribute name
            ascending (bool): 是否升序 Whether to sort in ascending order
            
        Returns:
            list: 排序后的用户列表 Sorted list of users
        """
        users_with_attrs = []
        
        for user_id in range(self.n):
            user_info = self.quick_user_lookup(user_id)
            if user_info and attribute in user_info:
                users_with_attrs.append((user_info[attribute], user_id))
        
        # 使用快速排序 Sort using quicksort
        sorted_users = quicksort(users_with_attrs, key_func=lambda x: x[0], ascending=ascending)
        
        return [(user_id, attr_val) for attr_val, user_id in sorted_users]
    
    def search_users_by_conditions(self, conditions):
        """
        根据条件搜索用户
        Search users by conditions
        
        Args:
            conditions (dict): 搜索条件 Search conditions
            
        Returns:
            list: 满足条件的用户列表 List of users satisfying conditions
        """
        # 构建用户列表 Build user list
        users_list = []
        for user_id in range(self.n):
            user_info = self.quick_user_lookup(user_id)
            if user_info:
                user_info['id'] = user_id
                users_list.append(user_info)
        
        # 执行多条件搜索 Perform multi-condition search
        return linear_search_multiple_conditions(users_list, conditions)
    
    def get_users_by_follower_range(self, min_followers, max_followers):
        """
        获取粉丝数在指定范围内的用户
        Get users with follower count in specified range
        
        Args:
            min_followers (int): 最小粉丝数 Minimum followers
            max_followers (int): 最大粉丝数 Maximum followers
            
        Returns:
            list: 满足条件的用户列表 List of users satisfying conditions
        """
        result = []
        for user_id in range(self.n):
            user_info = self.quick_user_lookup(user_id)
            if user_info:
                followers = user_info.get('followers', 0)
                if min_followers <= followers <= max_followers:
                    result.append((user_id, followers))
        
        return result


def generate_test_data(network_size, edge_count):
    """
    生成测试数据
    Generate test data
    
    Args:
        network_size (int): 网络大小 Network size
        edge_count (int): 边的数量 Number of edges
        
    Returns:
        SocialNetwork: 生成的社交网络 Generated social network
    """
    # 创建社交网络 Create social network
    network = SocialNetwork(network_size, directed=True)
    
    # 随机生成边 Randomly generate edges
    edges_added = 0
    while edges_added < edge_count:
        u = random.randint(0, network_size - 1)
        v = random.randint(0, network_size - 1)
        
        # 避免自环 Avoid self-loops
        if u != v:
            # 检查是否已存在边 Check if edge already exists
            if network.storage_type == "adj_list":
                if v not in network.graph[u]:
                    network.add_edge(u, v)
                    edges_added += 1
            else:  # adj_matrix
                if network.graph[u][v] == 0:
                    network.add_edge(u, v)
                    edges_added += 1
    
    return network


# 测试数据生成函数 Test data generation functions
def generate_small_network():
    """生成小型网络 (N=1000, 边数=5000)"""
    """Generate small network (N=1000, edges=5000)"""
    return generate_test_data(1000, 5000)


def generate_medium_network():
    """生成中型网络 (N=10000, 边数=100000)"""
    """Generate medium network (N=10000, edges=100000)"""
    return generate_test_data(10000, 100000)


def generate_large_network():
    """生成大型网络 (N=100000, 边数=1000000)"""
    """Generate large network (N=100000, edges=1000000)"""
    return generate_test_data(100000, 1000000)


def run_comprehensive_tests():
    """
    运行综合测试
    Run comprehensive tests
    """
    print("=" * 60)
    print("社交媒体网络分析系统 - 综合测试")
    print("Social Network Analysis System - Comprehensive Tests")
    print("=" * 60)
    
    # 1. 测试基本功能 Test basic functionality
    print("\n1. 测试基本功能...")
    print("Testing Basic Functionality...")
    
    # 创建一个小型网络 Create a small network
    network = SocialNetwork(10, directed=True, storage_type="adj_list")
    
    # 添加一些边 Add some edges
    edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]
    for u, v in edges:
        network.add_edge(u, v)
    
    print(f"   添加了 {len(edges)} 条边")
    print(f"   Added {len(edges)} edges")
    
    # 测试关注和粉丝列表 Test following and followers lists
    print(f"   用户0的关注列表: {network.get_following(0)}")
    print(f"   用户3的粉丝列表: {network.get_followers(3)}")
    
    # 2. 测试影响力传播 Test influence propagation
    print("\n2. 测试影响力传播...")
    print("Testing Influence Propagation...")
    
    affected_count, affected_users = network.k_step_influence(0, 3)
    print(f"   从用户0开始3步内影响了 {affected_count} 个用户")
    print(f"   Affected {affected_count} users within 3 steps from user 0")
    
    # 3. 测试种子用户选择 Test seed user selection
    print("\n3. 测试种子用户选择...")
    print("Testing Seed User Selection...")
    
    seed_users = network.select_seed_users_greedy(k_steps=2, target_coverage=5, max_seeds=3)
    print(f"   选择了 {len(seed_users)} 个种子用户以覆盖至少5个用户")
    print(f"   Selected {len(seed_users)} seed users to cover at least 5 users")
    
    # 4. 测试社区检测 Test community detection
    print("\n4. 测试社区检测...")
    print("Testing Community Detection...")
    
    communities = network.community_detection(algorithm='lpa', iterations=50)
    print(f"   检测到 {len(communities)} 个社区")
    print(f"   Detected {len(communities)} communities")
    
    # 5. 测试最短路径和介数中心性 Test shortest path and betweenness centrality
    print("\n5. 测试最短路径和介数中心性...")
    print("Testing Shortest Path and Betweenness Centrality...")
    
    # 计算介数中心性 Calculate betweenness centrality
    betweenness = network.compute_betweenness_centrality()
    top_betweenness = sorted(betweenness.items(), key=lambda x: x[1], reverse=True)[:3]
    print(f"   介数中心性最高的3个节点: {top_betweenness}")
    print(f"   Top 3 nodes by betweenness centrality: {top_betweenness}")
    
    # 6. 测试拓扑排序 Test topological sort
    print("\n6. 测试拓扑排序...")
    print("Testing Topological Sort...")
    
    topo_order = network.topological_sort()
    if topo_order:
        print(f"   拓扑排序成功，顺序: {topo_order[:10]}...")  # 显示前10个节点 Show first 10 nodes
        print(f"   Topological sort successful, order: {topo_order[:10]}...")
    else:
        print("   检测到循环依赖")
        print("   Circular dependency detected")
    
    # 检测是否有循环 Detect cycles
    has_cycle = network.has_cycle()
    print(f"   网络是否有循环: {has_cycle}")
    print(f"   Does network have cycles: {has_cycle}")
    
    # 7. 测试哈希表功能 Test hash table functionality
    print("\n7. 测试哈希表功能...")
    print("Testing Hash Table Functionality...")
    
    opt_network = OptimizedSocialNetwork(10, directed=True, storage_type="adj_list")
    
    # 添加相同的边 Add the same edges
    for u, v in edges:
        opt_network.add_edge(u, v)
    
    # 测试快速查找 Test quick lookup
    user_info = opt_network.quick_user_lookup(5)
    print(f"   用户5的信息: {user_info}")
    print(f"   User 5 info: {user_info}")
    
    # 测试边快速检查 Test quick edge check
    edge_exists = opt_network.quick_edge_check(0, 1)
    print(f"   用户0到用户1的边是否存在: {edge_exists}")
    print(f"   Edge from user 0 to user 1 exists: {edge_exists}")
    
    # 8. 测试堆结构和Top-K功能 Test heap structure and Top-K functionality
    print("\n8. 测试堆结构和Top-K功能...")
    print("Testing Heap Structure and Top-K Functionality...")
    
    # 更新一些用户的帖子数 Update some user post counts
    for i in range(10):
        opt_network.update_user_posts(i, random.randint(10, 100))
    
    # 获取粉丝数前3的用户 Get top 3 users by followers
    top_followers = opt_network.get_top_k_by_followers(3)
    print(f"   粉丝数前3的用户: {top_followers}")
    print(f"   Top 3 users by followers: {top_followers}")
    
    # 获取发帖数前3的用户 Get top 3 users by posts
    top_posts = opt_network.get_top_k_by_posts(3)
    print(f"   发帖数前3的用户: {top_posts}")
    print(f"   Top 3 users by posts: {top_posts}")
    
    # 9. 测试排序和搜索功能 Test sorting and searching functionality
    print("\n9. 测试排序和搜索功能...")
    print("Testing Sorting and Searching Functionality...")
    
    sorted_network = SocialNetworkWithSorting(10, directed=True, storage_type="adj_list")
    
    # 添加相同的边 Add the same edges
    for u, v in edges:
        sorted_network.add_edge(u, v)
    
    # 更新一些用户的属性 Update some user attributes
    for i in range(10):
        sorted_network.user_attributes[i]['followers'] = random.randint(50, 500)
        sorted_network.user_attributes[i]['posts'] = random.randint(10, 100)
        sorted_network.user_info_table.insert(i, sorted_network.user_attributes[i])
    
    # 按粉丝数排序 Sort by followers
    sorted_by_followers = sorted_network.sort_users_by_attribute('followers', ascending=False)
    print(f"   按粉丝数排序前3: {sorted_by_followers[:3]}")
    print(f"   Top 3 by followers: {sorted_by_followers[:3]}")
    
    # 搜索满足条件的用户 Search users with conditions
    conditions = {'followers': lambda x: x > 200}
    filtered_users = sorted_network.get_users_by_follower_range(200, 500)
    print(f"   粉丝数在200-500之间的用户: {filtered_users[:5]}...")  # 显示前5个 Show first 5
    print(f"   Users with followers between 200-500: {filtered_users[:5]}...")
    
    # 10. 测试不同存储结构的性能 Test performance of different storage structures
    print("\n10. 测试不同存储结构的性能...")
    print("Testing Performance of Different Storage Structures...")
    
    import time
    
    # 创建邻接表和邻接矩阵网络 Create networks with different storage structures
    adj_list_net = SocialNetwork(100, directed=True, storage_type="adj_list")
    adj_matrix_net = SocialNetwork(100, directed=True, storage_type="adj_matrix")
    
    # 添加相同的边 Add same edges to both
    test_edges = [(random.randint(0, 99), random.randint(0, 99)) for _ in range(200)]
    for u, v in test_edges:
        if u != v:
            adj_list_net.add_edge(u, v)
            adj_matrix_net.add_edge(u, v)
    
    # 测试邻接表查找速度 Test adjacency list lookup speed
    start_time = time.time()
    for _ in range(1000):
        adj_list_net.get_following(random.randint(0, 99))
    adj_list_time = time.time() - start_time
    
    # 测试邻接矩阵查找速度 Test adjacency matrix lookup speed
    start_time = time.time()
    for _ in range(1000):
        adj_matrix_net.get_following(random.randint(0, 99))
    adj_matrix_time = time.time() - start_time
    
    print(f"   邻接表查找1000次耗时: {adj_list_time:.4f}s")
    print(f"   Adjacency list lookup time for 1000 queries: {adj_list_time:.4f}s")
    print(f"   邻接矩阵查找1000次耗时: {adj_matrix_time:.4f}s")
    print(f"   Adjacency matrix lookup time for 1000 queries: {adj_matrix_time:.4f}s")
    
    print("\n" + "=" * 60)
    print("所有测试完成！")
    print("All tests completed!")
    print("=" * 60)


# 运行示例代码 Example usage
if __name__ == "__main__":
    print("社交媒体网络分析系统 - 示例运行")
    print("Social Network Analysis System - Example Run")
    
    # 创建一个小的社交网络 Create a small social network
    network = SocialNetwork(5, directed=True, storage_type="adj_list")
    
    # 添加一些关注关系 Add some following relationships
    network.add_edge(0, 1)
    network.add_edge(0, 2)
    network.add_edge(1, 2)
    network.add_edge(2, 3)
    network.add_edge(3, 4)
    
    print(f"\n用户0的关注列表: {network.get_following(0)}")  # User 0's following list
    print(f"用户2的粉丝列表: {network.get_followers(2)}")   # User 2's followers list
    print(f"用户2的粉丝数: {network.user_attributes[2]['followers']}")  # User 2's follower count
    
    # 测试邻接矩阵存储方式 Test adjacency matrix storage
    network_matrix = SocialNetwork(5, directed=True, storage_type="adj_matrix")
    network_matrix.add_edge(0, 1)
    network_matrix.add_edge(0, 2)
    network_matrix.add_edge(1, 2)
    network_matrix.add_edge(2, 3)
    network_matrix.add_edge(3, 4)
    
    print(f"\n邻接矩阵 - 用户0的关注列表: {network_matrix.get_following(0)}")
    print(f"邻接矩阵 - 用户2的粉丝列表: {network_matrix.get_followers(2)}")
    print(f"邻接矩阵 - 用户2的粉丝数: {network_matrix.user_attributes[2]['followers']}")
    
    # 生成小型测试网络 Generate small test network
    print("\n生成小型测试网络...")
    small_network = generate_small_network()
    print(f"小型网络创建成功: {small_network.n} 用户, 邻接表存储")
    print(f"Small network created: {small_network.n} users, adjacency list storage")
    
    # 运行综合测试 Run comprehensive tests
    run_comprehensive_tests()