Find a list of related classes Recursively

Question

Supose I have a class representing a friend and another one representing pairs of best friends and a list of pairs of best friends and want to know each friend that is indirectly related to each one's best friend, as follows:

class Friend
{
    string Name;
}

class BestFriends
{
    Friend NameFriend1;
    Friend NameFriend2;
}

List<BestFriends> ListOfBestFriends = new List<BestFriends>();

Supose I have the BestFriends pairs as follows:

Adam and Brian;
Brian and Chris;
Chris and Daniel;
Eddie and Ian;
Brian and John.

I want to create a method that returns a list of all friends indirectly related to one specific friend. For example: if I want all indirect friends of Brian, the method would return { Adam, Chris, Daniel, John }.

List<Friend> IndirectFriends (Friend friendToHasItsIndirectFriendsFound, List<BestFriends> bestFriendsPairs)
{
    ...
}

How could I do that?

Your wording is misleading. You are not searching for related classes, but for related objects of the same class (which is `Friend` in your case). Given this, I don't get the meaning of the first parameter in your `IndirectFriends` method. I guess it is the `Friend` you want the indirect friends for? How do you define "IndirectFriend"? Any depth in your recursion, or only the first level starting from the best friends of the friend to find the indirects for? Please clarify. Hint: Read up on graphs. — K. Berger, Dec 19 '16 at 18:05
I think you effectively need a graph traversal algorithm, which may be beyond the scope of a Stack Overflow answer. — BradleyDotNET, Dec 19 '16 at 18:05
@K.Berger The `Friend` parameter is the friend I want to find all indirectly related friends. By "indirect friends" I mean all friends in all levels that can be indirecly connected to the `Friend`parameter (look up at my example). I guess I should use graph transversal, but I have never used it before. — Guilherme Campos, Dec 19 '16 at 18:48

score 1 · Answer 1 · answered Dec 19 '16 at 18:06

1

Look up graph traversal. In your case you can add a list of best friends to the friend class like this:

class Friend
{
    string Name;
    List<Friend> bestFriends;
}

then fill this list for each friend using the BestFriends pairs you have.

Afterwards you can use breadth-first or depth-first-search to find all indirectly related friends.

answered Dec 19 '16 at 18:06

fafl

7,222
3
27
50

Yes, I think I must use graph transversal. Thanks! I cannot add a list of best friends to my `Friend` class for other reasons. – Guilherme Campos Dec 19 '16 at 18:51
If you can't change the class, you might create a dictionary instead, that holds for each friend the list of bestfriends: `Dictionary>` – fafl Dec 19 '16 at 19:15

score 1 · Answer 2 · edited May 23 '17 at 11:55

Consider using set based operations to solve this with Linq.

Given the data structure you proposed, to solve the problem you need to solve for both direct friends and indirect friends. There are 2 cases for direct friends. 1, where the common friend is NameFriend1, the other is nameFriend2. These two cases are solved at the end of the method IndirectFriends.

For indirect friends, the case gets more complicated, because you will need to join the results of the direct friends to the same dataset twice, one for where the direct friend is NameFriend1 on the 2nd list, another for when it's NameFriend2. That is why there are 4 cases to resolve.

At the end of the method IndirectFriends, I exclude the common friend from the list and return only distinct results.

Please note, this code only works because the same object brian is being used in the list and also for comparisons. If you are instantiating new variables with the same values and you want them to be evaluated by linq as being equal, you'll need to implement the IComparable interface Link below How to Implement IComparable interface?

[TestMethod]
public void TestMethod1()
{
    List<BestFriends> ListOfBestFriends = new List<BestFriends>();
    var adam = new Friend { Name = "Adam" };
    var brian = new Friend { Name = "Brian" };
    var chris = new Friend { Name = "Chris" };
    var daniel = new Friend { Name = "Daniel" };
    var eddie = new Friend { Name = "Eddie" };
    var ian = new Friend { Name = "Ian" };
    var john = new Friend { Name = "John" };

    ListOfBestFriends.Add(new BestFriends { NameFriend1 = adam, NameFriend2 = brian });
    ListOfBestFriends.Add(new BestFriends { NameFriend1 = brian, NameFriend2 = chris });
    ListOfBestFriends.Add(new BestFriends { NameFriend1 = chris, NameFriend2 = daniel });
    ListOfBestFriends.Add(new BestFriends { NameFriend1 = eddie, NameFriend2 = ian });
    ListOfBestFriends.Add(new BestFriends { NameFriend1 = brian, NameFriend2 = john });

    var result = IndirectFriends(brian, ListOfBestFriends);
}

List<Friend> IndirectFriends(Friend commonFriend, List<BestFriends> bestFriendsPairs)
{
    /* Get inDirect Friends where commonfriend = NameFriend2 */
    /*  First list is joined on Namefriend2 and Namefriend1 */
    var l1 =  (from bfp in bestFriendsPairs
                join bfpR in bestFriendsPairs
                on bfp.NameFriend2 equals bfpR.NameFriend1
                where bfp.NameFriend1 == commonFriend
                select bfpR.NameFriend2).ToList();

    /* Get inDirect Friends where commonfriend= NameFriend2 */
    /*  First list is joined on Namefriend2 and Namefriend2 */
    l1.AddRange(from bfp in bestFriendsPairs
        join bfpR in bestFriendsPairs
            on bfp.NameFriend2 equals bfpR.NameFriend2
        where bfp.NameFriend1 == commonFriend
        select bfpR.NameFriend1);

    /* Get InDirect Friends where commonfriend = NameFriend2 */
    /*  First list is joined on Namefriend1 and Namefriend2 */
    l1.AddRange (from bfp in bestFriendsPairs
              join bfpL in bestFriendsPairs
              on bfp.NameFriend1 equals bfpL.NameFriend2
              where bfp.NameFriend2 == commonFriend
              select bfpL.NameFriend1);

    /* Get InDirect Friends where commonfriend= NameFriend2 */
    /*  First list is joined on Namefriend1 and Namefriend1 */
    l1.AddRange(from bfp in bestFriendsPairs
                join bfpL in bestFriendsPairs
                on bfp.NameFriend1 equals bfpL.NameFriend1
                where bfp.NameFriend2 == commonFriend
                select bfpL.NameFriend2);

    /* Get Direct Friends where commonfriend= NameFriend2 */
    l1.AddRange(from bfp in bestFriendsPairs
                where bfp.NameFriend2 == commonFriend
                select bfp.NameFriend1);

    /* Get Direct Friends where commonfriend= NameFriend1 */
    l1.AddRange(from bfp in bestFriendsPairs
                where bfp.NameFriend1 == commonFriend
                select bfp.NameFriend2);

    /*exclude commonfriend, and get distinct */
    return l1.Where(f=>f!= commonFriend).Distinct().ToList();
}

Ashkan Mobayen Khiabani · Answer 3 · 2016-12-19T18:08:01.213

0

    BestFriends.Where(
    b=>b.NameFriend1.Name!=friend.Name &&
    b.NameFriend2.Name!=friend.Name && 
   BestFriends.Any(b2=>b2.NameFriend1.Name==friend.Name||b2.NameFriend2.Name==friend.Name));

Also consider adding an Id to the Friend class and use that to compare instead of names

edited Dec 19 '16 at 18:08

answered Dec 19 '16 at 18:06

Ashkan Mobayen Khiabani

33,575
33
102
171

This only goes one level deep; if he wants more you need real graph traversal. – BradleyDotNET Dec 19 '16 at 18:07

Find a list of related classes Recursively

3 Answers3

Linked