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 as:-

List<Pair> sList = new List<Pair>();

   1 | 2
   2 | 3
   1 | 4
   4 | 6

I need to convert it into 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 go about this (without LINQ)?

Loveinidleness

Where's 3 in [2, 3, 4] come from? 2 comes from 1 | 2, and 4 comes from 1 | 4, but there's no 1 | 3. Do you have more records in your list? – Anticathode

1 and 2 are pairs 2 and 3 are pairs. so 1 is connected to 2 and 3. Similarly for others. kind of like an adjacency list – Loveinidleness

Why exclude LINQ? If you are limited by the .NET Framework you should tag the question with .net framework2.0 or .net framework3.0. – Topsoil

@Loveinidleness In that case 1 is not adjacent to 3. – Intercurrent

@heyNow: If this is an adjacency list, why can you have 1 be "adjacent" to 3 through 2, but not to 6 through 4? There is no clear pattern from the sample output you have given. – Topsoil

Sorry. edited. i was trying to get the general idea accross – Loveinidleness

Wouldn't all numbers in this set be 'adjacent' to all others since there is some path between all of them? – Intercurrent

maybe in above example. But what if there's a 9 | 10 that have nothing to do with any other numbers – Loveinidleness

@Loveinidleness It sounds like what you're really after is more like finding connected components of a graph. See my updated answer. – Intercurrent

https://mcmap.net/q/1781766/-how-do-i-represent-a-graph-given-as-an-adjacency-list-in-c – Paisley

Answer 1

I would go with an ILookup<int, int>, but you need to include the reverse associations as well:

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 methods above will produce an Adjacency List, however from your comments it sounds like what you want to do more like Connected Component Labeling

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 the input is

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

This will produce the output:

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

It's then not too difficult to convert this to the format you want:

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 ]

Intercurrent

Answer 2

You can do this with LINQ's GroupBy method, like this:

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

Note that this would not compute a transitive closure of your graph, i.e. only the direct links will be present.

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

Anticathode

without linq . sorry i should have mentioned earlier – Loveinidleness