Pytanie Cykle w oprogramowaniu drzewa genealogicznego


Jestem programistą oprogramowania do tworzenia rodziny (napisanego w C ++ i Qt). Nie miałem problemów, dopóki jeden z moich klientów nie przesłał mi raportu o błędzie. Problem polega na tym, że klient ma dwoje dzieci z własną córką, a co za tym idzie, nie może używać mojego oprogramowania z powodu błędów.

Błędy te są wynikiem moich różnych twierdzeń i niezmienników o przetwarzanym wykresie rodziny (na przykład po przejściu cyklu program stwierdza, że ​​X nie może być ojcem ani dziadkiem Y).

Jak mogę rozwiązać te błędy bez usuwania wszystkich asercji danych?


1594
2018-05-28 18:39


pochodzenie


Wygląda na to, że należy ograniczyć sprzedaż oprogramowania do tych, które unikają trudnych sytuacji rodzinnych! Jak ma się dzieci z własną córką - mam nadzieję, że mówisz o jego synowej! - Will A
Powinieneś oczywiście napisać swoje oprogramowanie z myślą o utworze Raya Stevensa. - Peter K.
Może to być jeden z tych przypadków, w których musisz zadać sobie pytanie: Czy naprawdę chcę robić interesy z tym facetem?  Innym rozwiązaniem byłoby wszczęcie przeciwko niemu oskarżeń kryminalnych. Kazirodztwo jest w końcu zakazane na większości świata. W końcu twoje oprogramowanie jest zepsute, ponieważ możesz (legalnie) mieć cykle w drzewie genealogicznym: kuzyni mogą zawierać związki małżeńskie w większości (wszystkich?) Zachodnich krajach. - sbi
Nie powinieneś dodawać twierdzeń dotyczących rzeczy nieprawdopodobnych, tylko rzeczy niemożliwe. Cykle to rzeczy oczywiste, które nie są możliwe na wykresie drzewa genealogicznego ... nikt nie może być jego własnym przodkiem za pomocą jakiejkolwiek metody. Te inne twierdzenia są po prostu fałszywe i powinny zostać usunięte. - pgod
Może następnym razem spróbujesz bardziej abstrakcyjnego przykładu. Ludzie tutaj nie mogą przeoczyć części kazirodczej i po prostu ją zamknąć, nawet jeśli jest to poprawne pytanie dotyczące reprezentacji danych drzewiastych. - stesch


Odpowiedzi:


Wygląda na to, że ty (i / lub twoja firma) macie fundamentalne niezrozumienie tego, jak powinno wyglądać drzewo genealogiczne.

Pozwól mi wyjaśnić, pracuję również dla firmy, która ma (jako jeden z jej produktów) drzewo genealogiczne w swoim portfelu i zmagamy się z podobnymi problemami.

Problem, w naszym przypadku, i zakładam również twoją sprawę, pochodzi z GEDCOM w formacie, który jest skrajnie uparty co do tego, jaka powinna być rodzina. Jednak ten format zawiera poważne nieporozumienia dotyczące tego, jak naprawdę wygląda drzewo genealogiczne.

GEDCOM ma wiele problemów, takich jak niekompatybilność z tymi samymi relacjami seksualnymi, kazirodztwo, itp. ... Które w rzeczywistości zdarzają się częściej niż można sobie wyobrazić (zwłaszcza gdy cofasz się w czasie do 1700-1800).

Modelujemy nasze drzewo genealogiczne na to, co dzieje się w realnym świecie: wydarzenia (na przykład urodzenia, śluby, zaangażowanie, związki zawodowe, zgony, adopcje itp.). Nie nakładamy na nie żadnych ograniczeń, z wyjątkiem sytuacji logicznie niemożliwych (na przykład nie można być własnym rodzicem, stosunki wymagają dwóch osób itp.)

Brak walidacji daje nam bardziej "rzeczywisty świat", prostsze i bardziej elastyczne rozwiązanie.

Jeśli chodzi o ten konkretny przypadek, sugerowałbym usunięcie twierdzeń, ponieważ nie mają one uniwersalnego charakteru.

Do wyświetlania problemów (które się pojawią) sugerowałbym rysowanie tego samego węzła tyle razy, ile potrzeba, wskazanie na duplikację poprzez zapalenie wszystkich kopii po wybraniu jednego z nich.


727
2018-06-01 08:25



