Rozluźnij swoje twierdzenia.

Nie zmieniając zasad, które są najprawdopodobniej bardzo pomocne dla 99,9% Twoich klientów w wyłapywaniu błędów we wprowadzaniu swoich danych.

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

Oto problem z drzewami rodzinnymi: nie są drzewami. Są to kierowane grafy acykliczne lub dag. Jeśli dobrze zrozumiem Zasady biologii ludzkiego rozrodu, nie będzie żadnych cykli.

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

Morał tej historii brzmi: wybierz odpowiednie struktury danych.

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

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

A dodaje się do programu jako A i jako B. Raz w roli ojca, nazwijmy to Chłopakiem.

Dodaj is_same_for_out() funkcję, która mówi części generującej wyjście programu, że wszystkie linki idąc do B wewnętrznie powinno być idąc do A po prezentacji danych.

Spowoduje to dodatkową pracę dla użytkownika, ale myślę, że będzie 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.

Powinieneś skupić się na co naprawdę czyni wartość dla Twojego oprogramowania . Czy czas spędzony na tym, aby działał dla jednego konsumenta, jest wart ceny licencji ? Raczej nie.

Radzę przeprosić tego klienta, powiedzieć mu, że jego sytuacja jest poza zasięgiem twojego oprogramowania i wydać mu zwrot pieniędzy.

Powinieneś założyć rodzinę Atrydów (albo nowoczesną, Dune, lub starożytny, Edyp Rex ) jako przypadek testowy. Nie znajdziesz błędów, używając sanitized data jako przypadku testowego.

