~ TOPOLOGICAL SORTING ~

Di bidang ilmu komputer , semacam topologi atau urutan topologi dari graf berarah adalah urutan linear simpulnya sehingga untuk setiap tepi yang diarahkan uv dari simpul u ke simpul v , u datang sebelum v dalam pemesanan. Misalnya, simpul grafik dapat mewakili tugas yang harus dilakukan, dan ujung-ujungnya mungkin merupakan kendala yang harus dilakukan satu tugas sebelum yang lain; Dalam aplikasi ini, pemesanan topologi hanyalah urutan yang valid untuk tugas. Pemesanan topologis dimungkinkan jika dan hanya jika grafik tidak memiliki siklus terarah , yaitu jika merupakan grafik asiklik terarah (DAG). Setiap DAG memiliki paling sedikit satu pemesanan topologi, dan algoritma dikenal untuk menyusun urutan topologi setiap DAG dalam waktu linier .

Contoh

Aplikasi penyortiran topologi kanonik adalah penjadwalan urutan pekerjaan atau tugas berdasarkan ketergantungan mereka. Pekerjaan diwakili oleh simpul, dan ada tepi dari x ke y jika pekerjaan x harus diselesaikan sebelum pekerjaan y dapat dimulai (misalnya saat mencuci pakaian, mesin cuci harus selesai sebelum kita meletakkan pakaian di pengering) . Kemudian, semacam topologi memberi perintah untuk melakukan pekerjaan. Aplikasi algoritma sortasi topologi yang terkait erat pertama kali dipelajari pada awal 1960an dalam konteks teknik PERT untuk penjadwalan dalam manajemen proyek ( Jarnagin 1960 ); Dalam aplikasi ini, simpul grafik mewakili tonggak sebuah proyek, dan ujung-ujungnya mewakili tugas yang harus dilakukan antara satu tonggak sejarah dan yang lainnya. Penyortiran topologi membentuk dasar algoritma linier untuk menemukan jalur kritis proyek, urutan tonggak dan tugas yang mengendalikan panjang keseluruhan jadwal proyek.
Dalam ilmu komputer, aplikasi jenis ini muncul dalam penjadwalan instruksi , memesan evaluasi sel formula saat menghitung ulang nilai rumus di spreadsheet , sintesis logika , menentukan urutan tugas kompilasi untuk dilakukan di makefiles , serialisasi data, dan penghilangan dependensi simbol pada penghubung . Hal ini juga digunakan untuk memutuskan di mana untuk memuat tabel dengan kunci asing di database.

Grafik yang ditunjukkan ke kiri memiliki banyak jenis topologi yang valid, termasuk:

5, 7, 3, 11, 8, 2, 9, 10 (visual kiri-ke-kanan, atas-ke-bawah)
3, 5, 7, 8, 11, 2, 9, 10 (simpul terkecil yang tersedia pertama)
5, 7, 3, 8, 11, 10, 9, 2 (sedikit tepinya dulu)
7, 5, 11, 3, 10, 8, 9, 2 (simpul yang tersedia dengan nomor terbesar terlebih dahulu)
5, 7, 11, 2, 3, 8, 9, 10 (mencoba dari atas ke bawah, kiri ke kanan)
3, 7, 8, 5, 11, 10, 2, 9 (sewenang-wenang)

Algoritma

Algoritma yang biasa untuk sortasi topologi memiliki waktu berjalan linier dalam jumlah simpul ditambah jumlah sisi, asimtotik,

HAI (| V | + | E |)

{\ displaystyle O (\ left | {V} \ right | + \ left | {E} \ right |)}

O (\ left | {V} \ right | + \ left | {E} \ right |)

Algoritma Kahn

Salah satu algoritma ini, yang pertama kali dideskripsikan oleh Kahn (1962) , bekerja dengan memilih simpul dalam urutan yang sama dengan jenis topologi akhir. Pertama, cari daftar "start nodes" yang tidak memiliki sisi yang masuk dan masukkan ke dalam satu set S; setidaknya satu simpul tersebut harus ada dalam grafik asiklik yang tidak kosong. Kemudian:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

