blib/lib/Genealogy/Relationship.pm

filter: Statementstmt 96.3% 130 / 135 Branchbran 83.8% 52 / 62 Conditioncond 100% 6 / 6 MC/DCmcdc 100% 4 / 4 Subroutinesub 100% 16 / 16 Podpod 100% 8 / 8 totaltotal 93.5% 216 / 231 CC 39 SCAR 15.9
CC
39
Cov
93%
make_rel
7.8
most_recent_common_ancestor
7.0
get_relationship_coords
7.0
CRAP 4.9
↑ Summary
1 =head1 NAME
2  
3 Genealogy::Relationship - calculate the relationship between two people
4  
5 =head1 SYNOPSIS
6  
7 use Genealogy::Relationship;
8 use Person; # Imaginary class modelling people
9  
10 my $rel = Genealogy::Relationship->new;
11  
12 my $grandfather = Person->new( ... );
13 my $father = Person->new( ... );
14 my $me = Person->new( ... );
15 my $aunt = Person->new( ... );
16 my $cousin = Person->new( ... );
17  
18 my $common_ancestor = $rel->most_recent_common_ancestor(
19 $me, $cousin,
20 );
21 say $common_ancestor->name; # Grandfather's name
22  
23 say $rel->get_relationship($me, $grandfather); # Grandson
24 say $rel->get_relationship($grandfather, $me); # Grandfather
25  
26 say $rel->get_relationship($father, $cousin); # Uncle
27 say $rel->get_relationship($cousin, $father); # Niece
28  
29 =head1 DESCRIPTION
30  
31 This module makes it easy to calculate the relationship between two people.
32  
33 If you have a set of objects modelling your family tree, then you will
34 be able to use this module to get a description of the relationship between
35 any two people on that tree.
36  
37 The objects that you use with this module need to implement three methods:
38  
39 =over 4
40  
41 =item * parents
42  
43 This method should return an array reference containing the objects which are
44 the parents of the current person. The array reference can contain zero, one
45 or two objects.
46  
47 If an object does not have a C<parents()> method, then the module will fall
48 back to using a C<parent()> method that returns a single parent object.
49  
50 =item * id
51  
52 This method should return a unique identifier for the current person.
53 The identifier can be a string or a number.
54  
55 =item * gender
56  
57 This method should return the gender of the current person. It should be
58 the character 'm' or 'f'.
59  
60 =back
61  
62 =head2 Note
63  
64 THe objects that you use with this class can actually have different names
65 for these methods. C<parent>, C<parents>, C<id> and C<gender> are the default
66 names used by this module, but you can change them by passing the correct names
67 to the constructor. For example:
68  
69 my $rel = Genealogy::Relationship->new(
70 parent_field_name => 'progenitor',
71 parents_field_name => 'progenitors',
72 identifier_field_name => 'person_id',
73 gender_field_name => 'sex',
74 );
75  
76 =head2 Limitations
77  
78 This module was born out of a need I had while creating
79 L<https://lineofsuccession.co.uk/>. Relationship calculations are based on
80 finding the most recent common ancestor between two people, and choosing the
81 path that uses the fewest generations.
82  
83 =head2 Constructor
84  
85 The constructor for this class takes one optional attribute called `abbr`.
86 The default value for this attribute is 2. When set, strings of repeated
87 "great"s in a relationship description will collapsed to "$n x great".
88  
89 For example, if the description you have is "Great, great, great
90 grandfather", then that will be abbreviated to to "3 x great grandfather".
91  
92 The value for `abbr` is the maximum number of repetitions that will be left
93 untouched. You can turn abbreviations off by setting `abbr` to zero.
94  
95 =head2 Caching
96  
97 Calculating relationship names isn't at all different. But there can be a lot
98 of (simple and repetitive) work involved. This is particularly true if your
99 objects are based on database tables (as I found to my expense).
100  
101 If you're calculating a lot of relationships, then you should probably
102 consider putting a caching layer in front of C<get_relationship>.
103  
104 =cut
105  
106 6 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
107 6 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
108 6 ▶use Feature::Compat::Class;
Subroutine BEGIN: called CC=1 SCAR=0.0
109  
110 class Genealogy::Relationship;
111  
112 6 ▶use List::Util qw[first];
Subroutine BEGIN: called CC=1 SCAR=0.0
113 6 ▶use Lingua::EN::Numbers qw[num2en num2en_ordinal];
Subroutine BEGIN: called CC=1 SCAR=0.0
114  
115 6 our $VERSION = '2.0.0';
116  
117 6 field $parent_field_name :param = 'parent';
118 6 field $parents_field_name :param = 'parents';
119 6 field $identifier_field_name :param = 'id';
120 6 field $gender_field_name :param = 'gender';
121  
122 field $relationship_table :param = {
123 m => [
124 [ undef, 'Father', 'Grandfather', 'Great grandfather', 'Great, great grandfather', 'Great, great, great grandfather' ],
125 ['Son', 'Brother', 'Uncle', 'Great uncle', 'Great, great uncle', 'Great, great, great uncle' ],
126 ['Grandson', 'Nephew', 'First cousin', 'First cousin once removed', 'First cousin twice removed', 'First cousin three times removed' ],
127 ['Great grandson', 'Great nephew', 'First cousin once removed', 'Second cousin', 'Second cousin once removed', 'Second cousin twice removed' ],
128 ['Great, great grandson', 'Great, great nephew', 'First cousin twice removed', 'Second cousin once removed', 'Third cousin', 'Third cousin once removed' ],
129 ['Great, great, great grandson', 'Great, great, great nephew', 'First cousin three times removed', 'Second cousin twice removed', 'Third cousin once removed', 'Fourth cousin' ],
130 ],
131 f => [
132 [ undef, 'Mother', 'Grandmother', 'Great grandmother', 'Great, great grandmother', 'Great, great great grandmother' ],
133 ['Daughter', 'Sister', 'Aunt', 'Great aunt', 'Great, great aunt', 'Great, great, great aunt' ],
134 ['Granddaughter', 'Niece', 'First cousin', 'First cousin once removed', 'First cousin twice removed', 'First cousin three times removed' ],
135 ['Great granddaughter', 'Great niece', 'First cousin once removed', 'Second cousin', 'Second cousin once removed', 'Second cousin twice removed' ],
136 ['Great, great granddaughter', 'Great, great niece', 'First cousin twice removed', 'Second cousin once removed', 'Third cousin', 'Third cousin once removed' ],
137 ['Great, great, great granddaughter', 'Great, great, great niece', 'First cousin three times removed', 'Second cousin twice removed', 'Third cousin once removed', 'Fourth cousin' ],
138 ],
139 6 };
140  
141 6 field $abbr :param = 3;
142  
143 =head1 Methods
144  
145 The following methods are defined.
146  
147 =head2 most_recent_common_ancestor
148  
149 Given two person objects, returns the person who is the most recent common
150 ancestor for the given people. When multiple common ancestors exist at the
151 same distance, returns the one reachable via the fewest total generations
152 across both people.
153  
154 =cut
155  
156 28 ▶method most_recent_common_ancestor {
Subroutine most_recent_common_ancestor: called CC=7 SCAR=19.5
Pod documented
157 28 my ($person1, $person2) = @_;
158  
159 # Are they the same person?
160 28 ▶ return $person1
Branch: 1 branch
BranchTrueFalseTotal
if $person1->$identifier_field_name eq $person2->$identifier_field_name 3 25 28
161 if $person1->$identifier_field_name eq $person2->$identifier_field_name;
162  
163 25 my $map1 = $self->_ancestor_map($person1);
164 25 my $map2 = $self->_ancestor_map($person2);
165  
166 25 my ($best_person, $best_total);
167  
168 25 for my $id (keys %$map1) {
169 91 ▶ if (exists $map2->{$id}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $map2->{$id}) 33 58 91
170 33 my $total = $map1->{$id}{distance} + $map2->{$id}{distance};
171 33 ▶ if (!defined $best_total || $total < $best_total) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $best_total or $total < $best_total) 23 10 33
Condition100%3/3
not defined $best_total or $total < $best_total
l!l&&r!l&&!r
21210
MC/DC100%2/2
not defined $best_total or $total < $best_total
not defined $best_total $total < $best_total
Truth table100%3/3
not(A) or B
A= not defined $best_totalB= $total < $best_total
ABresult
1X1
011
000
172 23 $best_total = $total;
173 23 $best_person = $map1->{$id}{person};
174 }
175 }
176 }
177  
178 25 ▶ die "Can't find a common ancestor.\n" unless defined $best_person;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $best_person 4 21 25
179  
180 21 return $best_person;
181 }
182  
183 =head2 _get_parents
184  
185 Internal method. Given a person object, returns a list of that person's
186 parents. Uses the C<parents_field_name> method if the person object supports
187 it; otherwise falls back to the configured C<parent_field_name> method.
188  
189 =cut
190  
191 786 ▶method _get_parents {
Subroutine _get_parents: called CC=3 SCAR=11.0
192 786 my ($person) = @_;
193  
194 786 ▶ if ($person->can($parents_field_name)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($person->can($parents_field_name)) 286 500 786
195 286 return @{ $person->$parents_field_name() };
196 }
197  
198 500 my $parent = $person->$parent_field_name;
199 500 ▶ return defined $parent ? ($parent) : ();
Branch: 1 branch
BranchTrueFalseTotal
defined $parent ? : 368 132 500
200 }
201  
202 =head2 _ancestor_map
203  
204 Internal method. Given a person object, returns a hash reference mapping
205 each ancestor's identifier to a hash containing C<distance> (number of
206 generations from the given person) and C<person> (the ancestor object).
207 The person themself is included at distance zero.
208  
209 =cut
210  
211 202 ▶method _ancestor_map {
Subroutine _ancestor_map: called CC=4 SCAR=13.9
212 202 my ($person) = @_;
213  
214 202 my %map;
215 202 my @queue = ([$person, 0]);
216  
217 202 ▶ while (@queue) {
Branch: 1 branch
BranchTrueFalseTotal
if (@queue) 742 202 944
218 742 my ($current, $dist) = @{ shift @queue };
219 742 my $id = $current->$identifier_field_name;
220  
221 742 ▶ next if exists $map{$id};
Branch: 1 branch
BranchTrueFalseTotal
if exists $map{$id} 0 742 742
222  
223 742 $map{$id} = { distance => $dist, person => $current };
224  
225 742 for my $parent ($self->_get_parents($current)) {
226 540 push @queue, [$parent, $dist + 1];
227 }
228 }
229  
230 202 return \%map;
231 }
232  
233 =head2 get_ancestors
234  
235 Given a person object, returns a list of person objects, one for each
236 ancestor of the given person. When a person has two parents, all ancestors
237 from both parent lines are included (breadth-first order).
238  
239 The first entries in the list will be the person's direct parent(s) and the
240 last person will be their most distant ancestor.
241  
242 =cut
243  
244 12 ▶method get_ancestors {
Subroutine get_ancestors: called CC=4 SCAR=13.9
Pod documented
245 12 my ($person) = @_;
246  
247 12 my %visited;
248 my @ancestors;
249 12 my @queue = ($person);
250  
251 12 ▶ while (@queue) {
Branch: 1 branch
BranchTrueFalseTotal
if (@queue) 30 12 42
252 30 my $current = shift @queue;
253 30 for my $parent ($self->_get_parents($current)) {
254 18 my $id = $parent->$identifier_field_name;
255 18 ▶ unless ($visited{$id}++) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($visited{$id}++) 18 0 18
256 18 push @ancestors, $parent;
257 18 push @queue, $parent;
258 }
259 }
260 }
261  
262 12 return @ancestors;
263 }
264  
265 =head2 get_relationship
266  
267 Given two person objects, returns a string containing a description of the
268 relationship between those two people.
269  
270 =cut
271  
272 55 ▶method get_relationship {
Subroutine get_relationship: called CC=3 SCAR=11.0
Pod documented
273 55 my ($person1, $person2) = @_;
274  
275 55 my ($x, $y) = $self->get_relationship_coords($person1, $person2);
276  
277 55 my $rel;
278  
279 55 ▶ if (defined $relationship_table->{$person1->$gender_field_name}[$x][$y]) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $$relationship_table{$person1->$gender_field_name}[$x][$y]) { } 41 14 55
280 41 $rel = $relationship_table->{$person1->$gender_field_name}[$x][$y];
281 } else {
282 14 $rel = $relationship_table->{$person1->$gender_field_name}[$x][$y] =
283 ucfirst $self->make_rel($person1->$gender_field_name, $x, $y);
284 }
285  
286 55 ▶ $rel = $self->abbr_rel($rel) if $abbr;
Branch: 1 branch
BranchTrueFalseTotal
if $abbr 52 3 55
287  
288 55 return $rel;
289 }
290  
291 =head2 abbr_rel
292  
293 Optionally abbreviate a relationship description.
294  
295 =cut
296  
297 52 ▶method abbr_rel {
Subroutine abbr_rel: called CC=3 SCAR=11.0
Pod documented
298 52 my ($rel) = @_;
299  
300 52 ▶ return $rel unless $abbr;
Branch: 1 branch
BranchTrueFalseTotal
unless $abbr 0 52 52
301  
302 52 my @greats = $rel =~ /(great)/gi;
303 52 my $count = @greats;
304  
305 52 ▶ return $rel if $count < $abbr;
Branch: 1 branch
BranchTrueFalseTotal
if $count < $abbr 45 7 52
306  
307 7 $rel =~ s/(great,\s+)+/$count x /i;
308  
309 7 return $rel;
310 }
311  
312 =head2 make_rel
313  
314 Given relationship co-ords and a gender, this will synthesise a relationship
315 description. This only works because we've hard-coded an initial relationship
316 table that covers all of the trickier situations.
317  
318 =cut
319  
320 14 ▶method make_rel {
Subroutine make_rel: called CC=7 SCAR=20.5
Pod documented
321 14 my ($gender, $x, $y) = @_;
322  
323 14 my %terms = (
324 m => {
325 child => 'son',
326 parent => 'father',
327 parent_sibling => 'uncle',
328 parent_sibling_child => 'nephew',
329 },
330 f => {
331 child => 'daughter',
332 parent => 'mother',
333 parent_sibling => 'aunt',
334 parent_sibling_child => 'niece',
335 },
336 );
337  
338 14 ▶ if ($x == $y) {
Branch: 1 branch
BranchTrueFalseTotal
if ($x == $y) 5 9 14
339 5 return num2en_ordinal($x - 1) . ' cousin';
340 }
341  
342 9 ▶ if ($x == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($x == 0) 0 9 9
343 0 return join(', ', ('great') x ($y - 2)) . ' grand' . $terms{$gender}{parent};
344 }
345  
346 9 ▶ if ($x == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($x == 1) 6 3 9
347 6 return join(', ', ('great') x ($y - 2)) . ' ' . $terms{$gender}{parent_sibling};
348 }
349  
350 3 ▶ if ($y == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($y == 0) 0 3 3
351 0 return join(', ', ('great') x ($x - 2)) . ' grand' . $terms{$gender}{child};
352 }
353  
354 3 ▶ if ($y == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($y == 1) 0 3 3
355 0 return join(', ', ('great') x ($x - 2)) . ' ' . $terms{$gender}{parent_sibling_child};
356 }
357  
358 3 ▶ if ($x > $y) {
Branch: 1 branch
BranchTrueFalseTotal
if ($x > $y) { } 1 2 3
359 1 return num2en_ordinal($y - 1) . ' cousin ' . times_str($x - $y) . ' removed';
360 } else {
361 2 return num2en_ordinal($x - 1) . ' cousin ' . times_str($y - $x) . ' removed';
362 }
363  
364 0 return 'working on it';
365 }
366  
367 =head2 times_str
368  
369 Given an integer, this method returns a string version for use in a
370 "removed" cousin relationship, i.e. "once", "twice", "three times", etc.
371  
372 =cut
373  
374 3 ▶sub times_str {
Subroutine times_str: called CC=3 SCAR=11.0
Pod documented
375 3 my ($num) = @_;
376  
377 3 ▶ return 'once' if $num == 1;
Branch: 1 branch
BranchTrueFalseTotal
if $num == 1 0 3 3
378 3 ▶ return 'twice' if $num == 2;
Branch: 1 branch
BranchTrueFalseTotal
if $num == 2 1 2 3
379  
380 2 return num2en($num) . ' times';
381 }
382  
383 =head2 get_relationship_coords
384  
385 Given two person objects, returns the "co-ordinates" of the relationship
386 between them.
387  
388 The relationship co-ordinates are a pair of integers. The first integer is
389 the number of generations between the first person and their most recent
390 common ancestor. The second integer is the number of generations between
391 the second person and their most recent common ancestor.
392  
393 When a person has two parents, the shortest path to the common ancestor
394 is used.
395  
396 =cut
397  
398 80 ▶method get_relationship_coords {
Subroutine get_relationship_coords: called CC=7 SCAR=19.5
Pod documented
399 80 my ($person1, $person2) = @_;
400  
401 # If the two people are the same person, then return (0, 0).
402 80 ▶ return (0, 0)
Branch: 1 branch
BranchTrueFalseTotal
if $person1->$identifier_field_name eq $person2->$identifier_field_name 4 76 80
403 if $person1->$identifier_field_name eq $person2->$identifier_field_name;
404  
405 76 my $map1 = $self->_ancestor_map($person1);
406 76 my $map2 = $self->_ancestor_map($person2);
407  
408 76 my ($best_i, $best_j, $best_total);
409  
410 76 for my $id (keys %$map1) {
411 276 ▶ if (exists $map2->{$id}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $map2->{$id}) 90 186 276
412 90 my $i = $map1->{$id}{distance};
413 90 my $j = $map2->{$id}{distance};
414 90 my $total = $i + $j;
415 90 ▶ if (!defined $best_total || $total < $best_total) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $best_total or $total < $best_total) 76 14 90
Condition100%3/3
not defined $best_total or $total < $best_total
l!l&&r!l&&!r
72414
MC/DC100%2/2
not defined $best_total or $total < $best_total
not defined $best_total $total < $best_total
Truth table100%3/3
not(A) or B
A= not defined $best_totalB= $total < $best_total
ABresult
1X1
011
000
416 76 $best_total = $total;
417 76 $best_i = $i;
418 76 $best_j = $j;
419 }
420 }
421 }
422  
423 76 ▶ die "Can't work out the relationship.\n" unless defined $best_total;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $best_total 4 72 76
424  
425 72 return ($best_i, $best_j);
426 }
427  
428 =head2 get_relationship_ancestors
429  
430 Given two people, returns lists of people linking those two people
431 to their most recent common ancestor.
432  
433 The return value is a reference to an array containing two array
434 references. The first referenced array contains the person1 and
435 all their ancestors up to and including the most recent common
436 ancestor. The second list does the same for person2.
437  
438 When a person has two parents, the shortest path to the common ancestor
439 is used.
440  
441 =cut
442  
443 5 ▶method get_relationship_ancestors {
Subroutine get_relationship_ancestors: called CC=2 SCAR=7.1
Pod documented
444 5 my ($person1, $person2) = @_;
445  
446 5 ▶ my $mrca = $self->most_recent_common_ancestor($person1, $person2)
Branch: 1 branch
BranchTrueFalseTotal
my $mrca = $self->most_recent_common_ancestor($person1, $person2) or die "There is no most recent common ancestor\n" 5 0 5
447 or die "There is no most recent common ancestor\n";
448  
449 return [
450 5 $self->_path_to_ancestor($person1, $mrca),
451 $self->_path_to_ancestor($person2, $mrca),
452 ];
453 }
454  
455 =head2 _path_to_ancestor
456  
457 Internal method. Given a person object and a target ancestor object, returns
458 an array reference containing the shortest path from the person to the
459 ancestor (inclusive of both endpoints). Uses breadth-first search so that
460 the shortest path is always found, even when a person has two parents.
461  
462 =cut
463  
464 10 ▶method _path_to_ancestor {
Subroutine _path_to_ancestor: called CC=6 SCAR=18.0
465 10 my ($person, $target) = @_;
466  
467 10 my $target_id = $target->$identifier_field_name;
468 10 my $person_id = $person->$identifier_field_name;
469  
470 10 ▶ return [$person] if $person_id eq $target_id;
Branch: 1 branch
BranchTrueFalseTotal
if $person_id eq $target_id 1 9 10
471  
472 # BFS to find the shortest path
473 9 my @queue = ([$person]);
474 9 my %visited = ($person_id => 1);
475  
476 9 ▶ while (@queue) {
Branch: 1 branch
BranchTrueFalseTotal
if (@queue) 14 0 14
477 14 my $path = shift @queue;
478 14 my $current = $path->[-1];
479  
480 14 for my $parent ($self->_get_parents($current)) {
481 19 my $parent_id = $parent->$identifier_field_name;
482 19 ▶ next if $visited{$parent_id}++;
Branch: 1 branch
BranchTrueFalseTotal
if $visited{$parent_id}++ 0 19 19
483  
484 19 my $new_path = [@$path, $parent];
485 19 ▶ return $new_path if $parent_id eq $target_id;
Branch: 1 branch
BranchTrueFalseTotal
if $parent_id eq $target_id 9 10 19
486 10 push @queue, $new_path;
487 }
488 }
489  
490 0 die "No path found to ancestor\n";
491 }
492  
493 =head1 AUTHOR
494  
495 Dave Cross <dave@perlhacks.com>
496  
497 =head1 SEE ALSO
498  
499 perl(1)
500  
501 =head1 COPYRIGHT AND LICENSE
502  
503 Copyright (C) 2018-2026, Magnum Solutions Ltd. All Rights Reserved.
504  
505 This script is free software; you can redistribute it and/or modify it
506 under the same terms as Perl itself.
507  
508 =cut
509  
510 6 1;
↑ Summary