0

I have a very large dataset with two columns of interest: Name and Cousin.

Each row has a unique name and each name has a cousin.

The data is mutually inclusive, so the cousin's name will also appear as another row in the data.

The effect is therefore a big dataset with lots of names of people who are related to each other.

The relations, however, form themselves into separate groups. These are groups that have no relation with any person in any other group.

E.g (using -> to denote a relation)

A->C->E->G = Group 1
B->D->F->H = Group 2

None of the people in Group 1 shares a relation with any person in Group 2.

So, I'm looking for an approach to find these groups of related people using only their names and relations. This could be some pseudo-code or a conceptual approach, anything to point me down the right path.

Example dataset:

Name Cousin  
A    C  
B    D 
C    E  
D    F  
E    G  
F    H  
G    E
H    K
I    M  
K    H  
M    I

This data would be aggregated into three groups: Group 1 (A,C,E,G); Group 2 (B,D,F,H,K); Group 3 (I,M).

  • You appear to have a graph. – user40980 Jun 5 '15 at 14:46
  • 1
    The cousin relationship is not transitive. So in your dataset C, D, F and H all have cousins, but they're not all cousins of each other. – TZHX Jun 5 '15 at 15:03
  • C to H could be cousin's cousin's cousin which as seen there doesn't imply any relationship that C is a cousin of F or H. – user40980 Jun 5 '15 at 15:06
  • Not that C is a cousin of F or H, no. But they are related by x degrees of separation. I was looking for a way to group those who are related, whatever the degrees of separation. – Chris M Jun 6 '15 at 16:05
  • 1
    Just corrected the mistake in group A. Each entry has one cousin relationship. – Chris M Jun 9 '15 at 16:40
1

You are building a set of graphs.

You start out and start walking the list of relationships you have gotten back.

A -> C

So, lets make a graph that represents that.

A - C 

And then you've got:

B -> D

Neither B nor D are represented in any of the graphs currently. So now you have:

A - C       

B - D

And then C -> E, so we hunt up C and link to to E. Now we've got:

A - C - E   

B - D       

And so on. That will give you the give you all of the related graphs.

"Fine," you say, "but that doesn't really get any closer to doing an implementation"

The real problem here is how to represent the graphs.

Lets write some pseudocode. I speak a perlish dialect - but its not perl.

$nextGroup = 1
for each ($key, $link) in (@row) {
    if(not defined $group{$key}) {
        $group{$key} = $nextGroup++;
    }
    if(not defined $group{$link} || $group{$link} == $group{$key}) {
        $group{$link} = $group{$key}
    } else {
        for each ($k, $v) in (entries %group) {
            if($v == $group{$link}) {
                $group{$k} = $group{$key};
            }
        }
    }
}

What is it doing? It iterates over each row returned. If the key isn't a known item, it assigns it to a new group. It then assigns the group the key belongs to to the link. If the link already has a different value, then it finds all the links with the same value as it and assigns them to the value of the key.

So, we start out again.

A = 1 (nextGroup = 2)
  C = 1
B = 2 (nextGroup = 3)
  D = 2
C is 1
  E = 1
D = 3 (nextGroup = 4)
  F = 3
E is 1
  G = 1
...

At the end of this, the groups map/dictionary/hash (whatever your language calls it) is going to have each individual in there with a corresponding value. All entries with the same value belong to the same graph being depicted.

  • This is incredible. Thank you so much for the clear explanation and implementation. I will now put this into practice, fully understanding what I'm doing. – Chris M Jun 18 '15 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.