Mengekstrak loop tanpa kunci dari grafik yang tidak diarahkan

Beberapa tahun yang lalu saya harus menyelami topik ini di tempat kerja. Googling, yang mengejutkan saya, saya tidak menemukan solusi yang siap pakai. Dan tetap saja, secara umum, tidak ada yang terlihat. Jadi saya harus mengembangkan tema dari awal.



Untuk memperjelas tentang apa ini, saya akan memberikan contoh yang paling sederhana.







Grafiknya sangat sederhana, dan untuk jenis grafik ini, mudah untuk membuat algoritme yang memilih siklus tanpa kunci (yaitu, siklus yang tidak memiliki persimpangan sendiri dan tidak dapat dipecah menjadi yang lebih kecil). Masalahnya adalah grafik bisa jauh lebih rumit, dan semua kasus harus dipertimbangkan. Melalui musyawarah, pengkodean, coba-coba, pada akhirnya, sebuah algoritma lahir yang sekarang berfungsi untuk kepentingan pencari teknik.



Deskripsi teks:

1. Untuk setiap simpul pada grafik, kita menemukan semua simpul yang berdekatan dan mulai membentuk sebuah siklus dengan bergerak menuju setiap simpul yang berdekatan secara bergantian.
2. Jika jumlah simpul yang berdekatan (tidak termasuk yang Anda masukkan) = 0, maka kita kembali, membentuk siklus ---> item 5
3. Jika jumlah simpul yang berdekatan (tidak termasuk yang Anda masukkan) sama dengan 1, maka kita ikut dengannya, membentuk siklus ---> item 5
4. ( , ) >=2, ( ), , ---> .5
5. — ? , ---> .2
6. , .
7. , , , .
8. , , ---> .1 ( )
9. Sekali lagi kita melalui siklus dan melihat cabang kiri darinya. Setelah menemukan cabang seperti itu, untuk masing-masing kami mengatur pencarian luas-pertama (atau kedalaman-pertama, tidak masalah). Jika pada saat yang sama kita berakhir di puncak siklus yang terbentuk (kecuali yang sekarang), maka kita menghentikan pembentukan siklus dan pergi ke ---> item 1
10. Kami menuliskan siklusnya, dan pergi untuk mencari yang baru ---> item 1

Pseudocode yang lebih besar:





Awalnya, grafik yang semakin canggih dibuat untuk menguji algoritme.



atau



, pada akhirnya, diuji pada semua grafik eksplorasi nyata seperti ini: Menurut



saya ini tidak optimal, tetapi saat ini (sudah sekitar 3 tahun) berfungsi tanpa kegagalan dan keluhan.



Saya tidak mengutip kodenya, hampir tidak ada orang yang tertarik padanya, dan akan sulit untuk mengeluarkan satu bagian, karena ini hanyalah satu bagian kecil dari pekerjaan.