Create an adjacency list type structure from a list of pairs

Question

In C # I have

class Pair{ int val1; int val2; } 

I have a list of pairs coming from a source like: -

 List<Pair> sList = new List<Pair>(); 1 | 2 2 | 3 1 | 4 4 | 6 

I need to convert it to the following type of structure: -

  [1, [2, 3, 4, 6]] [2, [3]] [3, [2]] [4, [1,6]] [6, [4]] 

What is the best way to do this (without LINQ)?

Answer 1

I would go with ILookup<int, int> , but you also need to enable reverse associations:

 var result = sList.Union(sList.Select(p => new Pair { val1 = p.val2, val2 = p.val1 })) .ToLookup(p => p.val1, p => p.val2); 

You can get a similar result without Linq using this:

 var dict = new Dictionary<int, List<int>>(); foreach(var pair in sList) { if (!dict.ContainsKey(pair.val1)) { dict[pair.val1] = new List<int>(); } if (!dict.ContainsKey(pair.val2)) { dict[pair.val2] = new List<int>(); } dict[pair.val1].Add(pair.val2); dict[pair.val2].Add(pair.val1); } 

---

Both of the above methods will create an Adhesion List , however from your comments it seems like you want to do more than the Labeling Connected Component

 var groups = new List<HashSet<int>>(); foreach (var p in sList) { var merge = new List<HashSet<int>>(); foreach(var g in groups) { if (g.Contains(p.val1) || g.Contains(p.val2)) { merge.Add(g); } } if (merge.Count == 0) { var h = new HashSet<int>(); groups.Add(h); merge.Add(h); } merge[0].Add(p.val1); merge[0].Add(p.val2); for(int i = 1; i < merge.Count; i ++) { foreach(int v in merge[i]) { merge[0].Add(v); } groups.Remove(merge[i]); } } 

When entrance

 sList = 1 | 2 4 | 6 2 | 3 1 | 4 9 | 10 

This will exit:

 groups = [ 1, 2, 3, 4, 6 ] [ 9, 10 ] 

Then it is not so difficult to convert this to the desired format:

 var dict = new Dictionary<int, List<int>>(); foreach(var g in groups) { foreach(var v in g) { var list = new List<int>(g); list.Remove(g); dict.Add(v, list) } } 

Using the previous example:

 dict = 1 | [ 2, 3, 4, 6 ] 2 | [ 1, 3, 4, 6 ] 3 | [ 1, 2, 4, 6 ] 4 | [ 1, 2, 3, 6 ] 6 | [ 1, 2, 3, 4 ] 9 | [ 9 ] 10 | [ 10 ] 

Answer 2

You can do this using the LINQ GroupBy method, for example:

 var adj = sList .GroupBy(p => p.val1) .ToDictionary(g => g.Key, g => g.Select(p => p.val2).ToList()); 

Please note that this will not calculate the transitive closure of your graph, i.e. only direct links will be present.

In .NET 4 and above, you can also use Tuple<int,int> instead of creating your own Pair class.