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