Penyortiran "topologis" grafik dengan siklus

Judul lengkap dari artikel seharusnya adalah "Penyortiran" topologis "berkelanjutan dari grafik dengan siklus dalam O(|V| + |e| log |e|) dalam waktu dan O(|V|) dalam memori tanpa rekursi," tetapi saya diberitahu apa itu berlebihan.

Penafian: Saya seorang programmer, bukan ahli matematika, jadi bahasa yang tidak akurat mungkin ada di beberapa tempat, di mana Anda bisa dan harus menendang.

Esensi dari tugas

Saya akan menganalisis kata-kata dari masalah, solusi yang ingin saya bagikan, di beberapa bagian.

Penyortiran topologis adalah urutan simpul dari grafik asiklik terarah di mana masing-masing simpul dari mana tepi keluar lebih awal dari simpul di mana tepi ini masuk. Ada dua nuansa penting di sini: grafik dapat memiliki lebih dari satu pemesanan seperti itu dan hanya berlaku untuk grafik asiklik . Matematikawan tidak peduli, tetapi programmer terkadang menginginkan determinisme dan sedikit lebih dari "Maaf, Anda memiliki siklus di sini, Anda tidak akan memiliki penyortiran."

Oleh karena itu, kami menambahkan persyaratan stabilitas : sepasang simpul, urutan di antaranya tidak ditentukan oleh tepi grafik, harus ditentukan oleh urutan di mana simpul-simpul ini sampai pada input algoritma. Akibatnya, pengulangan yang berulang tidak akan mengubah urutan simpul.

Dengan kurangnya rekursi, semuanya sederhana, komputer secara signifikan lebih lemah daripada mesin Turing dan memori (dan terutama tumpukan) telah terbatas. Oleh karena itu, dalam pemrograman terapan, biasanya algoritma berulang lebih disukai daripada yang rekursif.

Dan akhirnya, saya akan mendefinisikan apa yang saya sebut pengurutan "topologis" jika ada siklus dalam grafik. Ini adalah urutan simpul, yang bertepatan dengan pemilahan topologi yang sebenarnya, jika masing-masing siklus diganti oleh satu simpul, dan simpul siklus itu sendiri, sesuai dengan persyaratan stabilitas, terletak relatif satu sama lain dalam urutan asli.

Dan sekarang dengan semua sampah ini kami akan mencoba untuk lepas landas. Saya akan melakukan semuanya dalam kerangka waktu dan batasan memori yang ditunjukkan di awal posting.

Cari solusinya

Jika Anda melihat algoritma pengurutan topologi yang ada ( algoritma Kahn , pencarian dalam ), ternyata semuanya, jika ada siklus, katakan "Saya tidak bisa" dan berhenti bekerja.

Karenanya, mari kita lanjutkan dengan algoritma yang dapat melakukan sesuatu yang dapat dipahami dengan siklus. Sebagai contoh, temukan mereka. Di antara algoritma yang tercantum di Wikipedia untuk menemukan siklus dalam grafik , perhatian diberikan pada algoritma Taryan . Ini berisi komentar yang menarik bahwa, sebagai produk sampingan, algoritma menghasilkan penyortiran topologi terbalik dari grafik:

Sementara tidak ada yang istimewa tentang urutan node dalam setiap komponen yang terhubung kuat, satu sifat yang berguna dari algoritma adalah bahwa tidak ada komponen yang terhubung kuat akan diidentifikasi sebelum penggantinya. Oleh karena itu, urutan pengidentifikasian komponen yang terhubung kuat merupakan jenis topologi terbalik DAG yang dibentuk oleh komponen yang terhubung kuat .

Benar, algoritmanya bersifat rekursif dan tidak jelas apa yang dimilikinya dengan stabilitas, tetapi ini jelas merupakan gerakan ke arah yang benar. Pembacaan lebih dekat dari Wikipedia mengungkapkan referensi ke artikel Algoritma hemat-ruang untuk menemukan komponen yang sangat terhubung , yang ditulis oleh kawan David Pierce, di mana tidak hanya terdapat algoritma imperatif, tetapi juga mengurangi kebutuhan memori dibandingkan dengan klasik. Algoritma Tarjan. Bonusnya adalah implementasi dari algoritma di Jawa . Harus mengambil!


