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