Inverting a graph

Question

(I hope I used 'inverting' correctly)

I have a collection of nodes (objects) and edges (a list of other objects to which the node refers to). The whole graph is represented in a Dictionary<string, List<string>.

(Sidebar: The object in question is not string in reality. The actual type of the object is of no consequence)

Now, I need to invert the graph, so rather than having a list of objects and all the objects they refer to, I have a list of objects and all the objects that refer to them.

I can do this pretty easily with a loop, but I imagine there's a better way using Linq. Is this the case, and if so, how do I do it?

Just to ensure that we're clear, let's pretend that my dataset looks like this:

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

I need to transform it into the moral equivalent of this:

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

Thanks in advance!

Answer 1

You can naively reverse by just saying "for every node, find all the vertices that have this node in its neighbors list" (the union is necessary in case there are nodes that can be reached, but don't have any neighbors but is unnecessary if for such nodes you have an entry of the form v -> { } in your dictionary):

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