Counting each record's Nth degree of mutual or directional edges in a (many to many) graphical network of < 50,000 rows/nodes

Question

Summary I have created a many-to-many network graph relationship (social network). A Person can have many Friends. A Friend can be a friend to many Persons. Full object model (ERD) is given at the bottom of the question.

Friendship in this model can either be mutual (commonly known as symmetric or undirectional edges which i represent by blue double arrows) or non-mutual (commonly known as asymmetric or directional linkage/edges which i represent by black single arrows).

I would like help crafting the apex/triggers needed to maintain a numerical field ( numberOfNthDirectOrMutualPersonConnections__c) on each node (Person__c) that counts the number of symmetric or asymmetric edges connected to the Person__c through any degree of separation obtained by traversing from the Person__c through the entire network only along symmetric or asymmetric edges. I guarantee there will always be less than 50,000 Person__c records in my system.

Objective: The Person__c.numberOfNthDirectOrMutualPersonConnections__c (numeric) field needs to count (to the nth degree) all the unique Friend__r.Person__c records reachable by Person__c through symmetric (blue double arrows) or asymmetric (black single arrow) edges/associations/links (this means that the numeric count needs to include friends (of nth degree in the network) reachable via direct (black arrow) friendship or mutual friendship (blue arrow).

Example & Expectation:

• Suppose that Person__c Tom has 2 Person__c records (Bill and Jane) in Tom's FriendList__c
• Person__c Bill has no direct friends (no black arrow pointing to others in other words no Person__c s in Bill's FriendsList__c), and no mutual friends (no blue arrow)
• Person__c Jane has 2 Person__c records (Tom and Lisa) in Jane's FriendsList__c and both edges are mutual (blue arrow means symmetric linkage).
• Person__c Lisa has 2 friends (Jane and Kim) in Lisa's FriendsList__c. Jane is a mutual friend and Kim is just a friend (black arrow means asymmetric direct linkage and points to the friend)
• Kim has no friends, meaning no Person__c child records associated to Kim's FriendsList__crecord

My expectation is that "4" is returned in Person__c Tom's numberOfNthDirectOrMutualPersonConnections__c field.

Similarly, numberOfNthDirectOrMutualPersonConnections__c would equal 0 for Bill. Similarly, numberOfNthDirectOrMutualPersonConnections__c would equal 4 for Jane. Similarly, numberOfNthDirectOrMutualPersonConnections__c would equal 4 for Lisa. Similarly, numberOfNthDirectOrMutualPersonConnections__c would equal 0 for Kim.

High-level Attempt, Limits, Considerations

• Query all associations SELECT Id,FriendId,Friend__r.FriendsList__c,Friend__r.FriendsList__r.Person__c FROM Person__c LIMIT 50000
• Iterate the query to create a "network structure" (Person__c as nodes, mapped to a map of all of their edges (fromPersonId, ToPersonId). It might look like Map<Id,Map<Id,Id>> myNetworkStructure.
• Maybe implement into Triggers (or Batch Apex) a "depth search" or "breadth search" counting algorithm to execute on myNetworkStructure that calculates the number that I'm seeking.
• Putting queries inside loops is not an appropriate solution because the SOQL governor limits will throw exceptions too soon for this project.
• For this project, there will never be more than 50,000 Person__c records in the system
• I'm assuming with under 50,000 records this can be done via synchronous logic. I have not worked with graphical network algorithms enough to justify having to use batch apex for this problem.
• In thinking about the Triggers needed to maintain truth/accuracy in all Person__c.numberOfNthDirectOrMutualPersonConnections__c record values the solution might call for:
• Trigger on Friend__c (after delete, before insert), //to handle when friends are added or deleted. We must recalculate the numberOfNthDirectOrMutualPersonConnections__c for some if not all Person__c in the database to sustain the new truth
• Trigger on Friend__c (before update) // to handle when a Friend__r.Person__c lookup changes then we must recalculate the numberOfNthDirectOrMutualPersonConnections__c for some if not all Person__c in the database to sustain the new truth
• Trigger on Person__c (after delete) //to handle when a Person__c is deleted because this will reduce friendships in the network therefore some if not all Person__c in the database would need to have Person__c.numberOfNthDirectOrMutualPersonConnections__c DML updated to sustain the new truth

ERD and Page Layout Details: FriendsList__c is the junction object that enables the many to many relationship. FriendsList__c is the master side in the master-detail relationship with Person__c. Person__c is the detail side. Every detail-side Person__c has 1 master FriendsList__c. Using the FriendsList__c standard page, we click New Friend to add a new Friend__c to the Friend__c related list on FriendsList__c. (Note that per my requirement the Friend__c edit page layout requires Lookup association to Person__c)

Answer 1

I created a similar data structure. It's basically just missing the lookup from friend to person. Also for the sake of simplicity, I'm using the name as an identifier, but it would be the same principle to use the person id instead.

The data I used to recreate the graph in you example:

Person__c:{Name=Lisa, Id=a0d9000000OJ2v7AAD}
Person__c:{Name=Jane, Id=a0d9000000OJ2v2AAD}
Person__c:{Name=Tom, Id=a0d9000000OJ2uxAAD}
Person__c:{Name=Kim, Id=a0d9000000OJ2vCAAT}
Person__c:{Name=Bill, Id=a0d9000000OJ2usAAD}

Friend__c:{Name=Jane, Id=a0f9000000W50uOAAR}
Friend__c:{Name=Kim, Id=a0f9000000W50uYAAR}
Friend__c:{Name=Lisa, Id=a0f9000000W50uTAAR}
Friend__c:{Name=Bill, Id=a0f9000000W50uEAAR}
Friend__c:{Name=Tom, Id=a0f9000000W50uJAAR}

// Jane <-> Lisa
Friendship__c:{Person__c=a0d9000000OJ2v2AAD, Friend__c=a0f9000000W50uTAAR, Id=a0e9000000U5eOAAAZ}
Friendship__c:{Person__c=a0d9000000OJ2v7AAD, Friend__c=a0f9000000W50uOAAR, Id=a0e9000000U5eO5AAJ}
// Lisa -> Kim
Friendship__c:{Person__c=a0d9000000OJ2v7AAD, Friend__c=a0f9000000W50uYAAR, Id=a0e9000000U5eOFAAZ}
// Jane <-> Tom
Friendship__c:{Person__c=a0d9000000OJ2v2AAD, Friend__c=a0f9000000W50uJAAR, Id=a0e9000000U5eO0AAJ}
Friendship__c:{Person__c=a0d9000000OJ2uxAAD, Friend__c=a0f9000000W50uOAAR, Id=a0e9000000U5eNvAAJ}
// Tom -> Bill
Friendship__c:{Person__c=a0d9000000OJ2uxAAD, Friend__c=a0f9000000W50uEAAR, Id=a0e9000000U5eNqAAJ}

So what I have here is a class that could be used on a trigger on the junction object whenever there is a change/addition/deletion to one of those records.

public class Trg_Friendship_NetworkSize {

    private map<String,set<String>> PersonFriendships = new map<String,set<String>>(); 
    map<String,Integer> PersonNetworkSize = new map<String,Integer>();

    public Trg_Friendship_NetworkSize(Integer NumberOfDegrees){
        list<Friendship__c> flist = [
            SELECT Person__r.Name, Friend__r.Name
            FROM Friendship__c
            LIMIT 50000
        ];

        for (Friendship__c f : flist){
            set<String> Friendships = PersonFriendships.get(f.Person__r.Name);
            if (Friendships == NULL) {
                Friendships = new set<String>(); 
                PersonFriendships.put(f.Person__r.Name,Friendships);
            }
            Friendships.add(f.Friend__r.Name);
        }

        // If you wanted to get the 0's right, you would have to query and loop over all the Person__c records here
        for (String Person : PersonFriendships.keySet()){
            set<String> Network = new set<String>();
            list<Node> Friends = new list<Node>{ new Node(this,Person,NumberOfDegrees) };
            while (Friends.size() > 0){
                list<Node> NextFriends = new list<Node>();
                for (Node n : Friends){
                    for (String s : n.getFriends()){
                        if (!Network.contains(s) && s != Person){
                            Network.add(s);
                            NextFriends.add(new Node(this,s,n.Depth-1));
                        }
                    }
                }
                Friends = NextFriends;
            }
            PersonNetworkSize.put(Person,Network.size());
        }
        System.debug(PersonNetworkSize); // or update your person records, etc.
    }

    private class Node {
        String  Name;
        Integer Depth;
        Trg_Friendship_NetworkSize Parent;

        Node (Trg_Friendship_NetworkSize Parent, String Name, Integer Depth){
            this.Name = Name;
            this.Depth = Depth;
            this.Parent = Parent;
        }

        set<String> getFriends(){
            if (Depth == 0) return new set<String>();
            else if (Parent.PersonFriendships.get(Name) == NULL) return new set<String>();
            else return Parent.PersonFriendships.get(Name);
        }
    }

}

To call the class, you would just need to run:

// I believe there would also need to be triggers on Person__c and Friend__c that do the same thing.
trigger Friendship on Friendship__c (after insert, after update, after delete, after undelete) {
    new Trg_Friendship_NetworkSize(3); // The integer parameter is the number of degrees of separation you want to consider.
}

Also, you mentioned in your question that you would expect to have small enough data volumes that you should be able to run this class synchronously, so that's how I wrote it, but keep in mind that for larger amounts of data, you would probably need to make this async, or even move it to a process outside of Salesforce.

---

With how I did it, all Friendship__c records are a one directional relationship from the Person__c to the Friend__c, so a two directional relationship would be made up of two Friendship__c records. You could try to save some space by adding a flag on the Friendship object to indicate that a relationship is two directional, but it would complicate the logic a bit.

Also, if you didn't want to limit the depth of relationships to consider for the network size, you could remove Depth from the Node class (or just always populate it with a positive number instead of having it count down). That way, it will keep going until there are no new people to add.

---

After adjusting the code to fit with your data model and removing the depth counter so that the trigger will calculate an infinite number of degrees of separation, the following should work in your org:

public class Trg_RecalculateNetworkSize {

    private map<Id,set<Id>> PersonFriendships = new map<Id,set<Id>>(); 
    map<Id,Integer> PersonNetworkSize = new map<Id,Integer>();

    public Trg_RecalculateNetworkSize(){
        list<Friendlist__c> flist = [
            SELECT Person__c, Friend__r.Person__c
            FROM Friendlist__c
            LIMIT 50000
        ];

        for (Friendlist__c f : flist){
            set<Id> Friendships = PersonFriendships.get(f.Person__c);
            if (Friendships == NULL) {
                Friendships = new set<Id>(); 
                PersonFriendships.put(f.Person__c,Friendships);
            }
            Friendships.add(f.Friend__r.Person__c);
        }

        for (Id Person :  PersonFriendships.keySet() ){
            set<Id> Network = new set<Id>();
            list<Node> Friends = new list<Node>{ new Node(this,Person) };
            while (Friends.size() > 0){
                list<Node> NextFriends = new list<Node>();
                for (Node n : Friends){
                    for (Id s : n.getFriends()){
                        if (!Network.contains(s) && s != Person){
                            Network.add(s);
                            NextFriends.add(new Node(this,s));
                        }
                    }
                }
                Friends = NextFriends;
            }
            PersonNetworkSize.put(Person,Network.size());
        }
        System.debug(PersonNetworkSize); // or update your person records, etc.
    }

    private class Node {
        Id  Person;
        Trg_Friendship_NetworkSize Parent;

        Node (Trg_Friendship_NetworkSize Parent, Id Person){
            this.Person = Person;
            this.Parent = Parent;
        }

        set<Id> getFriends(){
            if (Parent.PersonFriendships.get(Person) == NULL) return new set<Id>();
            else return Parent.PersonFriendships.get(Person);
        }
    }

} 

Triggers

trigger Friendlist on Friendlist__c (after insert, after update, after delete, after undelete) {
    new Trg_RecalculateNetworkSize(); 
}

trigger Person on Person__c (after insert, after delete, after undelete) {
    new Trg_RecalculateNetworkSize(); 
}

trigger Friend on Friend__c (after insert, after delete, after undelete) {
    new Trg_RecalculateNetworkSize(); 
}