Skip to content

Readme.md

Latest commit

 

History

History
63 lines (50 loc) · 3.61 KB

Readme.md

File metadata and controls

63 lines (50 loc) · 3.61 KB

SocialNet Simulator

This project is a C++ implementation of the "SocialNet Simulator" assignment. It simulates a social network's backend, managing users, friendships, and posts using custom-built Graph and AVL Tree data structures.

Core Data Structures

As required by the assignment, this project implements the following data structures from scratch:

  1. Graph: An undirected graph is implemented using an adjacency list (std::vector<std::set<int>>). This graph represents the social network, where vertices are users and edges are friendships.
  2. AVL Tree: A templated, self-balancing binary search tree (AVL Tree) is implemented from scratch. Each user has their own AVL Tree to store their posts, ensuring efficient, sorted retrieval by creation time.

A C++ hashmap (std::unordered_map) is used only to map string usernames to their corresponding integer vertex IDs in the graph, as explicitly permitted by the assignment.

How to Compile and Run

  1. Make the compile script executable:

    chmod +x compile.sh

  2. Run the compile script:

    ./compile.sh

    This will create an executable file named socialnet.

  3. Run the simulator:

    ./socialnet

Command Reference

The simulator accepts the following commands:

  • ADD_USER <username>
    • Adds a new user to the network.
  • ADD_FRIEND <username1> <username2>
    • Creates a bidirectional friendship.
  • LIST_FRIENDS <username>
    • Prints an alphabetically sorted list of the user's friends.
  • SUGGEST_FRIENDS <username> <N>
    • Recommends up to N friends-of-friends, ranked by mutual friends (descending) and then by name (alphabetical).
  • DEGREES_OF_SEPARATION <username1> <username2>
    • Calculates the shortest friendship path between two users using BFS. Returns -1 if no path exists.
  • ADD_POST <username> "<post_content>"
    • Adds a new post for the user. The post content must be enclosed in double quotes.
  • OUTPUT_POSTS <username> <N>
    • Outputs the N most recent posts in reverse chronological order.
    • If N is -1, outputs all posts.
  • LIST_USERS
    • Prints all users in the network in alphabetical order.
  • HELP
    • Displays a list of all supported commands and their usage.
  • EXIT
    • Exits the simulator.

Assumptions Made

  1. Case-Insensitivity: All usernames are normalized to lowercase internally for all operations (storage, lookup, comparison), as specified. The original casing of the username is stored separately and used only for display purposes (e.g., in LIST_FRIENDS).
  2. Post Content Case: The assignment states post content is also not case-sensitive. This implementation stores the post content as-is (preserving case) since there are no operations (like searching post content) that depend on its case.
  3. Post Sorting (Time): To satisfy the "sorted according to the time of post creation" requirement, a global, monolithically increasing long long integer (nextPostId) is used as the key in each user's AVL tree. This strictly ensures that posts added later have a higher key, and thus can be retrieved in chronological order.
  4. Command Parsing: The command parser strictly assumes that post content is the only argument that contains spaces and is always enclosed in double quotes (e.g., ADD_POST amit "This is my post"), as shown in the example. Usernames are assumed to be single strings without spaces
  5. Error Handling: Basic error handling is implemented. The program reports errors (e.g., "User not found," "Invalid command") to stdout and continues running, rather than crashing.