反转图表

Question

(我希望我正确使用'反转')

我有一组节点(对象)和边(节点所引用的其他对象的列表).整个图表用a表示Dictionary<string, List<string>.

(补充工具栏:有问题的对象不string实际.对象的实际类型无关紧要)

现在,我需要反转图形,所以我没有一个对象列表和它们引用的所有对象,而是有一个对象列表和引用它们的所有对象.

我可以通过循环很容易地做到这一点,但我想有一个更好的方法使用Linq.是这种情况,如果是这样,我该怎么办？

为了确保我们清楚,让我们假装我的数据集看起来像这样:

var graph = new Dictionary<string, List<string>> {
    {"A", new string[] { "C", "D" } },
    {"B", new string[] { "D" } },
    {"C", new string[] { "D" } },
    {"D", new string[] { "B" } }, //note that C and D refer to each other
};

我需要将其转化为道德等同于此:

var graph = new Dictionary<string, List<string>> {
    {"A", new string[] {  } },
    {"B", new string[] { "D" } },
    {"C", new string[] { "A" } },
    {"D", new string[] { "A", "C", "B" } },
};

提前致谢!

Answer 1

您可以天真地逆转，只需说“对于每个节点，找到其邻居列表中包含该节点的所有顶点”（如果有可以到达的节点，但没有任何邻居，则需要并集，但这是不必要的如果对于此类节点，您的字典中有以下形式的条目v -> { }）：

var inverse = graph.Keys
                   .Union(
                       graph.Values
                            .SelectMany(v => v)
                            .Distinct()
                   )
                   .ToDictionary(
                       v => v,
                       v => graph.Keys.Where(key => graph[key].Contains(v))
                   );