When Lists Are Appropriate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

def recommend_representation(
    num_vertices: int,
    num_edges: int,
    available_memory_mb: int,
    dominant_op: str  # 'traversal', 'edge_query', 'modification'
) -> str:
    """
    Recommend graph representation based on problem characteristics.
    
    Returns: 'adjacency_list', 'hash_set_list', or 'adjacency_matrix'
    """
    max_edges = num_vertices * (num_vertices - 1) // 2
    density = num_edges / max_edges if max_edges > 0 else 0
    
    # Calculate memory requirements (rough estimates)
    list_memory_mb = (num_vertices * 24 + num_edges * 2 * 8) / 1e6
    matrix_memory_mb = (num_vertices ** 2) / 1e6  # 1 byte per cell
    
    # Memory check first - if matrix doesn't fit, must use list
    if matrix_memory_mb > available_memory_mb:
        if dominant_op == 'edge_query':
            return 'hash_set_list'  # O(1) lookup with list space
        return 'adjacency_list'
    
    # Both fit in memory - choose by density and operations
    if density > 0.5:
        # Dense graph - matrix likely better
        if dominant_op == 'traversal':
            # Even for dense graphs, list traversal is O(E) vs O(V²)
            return 'adjacency_list' if density < 0.7 else 'adjacency_matrix'
        return 'adjacency_matrix'
    
    # Sparse graph
    if dominant_op == 'edge_query':
        return 'hash_set_list'
    elif dominant_op == 'modification':
        return 'adjacency_list'  # Easy to add/remove edges
    else:
        return 'adjacency_list'  # Default for sparse + traversal
 
# Examples
print(recommend_representation(1000, 5000, 500, 'traversal'))
# → 'adjacency_list' (sparse, traversal-heavy)
 
print(recommend_representation(1000, 400000, 500, 'edge_query'))
# → 'adjacency_matrix' (dense, query-heavy)
 
print(recommend_representation(100000, 500000, 500, 'traversal'))
# → 'adjacency_list' (matrix would need 10GB!)
 
print(recommend_representation(1000, 50000, 500, 'edge_query'))
# → 'hash_set_list' (moderate density, query-heavy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

class DynamicGraph:
    """
    Graph supporting efficient edge modifications.
    
    Uses hash sets for O(1) edge operations while
    maintaining O(V + E) space.
    """
    
    def __init__(self):
        self.adj = {}  # vertex → set of neighbors
    
    def add_vertex(self, v):
        if v not in self.adj:
            self.adj[v] = set()
    
    def add_edge(self, u, v):
        """O(1) average time."""
        self.add_vertex(u)
        self.add_vertex(v)
        self.adj[u].add(v)
        self.adj[v].add(u)
    
    def remove_edge(self, u, v):
        """O(1) average time (vs O(degree) with lists!)."""
        if u in self.adj:
            self.adj[u].discard(v)
        if v in self.adj:
            self.adj[v].discard(u)
    
    def remove_vertex(self, v):
        """O(degree(v)) time to clean up edges."""
        if v not in self.adj:
            return
        
        # Remove v from all neighbors' lists
        for neighbor in self.adj[v]:
            self.adj[neighbor].discard(v)
        
        # Remove v's entry
        del self.adj[v]
    
    def contract_edge(self, u, v):
        """
        Merge vertex v into u, removing edge (u,v).
        Common in graph algorithms like Karger's min-cut.
        """
        if u not in self.adj or v not in self.adj:
            return
        
        # Move all v's edges to u
        for neighbor in self.adj[v]:
            if neighbor != u:
                self.adj[u].add(neighbor)
                self.adj[neighbor].discard(v)
                self.adj[neighbor].add(u)
        
        # Remove v
        del self.adj[v]
        self.adj[u].discard(v)
 
# Dynamic graphs appear in:
# - Social network updates (friend/unfriend)
# - Network routing (link up/down)
# - Incremental algorithms (streaming graphs)
# - Game AI (navigable regions changing)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def create_complete_bipartite(m: int, n: int):
    """
    Complete bipartite graph K_{m,n}:
    Every vertex in set A (size m) connects to every vertex in set B (size n).
    
    Edges: m × n
    Density: m × n / (m + n - 1)² → approaches 1 as m, n grow together
    
    Matrix makes sense here:
    - Space: (m + n)² vs (m + n) + 2(m × n) for list
    - Edge queries are frequent in bipartite matching algorithms
    """
    V = m + n
    matrix = [[0] * V for _ in range(V)]
    
    for i in range(m):
        for j in range(m, V):
            matrix[i][j] = 1
            matrix[j][i] = 1
    
    return matrix
 
# For K_{100,100}:
# Matrix: 40,000 cells = 40 KB
# List: 200 vertices + 20,000 edges = similar space
# But matrix gives O(1) edge lookup!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

