Finding Paths in a Social Network

Imagine a social network represented as a graph where users are nodes and friendships are edges. This challenge asks you to implement SQL queries to traverse this graph and find paths between users. Understanding how to query graph-like structures in SQL is crucial for analyzing relationships, recommendations, and influence within networks.

Problem Description

You are given two tables: users and friendships.

The users table contains information about each user, identified by a unique user_id. The friendships table represents the connections between users. Each row indicates that user1_id is friends with user2_id. Friendships are bidirectional, meaning if A is friends with B, then B is also friends with A.

Your task is to write SQL queries that can answer questions about paths between users. Specifically, you need to implement a query that finds all direct friends of a given user and then extend this to find friends of friends, and so on, up to a specified depth.

Key Requirements:

Direct Friends: Find all users directly connected to a starting user.
Friends of Friends (up to N degrees): Find all users reachable from a starting user within a specified number of friendship steps (degrees of separation).
Path Reconstruction (Optional but Recommended): If possible, reconstruct the shortest path(s) between two users.

Expected Behavior:

The queries should return distinct users and their relationship to the starting user (e.g., direct friend, friend of friend).
For multi-degree traversals, the results should include users at each degree, without duplicates across degrees for a single traversal.
The queries should be efficient, especially for larger datasets.

Edge Cases to Consider:

Users with no friends.
Cycles in the friendship graph (e.g., A is friends with B, B with C, and C with A). The traversal should not get stuck in infinite loops.
Finding paths to oneself.
Starting with a user that does not exist.

Examples

Let's assume the following schema:

users Table:

user_id	username
1	Alice
2	Bob
3	Charlie
4	David
5	Eve
6	Frank

friendships Table:

user1_id	user2_id
1	2
1	3
2	4
3	4
3	5
4	5
5	6

Example 1: Direct Friends of Alice (user_id = 1)

Input:

Starting User ID: 1

Output:

friend_id	friend_username
2	Bob
3	Charlie

Explanation: Users 2 and 3 are directly listed as friends with user 1 in the friendships table.

Example 2: Friends of Friends of Alice (user_id = 1, up to 2 degrees)

Input:

Starting User ID: 1
Max Degrees: 2

Output:

reachable_user_id	degree
2	1
3	1
4	2
5	2

Explanation:

Degree 1: Bob (2) and Charlie (3) are direct friends of Alice (1).
Degree 2: David (4) is friends with Bob (2) and Charlie (3). Eve (5) is friends with Charlie (3) and David (4). Frank (6) is friends with Eve (5).
The output shows users reachable within 2 steps. User 1 is excluded as we are looking for other users. Users 2 and 3 are at degree 1. Users 4 and 5 are reachable at degree 2 (e.g., Alice -> Bob -> David; Alice -> Charlie -> David; Alice -> Charlie -> Eve). Frank (6) is at degree 3 and thus not included in this example.

Example 3: Path Reconstruction (Alice to David)

Input:

Starting User ID: 1
Target User ID: 4

Output:

path
1 -> 2 -> 4
1 -> 3 -> 4

Explanation: There are two shortest paths of length 2 between Alice (1) and David (4).

Constraints

user_id and friendship IDs are integers.
The number of users can be up to 100,000.
The number of friendships can be up to 500,000.
Queries should aim to complete within 5 seconds on a typical database system.
The friendships table does not contain self-referential entries (a user cannot be friends with themselves).
The friendships table is symmetric (if (A, B) exists, (B, A) also exists or is implied). For implementation, you might need to consider how to handle this bidirectionality.

Notes

SQL features like Common Table Expressions (CTEs), particularly recursive CTEs, are very useful for graph traversal problems.
When performing multi-degree traversals, be mindful of potential performance bottlenecks and duplicate results. Techniques for preventing cycles and ensuring distinct results are important.
For path reconstruction, you'll likely need to accumulate path information as you traverse.
Consider how you will represent the bidirectional nature of friendships in your queries. You might need to "unpivot" or UNION the friendships table to treat both directions equally.

Finding Paths in a Social Network

Problem Description

You are given two tables: users and friendships.

Key Requirements:

Direct Friends: Find all users directly connected to a starting user.
Friends of Friends (up to N degrees): Find all users reachable from a starting user within a specified number of friendship steps (degrees of separation).
Path Reconstruction (Optional but Recommended): If possible, reconstruct the shortest path(s) between two users.

Expected Behavior:

The queries should return distinct users and their relationship to the starting user (e.g., direct friend, friend of friend).
For multi-degree traversals, the results should include users at each degree, without duplicates across degrees for a single traversal.
The queries should be efficient, especially for larger datasets.

Edge Cases to Consider:

Users with no friends.
Cycles in the friendship graph (e.g., A is friends with B, B with C, and C with A). The traversal should not get stuck in infinite loops.
Finding paths to oneself.
Starting with a user that does not exist.

Examples

Let's assume the following schema:

users Table:

user_id	username
1	Alice
2	Bob
3	Charlie
4	David
5	Eve
6	Frank

friendships Table:

user1_id	user2_id
1	2
1	3
2	4
3	4
3	5
4	5
5	6

Example 1: Direct Friends of Alice (user_id = 1)

Input:

Starting User ID: 1

Output:

friend_id	friend_username
2	Bob
3	Charlie

Explanation: Users 2 and 3 are directly listed as friends with user 1 in the friendships table.

Example 2: Friends of Friends of Alice (user_id = 1, up to 2 degrees)

Input:

Starting User ID: 1
Max Degrees: 2

Output:

reachable_user_id	degree
2	1
3	1
4	2
5	2

Explanation:

Degree 1: Bob (2) and Charlie (3) are direct friends of Alice (1).
Degree 2: David (4) is friends with Bob (2) and Charlie (3). Eve (5) is friends with Charlie (3) and David (4). Frank (6) is friends with Eve (5).
The output shows users reachable within 2 steps. User 1 is excluded as we are looking for other users. Users 2 and 3 are at degree 1. Users 4 and 5 are reachable at degree 2 (e.g., Alice -> Bob -> David; Alice -> Charlie -> David; Alice -> Charlie -> Eve). Frank (6) is at degree 3 and thus not included in this example.

Example 3: Path Reconstruction (Alice to David)

Input:

Starting User ID: 1
Target User ID: 4

Output:

path
1 -> 2 -> 4
1 -> 3 -> 4

Explanation: There are two shortest paths of length 2 between Alice (1) and David (4).

Constraints

user_id and friendship IDs are integers.
The number of users can be up to 100,000.
The number of friendships can be up to 500,000.
Queries should aim to complete within 5 seconds on a typical database system.
The friendships table does not contain self-referential entries (a user cannot be friends with themselves).
The friendships table is symmetric (if (A, B) exists, (B, A) also exists or is implied). For implementation, you might need to consider how to handle this bidirectionality.

Notes

SQL features like Common Table Expressions (CTEs), particularly recursive CTEs, are very useful for graph traversal problems.
When performing multi-degree traversals, be mindful of potential performance bottlenecks and duplicate results. Techniques for preventing cycles and ensuring distinct results are important.
For path reconstruction, you'll likely need to accumulate path information as you traverse.
Consider how you will represent the bidirectional nature of friendships in your queries. You might need to "unpivot" or UNION the friendships table to treat both directions equally.