  Comprehensive Graph Algorithms Demo - Aprender v0.6.0
═══════════════════════════════════════════════════════════════

╔═══════════════════════════════════════════════════════════════╗
║ PHASE 1: PATHFINDING ALGORITHMS                               ║
╚═══════════════════════════════════════════════════════════════╝

📍 Building road network graph:
   Cities: A(0), B(1), C(2), D(3), E(4), F(5)
   Roads with distances (km):

─────────────────────────────────────────────────────────────────
1️⃣  Shortest Path (BFS - unweighted hops)
─────────────────────────────────────────────────────────────────
   Route from A to F: A → B → D → F (3 hops)

─────────────────────────────────────────────────────────────────
2️⃣  Dijkstra's Algorithm (weighted shortest path)
─────────────────────────────────────────────────────────────────
   Shortest route from A to F: A → C → B → D → E → F (13.0 km)

─────────────────────────────────────────────────────────────────
3️⃣  A* Search (heuristic-guided pathfinding)
─────────────────────────────────────────────────────────────────
   A* route from A to F: A → C → B → D → E → F (heuristic-guided)

─────────────────────────────────────────────────────────────────
4️⃣  All-Pairs Shortest Paths (distance matrix)
─────────────────────────────────────────────────────────────────
   Distance matrix (hops):
        A   B   C   D   E   F 
    A   0   1   1   2   2   3 
    B   1   0   1   1   2   2 
    C   1   1   0   1   1   2 
    D   2   1   1   0   1   1 
    E   2   2   1   1   0   1 
    F   3   2   2   1   1   0 


╔═══════════════════════════════════════════════════════════════╗
║ PHASE 2: COMPONENTS & TRAVERSAL ALGORITHMS                    ║
╚═══════════════════════════════════════════════════════════════╝

─────────────────────────────────────────────────────────────────
1️⃣  Depth-First Search (DFS)
─────────────────────────────────────────────────────────────────
   Tree structure:
        0
       / \
      1   2
     / \   \
    3   4   5

   DFS traversal from root: 0 → 1 → 3 → 4 → 2 → 5

─────────────────────────────────────────────────────────────────
2️⃣  Connected Components (undirected graphs)
─────────────────────────────────────────────────────────────────
   Graph with 6 nodes, 3 edges
   Found 2 connected components:
   Component 1: [0, 1, 2]
   Component 2: [3, 4]

─────────────────────────────────────────────────────────────────
3️⃣  Strongly Connected Components (directed graphs)
─────────────────────────────────────────────────────────────────
   Directed graph:
   0 → 1 → 2 → 0  (cycle 1)
           ↓
           3 ⇄ 4  (cycle 2)

   Found 2 strongly connected components:
   SCC 1: [0, 1, 2]
   SCC 2: [3, 4]

─────────────────────────────────────────────────────────────────
4️⃣  Topological Sort (DAG ordering)
─────────────────────────────────────────────────────────────────
   Task dependency graph (DAG):
   Setup Environment → Install Dependencies
   Setup Environment → Configure System
   Install Dependencies → Build Project
   Configure System → Build Project
   Build Project → Run Tests

   Valid execution order:
   1. Setup Environment
   2. Configure System
   3. Install Dependencies
   4. Build Project
   5. Run Tests


╔═══════════════════════════════════════════════════════════════╗
║ PHASE 3: COMMUNITY & LINK ANALYSIS                            ║
╚═══════════════════════════════════════════════════════════════╝

─────────────────────────────────────────────────────────────────
1️⃣  Label Propagation (community detection)
─────────────────────────────────────────────────────────────────
   Social network with 2 communities connected by a bridge:
   Community A: {0,1,2,3}  ←bridge(3-4)→  Community B: {4,5,6,7}

   Detected 2 communities:
   Community 1: [0, 1, 2, 3]
   Community 2: [4, 5, 6, 7]

─────────────────────────────────────────────────────────────────
2️⃣  Common Neighbors (link prediction)
─────────────────────────────────────────────────────────────────
   Link prediction: Will nodes 1 and 3 become friends?

   Common neighbors of 1 and 3: 2
   Node 1 neighbors: [0, 2]
   Node 3 neighbors: [0, 2, 4]
   Actual common neighbors: [0, 2]
   → High common neighbor count suggests likely future connection

─────────────────────────────────────────────────────────────────
3️⃣  Adamic-Adar Index (weighted link prediction)
─────────────────────────────────────────────────────────────────
   Adamic-Adar score for nodes 1 and 3: 1.8205
   Adamic-Adar score for nodes 0 and 7: 0.0000

   💡 Interpretation:
   - Higher score = stronger prediction for future link
   - Nodes 1-3 (same community): 1.8205
   - Nodes 0-7 (different communities): 0.0000
   → Algorithm correctly identifies within-community links as more likely

═══════════════════════════════════════════════════════════════
  Demo Complete! All 11 algorithms demonstrated.
═══════════════════════════════════════════════════════════════
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 54.79    0.000950           8       116           write
 13.26    0.000230          13        17           mmap
  3.81    0.000066           9         7           mprotect
  5.36    0.000093          13         7           read
  2.71    0.000047           9         5           close
  2.83    0.000049           9         5           newfstatat
  4.04    0.000070          14         5           openat
  1.85    0.000032           6         5           rt_sigaction
  1.50    0.000026           6         4           unknown
  1.50    0.000026           6         4           pread64
  2.02    0.000035          11         3           brk
  1.04    0.000018           6         3           sigaltstack
  1.10    0.000019           9         2           getrandom
  1.15    0.000020          10         2         1 arch_prctl
  1.27    0.000022          11         2           munmap
  0.40    0.000007           7         1           poll
  0.69    0.000012          12         1         1 access
  0.35    0.000006           6         1           set_tid_address
  0.35    0.000006           6         1           set_robust_list
------ ----------- ----------- --------- --------- ----------------
100.00    0.001734           9       191         2 total