class HybridPowerLawGraph:
    """
    Specialized for power-law graphs (social networks, web graphs).
    
    Observation: Few 'hub' vertices have very high degree.
    Strategy: Use different representations for hubs vs regular vertices.
    
    Hubs: Store neighbors as sorted array for binary search O(log d)
    Regular: Store neighbors as unsorted list (small d ≈ O(1))
    """
    
    def __init__(self, num_vertices: int, hub_threshold: int = 1000):
        self.V = num_vertices
        self.hub_threshold = hub_threshold
        self.regular = [[] for _ in range(num_vertices)]  # Unsorted
        self.hubs = {}  # vertex → sorted list of neighbors
        self.is_hub = [False] * num_vertices
    
    def _promote_to_hub(self, v: int):
        """Convert regular vertex to hub representation."""
        if not self.is_hub[v]:
            self.hubs[v] = sorted(self.regular[v])
            self.regular[v] = None  # Free memory
            self.is_hub[v] = True
    
    def add_edge(self, u: int, v: int):
        """Add edge, promoting to hub if threshold exceeded."""
        for x, y in [(u, v), (v, u)]:
            if self.is_hub[x]:
                # Insert into sorted array
                import bisect
                bisect.insort(self.hubs[x], y)
            else:
                self.regular[x].append(y)
                if len(self.regular[x]) > self.hub_threshold:
                    self._promote_to_hub(x)
    
    def has_edge(self, u: int, v: int) -> bool:
        """O(log d) for hubs, O(d) for regular."""
        if self.is_hub[u]:
            import bisect
            neighbors = self.hubs[u]
            pos = bisect.bisect_left(neighbors, v)
            return pos < len(neighbors) and neighbors[pos] == v
        else:
            return v in self.regular[u]
    
    def neighbors(self, v: int):
        """Get neighbors of v."""
        if self.is_hub[v]:
            return self.hubs[v]
        return self.regular[v]
 
# This hybrid approach gives:
# - O(log d) lookup for high-degree hubs (instead of O(d))
# - O(d) lookup for regular vertices (where d is small)
# - Same asymptotic space as regular adjacency list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

def choose_graph_representation(
    V: int, 
    E: int, 
    available_memory_bytes: int,
    operations: list[str]  # e.g., ['bfs', 'edge_query', 'add_edge']
) -> dict:
    """
    Comprehensive graph representation recommendation.
    
    Returns a dict with:
    - 'recommendation': str
    - 'reasoning': list of factors that influenced the decision
    - 'alternatives': other viable options
    """
    result = {
        'recommendation': None,
        'reasoning': [],
        'alternatives': []
    }
    
    # Calculate metrics
    max_edges = V * (V - 1) // 2
    density = E / max_edges if max_edges > 0 else 0
    matrix_size = V * V  # cells (at least 1 byte each)
    list_size = V * 8 + E * 2 * 8  # rough estimate in bytes
    
    # Step 1: Memory check
    if matrix_size > available_memory_bytes:
        result['recommendation'] = 'adjacency_list'
        result['reasoning'].append(
            f'Matrix would require {matrix_size/1e9:.1f}GB, exceeds available memory'
        )
        
        # Refine list type based on operations
        if 'edge_query' in operations:
            result['recommendation'] = 'hash_set_list'
            result['reasoning'].append('Edge queries benefit from O(1) hash set lookup')
        
        return result
    
    result['reasoning'].append(f'Both representations fit in memory')
    
    # Step 2: Density analysis
    if density < 0.10:
        result['recommendation'] = 'adjacency_list'
        result['reasoning'].append(f'Graph is sparse ({density:.1%} density)')
    elif density > 0.50:
        result['recommendation'] = 'adjacency_matrix'
        result['reasoning'].append(f'Graph is dense ({density:.1%} density)')
    else:
        result['reasoning'].append(
            f'Medium density ({density:.1%}), considering operations'
        )
    
    # Step 3: Operation-based refinement
    op_scores = {'list': 0, 'matrix': 0, 'hash_set': 0}
    
    for op in operations:
        if op in ['bfs', 'dfs', 'dijkstra', 'bellman_ford', 'topological_sort']:
            op_scores['list'] += 2
        elif op in ['edge_query', 'has_edge']:
            op_scores['matrix'] += 1
            op_scores['hash_set'] += 2
        elif op in ['add_edge', 'remove_edge', 'dynamic']:
            op_scores['list'] += 1
            op_scores['hash_set'] += 1
        elif op in ['floyd_warshall', 'matrix_multiply', 'spectral']:
            op_scores['matrix'] += 3
    
    # Final decision
    best = max(op_scores, key=op_scores.get)
    if best == 'hash_set':
        result['recommendation'] = 'hash_set_list'
    elif best == 'matrix':
        result['recommendation'] = 'adjacency_matrix'
    else:
        result['recommendation'] = 'adjacency_list'
    
    result['reasoning'].append(f'Operations favor {best} (score: {op_scores[best]})')
    
    # Document alternatives
    for rep, score in sorted(op_scores.items(), key=lambda x: -x[1]):
        if rep != best:
            result['alternatives'].append(f'{rep} (score: {score})')
    
    return result
 
# Example usage
rec = choose_graph_representation(
    V=10000, 
    E=50000, 
    available_memory_bytes=100_000_000,
    operations=['bfs', 'dfs', 'edge_query']
)
print(f"Recommendation: {rec['recommendation']}")
for reason in rec['reasoning']:
    print(f"  - {reason}")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#include <bits/stdc++.h>
using namespace std;
 
// Standard adjacency list (unweighted)
vector<int> adj[100005];  // Static array of vectors
 
// Weighted adjacency list
vector<pair<int, int>> wAdj[100005];  // (neighbor, weight)
 
// Reading graph from input
void readGraph(int n, int m, bool weighted = false, bool directed = false) {
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        
        if (weighted) {
            int w;
            cin >> w;
            wAdj[u].push_back({v, w});
            if (!directed) wAdj[v].push_back({u, w});
        } else {
            adj[u].push_back(v);
            if (!directed) adj[v].push_back(u);
        }
    }
}
 
// BFS with adjacency list
vector<int> bfs(int start, int n) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {  // O(degree) iteration
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}
 
// Dijkstra with adjacency list
vector<long long> dijkstra(int start, int n) {
    vector<long long> dist(n + 1, LLONG_MAX);
    priority_queue<pair<long long, int>, 
                   vector<pair<long long, int>>,
                   greater<pair<long long, int>>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto [v, w] : wAdj[u]) {  // O(degree) iteration
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}