Jika grafik adalah DAG , solusi akan terkandung dalam daftar L (solusinya belum tentu unik).  Jika tidak, grafik harus memiliki setidaknya satu siklus dan oleh karena itu penyortiran topologi tidak mungkin dilakukan.

Mencerminkan keunikan non-dari jenis yang dihasilkan, struktur S bisa berupa satu set atau antrian atau setumpuk. Bergantung pada urutan nodes yang dihapus dari set S, solusi yang berbeda dibuat. Variasi algoritma Kahn yang mematahkan ikatan secara leksikografis membentuk komponen kunci dari algoritma Coffman-Graham untuk penjadwalan paralel dan gambar grafik berlapis .

Kedalaman-pencarian pertama

Algoritma alternatif untuk sortasi topologi didasarkan pada pencarian mendalam pertama . Algoritma melompati setiap simpul grafik, dalam urutan yang sewenang-wenang, memulai pencarian mendalam pertama yang berakhir saat menyentuh setiap simpul yang telah dikunjungi sejak permulaan sort topologi atau nodus tidak memiliki tepi keluar (yaitu a simpul daun):

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then return
    if n has a temporary mark then stop (not a DAG)
    mark n temporarily
    for each node m with an edge from n to m do
        visit(m)
    mark n permanently
    add n to head of L

Setiap node n mendapat prepended ke daftar output L hanya setelah mempertimbangkan semua node lain yang bergantung pada n (semua keturunan n dalam grafik).  Secara khusus, ketika algoritma menambahkan node n , kita dijamin bahwa semua node yang bergantung pada n
sudah ada dalam daftar output L: mereka ditambahkan ke L baik oleh 
panggilan rekursif untuk mengunjungi () yang berakhir sebelum panggilan 
untuk mengunjungi n , atau dengan panggilan untuk mengunjungi () yang dimulai bahkan sebelum panggilan untuk mengunjungi n .  Karena setiap tepi dan simpul dikunjungi satu kali, algoritma berjalan dalam waktu linier.  Algoritma berbasis depth-first-search ini adalah algoritma yang dijelaskan oleh Cormen et al.  (2001) ;  tampaknya telah pertama kali dijelaskan dalam cetak oleh Tarjan (1976) .

Algoritma paralel

Pada mesin akses acak paralel , pemesanan topologi dapat dibangun dalam waktu O (log ² n ) dengan menggunakan jumlah prosesor polinomial, memasukkan masalah ke kelas kompleksitas NC ² ( Cook 1985 ). Salah satu metode untuk melakukan ini adalah dengan mengulang secara berulang matriks adjacency dari grafik yang diberikan, secara logaritma berkali-kali, dengan menggunakan perkalian matriks min-plus dengan maksimalisasi di tempat minimisasi. Matriks yang dihasilkan menggambarkan jarak jalur terpanjang dalam grafik. Mengurutkan simpul dengan panjang jalur masuk terpanjang mereka menghasilkan pemesanan topologis ( Dekel, Nassimi & Sahni 1981 ).

Aplikasi untuk menemukan jalan terpendek

Pemesanan topologis juga dapat digunakan untuk menghitung jalur terpendek dengan cepat melalui grafik asiklik tertimbang yang tertimbang . Misalkan

V

adalah daftar simpul dalam grafik seperti itu, dalam urutan topologi. Kemudian algoritma berikut menghitung jalur terpendek dari beberapa sumber vertex

s

ke semua simpul lainnya:

Let $d$ be an array of the same length as $V$ ; this will hold the shortest-path distances from $s$ . Set $d [s] = 0$ , all other $d [u] = \infty$ .
Let $p$ be an array of the same length as $V$ , with all elements initialized to nil. Each $p [u]$ will hold the predecessor of $u$ in the shortest path from $s$ to $u$ .
Loop over the vertices u as ordered in V, starting from s:
- For each vertex v directly following u (i.e., there exists an edge from u to v):
  - Let $w$ be the weight of the edge from $u$ to $v$ .
  - Relax the edge: if d[v] > d[u] + w, set
    - $d [v] \leftarrow d [u] + w$ ,
    - $p [v] \leftarrow u$ .

