Kalkulator Pengurutan Topologi

Tentang Kalkulator Pengurutan Topologi

Kalkulator Pengurutan Topologi menghitung pengurutan linier dari simpul-simpul dalam graf asiklik terarah (DAG) sedemikian rupa sehingga setiap tepi terarah dari u ke v menempatkan u sebelum v. Masukkan graf Anda sebagai daftar tepi atau daftar adjasensi dan alat ini akan mengembalikan urutan topologi menggunakan algoritma Kahn atau DFS post-order, mendeteksi siklus (dengan jalur siklus yang tepat), mengelompokkan tugas ke dalam lapisan eksekusi paralel, menghitung jumlah urutan yang valid, dan menganimasikan setiap langkah pada graf interaktif.

Apa itu pengurutan topologi?

Diberikan sebuah graf terarah G = (V, E), pengurutan topologi adalah pengaturan linier v₁, v₂, …, vₙ dari simpul-simpulnya sedemikian rupa sehingga untuk setiap tepi terarah (u → v), u muncul sebelum v dalam pengaturan tersebut. Pengurutan topologi ada jika dan hanya jika graf tersebut tidak memiliki siklus terarah — artinya, graf tersebut adalah sebuah DAG. Pengurutan ini jarang bersifat unik: sebuah graf dapat memiliki banyak pengurutan topologi yang valid ketika beberapa simpul memiliki in-degree nol pada saat yang sama.

Algoritma yang digunakan oleh kalkulator ini

Algoritma Kahn (berbasis BFS, 1962)

Algoritma Kahn adalah pengurutan topologi yang paling intuitif. Pada setiap langkah, algoritma ini memilih simpul dengan in-degree nol (tidak ada tepi masuk), menambahkannya ke hasil, dan "menghapus"-nya dari graf dengan mengurangi in-degree dari setiap penerusnya. Ketika beberapa simpul memiliki in-degree nol, penyelesaian kebuntuan dapat menggunakan min-heap (memberikan urutan terkecil secara leksikografis) atau antrean FIFO (memberikan urutan input). Algoritma Kahn berjalan dalam waktu O(|V| + |E|) dan berfungsi ganda sebagai detektor siklus: jika ada simpul yang masih memiliki in-degree > 0 setelah antrean kosong, graf tersebut memiliki siklus.

DFS post-order (Tarjan, 1976)

Algoritma DFS menjalankan pencarian depth-first, dan setiap kali sebuah simpul selesai (artinya semua penerusnya telah dieksplorasi sepenuhnya), simpul tersebut dimasukkan ke dalam tumpukan (stack). Membalikkan tumpukan di akhir menghasilkan urutan topologi yang valid. Deteksi siklus terjadi secara alami: menemukan simpul yang masih dalam proses (ditandai ABU-ABU) berarti tepi balik telah ditemukan, sehingga graf tersebut bukan DAG. DFS post-order juga berjalan dalam waktu O(|V| + |E|).

Lapisan eksekusi paralel

Tampilan berlapis dari sebuah DAG membagi simpul-simpulnya menjadi level-level sedemikian rupa sehingga setiap tepi mengarah dari level bernomor lebih rendah ke level yang lebih tinggi. Simpul dalam lapisan yang sama independen satu sama lain, sehingga dapat dieksekusi secara paralel. Jumlah lapisan sama dengan panjang jalur terpanjang ditambah satu — ini adalah jalur kritis dari DAG, jumlah minimum putaran sekuensial yang diperlukan untuk menyelesaikan semua tugas bahkan dengan paralelisme tak terbatas. Kalkulator ini menghasilkan tampilan lapisan secara otomatis setiap kali inputnya adalah sebuah DAG.

Deteksi siklus

Jika graf mengandung siklus terarah, pengurutan topologi tidak mungkin dilakukan. Kalkulator kami melaporkan jalur siklus yang tepat (misalnya A → B → C → A) dan menyorot tepi siklus dengan warna merah pada visualisasi. Menghapus satu pun tepi pada siklus sudah cukup untuk memulihkan sifat asiklik.

Format input

Daftar tepi (Edge list)

