xref: /webtrees/app/Module/RelationshipsChartModule.php (revision 8365f91036c0357ecd08abcae52682cc3b682160) 
1<?php
2/**
3 * webtrees: online genealogy
4 * Copyright (C) 2019 webtrees development team
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 * You should have received a copy of the GNU General Public License
14 * along with this program. If not, see <http://www.gnu.org/licenses/>.
15 */
16declare(strict_types=1);
17
18namespace Fisharebest\Webtrees\Module;
19
20use Closure;
21use Fisharebest\Algorithm\Dijkstra;
22use Fisharebest\Webtrees\Auth;
23use Fisharebest\Webtrees\Contracts\UserInterface;
24use Fisharebest\Webtrees\Family;
25use Fisharebest\Webtrees\FlashMessages;
26use Fisharebest\Webtrees\Functions\Functions;
27use Fisharebest\Webtrees\I18N;
28use Fisharebest\Webtrees\Individual;
29use Fisharebest\Webtrees\Menu;
30use Fisharebest\Webtrees\Tree;
31use Illuminate\Database\Capsule\Manager as DB;
32use Illuminate\Database\Query\JoinClause;
33use Psr\Http\Message\ResponseInterface;
34use Psr\Http\Message\ServerRequestInterface;
35use function view;
36
37/**
38 * Class RelationshipsChartModule
39 */
40class RelationshipsChartModule extends AbstractModule implements ModuleChartInterface, ModuleConfigInterface
41{
42    use ModuleChartTrait;
43    use ModuleConfigTrait;
44
45    /** It would be more correct to use PHP_INT_MAX, but this isn't friendly in URLs */
46    public const UNLIMITED_RECURSION = 99;
47
48    /** By default new trees allow unlimited recursion */
49    public const DEFAULT_RECURSION = '99';
50
51    /** By default new trees search for all relationships (not via ancestors) */
52    public const DEFAULT_ANCESTORS = '0';
53
54    /**
55     * A sentence describing what this module does.
56     *
57     * @return string
58     */
59    public function description(): string
60    {
61        /* I18N: Description of the “RelationshipsChart” module */
62        return I18N::translate('A chart displaying relationships between two individuals.');
63    }
64
65    /**
66     * Return a menu item for this chart - for use in individual boxes.
67     *
68     * @param Individual $individual
69     *
70     * @return Menu|null
71     */
72    public function chartBoxMenu(Individual $individual): ?Menu
73    {
74        return $this->chartMenu($individual);
75    }
76
77    /**
78     * A main menu item for this chart.
79     *
80     * @param Individual $individual
81     *
82     * @return Menu
83     */
84    public function chartMenu(Individual $individual): Menu
85    {
86        $gedcomid = $individual->tree()->getUserPreference(Auth::user(), 'gedcomid');
87
88        if ($gedcomid !== '' && $gedcomid !== $individual->xref()) {
89            return new Menu(
90                I18N::translate('Relationship to me'),
91                $this->chartUrl($individual, ['xref2' => $gedcomid]),
92                $this->chartMenuClass(),
93                $this->chartUrlAttributes()
94            );
95        }
96
97        return new Menu(
98            $this->title(),
99            $this->chartUrl($individual),
100            $this->chartMenuClass(),
101            $this->chartUrlAttributes()
102        );
103    }
104
105    /**
106     * CSS class for the URL.
107     *
108     * @return string
109     */
110    public function chartMenuClass(): string
111    {
112        return 'menu-chart-relationship';
113    }
114
115    /**
116     * How should this module be identified in the control panel, etc.?
117     *
118     * @return string
119     */
120    public function title(): string
121    {
122        /* I18N: Name of a module/chart */
123        return I18N::translate('Relationships');
124    }
125
126    /**
127     * @return ResponseInterface
128     */
129    public function getAdminAction(): ResponseInterface
130    {
131        $this->layout = 'layouts/administration';
132
133        return $this->viewResponse('modules/relationships-chart/config', [
134            'all_trees'         => Tree::getAll(),
135            'ancestors_options' => $this->ancestorsOptions(),
136            'default_ancestors' => self::DEFAULT_ANCESTORS,
137            'default_recursion' => self::DEFAULT_RECURSION,
138            'recursion_options' => $this->recursionConfigOptions(),
139            'title'             => I18N::translate('Chart preferences') . ' — ' . $this->title(),
140        ]);
141    }
142
143    /**
144     * Possible options for the ancestors option
145     *
146     * @return string[]
147     */
148    private function ancestorsOptions(): array
149    {
150        return [
151            0 => I18N::translate('Find any relationship'),
152            1 => I18N::translate('Find relationships via ancestors'),
153        ];
154    }
155
156    /**
157     * Possible options for the recursion option
158     *
159     * @return string[]
160     */
161    private function recursionConfigOptions(): array
162    {
163        return [
164            0                         => I18N::translate('none'),
165            1                         => I18N::number(1),
166            2                         => I18N::number(2),
167            3                         => I18N::number(3),
168            self::UNLIMITED_RECURSION => I18N::translate('unlimited'),
169        ];
170    }
171
172    /**
173     * @param ServerRequestInterface $request
174     *
175     * @return ResponseInterface
176     */
177    public function postAdminAction(ServerRequestInterface $request): ResponseInterface
178    {
179        foreach (Tree::getAll() as $tree) {
180            $recursion = $request->getParsedBody()['relationship-recursion-' . $tree->id()] ?? '';
181            $ancestors = $request->getParsedBody()['relationship-ancestors-' . $tree->id()] ?? '';
182
183            $tree->setPreference('RELATIONSHIP_RECURSION', $recursion);
184            $tree->setPreference('RELATIONSHIP_ANCESTORS', $ancestors);
185        }
186
187        FlashMessages::addMessage(I18N::translate('The preferences for the module “%s” have been updated.', $this->title()), 'success');
188
189        return redirect($this->getConfigLink());
190    }
191
192    /**
193     * A form to request the chart parameters.
194     *
195     * @param ServerRequestInterface $request
196     * @param Tree                   $tree
197     * @param UserInterface          $user
198     *
199     * @return ResponseInterface
200     */
201    public function getChartAction(ServerRequestInterface $request, Tree $tree, UserInterface $user): ResponseInterface
202    {
203        $ajax = $request->getQueryParams()['ajax'] ?? '';
204
205        $xref  = $request->getQueryParams()['xref'] ?? '';
206        $xref2 = $request->getQueryParams()['xref2'] ?? '';
207
208        $individual1 = Individual::getInstance($xref, $tree);
209        $individual2 = Individual::getInstance($xref2, $tree);
210
211        $recursion = (int) ($request->getQueryParams()['recursion'] ?? 0);
212        $ancestors = (int) ($request->getQueryParams()['ancestors'] ?? 0);
213
214        $ancestors_only = (int) $tree->getPreference('RELATIONSHIP_ANCESTORS', static::DEFAULT_ANCESTORS);
215        $max_recursion  = (int) $tree->getPreference('RELATIONSHIP_RECURSION', static::DEFAULT_RECURSION);
216
217        $recursion = min($recursion, $max_recursion);
218
219        if ($tree->getPreference('SHOW_PRIVATE_RELATIONSHIPS') !== '1') {
220            if ($individual1 instanceof Individual) {
221                Auth::checkIndividualAccess($individual1);
222            }
223
224            if ($individual2 instanceof Individual) {
225                Auth::checkIndividualAccess($individual2);
226            }
227        }
228
229        Auth::checkComponentAccess($this, 'chart', $tree, $user);
230
231        if ($individual1 instanceof Individual && $individual2 instanceof Individual) {
232            if ($ajax === '1') {
233                return $this->chart($individual1, $individual2, $recursion, $ancestors);
234            }
235
236            /* I18N: %s are individual’s names */
237            $title = I18N::translate('Relationships between %1$s and %2$s', $individual1->fullName(), $individual2->fullName());
238
239            $ajax_url = $this->chartUrl($individual1, [
240                'ajax'      => true,
241                'xref2'     => $individual2->xref(),
242                'recursion' => $recursion,
243                'ancestors' => $ancestors,
244            ]);
245        } else {
246            $title = I18N::translate('Relationships');
247
248            $ajax_url = '';
249        }
250
251        return $this->viewResponse('modules/relationships-chart/page', [
252            'ajax_url'          => $ajax_url,
253            'ancestors'         => $ancestors,
254            'ancestors_only'    => $ancestors_only,
255            'ancestors_options' => $this->ancestorsOptions(),
256            'individual1'       => $individual1,
257            'individual2'       => $individual2,
258            'max_recursion'     => $max_recursion,
259            'module_name'       => $this->name(),
260            'recursion'         => $recursion,
261            'recursion_options' => $this->recursionOptions($max_recursion),
262            'title'             => $title,
263        ]);
264    }
265
266    /**
267     * @param Individual $individual1
268     * @param Individual $individual2
269     * @param int        $recursion
270     * @param int        $ancestors
271     *
272     * @return ResponseInterface
273     */
274    public function chart(Individual $individual1, Individual $individual2, int $recursion, int $ancestors): ResponseInterface
275    {
276        $tree = $individual1->tree();
277
278        $max_recursion = (int) $tree->getPreference('RELATIONSHIP_RECURSION', static::DEFAULT_RECURSION);
279
280        $recursion = min($recursion, $max_recursion);
281
282        $paths = $this->calculateRelationships($individual1, $individual2, $recursion, (bool) $ancestors);
283
284        // @TODO - convert to views
285        ob_start();
286        if (I18N::direction() === 'ltr') {
287            $diagonal1 = asset('css/images/dline.png');
288            $diagonal2 = asset('css/images/dline2.png');
289        } else {
290            $diagonal1 = asset('css/images/dline2.png');
291            $diagonal2 = asset('css/images/dline.png');
292        }
293
294        $num_paths = 0;
295        foreach ($paths as $path) {
296            // Extract the relationship names between pairs of individuals
297            $relationships = $this->oldStyleRelationshipPath($tree, $path);
298            if (empty($relationships)) {
299                // Cannot see one of the families/individuals, due to privacy;
300                continue;
301            }
302            echo '<h3>', I18N::translate('Relationship: %s', Functions::getRelationshipNameFromPath(implode('', $relationships), $individual1, $individual2)), '</h3>';
303            $num_paths++;
304
305            // Use a table/grid for layout.
306            $table = [];
307            // Current position in the grid.
308            $x = 0;
309            $y = 0;
310            // Extent of the grid.
311            $min_y = 0;
312            $max_y = 0;
313            $max_x = 0;
314            // For each node in the path.
315            foreach ($path as $n => $xref) {
316                if ($n % 2 === 1) {
317                    switch ($relationships[$n]) {
318                        case 'hus':
319                        case 'wif':
320                        case 'spo':
321                        case 'bro':
322                        case 'sis':
323                        case 'sib':
324                            $table[$x + 1][$y] = '<div style="background:url(' . e(asset('css/images/hline.png')) . ') repeat-x center;  width: 94px; text-align: center"><div class="hline-text" style="height: 32px;">' . Functions::getRelationshipNameFromPath($relationships[$n], Individual::getInstance($path[$n - 1], $tree), Individual::getInstance($path[$n + 1], $tree)) . '</div><div style="height: 32px;">' . view('icons/arrow-right') . '</div></div>';
325                            $x                 += 2;
326                            break;
327                        case 'son':
328                        case 'dau':
329                        case 'chi':
330                            if ($n > 2 && preg_match('/fat|mot|par/', $relationships[$n - 2])) {
331                                $table[$x + 1][$y - 1] = '<div style="background:url(' . $diagonal2 . '); width: 64px; height: 64px; text-align: center;"><div style="height: 32px; text-align: end;">' . Functions::getRelationshipNameFromPath($relationships[$n], Individual::getInstance($path[$n - 1], $tree), Individual::getInstance($path[$n + 1], $tree)) . '</div><div style="height: 32px; text-align: start;">' . view('icons/arrow-down') . '</div></div>';
332                                $x                     += 2;
333                            } else {
334                                $table[$x][$y - 1] = '<div style="background:url(' . e('"' . asset('css/images/vline.png') . '"') . ') repeat-y center; height: 64px; text-align: center;"><div class="vline-text" style="display: inline-block; width:50%; line-height: 64px;">' . Functions::getRelationshipNameFromPath($relationships[$n], Individual::getInstance($path[$n - 1], $tree), Individual::getInstance($path[$n + 1], $tree)) . '</div><div style="display: inline-block; width:50%; line-height: 64px;">' . view('icons/arrow-down') . '</div></div>';
335                            }
336                            $y -= 2;
337                            break;
338                        case 'fat':
339                        case 'mot':
340                        case 'par':
341                            if ($n > 2 && preg_match('/son|dau|chi/', $relationships[$n - 2])) {
342                                $table[$x + 1][$y + 1] = '<div style="background:url(' . $diagonal1 . '); background-position: top right; width: 64px; height: 64px; text-align: center;"><div style="height: 32px; text-align: start;">' . Functions::getRelationshipNameFromPath($relationships[$n], Individual::getInstance($path[$n - 1], $tree), Individual::getInstance($path[$n + 1], $tree)) . '</div><div style="height: 32px; text-align: end;">' . view('icons/arrow-down') . '</div></div>';
343                                $x                     += 2;
344                            } else {
345                                $table[$x][$y + 1] = '<div style="background:url(' . e('"' . asset('css/images/vline.png') . '"') . ') repeat-y center; height: 64px; text-align:center; "><div class="vline-text" style="display: inline-block; width: 50%; line-height: 64px;">' . Functions::getRelationshipNameFromPath($relationships[$n], Individual::getInstance($path[$n - 1], $tree), Individual::getInstance($path[$n + 1], $tree)) . '</div><div style="display: inline-block; width: 50%; line-height: 32px">' . view('icons/arrow-up') . '</div></div>';
346                            }
347                            $y += 2;
348                            break;
349                    }
350                    $max_x = max($max_x, $x);
351                    $min_y = min($min_y, $y);
352                    $max_y = max($max_y, $y);
353                } else {
354                    $individual    = Individual::getInstance($xref, $tree);
355                    $table[$x][$y] = view('chart-box', ['individual' => $individual]);
356                }
357            }
358            echo '<div class="wt-chart wt-chart-relationships">';
359            echo '<table style="border-collapse: collapse; margin: 20px 50px;">';
360            for ($y = $max_y; $y >= $min_y; --$y) {
361                echo '<tr>';
362                for ($x = 0; $x <= $max_x; ++$x) {
363                    echo '<td style="padding: 0;">';
364                    if (isset($table[$x][$y])) {
365                        echo $table[$x][$y];
366                    }
367                    echo '</td>';
368                }
369                echo '</tr>';
370            }
371            echo '</table>';
372            echo '</div>';
373        }
374
375        if (!$num_paths) {
376            echo '<p>', I18N::translate('No link between the two individuals could be found.'), '</p>';
377        }
378
379        $html = ob_get_clean();
380
381        return response($html);
382    }
383
384    /**
385     * Calculate the shortest paths - or all paths - between two individuals.
386     *
387     * @param Individual $individual1
388     * @param Individual $individual2
389     * @param int        $recursion How many levels of recursion to use
390     * @param bool       $ancestor  Restrict to relationships via a common ancestor
391     *
392     * @return string[][]
393     */
394    private function calculateRelationships(Individual $individual1, Individual $individual2, $recursion, $ancestor = false): array
395    {
396        $tree = $individual1->tree();
397
398        $rows = DB::table('link')
399            ->where('l_file', '=', $tree->id())
400            ->whereIn('l_type', ['FAMS', 'FAMC'])
401            ->select(['l_from', 'l_to'])
402            ->get();
403
404        // Optionally restrict the graph to the ancestors of the individuals.
405        if ($ancestor) {
406            $ancestors = $this->allAncestors($individual1->xref(), $individual2->xref(), $tree->id());
407            $exclude   = $this->excludeFamilies($individual1->xref(), $individual2->xref(), $tree->id());
408        } else {
409            $ancestors = [];
410            $exclude   = [];
411        }
412
413        $graph = [];
414
415        foreach ($rows as $row) {
416            if (empty($ancestors) || in_array($row->l_from, $ancestors, true) && !in_array($row->l_to, $exclude, true)) {
417                $graph[$row->l_from][$row->l_to] = 1;
418                $graph[$row->l_to][$row->l_from] = 1;
419            }
420        }
421
422        $xref1    = $individual1->xref();
423        $xref2    = $individual2->xref();
424        $dijkstra = new Dijkstra($graph);
425        $paths    = $dijkstra->shortestPaths($xref1, $xref2);
426
427        // Only process each exclusion list once;
428        $excluded = [];
429
430        $queue = [];
431        foreach ($paths as $path) {
432            // Insert the paths into the queue, with an exclusion list.
433            $queue[] = [
434                'path'    => $path,
435                'exclude' => [],
436            ];
437            // While there are un-extended paths
438            for ($next = current($queue); $next !== false; $next = next($queue)) {
439                // For each family on the path
440                for ($n = count($next['path']) - 2; $n >= 1; $n -= 2) {
441                    $exclude = $next['exclude'];
442                    if (count($exclude) >= $recursion) {
443                        continue;
444                    }
445                    $exclude[] = $next['path'][$n];
446                    sort($exclude);
447                    $tmp = implode('-', $exclude);
448                    if (in_array($tmp, $excluded, true)) {
449                        continue;
450                    }
451
452                    $excluded[] = $tmp;
453                    // Add any new path to the queue
454                    foreach ($dijkstra->shortestPaths($xref1, $xref2, $exclude) as $new_path) {
455                        $queue[] = [
456                            'path'    => $new_path,
457                            'exclude' => $exclude,
458                        ];
459                    }
460                }
461            }
462        }
463        // Extract the paths from the queue.
464        $paths = [];
465        foreach ($queue as $next) {
466            // The Dijkstra library does not use strict types, and converts
467            // numeric array keys (XREFs) from strings to integers;
468            $path = array_map($this->stringMapper(), $next['path']);
469
470            // Remove duplicates
471            $paths[implode('-', $next['path'])] = $path;
472        }
473
474        return $paths;
475    }
476
477    /**
478     * Convert numeric values to strings
479     *
480     * @return Closure
481     */
482    private function stringMapper(): Closure
483    {
484        return static function ($xref) {
485            return (string) $xref;
486        };
487    }
488
489    /**
490     * Find all ancestors of a list of individuals
491     *
492     * @param string $xref1
493     * @param string $xref2
494     * @param int    $tree_id
495     *
496     * @return string[]
497     */
498    private function allAncestors($xref1, $xref2, $tree_id): array
499    {
500        $ancestors = [
501            $xref1,
502            $xref2,
503        ];
504
505        $queue = [
506            $xref1,
507            $xref2,
508        ];
509        while (!empty($queue)) {
510            $parents = DB::table('link AS l1')
511                ->join('link AS l2', static function (JoinClause $join): void {
512                    $join
513                        ->on('l1.l_to', '=', 'l2.l_to')
514                        ->on('l1.l_file', '=', 'l2.l_file');
515                })
516                ->where('l1.l_file', '=', $tree_id)
517                ->where('l1.l_type', '=', 'FAMC')
518                ->where('l2.l_type', '=', 'FAMS')
519                ->whereIn('l1.l_from', $queue)
520                ->pluck('l2.l_from');
521
522            $queue = [];
523            foreach ($parents as $parent) {
524                if (!in_array($parent, $ancestors, true)) {
525                    $ancestors[] = $parent;
526                    $queue[]     = $parent;
527                }
528            }
529        }
530
531        return $ancestors;
532    }
533
534    /**
535     * Find all families of two individuals
536     *
537     * @param string $xref1
538     * @param string $xref2
539     * @param int    $tree_id
540     *
541     * @return string[]
542     */
543    private function excludeFamilies($xref1, $xref2, $tree_id): array
544    {
545        return DB::table('link AS l1')
546            ->join('link AS l2', static function (JoinClause $join): void {
547                $join
548                    ->on('l1.l_to', '=', 'l2.l_to')
549                    ->on('l1.l_type', '=', 'l2.l_type')
550                    ->on('l1.l_file', '=', 'l2.l_file');
551            })
552            ->where('l1.l_file', '=', $tree_id)
553            ->where('l1.l_type', '=', 'FAMS')
554            ->where('l1.l_from', '=', $xref1)
555            ->where('l2.l_from', '=', $xref2)
556            ->pluck('l1.l_to')
557            ->all();
558    }
559
560    /**
561     * Convert a path (list of XREFs) to an "old-style" string of relationships.
562     * Return an empty array, if privacy rules prevent us viewing any node.
563     *
564     * @param Tree     $tree
565     * @param string[] $path Alternately Individual / Family
566     *
567     * @return string[]
568     */
569    private function oldStyleRelationshipPath(Tree $tree, array $path): array
570    {
571        $spouse_codes  = [
572            'M' => 'hus',
573            'F' => 'wif',
574            'U' => 'spo',
575        ];
576        $parent_codes  = [
577            'M' => 'fat',
578            'F' => 'mot',
579            'U' => 'par',
580        ];
581        $child_codes   = [
582            'M' => 'son',
583            'F' => 'dau',
584            'U' => 'chi',
585        ];
586        $sibling_codes = [
587            'M' => 'bro',
588            'F' => 'sis',
589            'U' => 'sib',
590        ];
591        $relationships = [];
592
593        for ($i = 1, $count = count($path); $i < $count; $i += 2) {
594            $family = Family::getInstance($path[$i], $tree);
595            $prev   = Individual::getInstance($path[$i - 1], $tree);
596            $next   = Individual::getInstance($path[$i + 1], $tree);
597            if (preg_match('/\n\d (HUSB|WIFE|CHIL) @' . $prev->xref() . '@/', $family->gedcom(), $match)) {
598                $rel1 = $match[1];
599            } else {
600                return [];
601            }
602            if (preg_match('/\n\d (HUSB|WIFE|CHIL) @' . $next->xref() . '@/', $family->gedcom(), $match)) {
603                $rel2 = $match[1];
604            } else {
605                return [];
606            }
607            if (($rel1 === 'HUSB' || $rel1 === 'WIFE') && ($rel2 === 'HUSB' || $rel2 === 'WIFE')) {
608                $relationships[$i] = $spouse_codes[$next->sex()];
609            } elseif (($rel1 === 'HUSB' || $rel1 === 'WIFE') && $rel2 === 'CHIL') {
610                $relationships[$i] = $child_codes[$next->sex()];
611            } elseif ($rel1 === 'CHIL' && ($rel2 === 'HUSB' || $rel2 === 'WIFE')) {
612                $relationships[$i] = $parent_codes[$next->sex()];
613            } elseif ($rel1 === 'CHIL' && $rel2 === 'CHIL') {
614                $relationships[$i] = $sibling_codes[$next->sex()];
615            }
616        }
617
618        return $relationships;
619    }
620
621    /**
622     * Possible options for the recursion option
623     *
624     * @param int $max_recursion
625     *
626     * @return string[]
627     */
628    private function recursionOptions(int $max_recursion): array
629    {
630        if ($max_recursion === static::UNLIMITED_RECURSION) {
631            $text = I18N::translate('Find all possible relationships');
632        } else {
633            $text = I18N::translate('Find other relationships');
634        }
635
636        return [
637            '0'            => I18N::translate('Find the closest relationships'),
638            $max_recursion => $text,
639        ];
640    }
641}
642