To wygląda na właściwe podejście i jest dość łatwe do rozszerzenia, aby wykryć bardziej złożone problemy. Możesz opracować zestaw relacji między zdarzeniami "A happen before B". Na przykład, że osoba urodziła się przed innymi wydarzeniami z nimi związanymi. To jest skierowany wykres. Następnie można sprawdzić, czy wykres nie zawiera cykli. Zobacz to pytanie na StackOverflow.  Powinno być dobrze, dopóki nie wynaleziono podróży w czasie. - Paul Harrison
@ Paul-Harrison Jeśli to jest tak proste. W starszych zapisach (nawet nowych) występują niespójności daty. Chrzest przed narodzinami, wiele zapisów dotyczących narodzin itp. W oficjalnych rejestrach są więc podróże w czasie. Pozwalamy na niespójne dane. Pozwalamy użytkownikom wskazać, co aplikacja powinna uwzględnić "urodzenia" w przypadku duplikatów. A my wskażemy złamane linie czasu, jeśli je znajdziemy. - Bert Goethals
@ ben-voigt GEDCOM to format stworzony przez Kościół Jezusa Chrystusa Świętych w Dniach Ostatnich. Specyfikacja wyraźnie stwierdza, że ​​małżeństwo (MARR) ma być między kobietami i mężczyznami. W przypadku małżeństw jednopłciowych lub kazirodztwa należy użyć znacznika ASSO (ASSOCIATES), również oznaczającego przyjaźń lub sąsiada. Oczywiste jest, że małżeństwo tej samej płci jest związkiem drugiej klasy w ramach tej specyfikacji. Bardziej neutralna specyfikacja nie wymagałaby męskich relacji kobiet. - Bert Goethals
@ Bert Goethals: Mylicie GEDCOM z niektórymi programami, które nie obsługują małżeństw osób tej samej płci (PAF, Legacy). GEDCOM nie wyklucza takich konstruktów jak "0 @ F1 @ FAM / 1 HUSB @ I1 @ / 1 HUSB @ I2 @", a zatem obsługuje małżeństwa osób tej samej płci, jeśli oprogramowanie wybierze. - Pierre
@Pierre Możesz naprawdę oszukać system. Jest to bezpośrednio z dokumentacji 5.5.1: "MARR {MAŁŻEŃSTWO}: = Prawne, common-law lub zwyczajowe wydarzenie utworzenia jednostki rodzinnej mężczyzny i kobiety jako męża i żony." (homepages.rootsweb.ancestry.com/~pmcbride/gedcom/55gcappa.htm) Jak widać, nie ma tu małżeństw tej samej płci. - Bert Goethals


Zrelaksuj swoje twierdzenia.

Nie poprzez zmianę zasad, które są najprawdopodobniej bardzo pomocne dla 99,9% klientów w łapaniu błędów przy wprowadzaniu ich danych.

Zamiast tego zmień go z błędu "nie można dodać relacji" na ostrzeżenie z "dodaj mimo to".


564
2018-05-28 19:20



Kiedy napotkasz a bardzo mało prawdopodobne sytuacja, czyli taka, w której byłby użytkownik zazwyczaj rób to tylko przez pomyłkę, dobrze jest pokazać użytkownikowi ostrzeżenie. To dobre opinie. Ale pozwól użytkownikowi iść dalej, jeśli są naprawdę na pewno chcą. Sądzę więc, że jest to dobra odpowiedź, nawet jeśli nie dostanie się do tego, w jaki sposób. - thomasrutter
Dobra odpowiedź! Zastanawiam się tylko, jak ten rodzaj oprogramowania poradzi sobie "Jestem moim własnym dziadkiem" (youtube.com/watch?v=eYlJH81dSiw) sytuacja? - Zaur Nasibov
To nie jest tak naprawdę odpowiedź, ponieważ myślę, że problem pochodzi z tego, że faktycznie przechodzimy przez drzewo? Jest to jednak dobra sugestia. - bdwakefield
@bdwakefield: Pytanie brzmiało: "Jak rozwiązać te błędy, bez usuwania wszystkich twierdzeń dotyczących danych?" Wierzę, że odpowiedziałem na to. - Ben Voigt
@Ben To zależy od tego, do czego służą stwierdzenia. Jeśli zapobiegają nieskończonym pętlom lub fatalnym błędom, wówczas skutecznie sugerujesz usunięcie twierdzeń. Jeśli są po to, aby ostrzec użytkownika przed potencjalnym błędem, twoja odpowiedź jest dobra. - rm999


