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