Tulis setiap tepi terarah sebagai sumber -> target, dipisahkan oleh koma atau baris baru. Varian panah yang diterima: ->, →, =>, -->, :. Anda juga dapat merantai tepi: A -> B -> C adalah singkatan untuk A->B dan B->C. Label simpul dapat berupa huruf, angka, garis bawah, tanda hubung, dan titik.

Daftar adjasensi (Adjacency list)

Tulis setiap simpul, titik dua, dan penerus langsungnya (simpul yang ditunjuknya). Simpul tanpa penerus tetap memerlukan barisnya sendiri, seperti D:.

Cara menggunakan kalkulator ini

1. Pilih format: Beralih antara daftar tepi dan daftar adjasensi dengan tombol radio.
2. Masukkan graf: Tempel data Anda atau klik salah satu contoh cepat (urutan berpakaian, prasyarat kursus, target build, graf dengan siklus, dan lainnya).
3. Pilih algoritma: Kahn leksikografis untuk urutan unik yang dapat diproduksi ulang; urutan input untuk mempertahankan urutan input; DFS post-order untuk metode depth-first klasik; atau Tampilkan semua untuk melihat setiap urutan berdampingan.
4. Klik "Urutkan Secara Topologi": Urutan, deteksi siklus, tampilan lapisan, panjang jalur kritis, total jumlah pengurutan yang valid, dan graf interaktif akan muncul di bawah.
5. Eksplorasi: Tekan Putar untuk melihat setiap simpul dikeluarkan langkah demi langkah. Badge in-degree akan diperbarui secara langsung. Geser simpul mana pun untuk mengatur ulang tata letak.

Aplikasi dunia nyata

Sistem build dan compiler

Alat seperti make, Bazel, Gradle, dan npm mengurutkan target build mereka secara topologi sehingga setiap target dikompilasi hanya setelah semua dependensinya selesai. Siklus dalam graf dependensi biasanya dilaporkan sebagai kesalahan fatal — sistem build tidak dapat menentukan dari mana harus memulai.

Penjadwalan tugas

Manajer proyek menggunakan DAG untuk mencatat dependensi tugas. Pengurutan topologi memberikan urutan eksekusi yang valid, dan tampilan lapisan memberikan jumlah minimum putaran di bawah paralelisme tak terbatas. Rantai terpanjang adalah jalur kritis yang menentukan durasi proyek.

Perencanaan prasyarat mata kuliah

Katalog kursus universitas adalah sebuah DAG: tepi adalah hubungan prasyarat. Urutan topologi adalah rencana studi yang valid, dan lapisan-lapisan memberi tahu mahasiswa kumpulan kursus mana yang dapat mereka ambil secara paralel selama setiap semester.

Penghitungan ulang spreadsheet

Ketika sebuah sel berubah, spreadsheet harus menghitung ulang setiap sel hilir dalam urutan dependensi — sebuah pengurutan topologi dari DAG dependensi sel. Referensi melingkar (siklus) akan ditolak oleh aplikasi.

Manajer paket dan pemuat plugin

Apt, pip, Homebrew, Maven, dan banyak kerangka kerja plugin menyelesaikan urutan instalasi atau pemuatan dengan mengurutkan DAG dependensi mereka secara topologi.

Resolusi simbol dan penjadwalan instruksi

Compiler menggunakan pengurutan topologi untuk mengurutkan deklarasi, dan CPU menggunakan DAG dependensi data untuk menjadwalkan instruksi dalam buffer urutan ulang tanpa melanggar hazard data.

Menghitung pengurutan topologi

Untuk sebuah DAG dengan n simpul, jumlah pengurutan topologi valid yang berbeda dapat berkisar dari 1 (untuk rantai yang terurut total) hingga n! (untuk graf tanpa tepi). Menghitung jumlah persisnya secara umum adalah masalah #P-complete, tetapi untuk graf hingga 16 simpul, kalkulator ini menghitungnya menggunakan formulasi bitmask dynamic-programming: f(S) = Σ f(S ∪ {v}) untuk semua v ∉ S yang pendahulunya semuanya ada di S.

Kompleksitas dan performa