Oto problem z drzewami genealogicznymi: nie są to drzewa. Są skierowane acykliczne wykresy lub DAG. Jeśli poprawnie zrozumiem zasady biologii ludzkiego rozmnażania, nie będzie żadnych cykli.

O ile mi wiadomo, nawet chrześcijanie akceptują małżeństwa (a więc i dzieci) między kuzynami, które zamieniają drzewo genealogiczne w rodzinną DAG.

Morał tej historii brzmi: wybierz właściwe struktury danych.


224
2018-06-01 09:58



Wymagałoby to dalszego ograniczenia każdego węzła mającego 1 lub 2 maksymalne węzły wskazujące na to w przypadku in vitro i rozmnażania płciowego. Chociaż może być bardziej prawdziwe w prawdziwym życiu, możesz pozwolić wielu przerywanym liniom na niepewne potomstwo po stronie ojca (zawsze jest jasne, kto jest matką, ale tylko testowanie DNA może zapewnić, kto jest ojcem, a to rzadko dzieje się nawet dzisiaj), lub nawet dla obu jest brana pod uwagę adopcja. - manixrock
@manixrock - ponieważ to pytanie dotyczy rzadkich przypadków, chciałbym potwierdzić, że nie zawsze jest jasne, kim jest matka. adopcje, porzucone dzieci, zastępcze matki itd. wszystko to może skomplikować sprawę. - Peter Recore
To niekoniecznie jest acykliczne, prawda? Mężczyzna-marries-babcia. - Ed Ropple
Mężczyzna poślubiający swoją babkę nie stanie się swoim własnym dziadkiem i nie doda cyklu. Jeśli mają dzieci, będzie to zwykły, nieszynowy, wykres. - exDM69
To DWA ADG. Jest wykres rodzicielstwa i wykres relacji prawnych. Zwykle to samo, ale rozbieżne więcej niż można się spodziewać. - JSacksteder


Sądzę, że masz jakąś wartość, która jednoznacznie identyfikuje osobę, na której możesz oprzeć swoje czeki.

To jest podchwytliwe. Zakładając, że chcesz zachować strukturę drzewa, sugeruję to:

Załóżmy, że: A ma dzieci z własną córką.

A dodaje się do programu jako A i jako B. Kiedyś w roli ojca, nazwijmy to chłopakiem.

Dodać is_same_for_out() funkcja, która mówi części generującej wynik twojego programu, do której prowadzą wszystkie linki B wewnętrznie powinno iść A po przedstawieniu danych.

Spowoduje to dodatkową pracę dla użytkownika, ale myślę, że byłoby to stosunkowo łatwe do wdrożenia i utrzymania.

Budując z tego, możesz pracować nad synchronizacją kodu A i B aby uniknąć niespójności.

To rozwiązanie z pewnością nie jest doskonałe, ale jest pierwszym podejściem.


115
2018-05-28 18:50



Prawdopodobnie takie węzły "proxy" są rzeczywiście odpowiednim rozwiązaniem. Jednak nie mam pojęcia, jak można je umieścić w interfejsie użytkownika bez obrażania użytkownika. Mogę wam powiedzieć, że pisanie oprogramowania, które zajmuje się prawdziwymi ludźmi (zwłaszcza waszymi klientami) nie jest łatwe. - Partick Höse
To się nigdy nie kończy - nowy syn B będzie jego własnym wujem. Rozważałbym pełny zwrot pieniędzy za program! - Bo Persson
Jup to rodzaj zawalonej sytuacji. Czy inline prolog jest możliwy w C ++? - Eduard Thamm
@Will A: A potem uświadamia sobie, że jest także jego własną matką, i rekrutuje swoją młodszą osobę do agencji czasu? - Null Set
Powielanie (i synchronizacja) danych w jednym systemie jest złą praktyką. Wskazuje, że roztwór jest mniej optymalny i należy go ponownie rozważyć. Jeśli konieczne byłoby utworzenie dodatkowych (duplikatów) węzłów, wskaż go jako serwer proxy i deleguj dane do odczytu i zapisu do oryginalnego węzła. - Bert Goethals


Powinieneś się skupić co naprawdę stanowi wartość dla twojego oprogramowania. Czy czas poświęcony na sprawienie, by działał JEDNYM konsumentem, wartym ceny licencji? Prawdopodobnie nie.

