main.py

"""
社交媒体网络分析系统 - 主程序入口
Social Network Analysis System - Main Entry Point

本程序整合了所有功能模块，包括：
- 图结构表示与存储 (graph_storage.py)
- 影响力传播模型 (influence_propagation.py)
- 社区发现 (community_detection.py)
- 最短路径与中间中心性 (shortest_path_centrality.py)
- 拓扑排序 (topological_sort.py)
- 哈希表应用 (hash_table_app.py)
- 堆结构应用 (heap_structure_app.py)
- 排序与搜索算法 (sorting_searching_algorithms.py)
"""

import time
import random
from graph_storage import SocialNetwork, generate_small_network
from influence_propagation import InfluencePropagationNetwork
from community_detection import CommunityDetectionNetwork
from shortest_path_centrality import ShortestPathNetwork
from topological_sort import TopologicalSortNetwork
from hash_table_app import HashOptimizedNetwork
from heap_structure_app import HeapOptimizedNetwork
from sorting_searching_algorithms import SortingSearchingNetwork


def run_comprehensive_tests():
    """
    运行综合测试
    Run comprehensive tests
    """
    print("=" * 80)
    print("社交媒体网络分析系统 - 综合测试")
    print("Social Network Analysis System - Comprehensive Tests")
    print("=" * 80)
    
    # 1. 测试图结构表示与存储 Test graph storage representation
    print("\n1. 测试图结构表示与存储...")
    print("Testing Graph Storage Representation...")
    
    # 创建一个小型网络 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)}")
    print(f"   用户3的粉丝数: {network.user_attributes[3]['followers']}")
    
    # 2. 测试影响力传播 Test influence propagation
    print("\n2. 测试影响力传播...")
    print("Testing Influence Propagation...")
    
    influence_network = InfluencePropagationNetwork(10, directed=True, storage_type="adj_list")
    for u, v in edges:
        influence_network.add_edge(u, v)
    
    affected_count, affected_users = influence_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 = influence_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...")
    
    community_network = CommunityDetectionNetwork(10, directed=True, storage_type="adj_list")
    # 添加一些边形成社区结构 Add edges to form community structure
    community_edges = [
        (0, 1), (0, 2), (1, 2),  # 社区1 Community 1
        (3, 4), (3, 5), (4, 5),  # 社区2 Community 2
        (6, 7), (6, 8), (7, 8), (7, 9), (8, 9),  # 社区3 Community 3
        (2, 3), (5, 6)  # 连接不同社区 Connect different communities
    ]
    for u, v in community_edges:
        community_network.add_edge(u, v)
    
    communities = community_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...")
    
    path_network = ShortestPathNetwork(6, directed=True, storage_type="adj_list")
    path_edges = [(0, 1), (1, 2), (2, 3), (0, 4), (4, 5), (5, 3), (1, 3)]
    for u, v in path_edges:
        path_network.add_edge(u, v)
    
    # 计算介数中心性 Calculate betweenness centrality
    betweenness = path_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_network = TopologicalSortNetwork(6, directed=True, storage_type="adj_list")
    topo_edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5)]
    for u, v in topo_edges:
        topo_network.add_edge(u, v)
    
    topo_order = topo_network.topological_sort()
    if topo_order:
        print(f"   拓扑排序成功，顺序: {topo_order}")
        print(f"   Topological sort successful, order: {topo_order}")
    else:
        print("   检测到循环依赖")
        print("   Circular dependency detected")
    
    # 检测是否有循环 Detect cycles
    has_cycle = topo_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...")
    
    hash_network = HashOptimizedNetwork(10, directed=True, storage_type="adj_list")
    for u, v in edges:
        hash_network.add_edge(u, v)
    
    # 测试快速查找 Test quick lookup
    user_info = hash_network.quick_user_lookup(5)
    print(f"   用户5的信息: {user_info}")
    print(f"   User 5 info: {user_info}")
    
    # 测试边快速检查 Test quick edge check
    edge_exists = hash_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...")
    
    heap_network = HeapOptimizedNetwork(10, directed=True, storage_type="adj_list")
    for u, v in edges:
        heap_network.add_edge(u, v)
    
    # 更新一些用户的帖子数 Update some user post counts
    for i in range(10):
        heap_network.update_user_posts(i, random.randint(10, 100))
        heap_network.user_attributes[i]['followers'] = random.randint(50, 500)
        heap_network.user_info_table.insert(i, heap_network.user_attributes[i])
    
    # 获取粉丝数前3的用户 Get top 3 users by followers
    top_followers = heap_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 = heap_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...")
    
    sort_network = SortingSearchingNetwork(10, directed=True, storage_type="adj_list")
    for u, v in edges:
        sort_network.add_edge(u, v)
    
    # 更新一些用户的属性 Update some user attributes
    for i in range(10):
        sort_network.user_attributes[i]['followers'] = random.randint(50, 500)
        sort_network.user_attributes[i]['posts'] = random.randint(10, 100)
        sort_network.user_info_table.insert(i, sort_network.user_attributes[i])
    
    # 按粉丝数排序 Sort by followers
    sorted_by_followers = sort_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
    filtered_users = sort_network.get_users_by_follower_range(200, 500)
    print(f"   粉丝数在200-500之间的用户数量: {len(filtered_users)}")
    print(f"   Number of users with followers between 200-500: {len(filtered_users)}")
    
    # 10. 测试不同存储结构的性能 Test performance of different storage structures
    print("\n10. 测试不同存储结构的性能...")
    print("Testing Performance of Different Storage Structures...")
    
    # 创建邻接表和邻接矩阵网络 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")
    
    # 11. 生成小型测试网络 Test with generated network
    print("\n11. 生成小型测试网络...")
    print("Testing with generated small network...")
    
    small_network = generate_small_network()
    print(f"   小型网络创建成功: {small_network.n} 用户, {sum(len(small_network.get_following(i)) for i in range(small_network.n))} 条边")
    print(f"   Small network created: {small_network.n} users, {sum(len(small_network.get_following(i)) for i in range(small_network.n))} edges")
    
    print("\n" + "=" * 80)
    print("所有测试完成！")
    print("All tests completed!")
    print("=" * 80)


