Social Network Simulation

Problem Statement

Write a Java program that simulates a social network using an undirected weighted graph. The program should allow adding users (vertices), forming friendships (weighted edges, where weights represent interaction strength), and finding mutual friends between two users using Depth-First Search (DFS). Mutual friends are users directly connected to both input users. The program should reuse the weighted graph implementation with an adjacency list and test with various scenarios, including users with mutual friends, no mutual friends, empty graphs, and isolated users. You can visualize this as a social media platform where users connect with friends, and you query who is friends with both of two selected users, like finding common contacts in a network.

Input:

• An undirected weighted graph with vertices as integers (0 to n-1, representing users).
• Operations to add users (vertices), add friendships (edges with weights), and query mutual friends (pairs of users [u, v]). Output: Confirmation of user and friendship additions, a list of mutual friends’ IDs for queried pairs, or an empty list if none, and a string representation of the graph’s adjacency list for clarity. Constraints:
• The number of vertices n is between 0 and 10^5.
• Edges are triplets [u, v, weight] where 0 ≤ u, v < n, and weight is a positive integer in [1, 10^9].
• The graph is undirected (friendship [u, v, weight] implies [v, u, weight]). Example:
• Input: Add users 0, 1, 2, 3; Add friendships [0, 1, 5], [1, 2, 3], [2, 3, 7], [0, 2, 4]; Query mutual friends [0, 2]
• Output:
  • Added users and friendships successfully
  • Mutual friends of 0 and 2: [1]
  • "Adjacency List: {0=[(1, 5), (2, 4)], 1=[(0, 5), (2, 3)], 2=[(1, 3), (3, 7), (0, 4)], 3=[(2, 7)]}"
• Explanation: User 1 is a mutual friend of users 0 and 2 (directly connected to both).
• Input: Add users 0, 1, 2; Add friendships [0, 1, 5]; Query mutual friends [0, 2]
• Output:
  • Added users and friendships successfully
  • Mutual friends of 0 and 2: []
  • "Adjacency List: {0=[(1, 5)], 1=[(0, 5)], 2=[]}"
• Explanation: No mutual friends between 0 and 2.

Pseudocode

CLASS Edge
    SET destination to integer
    SET weight to integer
ENDCLASS

FUNCTION createGraph(n)
    CREATE adjList as new HashMap
    FOR i from 0 to n-1
        SET adjList[i] to empty list
    ENDFOR
    RETURN adjList
ENDFUNCTION

FUNCTION addFriendship(adjList, u, v, weight)
    IF u not in adjList OR v not in adjList THEN
        RETURN false
    ENDIF
    CREATE edge1 as new Edge(v, weight)
    CREATE edge2 as new Edge(u, weight)
    ADD edge1 to adjList[u]
    ADD edge2 to adjList[v]
    RETURN true
ENDFUNCTION

FUNCTION getFriends(vertex, adjList, visited)
    CREATE friends as new list
    FUNCTION dfs(node)
        SET visited[node] to true
        FOR each edge in adjList[node]
            IF NOT visited[edge.destination] THEN
                ADD edge.destination to friends
                CALL dfs(edge.destination)
            ENDIF
        ENDFOR
    ENDFUNCTION
    SET visited[vertex] to true
    FOR each edge in adjList[vertex]
        ADD edge.destination to friends
    ENDFOR
    RETURN friends
ENDFUNCTION

FUNCTION findMutualFriends(adjList, u, v)
    IF u not in adjList OR v not in adjList THEN
        RETURN empty list
    ENDIF
    CREATE visited1 as boolean array, initialized to false
    CREATE visited2 as boolean array, initialized to false
    SET friends1 to getFriends(u, adjList, visited1)
    SET friends2 to getFriends(v, adjList, visited2)
    CREATE mutual as new list
    FOR each friend in friends1
        IF friend in friends2 THEN
            ADD friend to mutual
        ENDIF
    ENDFOR
    RETURN mutual
ENDFUNCTION

FUNCTION toString(adjList)
    CREATE result as new StringBuilder
    APPEND "Adjacency List: {" to result
    FOR each vertex in adjList
        APPEND vertex and "=" to result
        APPEND "[" to result
        FOR each edge in adjList[vertex]
            APPEND "(" and edge.destination and ", " and edge.weight and ")" to result
            IF edge is not last THEN
                APPEND ", " to result
            ENDIF
        ENDFOR
        APPEND "]" to result
        IF vertex is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "}" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of (n, edges, queries) triples
    FOR each testCase in testCases
        PRINT test case details
        SET adjList to createGraph(testCase.n)
        FOR each edge [u, v, weight] in testCase.edges
            CALL addFriendship(adjList, u, v, weight)
        ENDFOR
        FOR each query [u, v] in testCase.queries
            CALL findMutualFriends(adjList, u, v)
            PRINT mutual friends
        ENDFOR
        PRINT graph using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Reuse the Edge class with: a. destination (integer for target vertex). b. weight (integer for friendship strength).
