Social Network System Design Document

System Overview

A console-based social network implementation that models users as nodes and friendships as undirected edges in a graph structure. The system provides core social networking functionality including user management, friendship management, mutual friend discovery, and friend suggestions.

Architecture

Data Structures

AVL Tree Implementation

• Self-balancing binary search tree for efficient string-keyed data storage
• Used for both user directory and friend relationship sets
• Provides O(log n) time complexity for insertions, searches, and deletions

User Structure

• name: String identifier for the user
• friends: AVL tree storing friend names (keys only, values unused)
• friend_count: Integer tracking number of friends for optimization

Global State

• g_users: Global AVL tree mapping usernames to User objects
• g_user_count: Integer tracking total number of users (max 50)

Core Functionality

User Management

ADD_USER Command

• Creates new user with specified name
• Validates: non-empty name, user limit (50), duplicate prevention
• Initializes empty friend set and zero friend count

Constraints

• Maximum 50 users
• Unique usernames required
• Case-sensitive user identification

Friendship Management

ADD_FRIEND Command

• Creates bidirectional friendship between two users
• Validates: both users exist, no self-friending, duplicate prevention
• Maintains symmetry by adding relationship to both users' friend sets

VIEW_FRIENDS Command

• Lists all direct friends of specified user
• Displays friend names in lexicographic order
• Handles empty friend sets gracefully

Social Analysis

MUTUAL Command

• Finds intersection of two users' friend sets
• Implements optimization by iterating smaller friend set
• Returns mutual friends in lexicographic order

SUGGEST Command

• Recommends friends-of-friends not already connected
• Uses common neighbor count as recommendation score
• Excludes self and existing friends from suggestions
• Displays suggestions with number of common connections

Algorithm Design

AVL Tree Operations

• Insertion: Standard AVL insertion with rotation balancing
• Search: Binary search with string comparison
• Traversal: In-order traversal for sorted output
• Memory Management: Recursive cleanup with value-specific deallocation

Mutual Friend Algorithm

1. Retrieve both users' friend sets
2. Select smaller set for iteration
3. Check each friend against larger set using AVL contains
4. Output matches in sorted order

Friend Suggestion Algorithm

1. For each friend of target user
2. For each friend-of-friend (excluding self and existing friends)
3. Count common connections using candidate map
4. Output suggestions sorted lexicographically with connection counts

User Interface

Command Line Interface

• Interactive prompt-based interface
• Case-insensitive command parsing
• Clear error messaging and usage instructions
• Real-time feedback for operations

Available Commands

• ADD_USER <name>
• ADD_FRIEND <name1> <name2>
• VIEW_FRIENDS <name>
• MUTUAL <name1> <name2>
• SUGGEST <name>
• EXIT

Performance Characteristics

Time Complexity

• User operations: O(log n)
• Friendship operations: O(log n)
• Mutual friends: O(m log n) where m is size of smaller friend set
• Friend suggestions: O(d² log n) where d is average friend count

Space Complexity

• O(n + e) where n is users and e is edges
• Each user: O(1) for structure + O(f) for friend storage
• Global: O(n) for user directory

Error Handling

Validation Checks

• Empty username prevention
• User existence verification
• Self-friending prevention
• Duplicate friendship detection
• Maximum user limit enforcement

Error Messages

• Clear, descriptive error messages
• Usage instructions for malformed commands
• Informative status messages for successful operations

Memory Management

Allocation Strategy

• Dynamic memory allocation for all structures
• String duplication for name storage
• Recursive tree deallocation on program exit

Cleanup Procedures

• Recursive AVL tree destruction
• User structure deallocation with friend tree cleanup
• Proper memory freeing for all dynamically allocated resources

Design Strengths

1. Efficient Data Structures: AVL trees provide optimal search and insertion performance
2. Scalable Design: Algorithm optimizations for large friend sets
3. Clean Separation: Modular architecture with distinct functional components
4. Robust Error Handling: Comprehensive input validation and error reporting
5. Memory Safe: Proper cleanup procedures prevent memory leaks

Limitations and Considerations

1. Fixed User Limit: Maximum 50 users hardcoded
2. In-Memory Only: No persistence between program executions
3. Single-Threaded: No concurrent access handling
4. Case Sensitivity: Usernames are case-sensitive
5. No Network: Local console-only implementation

Implementation Details

Key Functions

AVL Tree Operations

• avl_insert(): Insert with balancing
• avl_find(): Search for key
• avl_contains(): Check existence
• avl_foreach(): In-order traversal
• avl_free(): Recursive cleanup

User Management

• add_user(): Create new user with validation
• get_user(): Retrieve user by name
• free_user_value(): Cleanup user resources

Friendship Operations

• add_friendship(): Create bidirectional friendship
• view_friends(): Display user's friends
• view_mutual(): Find common friends
• suggest_friends(): Generate friend recommendations

Data Flow

1. Command Input: User enters command via CLI
2. Parsing: Command tokenized and validated
3. Execution: Corresponding function called with parameters
4. Data Access: AVL tree operations performed
5. Output: Results displayed to user
6. Cleanup: Memory freed on program exit

This design provides a solid foundation for a social network system with efficient algorithms for core social networking operations while maintaining clean, maintainable code structure.