Jestem programistą niektórych programów drzewa genealogicznego (napisanych 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ą, w wyniku czego nie może korzystać z mojego oprogramowania z powodu błędów.

Błędy te są wynikiem moich różnych twierdzeń i niezmienników dotyczących przetwarzanego wykresu rodzinnego (na przykład po przejściu cyklu program stwierdza, że ​​X nie może być jednocześnie ojcem i dziadkiem Y).

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

Wygląda na to, że ty (i / lub Twoja firma) zasadniczo nie rozumiesz, czym powinno być drzewo genealogiczne.

Pozwólcie, że wyjaśnię, pracuję również dla firmy, która ma (jako jeden z jej produktów) drzewo genealogiczne w swoim portfolio i borykamy się z podobnymi problemami.

Problem, w naszym przypadku, i zakładam, że również i twój, pochodzi z formatu GEDCOM , który jest bardzo opiniotwórczy na temat tego, jaka powinna być rodzina. Jednak ten format zawiera poważne nieporozumienia na temat tego, jak naprawdę wygląda drzewo genealogiczne.

GEDCOM ma wiele problemów, takich jak niezgodność z relacjami homoseksualnymi, kazirodztwo itp., Które w prawdziwym życiu zdarzają się częściej, niż można sobie wyobrazić (szczególnie, gdy cofamy się w czasie do 1700-1800).

Zmodelowaliśmy nasze drzewo genealogiczne do tego, co dzieje się w prawdziwym świecie: wydarzeń (na przykład narodzin, ślubów, zaręczyn, związków, zgonów, adopcji itp.). Nie nakładamy na nie żadnych ograniczeń, z wyjątkiem logicznie niemożliwych (na przykład nie można być własnym rodzicem, relacje potrzebują 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.

W celu wyświetlenia problemów (które się pojawią) sugerowałbym rysowanie tego samego węzła tyle razy, ile potrzeba, wskazując na duplikację, oświetlając wszystkie kopie po wybraniu jednego z nich.

Rozluźnij swoje twierdzenia.

Nie poprzez zmianę zasad, które najprawdopodobniej są bardzo pomocne dla 99,9% klientów w wykrywaniu błędów podczas wprowadzania danych.

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

Oto problem z drzewami rodzinnymi: nie są drzewami. Są to ukierunkowane wykresy acykliczne lub DAG. Jeśli dobrze zrozumiem zasady biologii reprodukcji człowieka, nie będzie żadnych cykli.

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

Morał tej historii jest następujący: wybierz odpowiednie struktury danych.

Myślę, ż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: Ama dzieci z własną córką.

Adodaje się do programu jako Ai jako B. Raz w roli ojca, nazwijmy to chłopakiem.

Dodaj is_same_for_out()funkcję, która mówi wyjściowej części twojego programu, że wszystkie łącza do Bwewnętrznej strony powinny być kierowane Apodczas prezentacji danych.

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

Na tej podstawie możesz pracować nad synchronizacją kodu Ai Bunikać niespójności.

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

Powinieneś skupić się na tym, co naprawdę stanowi wartość dla twojego oprogramowania . Czy czas poświęcony na uruchomienie go dla JEDNEGO konsumenta jest wart ceny licencji? Prawdopodobnie nie.

Radzę przeprosić tego klienta, powiedzieć mu, że jego sytuacja nie wchodzi w zakres oprogramowania i zwrócić mu zwrot pieniędzy.

Powinieneś założyć rodzinę Atrydów (nowoczesną, Wydmową lub starożytną, Edypa Rexa ) jako przypadek testowy. Nie można znaleźć błędów, używając oczyszczonych danych jako przypadku testowego.

Jest to jeden z powodów, dla których języki takie jak „Go” nie mają zapewnień. Służą do obsługi spraw, o których prawdopodobnie nie myślałeś zbyt często. Powinieneś twierdzić tylko niemożliwe, a nie tylko mało prawdopodobne . Robienie tego drugiego powoduje, że twierdzenia mają złą reputację. Za każdym razem, gdy piszesz assert(, odejdź na dziesięć minut i naprawdę się nad tym zastanów.

W szczególnie niepokojącym przypadku jest zarówno możliwe, jak i przerażające, że takie twierdzenie byłoby fałszywe w rzadkich, ale możliwych okolicznościach. Dlatego obsłuż go w swojej aplikacji, choćby po to, by powiedzieć „To oprogramowanie nie zostało zaprojektowane do obsługi przedstawionego scenariusza”.

Twierdzenie, że twój pra-pra-pra-dziadek będąc ojcem jest niemożliwe, jest rozsądnym posunięciem.

Gdybym pracował dla firmy testującej, która została zatrudniona do testowania twojego oprogramowania, oczywiście przedstawiłbym ten scenariusz. Dlaczego? Każdy nieletni, ale inteligentny „użytkownik” zrobi dokładnie to samo i rozkoszuje się wynikowym „raportem o błędzie”.

Nienawidzę komentowania takiej zepsutej sytuacji, ale najłatwiejszym sposobem, aby nie zmieniać wszystkich niezmienników, jest utworzenie fantomowego wierzchołka na swoim wykresie, który działa jak proxy z powrotem do kazirodczego ojca.

Więc trochę popracowałem nad oprogramowaniem drzewa genealogicznego. Myślę, że problem, który próbujesz rozwiązać, polega na tym, że musisz być w stanie chodzić po drzewie bez wchodzenia w nieskończone pętle - innymi słowy, drzewo musi być acykliczne.

Wygląda jednak na to, że zapewniasz, że istnieje tylko jedna ścieżka między osobą a jednym z jej przodków. To gwarantuje, że nie ma cykli, ale jest zbyt surowe. Biologicznie rzecz biorąc potomstwo jest ukierunkowanym wykresem acyklicznym (DAG). Sprawa, którą masz, jest z pewnością sprawą zdegenerowaną, ale takie rzeczy zdarzają się cały czas na większych drzewach.

Na przykład, jeśli spojrzysz na 2 ^ n przodków, których masz w pokoleniu n, gdyby nie było nakładania się, miałbyś więcej przodków w 1000 r. Niż żyli ludzie. Więc muszą się nakładać.

Jednak często zdarza się, że cykle są nieprawidłowe, po prostu złe dane. Jeśli przemierzasz drzewo, musisz sobie radzić z cyklami. Możesz to zrobić w każdym algorytmie lub przy obciążeniu. Zrobiłem to przy obciążeniu.

Znalezienie prawdziwych cykli w drzewie można wykonać na kilka sposobów. Nieodpowiednim sposobem jest oznaczenie każdego przodka danej osoby, a podczas przechodzenia, jeśli osoba, do której przejdziesz, jest już zaznaczona, to odetnij link. To zerwie potencjalnie dokładne relacje. Właściwy sposób to zacząć od każdej osoby i oznaczyć każdego przodka ścieżką do tej osoby. Jeśli nowa ścieżka zawiera bieżącą ścieżkę jako podścieżkę, oznacza to cykl i powinna zostać zerwana. Ścieżki można przechowywać jako wektor <bool> (MFMF, MFFFMF itp.), Co sprawia, że ​​porównanie i przechowywanie są bardzo szybkie.

Istnieje kilka innych sposobów wykrywania cykli, takich jak wysłanie dwóch iteratorów i sprawdzenie, czy kiedykolwiek kolidują one z testem podzbioru, ale skończyłem na lokalnej metodzie przechowywania.

Zauważ również, że nie musisz tak naprawdę przerywać łącza, możesz po prostu zmienić go z normalnego na „słaby”, po którym nie ma niektórych algorytmów. Będziesz także chciał zachować ostrożność przy wyborze linku oznaczonego jako słaby; czasami możesz dowiedzieć się, gdzie powinien zostać przerwany cykl, patrząc na informacje o dacie urodzenia, ale często nie możesz niczego zrozumieć, ponieważ brakuje tak wielu danych.

Kolejna kpiąca poważna odpowiedź na głupie pytanie:

Prawdziwa odpowiedź brzmi: użyj odpowiedniej struktury danych. Ludzkiej genealogii nie można w pełni wyrazić przy użyciu czystego drzewa bez cykli. Powinieneś użyć jakiegoś wykresu. Porozmawiaj też z antropologiem, zanim przejdziesz dalej, ponieważ istnieje wiele innych miejsc, w których można popełnić podobne błędy, próbując modelować genealogię, nawet w najprostszym przypadku „zachodniego patriarchalnego małżeństwa monogamicznego”.

Nawet jeśli chcemy zignorować lokalnie relacje tabu, jak tu omówiono, istnieje wiele całkowicie legalnych i zupełnie nieoczekiwanych sposobów wprowadzania cykli do drzewa genealogicznego.

Na przykład: http://en.wikipedia.org/wiki/Cousin_marriage

Zasadniczo małżeństwo kuzynów jest nie tylko powszechne i oczekiwane, ale jest powodem, dla którego ludzie przeszli z tysięcy małych rodzin do 6 miliardów populacji na całym świecie. Nie może działać w żaden inny sposób.

Naprawdę niewiele jest uniwersaliów, jeśli chodzi o genealogię, rodzinę i rodowód. Niemal każde ścisłe założenie dotyczące norm sugerujących, kim może być ciotka lub kto może poślubić, kim lub w jaki sposób dzieci są uprawnione do dziedziczenia, może być zaniepokojone przez jakiś wyjątek gdzieś na świecie lub w historii.

Pomijając potencjalne implikacje prawne, z pewnością wydaje się, że należy traktować „węzeł” w drzewie genealogicznym jako osobę poprzedniczą, a nie zakładać, że węzeł może być osobą jedyną.

Niech węzeł drzewa obejmuje zarówno osobę, jak i następców - a następnie możesz mieć inny węzeł głębiej w drzewie, który obejmuje tę samą osobę z różnymi następcami.

Kilka odpowiedzi pokazało sposoby na zachowanie asercji / niezmienników, ale wydaje się to niewłaściwym wykorzystaniem asercji / niezmienników. Twierdzenia mają upewnić się, że coś, co powinno być prawdą, jest prawdą, a niezmienniki mają upewnić się, że coś, co nie powinno się zmienić, nie zmieni się.

Twierdzisz tutaj, że kazirodztwo nie istnieje. Wyraźnie zrobić istnieje, więc twierdzenie jest nieprawidłowy. Możesz obejść to twierdzenie, ale prawdziwy błąd dotyczy samego twierdzenia. Twierdzenie powinno zostać usunięte.

Twoje drzewo genealogiczne powinno wykorzystywać ukierunkowane relacje. W ten sposób nie będziesz mieć cyklu.

Dane genealogiczne są cykliczne i nie pasują do wykresu acyklicznego, więc jeśli masz twierdzenia o cyklach, powinieneś je usunąć.

Sposób obsługi tego w widoku bez tworzenia widoku niestandardowego polega na traktowaniu cyklicznego rodzica jako rodzica „ducha”. Innymi słowy, gdy dana osoba jest zarówno ojcem, jak i dziadkiem tej samej osoby, wówczas węzeł dziadka jest wyświetlany normalnie, ale węzeł ojca jest renderowany jako węzeł „duchowy”, który ma prostą etykietę podobną do („patrz dziadek” ) i wskazuje na dziadka.

Aby wykonać obliczenia, może być konieczne poprawienie logiki w celu obsługi cyklicznych wykresów, aby węzeł nie był odwiedzany więcej niż jeden raz, jeśli istnieje cykl.

Najważniejsze jest to avoid creating a problem, więc uważam, że powinieneś używać bezpośredniej relacji, aby uniknąć cyklu.

Jak powiedział @markmywords, #include „fritzl.h”.

Wreszcie muszę powiedzieć recheck your data structure. Może coś idzie nie tak (może dwukierunkowa lista łączy rozwiązuje problem).

Asercje nie przetrwają rzeczywistości

Zazwyczaj twierdzenia nie przetrwają kontaktu z danymi ze świata rzeczywistego. Decyzja o tym, z którymi danymi chcesz się zajmować, a które są poza zakresem, jest częścią procesu inżynierii oprogramowania.

Cykliczne wykresy rodzinne

Jeśli chodzi o rodzinne „drzewa” (w rzeczywistości są to pełne wykresy, w tym cykle), istnieje miła anegdota:

Poślubiłem wdowę, która miała dorosłą córkę. Mój ojciec, który często nas odwiedzał, zakochał się w mojej pasierbicy i poślubił ją. W rezultacie mój ojciec stał się moim synem, a moja córka stała się moją matką. Jakiś czas później dałem mojej żonie syna, który był bratem mojego ojca i mojego wuja. Żona mojego ojca (która jest również moją córką i matką) ma syna. W rezultacie mam brata i wnuka w tej samej osobie. Moja żona jest teraz moją babcią, ponieważ jest matką mojej matki. Jestem więc mężem mojej żony, a jednocześnie wnukiem mojej żony. Innymi słowy, jestem moim dziadkiem.

Sprawa staje się jeszcze bardziej dziwna, jeśli weźmie się pod uwagę surogaty lub „rozmyte ojcostwo”.

Jak sobie z tym poradzić

Zdefiniuj cykle jako poza zakresem

Możesz zdecydować, że twoje oprogramowanie nie powinno obsługiwać tak rzadkich przypadków. W takim przypadku użytkownik powinien użyć innego produktu. Dzięki temu radzenie sobie z najczęstszymi przypadkami jest znacznie bardziej niezawodne, ponieważ można zachować więcej asercji i prostszy model danych.

W takim przypadku dodaj do oprogramowania kilka dobrych funkcji importu i eksportu, aby w razie potrzeby użytkownik mógł łatwo migrować do innego produktu.

Zezwalaj na ręczne relacje

Możesz zezwolić użytkownikowi na dodanie relacji ręcznych. Relacje te nie są „pierwszorzędnymi obywatelami”, tzn. Oprogramowanie traktuje ich takimi, jakimi są, nie sprawdza ich i nie obsługuje ich w głównym modelu danych.

Użytkownik może następnie obsługiwać rzadkie przypadki ręcznie. Twój model danych nadal będzie dość prosty, a twoje twierdzenia przetrwają.

Uważaj na relacje manualne. Istnieje pokusa, aby uczynić je całkowicie konfigurowalnymi, a tym samym stworzyć w pełni konfigurowalny model danych. To nie zadziała: Twoje oprogramowanie nie skaluje się, dostaniesz dziwne błędy i ostatecznie interfejs użytkownika stanie się bezużyteczny. Ten anty-wzór nazywa się „miękkim kodowaniem” , a „Daily WTF” jest tego pełen.

Uelastycznij model danych, pomiń twierdzenia, testuj niezmienniki

Ostatnim rozwiązaniem byłoby uelastycznienie modelu danych. Będziesz musiał pominąć prawie wszystkie stwierdzenia i oprzeć swój model danych na w pełni rozwiniętym wykresie. Jak pokazuje powyższy przykład, łatwo jest być własnym dziadkiem, więc możesz nawet mieć cykle.

W takim przypadku powinieneś dokładnie przetestować swoje oprogramowanie. Trzeba było pominąć prawie wszystkie twierdzenia, więc jest spora szansa na dodatkowe błędy.

Użyj generatora danych testowych, aby sprawdzić nietypowe przypadki testowe. Istnieje szybki biblioteki wyboru dla Haskell , Erlang lub C . W Javie / Scali są ScalaCheck i Nyaya . Jednym z pomysłów testowych może być symulacja losowej populacji, niech krzyżuje się losowo, a następnie pozwól oprogramowaniu najpierw zaimportować, a następnie wyeksportować wynik. Oczekuje się, że wszystkie połączenia na wyjściu znajdują się również na wejściu i odwrotnie.

Przypadek, w którym właściwość pozostaje taka sama, nazywa się niezmiennikiem. W tym przypadku niezmiennikiem jest zestaw „romantycznych relacji” między osobami w symulowanej populacji. Spróbuj znaleźć jak najwięcej niezmienników i przetestuj je losowo generowanymi danymi. Niezmienniki mogą być funkcjonalne, np .:

• wujek pozostaje wujem, nawet jeśli dodasz więcej „romantycznych relacji”
• każde dziecko ma rodzica
• populacja z dwoma pokoleniami ma co najmniej jednego dziadka

Lub mogą być techniczne:

• Twoje oprogramowanie nie ulegnie awarii na wykresie do 10 miliardów członków (bez względu na liczbę połączeń)
• Twoje oprogramowanie skaluje się z O (liczba węzłów) i O (liczba krawędzi ^ 2)
• Twoje oprogramowanie może zapisać i ponownie załadować każdy wykres rodzinny do 10 miliardów członków

Uruchamiając symulowane testy, znajdziesz wiele dziwnych przypadków narożnych. Naprawienie ich zajmie dużo czasu. Ponadto stracisz wiele optymalizacji, twoje oprogramowanie będzie działało znacznie wolniej. Musisz zdecydować, czy warto i czy leży to w zakresie twojego oprogramowania.

Zamiast usuwać wszystkie twierdzenia, powinieneś nadal sprawdzać, czy dana osoba jest jego własnym rodzicem lub inne niemożliwe sytuacje i przedstawiać błąd. Może wydaje ostrzeżenie, jeśli jest mało prawdopodobne, aby użytkownik mógł nadal wykryć typowe błędy wejściowe, ale zadziała, jeśli wszystko będzie poprawnie.

Chciałbym przechowywać dane w wektorze ze stałą liczbą całkowitą dla każdej osoby i przechowywać rodziców i dzieci w obiektach osobistych, gdzie wspomniana liczba całkowita jest indeksem wektora. Byłoby to dość szybkie przejście między pokoleniami (ale powolne w przypadku takich rzeczy jak wyszukiwanie nazw). Obiekty byłyby w kolejności, w której zostały utworzone.

Zduplikuj ojca (lub użyj dowiązania symbolicznego / referencyjnego).

Na przykład, jeśli używasz hierarchicznej bazy danych:

$ #each person node has two nodes representing its parents.
$ mkdir Family
$ mkdir Family/Son
$ mkdir Family/Son/Daughter
$ mkdir Family/Son/Father
$ mkdir Family/Son/Daughter/Father
$ ln -s Family/Son/Daughter/Father Family/Son/Father
$ mkdir Family/Son/Daughter/Wife
$ tree Family
Family
└── Son
    ├── Daughter
    │   ├── Father
    │   └── Wife
    └── Father -> Family/Son/Daughter/Father

4 directories, 1 file