Timeline for How can I find loops in GEDCOM files?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 19, 2013 at 21:38 | comment | added | lkessler | That is true. But people do need good error messages when they have a really messed up database, such as Enno's | |
| May 19, 2013 at 19:09 | comment | added | Tom Wetmore | Louis, You are correct, but my question is how often are databases going to be so messed up that a single person is in multiple ancestry cycles? In my own experience never, in which case components are exactly cycles. How about in your experience? I will add the complexity of breaking components down into cycles if there is ever evidence that it is an important thing to do. | |
| May 19, 2013 at 18:06 | comment | added | lkessler | Tom, yes I understand that the connected components contain the loops. But it is better to identify loops because that tells the person how many corrections that are needed. For example, in upload.wikimedia.org/wikipedia/commons/5/5c/Scc.png there are 3 connected components, but 4 loops, since c-d and d-h are both loops. If a person corrects c-d, they will still be left with 3 connected components (ignoring c which is now on its own). It just is less confusing to people to know that there's 4 loops with 4 corrections to make. | |
| May 19, 2013 at 15:21 | comment | added | Tom Wetmore | @lkessler, So yes, I agree with you, that my error notation, "ancestryCycle," is misleading, since a component, though usually a cycle for simple GEDCOM errors, can actually be considerably more than a cycle. Thanks for helping me get a better clarification on that topic. I'll probably change the error code to "AncestryCycles" for the more complex components with multiple loops. | |
| May 19, 2013 at 15:01 | comment | added | Tom Wetmore | @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 18, 2013 at 18:57 | comment | added | lkessler | 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. | |
| May 16, 2013 at 6:46 | history | edited | Tom Wetmore | CC BY-SA 3.0 |
added 93 characters in body
|
| S May 15, 2013 at 23:09 | history | suggested | Sam | CC BY-SA 3.0 |
wikipedia link
|
| May 15, 2013 at 22:12 | review | Suggested edits | |||
| S May 15, 2013 at 23:09 | |||||
| May 15, 2013 at 13:56 | comment | added | lkessler | Thx, but don't have Mac nor C. Tarjan's is well described on Wikipedia with pseudo code. | |
| May 15, 2013 at 9:11 | comment | added | Tom Wetmore | 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 4:24 | comment | added | lkessler | Tom: Is your GEDCOM validation suite publicly available? | |
| May 15, 2013 at 3:29 | history | answered | Tom Wetmore | CC BY-SA 3.0 |
