8

I have a Gramps database that probably has an ancestral loop, i.e. a person who is his or her own ancestor. I say that, because the program freezes when I try to find a path between that person and me.

Since Gramps' built-in analysis tools can't find anything wrong, and PAF and RM don't detect this type of error either, I'm looking for an external tool on Linux, Windows, or on-line.

If you answer my question, please refer to a tool that you actually use yourself.

6
  • 2
    Hi Enno, Of course, you are free to specify the types of resources you prefere, I'd just like to point out that Cyndi Howells of Cyndi's List is a real person and published author. Therefore, her site is "a live author's web-site." I think she works really hard to weed out dead links and keep it maintained. In my personal experience, I've discovered relevant information on her site that I wasn't aware of before. May 11, 2013 at 16:55
  • 1
    Welcome to Genealogy.SE! I've edited your question to remove the signature. Because your posts are always automatically pre-signed, there's no use resigning them. :)
    – Luke_0
    May 11, 2013 at 21:03
  • You may have intentionally left out a gramps tag but I have added it in because other Gramps users may face (or have already faced and resolved) the same issue.
    – PolyGeo
    May 12, 2013 at 1:54
  • Sorry about my live author's phrase. I meant to say that I would appreciate a link to a live web-site, made by the tool's author/business, not a directory with dead links. May 13, 2013 at 23:41
  • Note also the Stackoverflow question: stackoverflow.com/questions/6163683/… which received (at the time I write this) 1144 upvotes. It may have been submitted as a joke, because I don't know of any genealogy software developers named Partick Höse. However the problem he refers to where a man has a child with his daughter, despite the title of the question, is neither a cycle nor a loop.
    – lkessler
    May 19, 2013 at 14:13

5 Answers 5

4

Two applications that I use and that can find loops are

Genealogica Grafica Shareware.

Behold Requires a license, 45-day trial license is free.

I do recommend not merely finding a loop, but regularly using these or other tools to check for more possible errors.

4
  • Genealogica Grafica just crashed on a file with a large loop. Will test Behold tomorrow on that file. May 13, 2013 at 23:37
  • 2
    Behold did the job. It found 14 small loops, but there might be more. That's because the total number of persons in the Behold report does not match the number that Genealogica Grafica reported just before it crashed. May 14, 2013 at 12:07
  • Your GEDCOM Validation page does not mention the types of checks that Behold does, but apparently you do know part of those. Would be nice if you can mention some, including loops. May 14, 2013 at 12:09
  • 1
    The GEDCOM validation article is an overview of some tools you can use GEDCOM validation, it is not about genealogy consistency & reasonability checks. These are two different things. Louis Kessler does advertise that Behold can detect loops. May 14, 2013 at 14:27
4

Geek warning. Non geeks use caution. Finding loops in ancestry trees is equivalent to a well known problem in graph theory, the problem of finding sets of strongly connected components in directed graphs. There is an efficient algorithm first described by Robert Tarjan, an American computer scientist, for finding the components. Each set of components is made up of elements forming a cycle; so in the genealogical application, a set of components makes up an impossible cycle of relationships.

I have incorporated Tarjan's algorithm in my Gedcom validation suite. Here is an example of the errors it catches. See the Gedcom file at the end of this post. It has four persons with an illegal loop, with Joan Hancock being both the mother of Thomas Wetmore IV and also a child of Thomas Wetmore IV. When run through the validator the following errors are reported:

Line    Type               Record
 3      ancestryCycle 1    I1 Thomas Trask Wetmore IV
24      ancestryCycle 1    I4 Joan Marie Hancock

This is the shortest loop possible. If a loop consists of three or more persons every person in the loop is reported in the errors. If there are more than 1 loop, each loop is given its own index (here the index is 1).

0 @I1@ INDI
1 NAME Thomas Trask /Wetmore/ IV
1 SEX M
1 FAMS @F1@
1 FAMC @F2@
0 @I2@ INDI
1 NAME Luann Frances /Grenda/
1 SEX F
1 FAMS @F1@
0 @F1@ FAM
1 HUSB @I1@
1 WIFE @I2@
1 CHIL @I4@
0 @I3@ INDI
1 NAME Thomas Trask /Wetmore/ III
1 SEX M
1 FAMS @F2@
0 @I4@ INDI
1 NAME Joan Marie /Hancock/
1 SEX F
1 FAMS @F2@
1 FAMC @F1@
0 @F2@ FAM
1 HUSB @I3@
1 WIFE @I4@
1 CHIL @I1@
9
  • Tom: Is your GEDCOM validation suite publicly available?
    – lkessler
    May 15, 2013 at 4:24
  • It is available as a Mac OS X Cocoa app. It is really a demo program that I am always fiddling with to experiment with new ideas. It is written in all Objective-C. I would be happy to send you the two methods that do the analysis so you can see what is needed to add Tarjan's algo. May 15, 2013 at 9:11
  • 1
    Thx, but don't have Mac nor C. Tarjan's is well described on Wikipedia with pseudo code.
    – lkessler
    May 15, 2013 at 13:56
  • I tried to implement Tarjan's and I found out that the connected components it results in are not the same as cycles. It basically partitions the graph, but misses some cycles. To get every cycle, a better algorithm (which is actually faster than Tarjan's) is described by Eminsenay in his answer to "Finding all cycles in graph" at: stackoverflow.com/a/2794683/30176 - If that algorithm is too complex (which it is), an alternative is simple depth first search with backtracking that Himadri Choudhury proposed as an answer to the same question.
    – lkessler
    May 18, 2013 at 18:57
  • @lkessler, Tarjan's finds "components." A component always includes AT LEAST ONE cycle/loop, and EVERY cycle/loop is in EXACTLY ONE component. (We are ignoring the components that have just one person/node in them.) Thus Tarjan's finds EVERY person that is in a cycle/loop, and identifies EVERY person that person is in a cycle/loop with, even if the person is in more than one cycle/loop. I don't know what more you could wish for. I think you are confused by the fact that a component may contain many cycles/loops. May 19, 2013 at 15:01
