c# - 反转图形

Question

(我希望我正确使用了“反转”)

我有一组节点(对象)和边(该节点所指的其他对象的列表)。整个图在 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))
                   );