0

ネストされたグループに関連する問題に取り組んでいます。グループがメンバーであるすべてのグループと、そのメンバーであるすべてのグループを特定する必要があります。直接の親と子だけでなく、上下の階層の全員。

私がこれまで行ってきたことは、上から下へのトラバース ロジックです。つまり、スタックを使用してアクセスされていないメモを格納し、ハッシュセットを使用してアクセスされたメモを格納する 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);
            }
        }
    }
}

この部分は機能します。私が問題を抱えているのは、トラバーサル中に各グループの親と子をどのように保存するかを考え出すことです。グループには他のグループまたはユーザーをメンバーとして含めることができ、重複した情報を保存したくないことに注意してください。

出力は、グループが次のようなグループのリストのようになります。

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

1 に答える 1

1

visitedHashSetでこれをすでに解決しているように見えるので、私が正しく理解しているかどうかはわかりません。それをローカル変数にしInitて、操作の結果として返すだけです。

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
于 2015-07-23T18:01:20.850 に答える