Rekonnect | Social Degrees of Separation Finder

Six degrees of separation is the idea that all people are six or fewer social connections away from each other. As a result, a chain of "friend of a friend" statements can be made to connect any two people in a maximum of six steps. It is also known as the six handshakes rule. Welcome to Rekonnect! The app is based on the six handshakes rule and allows you to add new users , add relations between them and find degrees of separation between two users.

Highlights:

---

Add User & Add Relation

---

---

Find Degrees

---

---

Demo:

---

https://vimeo.com/697225882

Instructions for testing:

---

• Clone the repository
• Update the .env in the server directory and add MONGO_URI connection string and PORT
• Run 'npm start' in the client and server directory
• The app will run on localhost:3000

---

Algorithm:

A breadth-first search approach is used to find the degrees of separation between two users. We picture the social network as a graph with the users as nodes and the connection between friends as edges.

• User 1 is treated as 'source' and User 2 as 'destination'
• We create a map to keep track of parent-child values where the friends of User 1 are treated as children of User 1 and so on..
• We also create a Set to keep track of visited nodes
• We push User 1 to the queue and traverse through every one of its friends and search for User 2
• If the friend is not yet visited,we push it to the queue and set user 1 as its parent and add it to visited set
• We continue this till the queue is empty or till we find User 2.

Snippet from User.js in 'controllers' folder in 'server' directory

    const visited = new Set();

    // BFS from user1 till we encounter user2
    var queue = [];
    visited.add(user1.name);
    queue.push(user1.name);

    while (queue.length > 0) {
      var current = queue.shift();

      //if found user2, stop traversing
      if (current === user2.name) break;

      //else traverse through next level
      var user = await User.findOne({ name: { $eq: current } });
    

      for (var i = 0; i < user.friends.length; i++) {
        var neighbor = user.friends[i];
        var neighborUser = await User.findById(neighbor);

        if (!visited.has(neighborUser.name)) {
          visited.add(neighborUser.name);
          parentsMap.set(neighborUser.name, current);
          queue.push(neighborUser.name);
        }
      }
    }

    //create the resultant path by linking parent nodes
    var path = [];
    path.push(user2.name);

    var next = parentsMap.get(user2.name);
    while (next != null) {
      path.push(next);
      next = parentsMap.get(next);
    }