• Waktu: Baik algoritma Kahn maupun DFS post-order berjalan dalam O(|V| + |E|) — linier terhadap ukuran graf.
• Ruang: O(|V|) untuk pelacakan in-degree dan urutan output, ditambah O(|V| + |E|) untuk struktur adjasensi.
• Deteksi siklus: Terpasang dalam kedua algoritma. Kahn mendeteksi siklus ketika |output| < |V|; DFS mendeteksinya ketika tepi balik (tetangga ABU-ABU) ditemukan.
• Batasan dalam alat ini: hingga 80 simpul dan 800 tepi untuk visualisasi interaktif. Penghitungan urutan dibatasi hingga 16 simpul.

Pertanyaan yang sering diajukan

Apa itu pengurutan topologi?

Pengurutan topologi dari graf asiklik terarah adalah pengurutan linier dari simpul-simpulnya sedemikian rupa sehingga setiap tepi terarah dari u ke v menempatkan u sebelum v. Ini mewakili urutan yang valid untuk memproses tugas-tugas yang menghormati dependensi mereka.

Algoritma mana yang digunakan kalkulator ini?

Kalkulator ini menjalankan algoritma Kahn dan DFS post-order. Algoritma Kahn berulang kali menghapus simpul dengan in-degree nol dan mengurangi in-degree penerusnya. DFS post-order menjalankan pencarian depth-first dan membalikkan urutan selesai. Keduanya berjalan dalam waktu O(|V| + |E|).

Bagaimana jika graf saya memiliki siklus?

Graf dengan siklus terarah tidak memiliki pengurutan topologi. Kalkulator mendeteksi siklus tersebut, menyorotnya dengan warna merah pada visualisasi, dan melaporkan jalur siklus yang tepat sehingga Anda dapat melihat tepi mana yang harus dihapus untuk menjadikan graf tersebut sebuah DAG.

Apa itu urutan topologi terkecil secara leksikografis?

Ketika banyak pengurutan topologi yang valid, yang terkecil secara leksikografis diperoleh dengan selalu memilih simpul terkecil secara alfabetis yang in-degree-nya nol pada setiap langkah. Mode default Kahn pada kalkulator ini mengembalikan urutan unik ini, yang stabil dan mudah diproduksi ulang.

Apa itu tampilan lapisan atau level?

Tampilan lapisan mengelompokkan simpul berdasarkan panjang jalur terpanjang dari sumber mana pun. Simpul dalam lapisan yang sama tidak memiliki dependensi di antara mereka, sehingga dapat dijalankan secara paralel. Jumlah lapisan sama dengan rantai dependensi terpanjang ditambah satu dan memberikan jumlah putaran paralel minimum yang diperlukan untuk menyelesaikan semua tugas.

Dapatkah sebuah graf memiliki banyak pengurutan topologi yang valid?

Ya. Jika pada langkah apa pun algoritma Kahn memiliki beberapa simpul dengan in-degree nol, salah satunya dapat dipilih berikutnya. Kalkulator ini menghitung jumlah persis pengurutan topologi yang berbeda untuk graf hingga 16 simpul.

Apa perbedaan antara algoritma Kahn dan DFS post-order?

Kahn bekerja secara top-down: ia berulang kali memilih sumber (in-degree 0) dan mengeluarkannya terlebih dahulu. DFS post-order bekerja secara bottom-up: ia menyelesaikan muara (sink) terlebih dahulu dan menambahkannya ke depan urutan. Keduanya adalah O(|V| + |E|) dan menghasilkan pengurutan topologi yang valid, tetapi biasanya berbeda. Kahn lebih mudah diparalelkan dan diadaptasi untuk pengurutan leksikografis; DFS lebih mudah digabungkan dengan analisis berbasis DFS lainnya seperti komponen terhubung kuat.

Berapa ukuran graf maksimum yang didukung alat ini?

Kalkulator mendukung hingga 80 simpul dan 800 tepi. Penghitungan jumlah total pengurutan topologi yang valid dibatasi hingga 16 simpul karena masalahnya adalah #P-complete dan ruang status tumbuh sebesar 2ⁿ. Visualisasi interaktif dan animasi algoritma dapat diskalakan dengan lancar hingga ukuran penuh.

Bacaan Selanjutnya

• Topological sorting — Wikipedia
• Directed acyclic graph — Wikipedia
• Depth-first search — Wikipedia
• Critical path method — Wikipedia
• Strongly connected component — Wikipedia