# 全局变量定义 Global variable definitions
NUM_USERS = 20  # 只需修改这个数字来控制用户数量 Change only this number to control user count
EDGE_COUNT = int(NUM_USERS * 2)  # 根据用户数量自动调整边数 Automatically adjust edge count based on user count


def demo_usage():
    """
    演示使用方法
    Demonstrate usage
    """
    print(f"\n演示如何使用社交媒体网络分析系统 (用户数: {NUM_USERS})")
    print(f"Demonstrating how to use the Social Network Analysis System (User count: {NUM_USERS})")
    print("-" * 60)
    
    # 创建一个社交网络实例 Create a social network instance
    network = SortingSearchingNetwork(NUM_USERS, directed=True, storage_type="adj_list")
    
    # 添加随机边 Add random edges
    for _ in range(EDGE_COUNT):
        u, v = random.randint(0, NUM_USERS - 1), random.randint(0, NUM_USERS - 1)
        if u != v:
            network.add_edge(u, v)
    
    # 设置用户属性 Set user attributes
    for i in range(NUM_USERS):
        network.user_attributes[i]['followers'] = random.randint(10, 200)
        network.user_attributes[i]['posts'] = random.randint(5, 50)
        network.user_info_table.insert(i, network.user_attributes[i])
    
    print(f"创建了包含{NUM_USERS}个用户和{sum(len(network.get_following(i)) for i in range(NUM_USERS))}条边的网络")
    print(f"Created a network with {NUM_USERS} users and {sum(len(network.get_following(i)) for i in range(NUM_USERS))} edges")
    
    # 影响力分析 Influence analysis
    affected_count, affected_users = network.k_step_influence(0, 2)
    print(f"从用户0开始2步内可影响 {affected_count} 个用户")
    print(f"User 0 can influence {affected_count} users within 2 steps")
    
    # 社区检测 Community detection
    communities = network.community_detection(algorithm='lpa', iterations=30)
    print(f"检测到 {len(communities)} 个社区")
    print(f"Detected {len(communities)} communities")
    
    # 排行榜 Rankings
    top_k = min(5, NUM_USERS)  # 确保Top-K不超过用户总数 Ensure Top-K doesn't exceed user count
    top_followers = network.get_top_k_by_followers(top_k)
    print(f"粉丝数前{top_k}名: {top_followers}")
    print(f"Top {top_k} by followers: {top_followers}")
    
    # 排序 Sorting
    sorted_users = network.sort_users_by_attribute('posts', ascending=False)
    print(f"按发帖数排序前{top_k}名: {[item for item in sorted_users[:top_k]]}")
    print(f"Top {top_k} by posts: {[item for item in sorted_users[:top_k]]}")
    
    print("-" * 60)


if __name__ == "__main__":
    print("社交媒体网络分析系统 - 主程序")
    print("Social Network Analysis System - Main Program")
    
    # 运行综合测试 Run comprehensive tests
    run_comprehensive_tests()
    
    # 演示使用方法 Demonstrate usage
    demo_usage()