xref: /webtrees/app/Module/RelationshipsChartModule.php (revision 4947e7089adb08f24bf1eef67994a106a8df60aa) 
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\Family;
23use Fisharebest\Webtrees\FlashMessages;
24use Fisharebest\Webtrees\FontAwesome;
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\Theme;
31use Fisharebest\Webtrees\Tree;
32use Fisharebest\Webtrees\User;
33use Illuminate\Database\Capsule\Manager as DB;
34use Illuminate\Database\Query\JoinClause;
35use Symfony\Component\HttpFoundation\RedirectResponse;
36use Symfony\Component\HttpFoundation\Request;
37use Symfony\Component\HttpFoundation\Response;
38
39/**
40 * Class RelationshipsChartModule
41 */
42class RelationshipsChartModule extends AbstractModule implements ModuleChartInterface, ModuleConfigInterface
43{
44    use ModuleChartTrait;
45    use ModuleConfigTrait;
46
47    /** It would be more correct to use PHP_INT_MAX, but this isn't friendly in URLs */
48    public const UNLIMITED_RECURSION = 99;
49
50    /** By default new trees allow unlimited recursion */
51    public const DEFAULT_RECURSION = '99';
52
53    /** By default new trees search for all relationships (not via ancestors) */
54    public const DEFAULT_ANCESTORS = '0';
55
56    /**
57     * How should this module be labelled on tabs, menus, etc.?
58     *
59     * @return string
60     */
61    public function title(): string
62    {
63        /* I18N: Name of a module/chart */
64        return I18N::translate('Relationships');
65    }
66
67    /**
68     * A sentence describing what this module does.
69     *
70     * @return string
71     */
72    public function description(): string
73    {
74        /* I18N: Description of the “RelationshipsChart” module */
75        return I18N::translate('A chart displaying relationships between two individuals.');
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     * Return a menu item for this chart - for use in individual boxes.
118     *
119     * @param Individual $individual
120     *
121     * @return Menu|null
122     */
123    public function chartBoxMenu(Individual $individual): ?Menu
124    {
125        return $this->chartMenu($individual);
126    }
127
128    /**
129     * @return Response
130     */
131    public function getAdminAction(): Response
132    {
133        $this->layout = 'layouts/administration';
134
135        return $this->viewResponse('modules/relationships-chart/config', [
136            'all_trees'         => Tree::getAll(),
137            'ancestors_options' => $this->ancestorsOptions(),
138            'default_ancestors' => self::DEFAULT_ANCESTORS,
139            'default_recursion' => self::DEFAULT_RECURSION,
140            'recursion_options' => $this->recursionConfigOptions(),
141            'title'             => I18N::translate('Chart preferences') . ' — ' . $this->title(),
142        ]);
143    }
144
145    /**
146     * @param Request $request
147     *
148     * @return RedirectResponse
149     */
150    public function postAdminAction(Request $request): RedirectResponse
151    {
152        foreach (Tree::getAll() as $tree) {
153            $recursion = $request->get('relationship-recursion-' . $tree->id(), '');
154            $ancestors = $request->get('relationship-ancestors-' . $tree->id(), '');
155
156            $tree->setPreference('RELATIONSHIP_RECURSION', $recursion);
157            $tree->setPreference('RELATIONSHIP_ANCESTORS', $ancestors);
158        }
159
160        FlashMessages::addMessage(I18N::translate('The preferences for the module “%s” have been updated.', $this->title()), 'success');
161
162        return new RedirectResponse($this->getConfigLink());
163    }
164
165    /**
166     * Possible options for the ancestors option
167     *
168     * @return string[]
169     */
170    private function ancestorsOptions(): array
171    {
172        return [
173            0 => I18N::translate('Find any relationship'),
174            1 => I18N::translate('Find relationships via ancestors'),
175        ];
176    }
177
178    /**
179     * Possible options for the recursion option
180     *
181     * @return string[]
182     */
183    private function recursionConfigOptions(): array
184    {
185        return [
186            0                         => I18N::translate('none'),
187            1                         => I18N::number(1),
188            2                         => I18N::number(2),
189            3                         => I18N::number(3),
190            self::UNLIMITED_RECURSION => I18N::translate('unlimited'),
191        ];
192    }
193
194    /**
195     * A form to request the chart parameters.
196     *
197     * @param Request $request
198     * @param Tree    $tree
199     * @param User    $user
200     *
201     * @return Response
202     */
203    public function getChartAction(Request $request, Tree $tree, User $user): Response
204    {
205        $ajax = (bool) $request->get('ajax');
206
207        $xref  = $request->get('xref', '');
208        $xref2 = $request->get('xref2', '');
209
210        $individual1 = Individual::getInstance($xref, $tree);
211        $individual2 = Individual::getInstance($xref2, $tree);
212
213        $recursion = (int) $request->get('recursion', '0');
214        $ancestors = (int) $request->get('ancestors', '0');
215
216        $ancestors_only = (int) $tree->getPreference('RELATIONSHIP_ANCESTORS', static::DEFAULT_ANCESTORS);
217        $max_recursion  = (int) $tree->getPreference('RELATIONSHIP_RECURSION', static::DEFAULT_RECURSION);
218
219        $recursion = min($recursion, $max_recursion);
220
221        if ($individual1 instanceof Individual) {
222            Auth::checkIndividualAccess($individual1);
223        }
224
225        if ($individual2 instanceof Individual) {
226            Auth::checkIndividualAccess($individual2);
227        }
228
229        Auth::checkComponentAccess($this, 'chart', $tree, $user);
230
231        if ($individual1 instanceof Individual && $individual2 instanceof Individual) {
232            if ($ajax) {
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->getFullName(), $individual2->getFullName());
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 Response
273     */
274    public function chart(Individual $individual1, Individual $individual2, int $recursion, int $ancestors): Response
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 = Theme::theme()->parameter('image-dline');
288            $diagonal2 = Theme::theme()->parameter('image-dline2');
289        } else {
290            $diagonal1 = Theme::theme()->parameter('image-dline2');
291            $diagonal2 = Theme::theme()->parameter('image-dline');
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(' . Theme::theme()->parameter('image-hline') . ') 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-end') . '</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(' . Theme::theme()
335                                        ->parameter('image-vline') . ') 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>';
336                            }
337                            $y -= 2;
338                            break;
339                        case 'fat':
340                        case 'mot':
341                        case 'par':
342                            if ($n > 2 && preg_match('/son|dau|chi/', $relationships[$n - 2])) {
343                                $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>';
344                                $x                     += 2;
345                            } else {
346                                $table[$x][$y + 1] = '<div style="background:url(' . Theme::theme()
347                                        ->parameter('image-vline') . ') 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>';
348                            }
349                            $y += 2;
350                            break;
351                    }
352                    $max_x = max($max_x, $x);
353                    $min_y = min($min_y, $y);
354                    $max_y = max($max_y, $y);
355                } else {
356                    $individual    = Individual::getInstance($xref, $tree);
357                    $table[$x][$y] = FunctionsPrint::printPedigreePerson($individual);
358                }
359            }
360            echo '<div class="wt-chart wt-relationship-chart">';
361            echo '<table style="border-collapse: collapse; margin: 20px 50px;">';
362            for ($y = $max_y; $y >= $min_y; --$y) {
363                echo '<tr>';
364                for ($x = 0; $x <= $max_x; ++$x) {
365                    echo '<td style="padding: 0;">';
366                    if (isset($table[$x][$y])) {
367                        echo $table[$x][$y];
368                    }
369                    echo '</td>';
370                }
371                echo '</tr>';
372            }
373            echo '</table>';
374            echo '</div>';
375        }
376
377        if (!$num_paths) {
378            echo '<p>', I18N::translate('No link between the two individuals could be found.'), '</p>';
379        }
380
381        $html = ob_get_clean();
382
383        return new Response($html);
384    }
385
386    /**
387     * Calculate the shortest paths - or all paths - between two individuals.
388     *
389     * @param Individual $individual1
390     * @param Individual $individual2
391     * @param int        $recursion How many levels of recursion to use
392     * @param bool       $ancestor  Restrict to relationships via a common ancestor
393     *
394     * @return string[][]
395     */
396    private function calculateRelationships(Individual $individual1, Individual $individual2, $recursion, $ancestor = false): array
397    {
398        $tree = $individual1->tree();
399
400        $rows = DB::table('link')
401            ->where('l_file', '=', $tree->id())
402            ->whereIn('l_type', ['FAMS', 'FAMC'])
403            ->select(['l_from', 'l_to'])
404            ->get();
405
406        // Optionally restrict the graph to the ancestors of the individuals.
407        if ($ancestor) {
408            $ancestors = $this->allAncestors($individual1->xref(), $individual2->xref(), $tree->id());
409            $exclude   = $this->excludeFamilies($individual1->xref(), $individual2->xref(), $tree->id());
410        } else {
411            $ancestors = [];
412            $exclude   = [];
413        }
414
415        $graph = [];
416
417        foreach ($rows as $row) {
418            if (empty($ancestors) || in_array($row->l_from, $ancestors) && !in_array($row->l_to, $exclude)) {
419                $graph[$row->l_from][$row->l_to] = 1;
420                $graph[$row->l_to][$row->l_from] = 1;
421            }
422        }
423
424        $xref1    = $individual1->xref();
425        $xref2    = $individual2->xref();
426        $dijkstra = new Dijkstra($graph);
427        $paths    = $dijkstra->shortestPaths($xref1, $xref2);
428
429        // Only process each exclusion list once;
430        $excluded = [];
431
432        $queue = [];
433        foreach ($paths as $path) {
434            // Insert the paths into the queue, with an exclusion list.
435            $queue[] = [
436                'path'    => $path,
437                'exclude' => [],
438            ];
439            // While there are un-extended paths
440            for ($next = current($queue); $next !== false; $next = next($queue)) {
441                // For each family on the path
442                for ($n = count($next['path']) - 2; $n >= 1; $n -= 2) {
443                    $exclude = $next['exclude'];
444                    if (count($exclude) >= $recursion) {
445                        continue;
446                    }
447                    $exclude[] = $next['path'][$n];
448                    sort($exclude);
449                    $tmp = implode('-', $exclude);
450                    if (in_array($tmp, $excluded)) {
451                        continue;
452                    }
453
454                    $excluded[] = $tmp;
455                    // Add any new path to the queue
456                    foreach ($dijkstra->shortestPaths($xref1, $xref2, $exclude) as $new_path) {
457                        $queue[] = [
458                            'path'    => $new_path,
459                            'exclude' => $exclude,
460                        ];
461                    }
462                }
463            }
464        }
465        // Extract the paths from the queue, removing duplicates.
466        $paths = [];
467        foreach ($queue as $next) {
468            $paths[implode('-', $next['path'])] = $next['path'];
469        }
470
471        return $paths;
472    }
473
474    /**
475     * Convert a path (list of XREFs) to an "old-style" string of relationships.
476     * Return an empty array, if privacy rules prevent us viewing any node.
477     *
478     * @param Tree     $tree
479     * @param string[] $path Alternately Individual / Family
480     *
481     * @return string[]
482     */
483    private function oldStyleRelationshipPath(Tree $tree, array $path): array
484    {
485        $spouse_codes  = [
486            'M' => 'hus',
487            'F' => 'wif',
488            'U' => 'spo',
489        ];
490        $parent_codes  = [
491            'M' => 'fat',
492            'F' => 'mot',
493            'U' => 'par',
494        ];
495        $child_codes   = [
496            'M' => 'son',
497            'F' => 'dau',
498            'U' => 'chi',
499        ];
500        $sibling_codes = [
501            'M' => 'bro',
502            'F' => 'sis',
503            'U' => 'sib',
504        ];
505        $relationships = [];
506
507        for ($i = 1, $count = count($path); $i < $count; $i += 2) {
508            $family = Family::getInstance($path[$i], $tree);
509            $prev   = Individual::getInstance($path[$i - 1], $tree);
510            $next   = Individual::getInstance($path[$i + 1], $tree);
511            if (preg_match('/\n\d (HUSB|WIFE|CHIL) @' . $prev->xref() . '@/', $family->gedcom(), $match)) {
512                $rel1 = $match[1];
513            } else {
514                return [];
515            }
516            if (preg_match('/\n\d (HUSB|WIFE|CHIL) @' . $next->xref() . '@/', $family->gedcom(), $match)) {
517                $rel2 = $match[1];
518            } else {
519                return [];
520            }
521            if (($rel1 === 'HUSB' || $rel1 === 'WIFE') && ($rel2 === 'HUSB' || $rel2 === 'WIFE')) {
522                $relationships[$i] = $spouse_codes[$next->getSex()];
523            } elseif (($rel1 === 'HUSB' || $rel1 === 'WIFE') && $rel2 === 'CHIL') {
524                $relationships[$i] = $child_codes[$next->getSex()];
525            } elseif ($rel1 === 'CHIL' && ($rel2 === 'HUSB' || $rel2 === 'WIFE')) {
526                $relationships[$i] = $parent_codes[$next->getSex()];
527            } elseif ($rel1 === 'CHIL' && $rel2 === 'CHIL') {
528                $relationships[$i] = $sibling_codes[$next->getSex()];
529            }
530        }
531
532        return $relationships;
533    }
534
535    /**
536     * Find all ancestors of a list of individuals
537     *
538     * @param string $xref1
539     * @param string $xref2
540     * @param int    $tree_id
541     *
542     * @return string[]
543     */
544    private function allAncestors($xref1, $xref2, $tree_id): array
545    {
546        $ancestors = [
547            $xref1,
548            $xref2,
549        ];
550
551        $queue = [
552            $xref1,
553            $xref2,
554        ];
555        while (!empty($queue)) {
556            $parents = DB::table('link AS l1')
557                ->join('link AS l2', function (JoinClause $join): void {
558                    $join
559                        ->on('l1.l_to', '=', 'l2.l_to')
560                        ->on('l1.l_file', '=', 'l2.l_file');
561                })
562                ->where('l1.l_file', '=', $tree_id)
563                ->where('l1.l_type', '=', 'FAMC')
564                ->where('l2.l_type', '=', 'FAMS')
565                ->whereIn('l1.l_from', $queue)
566                ->pluck('l2.l_from');
567
568            $queue = [];
569            foreach ($parents as $parent) {
570                if (!in_array($parent, $ancestors)) {
571                    $ancestors[] = $parent;
572                    $queue[]     = $parent;
573                }
574            }
575        }
576
577        return $ancestors;
578    }
579
580    /**
581     * Find all families of two individuals
582     *
583     * @param string $xref1
584     * @param string $xref2
585     * @param int    $tree_id
586     *
587     * @return string[]
588     */
589    private function excludeFamilies($xref1, $xref2, $tree_id): array
590    {
591        return DB::table('link AS l1')
592            ->join('link AS l2', function (JoinClause $join): void {
593                $join
594                    ->on('l1.l_to', '=', 'l2.l_to')
595                    ->on('l1.l_type', '=', 'l2.l_type')
596                    ->on('l1.l_file', '=', 'l2.l_file');
597            })
598            ->where('l1.l_file', '=', $tree_id)
599            ->where('l1.l_type', '=', 'FAMS')
600            ->where('l1.l_from', '=', $xref1)
601            ->where('l2.l_from', '=', $xref2)
602            ->pluck('l1.l_to')
603            ->all();
604    }
605
606    /**
607     * Possible options for the recursion option
608     *
609     * @param int $max_recursion
610     *
611     * @return array
612     */
613    private function recursionOptions(int $max_recursion): array
614    {
615        if ($max_recursion === static::UNLIMITED_RECURSION) {
616            $text = I18N::translate('Find all possible relationships');
617        } else {
618            $text = I18N::translate('Find other relationships');
619        }
620
621        return [
622            '0'            => I18N::translate('Find the closest relationships'),
623            $max_recursion => $text,
624        ];
625    }
626}
627