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