12

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).

See the Example & Expectation below as it is based on this image

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. This is because Person__c Tom has 2 friends, plus 0 unique from Bill's friends list, plus 1 unique from Jane's friends (we dont need to count Tom because the calculation is being done for Tom), plus 0 unique from Kim's friends list.

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)

enter image description here

  • 1
    Ultimately it is your question but the reason I added the tree structure is that is how the Database is structured and how the query needs to be viewing the data. We do all think / visualize differently though. Hope you get an working answer although the question is a bit broad – Eric Sep 4 '17 at 16:45
  • 1
    Hi @Eric, the reason i replaced your tree structure with a network graph is because although SOQL queries are tree-like in traversal, I have implemented a many-to-many relationship which gives the effect of a network. Tree's don't support "Jane" having two parents. Networks do. I believe I have to perform a single giant query on all Friend__c then iterate it to create in memory a "Network" structure meaning a collection of Person__c "nodes" and their edge mapping (from/to other Person__c Ids). Then count via some depth algorithm – Peter Noges Sep 4 '17 at 16:53
  • 3
    No worries at all. I also believe you will have to query the entire thing and logically decipher it via code. This will ultimately need to be an async process though. Queueable Apex seems to be the appropriate choice here. Hopefully much smarter than I will be able to help you find the final solution – Eric Sep 4 '17 at 16:56
5
+200

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.

enter image description here

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(); 
}
  • very helpful. I am eager to test your answer. Until then I am curious to know if you can modify it so that it is depth-agnostic. In fact I would like to use synchronous logic to process the directional+mutual depth count of Person__c 's friends in their network unless of course Governor Limits are predicted to fail in which case I would instead want to offload the depth counting to async Batch Apex. Would you be willing to to update your answer to meet these new requirements? Or i can start a new question. Either way, thank you! – Peter Noges Sep 6 '17 at 21:20
  • Great solution, Martin! @SFDC_peter, your question says that you want to find friends to the Nths degree. To me, this suggests that you want the depth to be variable, like Martin created it. Does your request for a depth-agnostic solution mean you want to find all the friends without ever specifying a depth? (This means you wouldn't be able to find out how many friends a person has within for instance three nodes of depth. But you would know how many the total of direct and indirect friends are for that person.) – Kasper Sep 7 '17 at 18:11
  • I completely agree. Martin answered it how asked. I asked incorrectly. It would be excellent to know total, not nth. @Martin I am more than willing to accept your answer here and raise second question asking for a total calculation. – Peter Noges Sep 8 '17 at 1:21
  • @SFDC_peter The simplest change to get the count of all relations no matter how distant would be to not decrement the counter when moving a layer deep: NextFriends.add(new Node(this,s,n.Depth-1)); -> NextFriends.add(new Node(this,s,1));. This way it will keep going until there are no new friends to add. – martin Sep 8 '17 at 1:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.