Алгоритм преобразования структуры (транзитивное замыкание?)

Question

Моя исходная структура - это словарь, похожий на:

new Dictionary<string, string>();
dic.Add("Dinges", new List<String>() { "A", "B" });
dic.Add("Facebook", new List<String>() { "Dinges" });
dic.Add("SocialMedia", new List<String>() { "FaceBook" });
dic.Add("Medium", new List<String>() { "SocialMedia" })

, или список кортежей, выглядящий следующим образом:

new List<Tuple<String, String>>();
list.Add(Tuple.Create("Dinges", "A");
list.Add(Tuple.Create("Dinges", "B");
list.Add(Tuple.Create("Facebook", "Dinges"); 
list.Add(Tuple.Create("SocialMedia", "Facebook");
list.Add(Tuple.Create("Medium", "SocialMedia");

Это ассоциации между элементами, которые лучше всего описать какнаследственное дерево.Средний - самый общий класс, а самый специализированный.

Я ищу способ перестановки предметов, чтобы он выглядел следующим образом:

new List<Tuple<String, String>>();
list.Add(Tuple.Create("Dinges", "A");
list.Add(Tuple.Create("Dinges", "B");
list.Add(Tuple.Create("Facebook", "Dinges"); 
list.Add(Tuple.Create("Facebook", "A");
list.Add(Tuple.Create("Facebook", "B");
list.Add(Tuple.Create("SocialMedia", "A");
list.Add(Tuple.Create("SocialMedia", "B");
list.Add(Tuple.Create("SocialMedia", "Dinges");
list.Add(Tuple.Create("SocialMedia", "Facebook");
list.Add(Tuple.Create("Medium", "A");
list.Add(Tuple.Create("Medium", "B");
list.Add(Tuple.Create("Medium", "Dinges");
list.Add(Tuple.Create("Medium", "FaceBook");
list.Add(Tuple.Create("Medium", "SocialMedia");

Мне действительно нужно немногопомогая в этом, у меня было несколько советов по поводу транзитивного замыкания, но я действительно не могу это обернуть.Любая помощь будет очень ценится.

Answer 1

Из словарного подхода, который, как я предполагаю, должен был быть объявлен как Dictionary<string, List<string>>:

private static IEnumerable<string> TransitiveValues(string name,
                    Dictionary<string, List<string>> lookup)
{
    yield return name;
    List<string> children;
    if (lookup.TryGetValue(name, out children))
    {
        foreach (string child in children)
        {
            foreach (string value in TransitiveValues(child, lookup))
            {
                yield return value;
            }
        }
    }
}

Тогда:

var query = from name in dictionary.Keys
            from value in TransitiveValues(name, dictionary)
            select Tuple.Create(name, value);
var list = query.ToList();

Просто убедитесь, что у вас нет циклов:)