Radzę przeprosić tego klienta, powiedzieć mu, że jego sytuacja jest poza zakresem oprogramowania i zwrócić mu koszty.


84
2018-06-01 08:51



Bardzo prawdziwe. Ale zważ także na inne potencjalne problemy z podobnymi problemami, które pojawiły się u innych. - Prof. Falken
Oczywiście. Rozumowanie jest następujące: jeśli jest to rzadki przypadek na niekrytycznej aplikacji, nie trzeba niczego naprawiać ani implementować. Jeśli to naprawdę boli użytkowników, warto nad tym pracować. - christopheml
Prawdopodobnie każdy ma jakiś przypadek kazirodztwa gdzieś w swoim rodowodzie. Więc uderzysz w to uderzenie, jeśli jedna z historii rodzinnych wykopie głęboko. - datenwolf
Tworzenie drzewa genealogicznego o jakiejś dziwnej sytuacji (wsobna królewskość, Fritzl itp.) Jest prawidłowym użyciem oprogramowania. - Bulwersator
Oprogramowanie do drzewa genealogicznego, które nie pozwoli na małżeństwo drugim kuzynom, jest bezużyteczne. Niemal wszystkie rodziny mają przynajmniej jeden taki przypadek. Dlatego uważam, że oryginalny przykład jest stworzony dla efektu. - Fuzzy76


Powinieneś skonfigurować Atreides rodzina (zarówno nowoczesna, Wydmalub starożytne, Oedipus Rex) jako przypadek testowy. Nie znajdziesz błędów, korzystając ze zdezynfekowanych danych jako przypadku testowego.


79
2018-06-01 16:10



Niestety, zbyt wiele osób najpierw myśli o "ok" danych zamiast o skrajnych przypadkach, które łamią ich systemy. - sjas