Jadi, kami memiliki daftar simpul pada input dan (terima kasih kepada Pierce) indeks tertentu dari komponen konektivitas kuat yang dimiliki oleh simpul ini pada output. Langkah selanjutnya adalah mengurutkan simpul secara stabil sesuai dengan nomor seri komponennya. Ada algoritma untuk tugas semacam itu, yang disebut penghitungan sortir , yang melakukan ini dalam waktu O(n) .

Dalam proses mengumpulkan algoritme menjadi tumpukan, ternyata fakta bahwa adalah wajar untuk memberikan penyortiran topologi terbalik untuk itu sebenarnya sangat luar dari Taryan - maka cabang-cabang tetangga dari grafik (tidak memiliki hubungan urutan di antara mereka) akan nomor mundur, maka potongan-potongan grafik tidak akan mundur. memiliki koneksi di antara mereka sendiri, ternyata berada dalam urutan terbalik ...

Jawabannya

Jadi solusi terakhir:

1. Kami menomori simpul dari daftar asli. O(|V|)
2. Kami mengurutkan tepi setiap simpul sesuai dengan jumlah simpul yang menjadi ujungnya. O(|e| log |e|)
3. Dengan menggunakan algoritma Pierce, kami menemukan dan menomori komponen koneksi yang kuat. O(|V|)
4. Dengan menggunakan pengurutan dengan menghitung, kami mengurutkan simpul berdasarkan jumlah komponen yang sangat terhubung yang mereka terima. O(|V|)

Kode GitHub, Java, domain publik . Dapat dicatat bahwa untuk memastikan stabilitas penyortiran, algoritma Pierce sedikit dimodifikasi dan memotong simpul dalam urutan terbalik.

Tapi kenapa ???

Dan sekarang latar belakangnya, mengapa semua ini dibutuhkan. Saat memuat / membongkar pustaka dinamis (.so), glibc perlu memutuskan untuk menginisialisasi variabel statis mana. Variabel tergantung satu sama lain, tergantung pada fungsi yang berbeda, dll. Secara umum, semua ini membentuk grafik di mana ada siklus dan yang harus disortir.

Sekali waktu, kode yang agak suboptimal yang melakukan tugas untuk O(n^2) terlibat dalam tugas ini. Dan secara umum, ini tidak terlalu mengganggu siapa pun, sampai pada tahun 2012 diketahui bahwa kode tersebut tidak berfungsi dengan benar dan dalam beberapa kasus salah.

Orang-orang kasar dari RedHat berpikir, berpikir dan mengacaukan beberapa siklus dari atas. Kasing bermasalah diperbaiki, tetapi algoritme mulai bekerja untuk O(n^3) , dan ini sudah menjadi nyata dan pada beberapa aplikasi mulai butuh beberapa puluh detik, yang merupakan bug pada 2013. Juga, penulis bug menemukan kasus di mana algoritma dengan O(n^3) juga salah . Dia menyarankan menggunakan algoritma Taryan, meskipun patch dengan koreksi belum pernah dirancang.

Dan waktu berlalu, glibc tanpa ampun melambat dan pada 2015 ada upaya lain untuk memperbaiki algoritme . Sayangnya, tidak berhasil, algoritma dipilih O(n^2) , selain membingungkan cabang-cabang grafik, di mana urutannya tidak ditentukan.

Hari ini adalah tahun 2019, glibc masih melambat. Menilai dari berapa banyak waktu yang saya perlukan untuk memperbaiki masalah, peluang saya untuk menyelesaikannya secara signifikan lebih rendah dari 100%. Ini semakin diperparah oleh fakta bahwa hal-hal terjadi di C, tanpa dukungan IDE, dalam kode gaya pengkodean GNU, pelari uji gila ("jika Anda ingin menjalankan tes lagi, cukup hapus file .out yang sesuai"). Dan agar glibc dapat melihat tambalan Anda, Anda harus melalui prosedur penetapan hak cipta , mengeluarkan tambalan dengan benar dan iblis tahu apa lagi. Oleh karena itu, untuk setidaknya menghapus masalah menciptakan suatu algoritma yang memecahkan masalah, posting ini ditulis.