I'm working on a problem related to nested groups. I need to determine all the groups a group is a member of and all the groups that are it's members. Not just immediate parents and children but everyone in the hierarchy up and down.
What I have done so far is the traversing logic from top-bottom ie, DFS using a stack to store the not visited notes and a hashset to store the visited notes. This is so that if there are any cycles in the resulting graph we wont go into infinite recursion.
static HashSet<string> visited = new HashSet<string>();
static Stack<string> notVisited = new Stack<string>();
static Dictionary<string, HashSet<string>> groupMembers = new Dictionary<string, HashSet<string>>
{
{ "G4", new HashSet<string> { "G5","G6","U1","U2"} },
{ "G1", new HashSet<string> { "G2","G3","G6"} },
{ "G3", new HashSet<string> { "G4"} },
{ "G2", new HashSet<string> { "G4","G1"} },
{ "G5", new HashSet<string> { "G2"} },
{ "G6", new HashSet<string> { "U2","G5"} },
};
static void Init(string start)
{
notVisited.Push(start);
while (notVisited.Count > 0)
{
string next = notVisited.Pop();
HashSet<string> found;
if (visited.Add(next) && groupMembers.TryGetValue(next, out found))
{
foreach (string member in found)
{
notVisited.Push(member);
}
}
}
}
This part works. What I'm having trouble with is, figuring out how do I store the parents and children for each group during traversal. Remember that a group can have other groups or users as members and we don't want to store duplicate information.
Output should look like a list of groups where a group is as follow
private class MyGroup
{
public string Identity { get; set; }
public HashSet<string> MemberOf { get; set; }
public HashSet<string> Members { get; set; }
public HashSet<string> Users { get; set; }
}
Not sure I'm understanding correctly because it seems like you've already solved this with your visited HashSet. Just make it a local variable in Init and return that as the result of the operation:
class Program
{
static Dictionary<string, HashSet<string>> groupMembers = new Dictionary<string, HashSet<string>>
{
{ "G4", new HashSet<string> { "G5","G6","U1","U2"} },
{ "G1", new HashSet<string> { "G2","G3","G6"} },
{ "G3", new HashSet<string> { "G4"} },
{ "G2", new HashSet<string> { "G4","G1"} },
{ "G5", new HashSet<string> { "G2"} },
{ "G6", new HashSet<string> { "U2","G5"} },
};
static void Main()
{
foreach(string start in groupMembers.Keys)
{
HashSet<string> result = Init(start);
Console.WriteLine("Start @ " + start + ": " + String.Join(", ", result.ToArray()));
}
Console.Write("Press Enter to Quit");
Console.ReadLine();
}
static HashSet<string> Init(string start)
{
HashSet<string> visited = new HashSet<string>();
Stack<string> notVisited = new Stack<string>();
notVisited.Push(start);
while (notVisited.Count > 0)
{
string next = notVisited.Pop();
HashSet<string> children;
if (visited.Add(next) && groupMembers.TryGetValue(next, out children))
{
foreach (string member in children)
{
notVisited.Push(member);
}
}
}
visited.Remove(start); // optionally remove "start" from the result?
return visited;
}
}
Output:
Start @ G4: U2, U1, G6, G5, G2, G1, G3
Start @ G1: G6, G5, G2, G4, U2, U1, G3
Start @ G3: G4, U2, U1, G6, G5, G2, G1
Start @ G2: G1, G6, G5, U2, G3, G4, U1
Start @ G5: G2, G1, G6, U2, G3, G4, U1
Start @ G6: G5, G2, G1, G3, G4, U2, U1
Press Enter to Quit
----- EDIT -----
Based on the new requirements, I ~think~ this is what you want:
class Program
{
private class MyGroup
{
public string Identity { get; set; }
public HashSet<string> MemberOf { get; set; }
public HashSet<string> Members { get; set; }
public HashSet<string> Users { get; set; }
public override string ToString()
{
StringBuilder sb = new StringBuilder();
sb.AppendLine("Identity: " + Identity);
sb.AppendLine("MemberOf: " + String.Join(", ", MemberOf.ToArray()));
sb.AppendLine("Members: " + String.Join(", ", Members.ToArray()));
sb.AppendLine("Users: " + String.Join(", ", Users.ToArray()));
return sb.ToString();
}
}
static Dictionary<string, HashSet<string>> groupMembers = new Dictionary<string, HashSet<string>>
{
{ "G4", new HashSet<string> { "G5","G6","U1","U2"} },
{ "G1", new HashSet<string> { "G2","G3","G6"} },
{ "G3", new HashSet<string> { "G4"} },
{ "G2", new HashSet<string> { "G4","G1"} },
{ "G5", new HashSet<string> { "G2"} },
{ "G6", new HashSet<string> { "U2","G5"} },
};
static void Main()
{
Dictionary<string, MyGroup> output = new Dictionary<string, MyGroup>();
// First Pass: Figure out Children and Users
foreach(string start in groupMembers.Keys)
{
MyGroup group = new MyGroup();
group.Identity = start;
HashSet<string> Users = new HashSet<string>();
group.Members = GetChildrenAndUsers(start, ref Users);
group.Users = Users;
output.Add(start, group);
}
// Second Pass: Figure out the Parents:
List<string> outer = output.Keys.ToList();
List<string> inner = output.Keys.ToList();
foreach (string outerKey in outer)
{
MyGroup group = output[outerKey];
group.MemberOf = new HashSet<string>();
foreach (string innerKey in inner)
{
MyGroup group2 = output[innerKey];
if (group2.Identity != group.Identity)
{
if(group2.Members.Contains(group.Identity))
{
group.MemberOf.Add(group2.Identity);
}
}
}
}
// Display the results:
foreach(MyGroup group in output.Values)
{
Console.Write(group.ToString());
Console.WriteLine("--------------------------------------------------");
}
Console.Write("Press Enter to Quit");
Console.ReadLine();
}
static HashSet<string> GetChildrenAndUsers(string start, ref HashSet<string> Users)
{
HashSet<string> visited = new HashSet<string>();
Stack<string> notVisited = new Stack<string>();
notVisited.Push(start);
while (notVisited.Count > 0)
{
string next = notVisited.Pop();
HashSet<string> children;
if (!groupMembers.ContainsKey(next))
{
Users.Add(next);
}
else
{
if (visited.Add(next) && groupMembers.TryGetValue(next, out children))
{
foreach (string member in children)
{
notVisited.Push(member);
}
}
}
}
visited.Remove(start); // optionally remove "start" from the result?
return visited;
}
}
Output:
Identity: G4
MemberOf: G1, G3, G2, G5, G6
Members: G6, G5, G2, G1, G3
Users: U2, U1
--------------------------------------------------
Identity: G1
MemberOf: G4, G3, G2, G5, G6
Members: G6, G5, G2, G4, G3
Users: U2, U1
--------------------------------------------------
Identity: G3
MemberOf: G4, G1, G2, G5, G6
Members: G4, G6, G5, G2, G1
Users: U2, U1
--------------------------------------------------
Identity: G2
MemberOf: G4, G1, G3, G5, G6
Members: G1, G6, G5, G3, G4
Users: U2, U1
--------------------------------------------------
Identity: G5
MemberOf: G4, G1, G3, G2, G6
Members: G2, G1, G6, G3, G4
Users: U2, U1
--------------------------------------------------
Identity: G6
MemberOf: G4, G1, G3, G2, G5
Members: G5, G2, G1, G3, G4
Users: U2, U1
--------------------------------------------------
Press Enter to Quit