2. Define createGraph: a. Create a HashMap adjList mapping vertices to lists of Edge objects. b. Initialize empty lists for vertices 0 to n-1.
3. Define addFriendship: a. Validate that users u and v exist. b. Add bidirectional edges Edge(v, weight) to u’s list and Edge(u, weight) to v’s list.
4. Define getFriends: a. Use DFS to collect direct neighbors of a vertex (friends). b. Mark visited vertices to avoid cycles.
5. Define findMutualFriends: a. Validate that users u and v exist. b. Get friends of u and v using DFS. c. Return the intersection of their friend lists.
6. Define toString: a. Convert adjacency list to a string, e.g., "{0=[(1, 5), (2, 4)], ...}".
7. In main, test with: a. A graph with mutual friends. b. A graph with no mutual friends. c. An empty graph. d. A single user.

Java Implementation

import java.util.*;

public class SocialNetworkSimulation {
    // Edge class to store destination and weight
    static class Edge {
        int destination;
        int weight;

        Edge(int destination, int weight) {
            this.destination = destination;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "(" + destination + ", " + weight + ")";
        }
    }

    // Creates adjacency list for n users
    private Map<Integer, List<Edge>> createGraph(int n) {
        Map<Integer, List<Edge>> adjList = new HashMap<>();
        for (int i = 0; i < n; i++) {
            adjList.put(i, new ArrayList<>());
        }
        return adjList;
    }

    // Adds a friendship (weighted edge) between users u and v
    public boolean addFriendship(Map<Integer, List<Edge>> adjList, int u, int v, int weight) {
        if (!adjList.containsKey(u) || !adjList.containsKey(v)) {
            return false;
        }
        adjList.get(u).add(new Edge(v, weight));
        adjList.get(v).add(new Edge(u, weight)); // Undirected graph
        return true;
    }

    // Gets friends of a vertex using DFS (direct neighbors only for mutual friends)
    private List<Integer> getFriends(int vertex, Map<Integer, List<Edge>> adjList, boolean[] visited) {
        List<Integer> friends = new ArrayList<>();
        visited[vertex] = true;
        for (Edge edge : adjList.get(vertex)) {
            friends.add(edge.destination);
        }
        return friends;
    }

    // Finds mutual friends between users u and v
    public List<Integer> findMutualFriends(Map<Integer, List<Edge>> adjList, int u, int v) {
        List<Integer> mutual = new ArrayList<>();
        if (!adjList.containsKey(u) || !adjList.containsKey(v)) {
            return mutual;
        }
        boolean[] visited1 = new boolean[adjList.size()];
        boolean[] visited2 = new boolean[adjList.size()];
        List<Integer> friends1 = getFriends(u, adjList, visited1);
        List<Integer> friends2 = getFriends(v, adjList, visited2);
        for (int friend : friends1) {
            if (friends2.contains(friend)) {
                mutual.add(friend);
            }
        }
        Collections.sort(mutual); // For consistent output
        return mutual;
    }

    // Converts graph to string (adjacency list)
    public String toString(Map<Integer, List<Edge>> adjList) {
        StringBuilder result = new StringBuilder("Adjacency List: {");
        List<Integer> vertices = new ArrayList<>(adjList.keySet());
        Collections.sort(vertices); // For consistent output
        for (int i = 0; i < vertices.size(); i++) {
            int vertex = vertices.get(i);
            result.append(vertex).append("=[");
            List<Edge> edges = adjList.get(vertex);
            for (int j = 0; j < edges.size(); j++) {
                result.append(edges.get(j));
                if (j < edges.size() - 1) {
                    result.append(", ");
                }
            }
            result.append("]");
            if (i < vertices.size() - 1) {
                result.append(", ");
            }
        }
        result.append("}");
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        int n;
        int[][] edges;
        int[][] queries;

        TestCase(int n, int[][] edges, int[][] queries) {
            this.n = n;
            this.edges = edges;
            this.queries = queries;
        }
    }