Jest to jeden z powodów, dla których języki takie jak "Go" nie mają twierdzeń. Są używane do obsługi spraw, o których prawdopodobnie nie myślałeś, zbyt często. należy tylko twierdzić niemożliwe, a nie po prostu mało prawdopodobne . Robienie tego drugiego jest tym, co daje twierdzeniom złą reputację. Za każdym razem, gdy wpisujesz assert(, odejdź na 10 minut inaprawdę pomyśl o tym.

W Twoim szczególnie niepokojącym przypadku, jest zarówno możliwe, jak i przerażające, że takie twierdzenie byłoby to fałszywe w rzadkich, ale możliwych okolicznościach. W związku z tym, obsługiwać go w aplikacji, choćby po to, aby powiedzieć "To oprogramowanie nie zostało zaprojektowane do obsługi scenariusza, który został przedstawiony".

Gdybym pracował dla firmy testującej, która została zatrudniona do testowania Twojego oprogramowania, oczywiście przedstawiłbym ten scenariusz. Dlaczego? Każdy młody, ale inteligentny "użytkownik" zrobi Dokładnie to samo i rozkoszuj się wynikowym 'raportem o błędzie'.

Nienawidzę komentować tak pokręconą sytuację, ale najprostszym sposobem, aby nie odmrozić wszystkich niezmienników, jest stworzenie widmowego wierzchołka w grafie, który działa jako proxy z powrotem do kazirodczego taty.

Więc, zrobiłem trochę pracy 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.

Jednak wygląda na to, że twierdzisz, że istnieje tylko jedna droga między osobą a jednym z ich przodków. To zagwarantuje, że nie ma cykli, ale jest zbyt rygorystyczne. Biologicznie rzecz biorąc, descendancy jest skierowany Graf acykliczny (DAG). Sprawa, którą masz, jest z pewnością zdegenerowana, 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, jeśli nie było nakładania się, to będziesz miał więcej przodków w 1000 r.n. e., niż ludzi żyjących. Więc musi się pokrywać.

Jednak, masz również tendencję do cykli, które są nieprawidłowe, tylko złe dane. Jeśli przemierzasz drzewo, musisz poradzić sobie z cyklami. Można to zrobić w każdym indywidualny algorytm lub przy obciążeniu. Zrobiłem to na obciążeniu.

Znalezienie prawdziwych cykli w drzewie można zrobić na kilka sposobów. Błędnym sposobem jest zaznaczenie każdego przodka z danej osoby, a podczas przechodzenia, jeśli osoba, do której idziesz, jest już zaznaczona, to odetnij link. Spowoduje to zerwanie potencjalnie dokładnych relacji. Poprawnym sposobem jest rozpoczęcie od każdego osobnika i oznaczenie każdego przodka ścieżką do tego osobnika. Jeśli nowa ścieżka zawiera bieżącą ścieżkę jako subpath, to jest cykl i powinien zostać przerwany. Ścieżki można zapisać jako wektor (MFMF, mfffmf, itd.) co sprawia, że porównanie 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 podzbiorowym, ale skończyło się na użyciu metody local storage.

Zauważ również, że nie musisz faktycznie odcinać linku, możesz po prostu zmienić go z normalnego linku na "słaby" link, który nie jest / align = "left" / Będziesz również chciał zachować ostrożność przy wyborze, który link oznaczyć jako słaby; czasami można dowiedzieć się, gdzie cykl powinien zostać przerwany, patrząc na informacje o dacie urodzenia, ale często nie można dowiedzieć się niczego, ponieważ tak wiele danych brakuje.

Kolejna udana poważna odpowiedź na głupie pytanie:

Prawdziwa odpowiedź brzmi: użyj odpowiedniej struktury danych. Ludzka Genealogia nie może być w pełni wyrażona za pomocą czystego drzewa bez cykli. Powinieneś użyć jakiegoś wykresu. Porozmawiaj również z antropologiem, zanim przejdziesz dalej, ponieważ istnieje wiele innych miejsc, podobnych błędów można by popełnić próbując modelować genealogię, nawet w najprostszym przypadku " zachodniego patriarchalnego małżeństwa monogamicznego."

Even if we chcesz zignorować lokalne relacje tabu, jak omówiono tutaj, istnieje wiele całkowicie legalnych i całkowicie nieoczekiwanych sposobów wprowadzenia 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, to jest powód, dla którego ludzie przeszli z tysięcy małych grup rodzinnych do 6 miliardów ludności na całym świecie. To nie może działać inaczej.

Naprawdę jest bardzo mało uniwersalne jeśli chodzi o genealogię, rodzinę i rodowód. Prawie każde surowe założenie dotyczące norm sugerujących, kim może być ciotka lub kto może się z kim ożenić, lub jak dzieci są legitymizowane w celu dziedziczenia, może być zdenerwowane 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ł" na drzewie genealogicznym jako poprzednika-osobę, a nie zakładać, że węzeł może być osobą-jedyną-i-jedyną.

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

Kilka odpowiedzi pokazało sposoby zachowania twierdzeń / niezmienników, ale wydaje się to być nadużyciem twierdzeń/niezmienników. Twierdzenia mają upewnić się, że coś, co powinno być prawdziwe, jest prawdą, a niezmienniki mają upewnić się, że coś, co nie powinno się zmienić, nie zmienia się.

Twierdzisz, że kazirodcze związki nie istnieją. Oczywiście one istnieją , więc twoje twierdzenie jest nieważne. Można obejść to twierdzenie, ale prawdziwy błąd jest w twierdzeniu siebie. Twierdzenie powinno zostać usunięte.

Twoje drzewo genealogiczne powinno używać relacji kierowanych. W ten sposób nie będziesz miał cyklu.

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

Sposób obsługi tego w widoku bez tworzenia niestandardowego widoku polega na traktowaniu cyklicznego rodzica jako" ducha". Innymi słowy, gdy osoba jest zarówno ojcem, jak i dziadkiem tej samej osoby, wtedy węzeł dziadka jest pokazywany normalnie, ale węzeł ojca jest renderowany jako węzeł "duch", który ma prostą Etykietę, taką jak ("patrz dziadek") i wskazuje na dziadka.

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

Najważniejszą rzeczą jest avoid creating a problem, więc uważam, że powinieneś użyć bezpośredniej relacji , Aby uniknąć cyklu.

Jak powiedział @markmywords, #include " fritzl.h".

Wreszcie muszę powiedzieć recheck your data structure. Może coś tam jest nie tak (może dwukierunkowa, połączona lista rozwiązuje twój problem).

Twierdzenia nie przetrwają rzeczywistości

Zazwyczaj twierdzenia nie przetrwają kontaktu z rzeczywistymi danymi. To część procesu inżynierii oprogramowania, aby zdecydować, z jakimi danymi chcesz się zajmować, a które są poza zakresem.

Wykresy rodziny cyklicznej

Jeśli chodzi o rodzinne "drzewa" (w rzeczywistości są to pełne wykresy, w tym cykle), jest fajna anegdota:

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

Jak sobie z tym poradzić

Zdefiniuj cykle jako poza zakresem

Możesz zdecydować, że Twoje oprogramowanie nie powinno radzić sobie z tak rzadkimi przypadkami. W takim przypadku Użytkownik powinien użyć innego produktu. To sprawia, że radzenie sobie z bardziej powszechnymi przypadkami jest znacznie bardziej solidne, ponieważ można zachować więcej twierdzeń i prostsze dane model.

W tym przypadku dodaj dobre funkcje importu i eksportu do oprogramowania, aby użytkownik mógł łatwo przenieść się do innego produktu, gdy jest to konieczne.

Zezwalaj na relacje ręczne

Możesz zezwolić użytkownikowi na dodawanie relacji ręcznych. Relacje te nie są "obywatelami pierwszej klasy", tzn. oprogramowanie przyjmuje je tak, jak jest, nie sprawdza ich i nie obsługuje ich w głównym modelu danych.

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

Spraw, aby twój model danych był bardziej elastyczny, pomiń twierdzenia, test niezmienników

W takim przypadku należy dokładnie przetestować oprogramowanie. Trzeba było pominąć prawie wszystkie twierdzenia, więc jest duża szansa na dodatkowe błędy.

Użyj danych testowych generator do sprawdzania nietypowych przypadków testowych. Istnieją biblioteki quick check dla Haskell, Erlang lub C . Dla Java / Scala istnieją ScalaCheck i Nyaya . Jednym z pomysłów testowych byłoby symulowanie losowej populacji, niech ona krzyżuje się losowo, a następnie niech oprogramowanie najpierw importuje, a następnie eksportuje wynik. Oczekiwanie byłoby, że wszystkie połączenia na wyjściu są również w wejściu i wersie vice.

Przypadek, w którym nieruchomość pozostaje to samo nazywa się niezmiennikiem. W tym przypadku niezmiennik jest zbiorem "romantycznych relacji" między jednostkami w symulowanej populacji. Spróbuj znaleźć jak najwięcej niezmienników i przetestować je za pomocą losowo wygenerowanych danych. Niezmienniki mogą być funkcjonalne, np.:

• wujek zostaje wujkiem, nawet jeśli dodasz więcej "romantycznych relacji"
• każde dziecko ma rodzica
• populacja Z dwoma pokoleniami ma co najmniej jednego pradziada

Lub oni może być techniczny:

• 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 rodziny do 10 miliardów członków

Przeprowadzając symulowane testy, znajdziesz wiele dziwnych przypadków narożnych. Naprawienie ich zajmie dużo czasu. Również stracisz wiele optymalizacji, Twój oprogramowanie będzie działać znacznie wolniej. Musisz zdecydować, czy warto i czy jest to w zakresie Twojego oprogramowania.

Zamiast usuwać wszystkie twierdzenia, powinieneś nadal sprawdzać, czy dana osoba jest jego rodzicem lub inne niemożliwe sytuacje i przedstawić błąd. Może wydać ostrzeżenie, jeśli jest mało prawdopodobne, aby użytkownik mógł nadal wykrywać typowe błędy wprowadzania, ale będzie działać, jeśli wszystko jest poprawne.

Chciałbym przechowywać dane w wektorze ze stałą liczbą całkowitą dla każdej osoby i przechowywać rodziców i dzieci w osobach, gdzie wspomniany int jest indeksem wektora. To byłoby dość szybko przejść między pokoleniami (ale powolne dla rzeczy takich jak wyszukiwanie nazw). Obiekty byłyby w kolejności, w jakiej zostały stworzone.

Duplikuj ojca (lub użyj dowiązania symbolicznego/referencji).

Na przykład, jeśli korzystasz z 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