如何确定有向循环图中每个节点的parents和children？

Question

我正在处理与嵌套组相关的问题。我需要确定一个组所属的所有组及其成员的所有组。不仅是直接的 parents 和 children，还有上下层级中的每个人。

到目前为止我所做的是top-bottom的遍历逻辑，即DFS使用堆栈存储未访问的笔记和哈希集存储访问过的笔记。这样一来，如果结果图中有任何循环，我们就不会进入无限递归。

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);
            }
        }
    }
}

这部分有效。我遇到的问题是，弄清楚如何在遍历期间为每个组存储 parents 和 children。请记住，一个组可以有其他组或用户作为成员，我们不想存储重复信息。

输出应该看起来像一个组列表，其中一个组如下所示

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; }
}

Answer 1

不确定我是否理解正确，因为您似乎已经用 visited HashSet 解决了这个问题。只需将其设为 Init 和 return 中的 local 变量，作为操作的结果：

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;
    }

}

输出：

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

----- 编辑 -----

根据新的要求，我~觉得~这就是你想要的：

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;
    }

}

输出：

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

如何确定有向循环图中每个节点的parents和children？

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

c#

directed-graph

cyclic-graph