Take the 2-minute tour ×
Genealogy & Family History Stack Exchange is a question and answer site for expert genealogists and people interested in genealogy or family history. It's 100% free, no registration required.

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.

share|improve this question
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. –  Canadian Girl Scout May 11 '13 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. :) –  American Luke May 11 '13 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 '13 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. –  Enno Borgsteede May 13 '13 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 '13 at 14:13
show 1 more comment

5 Answers 5

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.

share|improve this answer
    
Genealogica Grafica just crashed on a file with a large loop. Will test Behold tomorrow on that file. –  Enno Borgsteede May 13 '13 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. –  Enno Borgsteede May 14 '13 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. –  Enno Borgsteede May 14 '13 at 12:09
    
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. –  TamuraJones May 14 '13 at 14:27
add comment

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.

share|improve this answer
    
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. –  Enno Borgsteede May 14 '13 at 13:48
add comment

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

share|improve this answer
    
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. –  Enno Borgsteede May 15 '13 at 14:53
1  
I just updated Bonkers and Adam to detect ancestor loops directly. timforsythe.com/blog/detecting-ancestral-loops –  Tim Forsythe May 15 '13 at 15:14
    
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. –  Enno Borgsteede May 16 '13 at 10:01
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? –  Enno Borgsteede May 17 '13 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. –  Enno Borgsteede May 17 '13 at 18:32
show 7 more comments

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@
share|improve this answer
    
Tom: Is your GEDCOM validation suite publicly available? –  lkessler May 15 '13 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. –  Tom Wetmore May 15 '13 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 '13 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 '13 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. –  Tom Wetmore May 19 '13 at 15:01
show 4 more comments

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.

share|improve this answer
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. –  Enno Borgsteede May 12 '13 at 20:02
    
Enno, glad it triggered the thought process but sorry you haven't found the problem. –  Colin May 13 '13 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 ... –  Enno Borgsteede May 13 '13 at 23:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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