Invert Graphics

Question

(Hope I used invert correctly)

I have a set of nodes (objects) and edges (a list of other objects that node belongs to). The entire graph is presented in Dictionary<string, List<string>.

(Sidebar: The object in question is not true string. The actual type of the object does not matter)

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

I can do this quite easily with a loop, but I think it's better to use Linq. This is so, and if so, how to do it?

Just to make sure we are clear, let it 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
};

:

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

, " node , node " ( , , , t , , v -> { } ):

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

Answer 2

:

var result = graph.Keys
    .Union(graph.SelectMany(x => x.Value))
    .Distinct()
    .ToDictionary(
        x => x, 
        x => graph.Where(y => y.Value.Contains(x)).Select(y => y.Key).ToList()
    );

:

foreach (var element in result)
{
    Console.WriteLine(element.Key + ": " + string.Join(", ", element.Value));
}

:

A:
B: D
C: A
D: A, B, C

Answer 3

, , . .ToDictionary() :

var inverse = graph.ToDictionary(
    i => i.Key,
    i => graph.Where(j => j.Value.Contains(i.Key))
              .Select(j => j.Key)
              .Distinct()
              .ToList());

This selects the current key as the key for the inverse dictionary, and then creates a new list of pairs in the source dictionary, choosing the keys in which the value of the edge list contains the target key and .ToList () is called.