Relationship Route Calculation

[Jan_B_Hansson 0]

Hi, this is my first post to this community. In these Corona times, it's good to have a winter project to work on, so I just want to share my planned project about missing Relationship Rute Calculation for non-blod rutes, that also can be used in Labelling Branches.

The task:
My genealogy database consists of well over 26000 people and I have a rule that all people must be able to connect to me and they must be arranged in 5 branches labelled according to connecting to me by passing through  one of grandparents or my wife (FF, FM, MF, MM, WF). My branches can be seen on my website:

https://xuri.dk/Genealogy/index.php

Solution idea / method:
When Google Maps has shortests route calculation that can quickly give the shortest route between 2 places, then it is the same solution I will focus on to check if each one in the genealogy database can be connected to me to comply with my rule of no islands, as well as by finding which shortest route that arrives to me, which of my 4 grandparents or wife was passed decides the branch group the person belongs to.

Solution recipe:
Build a network model where Google Map's cities are replaced by my 26000 people and connecting paths (roads) between cities are replaced by each person's family relationships. My original genealogy database, where all updates take place is offline on PC in the program Legacy 9 which has a build-in function to determine if a connection can be created between 2 random people and which people are part of the connection (not only directly related - I miss this in TNG's relationships solution). By the help of DBeaver application I have found out to take a snapshot of Legacy's MSAccess database and place it in MariaDB (works like MySQL) which is my TNG database, so I can make a (graph) table on MariaDB to build the network model. In order not to start from Adam and Eve every time, I have searched the internet to find PHP code that performs the shortest route calculations on the network model - a well and extensively described solution I have found here:

https://www.sitepoint.com/data-structures-4/

Here is how TNG Relationship Calculation could become in the future:

https://news.legacyfamilytree.com/legacy_news/2018/05/tuesdays-tip-the-relationship-calculator-beginner.html

So what do you think of the ideas ?

/ Jan

 

[XerxX 0]

Hi Jan,

Have you had a look at Chris Moss' Relate mod?

https://tng.lythgoes.net/wiki/index.php?title=Relate_mod

It's - in my opinion - an excellent "calculator" to find the shortest route, no matter how complex, between two persons including in-laws, step-children and such OR only genetics; you select.

This is the name of the algorithm (from the ajax script):

Quote

*  Description of the bidirectional breadth-first algorithm:

 

It is originally only giving a text description of the path, on the getperson.php page; for example here is my relation to king Gustav I Vasa of Sweden:

Quote

Erik* Enar Hoppe Hoppe is the grandson of Skomakarmästare Enar* Eugen Andersson, who is the cousin of Emmy Marta Sofia Andersson, who is the sister-in-law of Ingenjör Hans Henning Baltzar Frithiofsson Broms.
He is the great grandson of Jean Johan Magnus Phalén, who is the stepson of Erik Ericus Knoop, who is the grandson of Anna Maria Andersdotter.
She is the stepdaughter of Kyrkoherde Olaus Simonis Clarevallensis, who is the son-in-law of Konung Erik XIV Vasa, who is the son of Konung Gustav I Vasa.

I have made a private mod from it, to replace TNG's original because it couldn't - at least at the time - find the above relationship. It stalled. I don't display spouses, though. The graphics for the above path is:

It's also very quick: The above took less than four seconds to calculate and display - the database contains 40,000 people. (The calculation at this site is for members only)

You can get a feeling for the use of it at my (Swedish only!) smaller site (720 persons) here:

https://botebygden.se/relateform.php?primaryID=I437&tree=bote

Enter i253 for Person 2, select Alla sorters relationer (all kinds of relations) and click Beräkna.

(This is a "community research site" and therefore contains lots of un-related branches - people that are not related at all.)

 

Just a small friendly tip to check it, as I really like the speed and ability of the mod. And it may save you lots of work..?

Best regards,

Erik

 

[tngrlkrz 0]

Hi Jan,  That would be a fascinating undertaking and would certainly interested in project results.  I have Legacy 9, and have always liked the 'set relationships' feature.  But now my primary Genealogy software is Family Historian, though I still backfill to Legacy 9 (or 7) at times, rather than exporting from it.  Family Historian also is able to nearly instantly set and switch relationships to a given person throughout my 14,000 person database.  I so wish TNG would similarly store, or obtain relationships across the database.  I have asked before how PC software can do so quickly what TNG cannot.  

BTW..agree with Erik about Chris's Relate mod..blazingly fast but sometimes the description requires considerable thought to ferret through the relationship to the end person.

Hope you have success in the endeavor.

 

 

[mjaro 0]

Hi all,

I went a step further and implemented an algorithm searching for not only the shortest path but also next shortest and next... as many as you want. The results look like below.

I have a private mod that integrates the script into TNG. The search is initiated from the standard form:

The implementation is incredibly fast: for my 30k people database, finding first 100 paths takes 1-2 seconds. It is based on "Yen's K-Shortest Path algorithm" modified by me and coded in PHP.

If there is anybody interested in these scripts I''d be happy sharing them for use. I'm also ready for discussion on possible improvements.

Best regards

Michal

[tngrlkrz 0]

Hi Michal,

Sure, thanks for offering to share.  Could you PM them to me?  Would be fascinating to experiment with it.

[Jan_B_Hansson 0]

Thanks Erik, Ron and Michael
- for your good answer. How nice that it seems that my project has already been done by others. I have some follow-up questions for you:

Erik (+ Chris) and Michael: is your solution compatible with TNG 13.0.2?

Erik (+ Chris): The search is a bidirectional breadth-first search it says in the MOD description and this fast (bidirectional) breadth-first version was the algorithm I had chosen to take a look at. The algorithm Google uses can give weights to edges (paths / routes) to prefer fast highways instead of slow side roads, I can not use of in my project. Is it correct that in your application can jump between siblings instead of as in Legacy having to go around one of the parents?

Erik (+ Chris), Ron and Michael: The result of the route calculation as family relations in text requires the large driving license to understand. The people listed and shown on the diagram are much easier to see - is it generations you have on the y-axis?

Michael: Your solution is based on modified "Yen's K-Shortest Path algorithm" which can also calculate alternative routes. I would very much like to try that solution also.

Erik: Did you remove Chris' route calculation presentation and make your own presentation?

Erik, Ron and Michael: To improve TNG's presentation, I'm working to replace TNG's no-photo solution with one based on Legacy tags to distinguish between no-photo for Ancestor, Ancestor Family and All Others - can be extended to also signal Branch with colors (does not yet work everywhere as TNG has the code 3 places) - my first test can be seen here
https://xuri.dk/Genealogy/familychart.php?personID=I4709&tree=TheHanssonTribe

/ Jan

[mjaro 0]

Jan,

some answers/explanations on my solution:

It is 13.0.2 compatible.

I use BiBFS as the shortest-path algorithm which is internal to YenKSP (it could be any shortest-path, but it is ran multiple times per one "next path" and thus its performance is critical). Btw I don't go directly between siblings (it could be changed quite easily) - I decided rather to follow the "Roman kinship degree calculations".

Yes - generations are reflected on the Y-axis.

I'm working on the public version of my private mod; I hope Ron can help me.

I currently use a very simple method of graphical path presenting based on a pure html table. I consider using a more standard TNG method, the weakness is its bad scaling. Anyway, the color coding of Branches could be included.

Chris Moss' Relate mod is a great solution, I used to use it very intensively, and also attempted to add the graphics to it. Eventually I used some of his ideas: BiBFS, creating relationship string for every path ... (In fact, I learned programming by analyzing his code. Thanks, Chris!). 

Michal

[XerxX 0]

Hi Jan,

First I have to say, that I was translating Chris' mod to Swedish, with all its pecularities, when he wrote it. This was several years ago and I immediately made my own version to replace TNG's Relationship tab - as I said above; it stalled at times. I have forgot some things about his mod since then...

Compatibility w/ TNG 13.0.2: I'm not sure as I haven't tried yet. I suspect it is, as it uses very little TNG code. Can try later. I use it in TNG 12.3 (the link in my post above).

Jump to siblings: If I understand you correct; it does in the verbal description but in my example above, I have only "...who is the cousin of Emmy Marta Sofia Andersson..." which I think is a bit of the same..? Chris' version (and therefore mine as well) has all "shortcuts" like "fourth cousin twice removed" (or how it's noted) and "4 X great grandfather" in English. It also works in Swedish where we use "3-männing", "4-männing" etc for children of cousins and their children...
I guess (correctly?) that you at least have a grasp of Swedish so you can check the link I gave above: There are both the "shortcut" and the "person-to-person" text versions (and I think I remember both are available in Chris' mod also).

Generations: Yes; parents and children are up/down, siblings and spouses are going right.

Removed Chris' presentation? I don't really understand this question... But No; I don't think so. I simply moved it from getperson.php to my version of relateform.php and then I use it to generate the graphics and I also display both the "shortcut" and the "person-to-person" in text. If you try his version and compare to the link I gave above, you'll find what's similar and not.

BTW: Under certain circumstances Chris' (and my) version give one or two alternative routes extra. Both versions only in text - not graphics. And I don't remember when or why it does that, but it does

I hope you got answers to all your questions.

And sure: If you want to test my version of Chris' mod, just PM me. I will not make it public, though, as I may not be able to maintain it properly.

Best regards,

Erik

[mjaro 0]

Erik (and Jan),

referring to Erik's "BTW" note about extra routes: 

BiBFS idea is to start from both ends (i.e. persons of concern) and every "search cycle" to mark neighbors of the people already marked. If there is a person found that has already been marked from the opposite side, the search is concluded as the path is found. In the Chris' implementation there is always a full cycle done before the "found" check. Thus this is not unusual that the both searches to meet in multiple persons. All the paths going through these persons are of equal length.

Michal

[Jan_B_Hansson 0]

Erik & Michael

Installed the relate_11.0.0.2a MOD and tested it on a relationship rute between Niels Bohr and I and the mod handled it but TNG failed - Legacy can find a rute so I will send you both a PM to test if your solutions can do the job.

/ Jan 

Edited February 7 by Jan_B_Hansson
It was TNG that failed not the MOD

[fluffy82 0]

I didn't read through everything (yet) but I just wanted to throw in an issue that you might want to watch out for: the shortest path is not necessarily the most direct path.

By that I mean that for example, the shortest path for a person might be 1st cousin 6x removed, while in reality that person is also the 8th great-grandfather through a different line. Family Tree Maker also gives the shourtest route to the home person, and I have several "father-in-law of the sister of your great-grandfather" while it should be "great-granduncle" or something. Just because the "roundabout" route is one or two steps shorter than the - different - direct route.

[mjaro 0]

4 minutes ago, fluffy82 said:

the shortest path is not necessarily the most direct path.

Yes! This was the main reason why my project was created! 

I love discovering complicated and multiple relationships between families.

[Jan_B_Hansson 0]

Maybe I was to quick "The algorithm Google uses can give weights to edges (paths / routes) to prefer fast highways instead of slow side roads, I can not use of in my project." - it start to looks like that there are routes you prefere to others - can it be solved with weights like highways better than side roads to select the solution that has the most value ?

(Sorry - all the places where I wrote rute i should have been route)

/ Jan

[XerxX 0]

Jan, the way I see it, a parent/child ("blood") connection is more valuable/interesting than others ("non-blood") in an "all kinds of relations" query.

If there is also a shorter route using "non-blood" relations, both routes could be shown if possible.

Just my $0.02

Erik