c# - How to determine parents and children of each node in a directed cyclic graph? -

i'm working on problem related nested groups. need determine groups group member of , groups it's members. not immediate parents , children in hierarchy , down.

what have done far traversing logic top-bottom ie, dfs using stack store not visited notes , hashset store visited notes. if there cycles in resulting graph wont go 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. i'm having trouble is, figuring out how store parents , children each group during traversal. remember group can have other groups or users members , don't want store duplicate information.

output should list of groups group 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 seems you've solved visited hashset. make local variable in init , return result of 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 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" 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 quit 

----- edit -----

based on new requirements, ~think~ 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 , 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 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 results:         foreach(mygroup group in output.values)         {             console.write(group.tostring());             console.writeline("--------------------------------------------------");         }         console.write("press enter 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" 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 quit