    // Main method to test social network simulation
    public static void main(String[] args) {
        SocialNetworkSimulation network = new SocialNetworkSimulation();

        // Test cases
        TestCase[] testCases = {
            // Graph with mutual friends
            new TestCase(
                4,
                new int[][]{{0, 1, 5}, {1, 2, 3}, {2, 3, 7}, {0, 2, 4}},
                new int[][]{{0, 2}}
            ),
            // Graph with no mutual friends
            new TestCase(
                3,
                new int[][]{{0, 1, 5}},
                new int[][]{{0, 2}}
            ),
            // Empty graph
            new TestCase(
                0,
                new int[][]{},
                new int[][]{{0, 1}}
            ),
            // Single user
            new TestCase(
                1,
                new int[][]{},
                new int[][]{{0, 0}}
            )
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Vertices (Users): " + testCases[i].n);
            System.out.println("Friendships: " + Arrays.deepToString(testCases[i].edges));
            Map<Integer, List<Edge>> adjList = network.createGraph(testCases[i].n);
            System.out.print("Added users");
            if (testCases[i].edges.length > 0) {
                System.out.print(" and friendships");
                for (int[] edge : testCases[i].edges) {
                    network.addFriendship(adjList, edge[0], edge[1], edge[2]);
                }
            }
            System.out.println(" successfully");
            System.out.println("Queries:");
            for (int[] query : testCases[i].queries) {
                int u = query[0], v = query[1];
                List<Integer> mutual = network.findMutualFriends(adjList, u, v);
                System.out.println("Mutual friends of " + u + " and " + v + ": " + mutual);
            }
            System.out.println(network.toString(adjList) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Vertices (Users): 4
Friendships: [[0, 1, 5], [1, 2, 3], [2, 3, 7], [0, 2, 4]]
Added users and friendships successfully
Queries:
Mutual friends of 0 and 2: [1]
Adjacency List: {0=[(1, 5), (2, 4)], 1=[(0, 5), (2, 3)], 2=[(1, 3), (3, 7), (0, 4)], 3=[(2, 7)]}

Test case 2:
Vertices (Users): 3
Friendships: [[0, 1, 5]]
Added users and friendships successfully
Queries:
Mutual friends of 0 and 2: []
Adjacency List: {0=[(1, 5)], 1=[(0, 5)], 2=[]}

Test case 3:
Vertices (Users): 0
Friendships: []
Added users successfully
Queries:
Mutual friends of 0 and 1: []
Adjacency List: {}

Test case 4:
Vertices (Users): 1
Friendships: []
Added users successfully
Queries:
Mutual friends of 0 and 0: []
Adjacency List: {0=[]}

Explanation:

• Test case 1: Users 0 and 2 have mutual friend 1 (connected to both).
• Test case 2: Users 0 and 2 have no mutual friends (2 is isolated).
• Test case 3: Empty graph, no mutual friends.
• Test case 4: Single user, no mutual friends with self.

How It Works

• Edge: Stores destination vertex and weight (friendship strength).
• createGraph: Initializes adjacency list for n users.
• addFriendship: Adds bidirectional weighted edges if users exist.
• getFriends: Uses DFS to collect direct neighbors (friends), marking visited to avoid cycles.
• findMutualFriends: Finds intersection of friends’ lists for two users.
• toString: Formats adjacency list with edge weights, sorting vertices.
• Example Trace (Test case 1):
  • Add users 0–3, friendships (0, 1, 5), (1, 2, 3), (2, 3, 7), (0, 2, 4).
  • Query (0, 2): Friends of 0 = [1, 2], friends of 2 = [1, 3, 0], intersection = [1].
• Main Method: Tests mutual friends, no mutual friends, empty graph, and single user.

Complexity Analysis Table

Note:

• n is the number of vertices, e is the number of edges, d_u and d_v are degrees of vertices u and v.
• Time complexity: O(n) for createGraph (initialize lists); O(1) for addFriendship (add edges); O(d_u + d_v) average for findMutualFriends (collect and intersect neighbors); O(n log n + e) for toString (sorting vertices).
• Space complexity: O(n) for createGraph (empty lists); O(1) for addFriendship; O(n) for findMutualFriends (visited arrays and friend lists); O(n + e) for toString (adjacency list).
• Worst case: O(n + e) time and space for dense graphs.

✅ Tip: Use DFS to collect direct neighbors for mutual friend queries, but limit to one level for efficiency. Store weights to represent friendship strength, enabling future extensions like weighted friend recommendations.

⚠ Warning: Validate user IDs before adding friendships or querying mutual friends to avoid accessing undefined adjacency lists. Ensure DFS avoids cycles by tracking visited vertices.