C# regrouping some elements into different groups by their friendship without cycles

Question

I am working on solving a problem of grouping some elements into different groups by their friendship.

For example,

Input:

 R1: R2, R6, R8, R10   // all elements in one group are friends
 R6: R1, R7, R8, R12 
 R8: R2, R5, R6, R10 
 R4: R11, R15, R16, R13  // **UPDATE** this is a group that do not have overlap with all other groups 

For R1, all R1's friends' friends are also R1's friends who need to be classified into the same group and so on.

Expected output:

 R1: R2, R6, R8, R10 , R7, R5, R12
 R4: R11, R15, R16, R13   // **UPDATE**

The output may be two or more groups.It depends on the input.

Now, the data is stored in a dictionary> of C# in Visual Studio 2012.

I find that there may be cycles in the grouping process.

Example, R1 ---> R6 ---> R8 --> R6

Would you please help me find how to solve the cycle problems.

Any help would be appreciated.

Thanks

Answer 1

Demo Code Shown Below :

    private static Dictionary<string, List<string>> ProcessData(Dictionary<string, List<string>> data)
    {
        var processedData = new Dictionary<string, List<string>>();
        var masterList = new List<string>();
        foreach (var value in data.Keys)
        {
            if (!masterList.Contains(value))
            {
                var friendList = FindFriends(data, value);
                masterList.AddRange(friendList);
                processedData.Add(value, friendList);
            }
        }
        return processedData;
    }

    private static List<string> FindFriends(Dictionary<string, List<string>> data,string source)
    {
        var friendMasterList = new List<string>();
        var friendQueue = new Queue<string>();
        if (data.ContainsKey(source))
        { 
            foreach (var value in data[source])
            {
                friendQueue.Enqueue(value);
            }
            while (friendQueue.Count > 0)
            {
                var value = friendQueue.Dequeue();
                if (!friendMasterList.Contains(value))
                    friendMasterList.Add(value);

                if (data.ContainsKey(value))
                {
                    foreach (var value2 in data[value])
                    {
                        if (!friendMasterList.Contains(value2))
                            friendQueue.Enqueue(value2);
                    }
                }
            } 
        }
        if (friendMasterList.Contains(source))
            friendMasterList.Remove(source);
        return friendMasterList;
    }