Jest to jeden z powodów, dla których języki takie jak "Go" nie mają zapewnień. Są używane do obsługi spraw, o których prawdopodobnie nie myśleliście, zbyt często. Powinieneś twierdzić, że to niemożliwe, a nie tylko mało prawdopodobne. Robienie tego drugiego jest tym, co daje stwierdzenia złą reputacją. Za każdym razem, gdy piszesz assert(odejdź na dziesięć minut i naprawdę Pomyśl o tym.

W szczególnie niepokojącym przypadku jest zarówno możliwe, jak i przerażające, że takie stwierdzenie byłoby fałszywe w rzadkich, ale możliwych okolicznościach. W związku z tym zajmij się tym w swojej aplikacji, jeśli tylko powie: "To oprogramowanie nie zostało zaprojektowane do obsługi przedstawionego scenariusza".

Zapewnienie, że twój wielki, wielki, pradziadek jest twoim ojcem jako niemożliwym, jest rozsądną rzeczą do zrobienia.

Gdybym pracował dla firmy testowej, która została zatrudniona do przetestowania oprogramowania, oczywiście przedstawiłbym ten scenariusz. Czemu? Każdy nieletni, ale inteligentny "użytkownik" ma zamiar zrobić dokładnie to samo i delektuj się wynikowym "raportem o błędzie".


59
2018-06-01 06:10



Nie zapomnij zamrożonych nasienia ... - Prof. Falken
Zgadzam się z argumentem "kiedy używać twierdzeń"; nie widzisz, jak to się ma do "pewnych języków, Go nie robi". - phooji
@Red Hue - czasami kompilatory sprawiają, że niemożliwe ... możliwe. Niektóre wersje gcc myślą -10 == 10 w implementacji abs (). - Tim Post♦
@Red Hue: Cały punkt asercji polega na dokumentowaniu i testowaniu warunków, które zawsze powinny być prawdziwe (lub fałszywe). Pomaga ci (i innym) "naprawić" rzeczy w taki sposób, że powstają te niemożliwe sytuacje, ponieważ wtedy jawnie (a nie subtelnie) przerwie aplikację. Jeśli istnieje uzasadniony powód pojawienia się "niemożliwego" przypadku, to zapewniłeś zbyt wiele. - cHao
Posiadanie asercji (lub kodu twierdzącego) nie ma znaczenia. Kod w językach takich jak Go może i będzie zawierał założenia dotyczące struktury danych; po prostu nie może udokumentować i egzekwować tych założeń za pomocą twierdzeń. Konkluzja: aplikacja ma błąd. - Tommy McGuire


Nienawidzę komentowania tak zawalonej sytuacji, ale najprostszym sposobem, aby nie rejugować wszystkich twoich niezmienników, jest stworzenie na twoim wykresie widmowego wierzchołka, który działa jako pośrednik z powrotem do kazirodczego ojca.


41
2018-05-28 18:55





Tak więc, wykonałem trochę pracy nad oprogramowaniem z rodziny rodzinnej. Myślę, że problem, który próbujesz rozwiązać, polega na tym, że musisz móc chodzić po drzewie bez wchodzenia w nieskończone pętle - innymi słowy, drzewo musi być acykliczne.

Wygląda jednak na to, że twierdzisz, że istnieje tylko jedna ścieżka między osobą a jednym z jej przodków. To zagwarantuje, że nie ma cykli, ale jest zbyt rygorystyczne. Z biologicznego punktu widzenia potomstwo jest skierowany wykres acykliczny(DAG). Sprawa, którą masz, jest z pewnością zdegenerowana, ale tego typu rzeczy zdarzają się cały czas na większych drzewach.

Na przykład, jeśli spojrzysz na dwóch przodków, których masz w pokoleniu n, gdyby nie było nakładania się, to miałbyś więcej przodków w 1000 roku, niż gdyby żyli ludzie. Tak więc, musi się pokrywać.

Jednak masz też tendencję do otrzymywania błędnych danych, które są nieprawidłowe. Jeśli przemierzasz drzewo, musisz sobie poradzić z cyklami. Możesz to zrobić w każdym indywidualnym algorytmie lub przy obciążeniu. Zrobiłem to na ładunek.

Znalezienie prawdziwych cykli w drzewie można wykonać na kilka sposobów. Błędnym sposobem jest oznaczenie każdego przodka danej osoby, a podczas przechodzenia, jeśli osoba, którą zamierzasz przejść do następnego, jest już zaznaczona, a następnie odciąć link. To zerwie potencjalnie dokładne relacje. Prawidłowym sposobem na to jest rozpoczęcie od każdej osoby i oznaczenie każdego przodka ścieżką do tej osoby. Jeśli nowa ścieżka zawiera bieżącą ścieżkę jako ścieżkę podrzędną, to jest to cykl i powinna być zerwana. Możesz przechowywać ścieżki jako wektor <bool> (MFMF, MFFFMF, itp.), Co sprawia, że ​​porównywanie i przechowywanie jest bardzo szybkie.

Istnieje kilka innych sposobów wykrywania cykli, takich jak wysyłanie dwóch iteratorów i sprawdzanie, czy kiedykolwiek zderzają się z testem podzbioru, ale w końcu skorzystałem z lokalnej metody przechowywania.

Zauważ, że nie musisz odrywać linku, możesz po prostu zmienić go z normalnego linku na "słaby" link, który nie jest przestrzegany przez niektóre z twoich algorytmów. Będziesz także chciał zachować ostrożność, wybierając link, który oznaczysz jako słaby; Czasami możesz dowiedzieć się, gdzie należy przerwać cykl, przeglądając informacje o urodzinach, ale często nie możesz niczego zrozumieć, ponieważ brakuje tak dużej ilości danych.


37
2018-06-01 18:39



Ostrożnie o tych założeniach; jeden mężczyzna i jedna kobieta nie są dane, gdy ludzie się przystosowują, lub lesbijki, które uważają się za rodziców, w najbliższej przyszłości mogą nawet być w stanie naprawdę być biologicznie rodzice, przynajmniej z dziewcząt. W tym przypadku, jeśli zastosujemy dolly do ludzi, nawet założenie "osoba ma dwóch różnych rodziców" jest obecnie niedostępne. - Agrajag
@Agrajag, tak, dlatego określiłem "biologicznie rzecz biorąc" dla wykrywania cyklu. Nawet biologicznie, istnieje wiele możliwych problemów, takich jak zastępcze matki i sztuczne zapłodnienie. Jeśli zezwalasz również na adopcje i inne niebiologiczne metody definiowania rodziców, wtedy możesz mieć prawdziwy prawdziwy cykl na drzewie - na przykład, być może ktoś adoptuje dziadka, gdy się zestarzeje i nie będzie już mógł dbać o siebie . Podejmowanie założeń dotyczących życia rodzinnego jest zawsze skomplikowane. Ale pisząc oprogramowanie, musisz przyjąć pewne założenia. - tfinniga