Pertanyaan Siklus dalam perangkat lunak pohon keluarga


Saya adalah pengembang dari beberapa perangkat lunak pohon keluarga (ditulis dalam C ++ dan Qt). Saya tidak punya masalah sampai salah satu pelanggan saya mengirimkan laporan bug kepada saya. Masalahnya adalah bahwa pelanggan memiliki dua anak dengan putri mereka sendiri, dan, sebagai akibatnya, dia tidak dapat menggunakan perangkat lunak saya karena kesalahan.

Kesalahan tersebut adalah hasil dari berbagai asersi dan invariant saya tentang grafik keluarga yang sedang diproses (misalnya, setelah berjalan satu siklus, program menyatakan bahwa X tidak dapat menjadi ayah dan kakek Y).

Bagaimana saya bisa menyelesaikan kesalahan tersebut tanpa menghapus semua pernyataan data?


1594
2018-05-28 18:39


asal


Jawaban:


Tampaknya Anda (dan / atau perusahaan Anda) memiliki kesalahpahaman mendasar tentang apa yang seharusnya menjadi pohon keluarga.

Biarkan saya mengklarifikasi, saya juga bekerja untuk perusahaan yang memiliki (sebagai salah satu produknya) pohon keluarga dalam portofolionya, dan kami telah berjuang dengan masalah serupa.

Masalahnya, dalam kasus kami, dan saya menganggap kasus Anda juga, berasal dari GEDCOM format yang sangat berpendirian tentang apa yang seharusnya menjadi keluarga. Namun format ini mengandung beberapa kesalahpahaman yang parah tentang seperti apa pohon keluarga itu sebenarnya.

GEDCOM memiliki banyak masalah, seperti ketidaksesuaian dengan hubungan seks yang sama, incest, dll ... Yang dalam kehidupan nyata lebih sering terjadi daripada yang Anda bayangkan (terutama ketika kembali ke masa 1700-1800).

Kami telah mencontoh pohon keluarga kami dengan apa yang terjadi di dunia nyata: Acara (misalnya, kelahiran, pernikahan, pertunangan, perserikatan, kematian, adopsi, dll.). Kami tidak menempatkan batasan pada ini, kecuali yang secara logis tidak mungkin (misalnya, seseorang tidak bisa menjadi orang tua sendiri, hubungan membutuhkan dua individu, dll ...)

Kurangnya validasi memberi kita solusi "dunia nyata", lebih sederhana, dan lebih fleksibel.

Untuk kasus spesifik ini, saya menyarankan untuk menghapus pernyataan yang tidak berlaku secara universal.

Untuk menampilkan masalah (yang akan muncul) saya akan menyarankan menggambar simpul yang sama sebanyak yang diperlukan, mengisyaratkan duplikasi dengan menerangi semua salinan untuk memilih salah satu dari mereka.


727
2018-06-01 08:25



Tenangkan pernyataan Anda.

Bukan dengan mengubah aturan, yang kemungkinan besar sangat membantu 99,9% pelanggan Anda dalam menangkap kesalahan dalam memasukkan data mereka.

Sebaliknya, ubah dari kesalahan "tidak dapat menambahkan hubungan" ke peringatan dengan "tambahkan saja".


564
2018-05-28 19:20



Inilah masalah dengan pohon keluarga: mereka bukan pohon. Mereka diarahkan grafik asiklik atau DAG. Jika saya memahami prinsip-prinsip biologi reproduksi manusia dengan benar, tidak akan ada siklus.

Sejauh yang saya tahu, bahkan orang Kristen menerima pernikahan (dan dengan demikian anak-anak) di antara sepupu, yang akan mengubah pohon keluarga menjadi DAG keluarga.

Moral dari cerita ini adalah: memilih struktur data yang tepat.


224
2018-06-01 09:58



Saya rasa Anda memiliki nilai yang secara unik mengidentifikasi seseorang yang dapat Anda gunakan sebagai dasar cek Anda.

Ini yang rumit. Dengan asumsi Anda ingin menjaga struktur pohon, saya sarankan ini:

Asumsikan ini: A memiliki anak dengan putrinya sendiri.

A menambahkan dirinya ke program sebagai A dan sebagai B. Setelah berperan sebagai ayah, mari kita menyebutnya pacar.

Tambah sebuah is_same_for_out() fungsi yang memberi tahu output yang menghasilkan bagian dari program Anda yang akan dilakukan semua tautan B internal harus pergi ke A pada presentasi data.

Ini akan membuat beberapa pekerjaan tambahan untuk pengguna, tapi saya kira IT akan relatif mudah untuk diterapkan dan dipelihara.

Bangunan dari itu, Anda dapat bekerja pada kode synching A dan B untuk menghindari inkonsistensi.

Solusi ini tentu saja tidak sempurna, tetapi merupakan pendekatan pertama.


115
2018-05-28 18:50



Anda harus fokus apa yang benar-benar membuat nilai untuk perangkat lunak Anda. Apakah waktu yang dihabiskan untuk membuatnya bekerja untuk SATU konsumen sepadan dengan harga lisensi? Mungkin tidak.