Pada grafik

n

simpul dan ujung

m

, algoritma ini mengambil

Θ (n + m)

, yaitu linear , time.

Keunikan

Jika jenis topologi memiliki properti bahwa semua pasang simpul berturut-turut dalam urutan yang diurutkan dihubungkan oleh tepinya, maka tepi ini membentuk jalur Hamilton yang diarahkan di DAG . Jika ada jalan Hamiltonian, urutan sortir topologis itu unik; Tidak ada perintah lain yang memperhatikan tepi jalan. Sebaliknya, jika jenis topologi tidak membentuk jalur Hamiltonian, DAG akan memiliki dua atau lebih urutan topologi yang valid, karena dalam kasus ini, selalu memungkinkan untuk membuat pemesanan kedua yang valid dengan menukar dua simpul berturut-turut yang tidak dihubungkan oleh tepi satu sama lain. Oleh karena itu, adalah mungkin untuk menguji secara linier apakah ada pemesanan unik, dan apakah jalur Hamiltonian ada, terlepas dari masalah jalur kasar Hamilton untuk graf berarah yang lebih umum ( Vernet & Markenzon 1997 ).

Hubungan dengan perintah parsial

Penataan topologi juga terkait erat dengan konsep perpanjangan linier dari urutan parsial dalam matematika.
Sebuah set yang sebagian dipesan hanya satu set benda bersama dengan definisi hubungan ketimpangan "≤", yang memenuhi aksioma refleksivitas ( x ≤ x ), antisimetri (jika x ≤ y dan y ≤ x maka x = y ) dan transitivitas (jika x ≤ y dan y ≤ z , maka x ≤ z ). Urutan total adalah urutan parsial dimana, untuk setiap dua objek x dan y dalam himpunan, baik x ≤ y atau y ≤ x . Total pesanan sudah familiar dalam ilmu komputer sebagai perbandingan operator yang dibutuhkan untuk melakukan algoritma sorting perbandingan . Untuk rangkaian yang terbatas, total pesanan dapat diidentifikasi dengan urutan linier objek, di mana relasi "≤" benar setiap kali objek pertama mendahului objek kedua dalam urutan; Algoritma sortasi perbandingan dapat digunakan untuk mengubah urutan total menjadi urutan dengan cara ini. Perpanjangan linier dari urutan parsial adalah urutan total yang sesuai dengannya, dalam arti bahwa, jika x ≤ y dalam urutan parsial, maka x ≤ y dalam urutan total juga.
Seseorang dapat menentukan sebagian pemesanan dari DAG manapun dengan membiarkan kumpulan objek menjadi simpul DAG, dan menentukan x ≤ y menjadi benar, untuk dua simpul x dan y , setiap kali ada jalur yang diarahkan dari x ke y ; yaitu, kapanpun y dapat dicapai dari x . Dengan definisi ini, urutan topologi DAG adalah sama dengan perluasan linear dari urutan parsial ini. Sebaliknya, setiap pemesanan parsial pada himpunan yang terbatas dapat didefinisikan sebagai hubungan reachability dalam DAG. Salah satu cara untuk melakukan ini adalah dengan mendefinisikan DAG yang memiliki simpul untuk setiap objek dalam rangkaian yang dipesan sebagian, dan sebuah edge xy untuk setiap pasangan objek yang x ≤ y . Cara alternatif untuk melakukan ini adalah dengan menggunakan pengurangan transitif dari pemesanan parsial; Secara umum, ini menghasilkan DAG dengan sedikit tepi, namun hubungan reachability pada DAG ini masih merupakan urutan parsial yang sama. Dengan menggunakan konstruksi ini, seseorang dapat menggunakan algoritma pemesanan topologi untuk menemukan ekstensi linier sebagian pesanan.

Cari Blog Ini

DUST15