3

I wrote Bonkers, a free online consistency checking tool that should work (albeit indirectly).

12
  • Looks nice, but not for me at the moment. I know that persons older than their parents are likely causes for a loop like I was after, but it's rather indirect, as you say. May 15, 2013 at 14:53
  • And I crashed it with my test file. Hope you find something about that in your logs. FTB found more than 100 loops in it, so I know it is a nasty one. May 16, 2013 at 10:01
  • Enno, I fixed the infinite loop stack overflow crash. Bonkers now finds 42 loops in your file. Bonkers now also lists the number of generations in the loop to aid in locating them. Note: Adam and Bonkers currently are just checking primary parents. Note: the program revision was not bumped. timforsythe.com/tools/bonkers
    – Deleted
    May 16, 2013 at 15:23
  • 1
    A number like 42 makes a lot of sense. I merged 92 persons in PAF, and 42 suggests that a little less than 50 % of those silly merges caused a loop. Sounds OK. And isn't it true that 42 is the answer to all questions in the universe? May 17, 2013 at 15:56
  • 2
    Results are in: After unlinking 19 persons, 18 as child, 1 as parent, all loops are gone, meaning that Behold, Bonkers, and FTB, all report 0 (persons in) ancestral loops. May 17, 2013 at 18:32
2

The main tools I use to process gedcom are gramps, myheritage, werelate, and tools I wrote myself. A process I follow for werelate may be useful for you. Werelate.org allows you to upload your gedcom to add individuals to the website. Part of their process for uploading involves running some tests on the gedcom that might find your issue. If your gedcom is too large, they might balk just at size prior to finding your loop. But you and try and see.

I'll confess I don't upload my entire main gedcom at once. It's cumbersome (and not recommended) to upload a huge gedcom so I use gramps or tools I write myself to trim my gedcom down to subset (eg a particular line). You might consider doing this just to find your issue. I usually use gramps to do this but that is obviously problematic in your case. You might consider splitting the gedcom manually into pieces (ie arbitrarily making it into several files using a text editor) and then using gramps on the pieces to rearrange into workable smaller gedcoms.If you know any programming, you could write a script instead of using a text editor to pull subsets of the gedcom more to how you'd like to split it up.

1
  • While your answer was not specific about which tool would actually work for this, it turns out that My Heritage Family Tree Builder does the job. It finds more and larger loops than the other tools that I tried, and it doesn't crash on my test file either. May 14, 2013 at 13:48
1

You could always try one of the external analysis tools to check out your Gedcom file. One I have heard good reports about (but not personally used) is Gedcom Validator that is available as a free download from here. There are several others according to Google.

Another way would be to take your current Gedcom file and import it into another Family Tree programme, there are many such as Family Historian, Legacy, Ancestral Quest etc that offer free trials / limited use before paying that will check your Gedcom on import and throw errors that may help you diagnose the issue. You can then correct the problem back in Gramps and delete the trial software.

3
  • 2
    Gedcom Validator is a nice tool for technical things like the proper use of tags, but as far as I can see it doesn't check for the kind of loops I'm looking for. The good thing is that your answer triggered me to read an article on GEDCOM Validation by Tamura Jones, and that article lists one tool that is supposed to do the job. It's called Genealogica Grafica, and the download link is at the bottom of the page. To my regret, it didn't find any in my own GEDCOM file though, so I don't really know how good it is. May 12, 2013 at 20:02
  • Enno, glad it triggered the thought process but sorry you haven't found the problem.
    – Colin
    May 13, 2013 at 6:43
  • 1
    Follow-up: After discovering that the freeze was probably caused by a long calculation, not a loop, I used PAF to create a large loop, and then fed that PAF gedcom to Gedcom Validator. The program then complained that it did not support GEDCOM version 5.2.18.0. And those familiar with PAF know that that's the PAF version! PAF writes gedcom 5.5, and puts that number in the gedcom too, but gedcom validator doesn't seem to recognize which version number belongs to PAF and which to GEDC ... May 13, 2013 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.