Saya menyarankan Anda untuk meminta maaf kepada pelanggan ini, beri tahu dia bahwa situasinya berada di luar ruang lingkup perangkat lunak Anda dan berikan pengembalian dana kepadanya.


84
2018-06-01 08:51



Anda harus sudah mengaturnya Atreides keluarga (baik modern, Bukit pasir, atau kuno, Oedipus Rex) sebagai kasus pengujian. Anda tidak menemukan bug dengan menggunakan data yang disanitasi sebagai test case.


79
2018-06-01 16:10



Ini adalah salah satu alasan mengapa bahasa seperti "Go" tidak memiliki asersi. Mereka digunakan untuk menangani kasus-kasus yang mungkin tidak Anda pikirkan, terlalu sering. Anda seharusnya hanya menegaskan hal yang tidak mungkin, tidak hanya tidak mungkin. Melakukan yang terakhir adalah apa yang memberi pernyataan reputasi yang buruk. Setiap kali Anda mengetik assert(, pergi selama sepuluh menit dan sangat Pikirkan tentang itu.

Dalam kasus Anda yang sangat mengganggu, hal itu dapat dibayangkan dan mengerikan bahwa pernyataan semacam itu akan menjadi palsu dalam keadaan yang jarang terjadi tetapi mungkin. Oleh karena itu, tangani di aplikasi Anda, jika hanya untuk mengatakan "Perangkat lunak ini tidak dirancang untuk menangani skenario yang Anda sajikan".

Menegaskan bahwa kakekmu yang hebat, hebat, dan hebat sebagai ayahmu adalah hal yang mustahil untuk dilakukan.

Jika saya bekerja untuk perusahaan penguji yang dipekerjakan untuk menguji perangkat lunak Anda, tentu saja saya akan mempresentasikan skenario itu. Mengapa? Setiap 'pengguna' remaja akan melakukan hal yang sama persis dan nikmati dalam 'laporan bug' yang dihasilkan.


59
2018-06-01 06:10



Saya tidak suka mengomentari situasi yang kacau ini, tetapi cara termudah untuk tidak mengubah semua invariants Anda adalah dengan menciptakan phantom vertex di grafik Anda yang bertindak sebagai proxy kembali ke ayah incest.


41
2018-05-28 18:55



Jadi, saya telah melakukan beberapa pekerjaan pada perangkat lunak pohon keluarga. Saya pikir masalah yang Anda coba pecahkan adalah bahwa Anda harus bisa berjalan di pohon tanpa mengalami loop yang tak terbatas - dengan kata lain, pohon itu harus bersifat siklus.

Namun, sepertinya Anda menegaskan bahwa hanya ada satu jalur antara seseorang dan salah satu leluhur mereka. Itu akan menjamin bahwa tidak ada siklus, tetapi terlalu ketat. Secara biologis, keturunan adalah a diarahkan grafik asiklik(DAG). Kasus yang Anda miliki tentu saja merupakan kasus yang merosot, tetapi hal semacam itu sering terjadi di pohon yang lebih besar.

Misalnya, jika Anda melihat nenek moyang kedua yang Anda miliki pada generasi n, jika tidak ada tumpang tindih, maka Anda akan memiliki lebih banyak leluhur di 1000 AD daripada ada orang yang hidup. Jadi, harus ada tumpang tindih.

Namun, Anda juga cenderung mendapatkan siklus yang tidak valid, hanya data buruk. Jika Anda melintasi pohon, maka siklus harus ditangani. Anda dapat melakukan ini di masing-masing algoritma, atau pada beban. Saya melakukannya pada beban.

Menemukan siklus yang benar dalam pohon dapat dilakukan dengan beberapa cara. Cara yang salah adalah menandai setiap leluhur dari individu tertentu, dan ketika melintasi, jika orang yang akan Anda tuju berikutnya sudah ditandai, lalu potong tautannya. Ini akan memutuskan hubungan yang berpotensi akurat. Cara yang benar untuk melakukannya adalah mulai dari masing-masing individu, dan tandai setiap leluhur dengan jalan menuju individu tersebut. Jika jalur baru berisi jalur saat ini sebagai sub jalan, maka itu adalah siklus, dan harus diputus. Anda dapat menyimpan jalur sebagai vektor <bool> (MFMF, MFFFMF, dll.) Yang membuat perbandingan dan penyimpanan sangat cepat.

Ada beberapa cara lain untuk mendeteksi siklus, seperti mengirim dua iterator dan melihat apakah mereka pernah bertabrakan dengan pengujian subset, tetapi saya akhirnya menggunakan metode penyimpanan lokal.

Perhatikan juga bahwa Anda tidak perlu benar-benar memutuskan tautan, Anda dapat mengubahnya dari tautan normal ke tautan 'lemah', yang tidak diikuti oleh beberapa algoritme Anda. Anda juga akan ingin berhati-hati ketika memilih tautan yang ditandai sebagai lemah; kadang-kadang Anda dapat mencari tahu di mana siklus harus dipecahkan dengan melihat informasi tanggal lahir, tetapi sering kali Anda tidak dapat menemukan apa pun karena begitu banyak data yang hilang.


37
2018-06-01 18:39