Bagaimana cara mengimplementasikan algoritma grafik yang memerlukan kontraksi dan perluasan komponen yang terhubung secara efisien?

Ada beberapa algoritme, seperti Algoritma Edmond, atau Algoritma Boruvka yang mengharuskan pemrogram membuat grafik yang diperoleh dengan mengontraksikan beberapa node menjadi satu node, dan kemudian mengembangkannya kembali.

Gambaran formal kontraksi adalah sebagai berikut:

Misalkan G adalah graf dengan simpul V dan sisi E. Misalkan C menjadi komponen terhubung dari G. Kontraksi G terhadap C didefinisikan sebagai grafik pada V - nodes(C) + C*, dimana C* adalah "supernode" yang mewakili komponen yang dikontrak. Tepi yang tidak melibatkan simpul di C adalah apa adanya. Tepi yang memiliki titik akhir di C kini terhubung ke C*.

Misalnya, langkah peralihan dalam Algoritma Edmond mungkin memerlukan kontraksi siklus, pengoperasian pada grafik yang dikontrak, dan kemudian memperluasnya kembali

Tidak jelas bagi saya bagaimana menerapkan primitif algoritmik menggunakan representasi seperti daftar kedekatan.

Apa cara yang elegan dan efisien untuk merepresentasikan grafik sehingga dapat dikontrak, sambil mengingat data yang relevan untuk memperluasnya?


algorithm data-structures graph-theory
person Agnishom Chattopadhyay    schedule 01.04.2018    source sumber
comment
Bisakah node terkontrak menjadi bagian dari node terkontrak yang lebih besar? Artinya, bisakah supernode disarangkan?   -  person Eric Lippert    schedule 01.04.2018
comment
@EricLippert Ya. Konstruksi seperti itu mungkin diperlukan dalam penerapan Algoritma Edmond, yang mungkin terdapat beberapa panggilan rekursif.   -  person Agnishom Chattopadhyay    schedule 01.04.2018
comment
Biasanya ada cara yang sangat sederhana yang bergantung pada detail implementasi lainnya, yaitu cara terbaik biasanya bukan pendekatan umum yang berlaku secara umum untuk sebagian besar algoritme atau sebagian besar implementasinya.   -  person Matt Timmermans    schedule 01.04.2018
comment
Untuk kasus umum, hal terdekat yang terlintas dalam pikiran adalah struktur data untuk kueri konektivitas dalam grafik dinamis (en.wikipedia.org/wiki/Dynamic_connectivity#General_graphs_2). Wikipedia mengatakan kueri konektivitas dinamis (dengan penghapusan dan penyisipan tepi dalam grafik tidak berarah) dapat didukung dalam waktu poli-log per operasi.   -  person Neal Young    schedule 01.04.2018

Jawaban (2)


arrow_upward
3
arrow_downward

Saya akan menggunakan struktur data disjoint-set yang juga disebut a struktur data union–find . Bayangkan setiap simpul sebagai suatu himpunan pada awalnya. Sekarang cara kerjanya seperti ini:

Untuk kontraksi: Ambil gabungan semua simpul yang berpartisipasi dalam semua kontraksi. Semua simpul dalam suatu himpunan diwakili oleh satu simpul yang disebut induk dari semua simpul, yang dapat Anda sebut sebagai supernode Anda. Tautan tersebut berisi semua detail tentang cara melakukan itu.

Untuk ekspansi lakukan saja kebalikannya, dalam kasus terburuk Anda harus membuat setiap simpul mewakili satu himpunan. Jadi pada dasarnya pendekatan ini berfungsi untuk operasi kumpulan yang tidak tumpang tindih.

person Sumeet    schedule 01.04.2018
comment
Dalam struktur data pencarian serikat yang saya tahu, Persatuan tidak mudah dibalik. Operasi pencarian memodifikasi struktur data (misalnya sepanjang jalur yang ditelusuri untuk pencarian, pencarian mengubah setiap penunjuk untuk menunjuk ke akar saat ini.) Hal ini diperlukan untuk efisiensi. Mengingat operasi Temukan mengubah struktur data dan kehilangan informasi, bagaimana pendapat Anda untuk melakukan ekspansi secara efisien? - person Neal Young; 01.04.2018
comment
@NealYoung Apa yang Anda bicarakan adalah heuristik kompresi jalur? Namun, saya di sisi lain hanya menunjukkan arah struktur data yang layak dan dapat digunakan. Tetapi bahkan literatur tidak berbicara tentang inversi dan oleh karena itu, saya menyerahkannya kepada OP untuk rincian implementasinya. - person Sumeet; 01.04.2018
comment
Yap, kompresi jalur, seperti yang disyaratkan oleh struktur data yang dijelaskan di tautan wikipedia Anda.. Adakah yang tahu detail implementasi yang tersisa untuk OP? Tidak sejauh yang saya tahu. - person Neal Young; 01.04.2018
comment
@NealYoung Saat Anda benar-benar bekerja dengan set, Anda cukup sering bekerja dengan find untuk mencapai pengoptimalan tetapi di sini Anda akan mengontrak atau memperluas. Seperti saya katakan, saya hanya menunjuk ke arah yang diberi masukan. - person Sumeet; 01.04.2018

arrow_upward
3
arrow_downward

Pertama-tama, saya menyukai gagasan jawaban Sumeet Singh, dan Anda dapat menjelajahinya terlebih dahulu. Saya punya ide serupa tetapi detailnya sedikit berbeda.

Sayangnya saat ini saya tidak dapat menggambar diagram, yang akan sangat membantu di sini. Izinkan saya mencoba menggambarkan apa yang ada dalam pikiran saya dengan jelas.

Solusinya melibatkan pembuatan dua jenis node baru:

  • sebuah "supernode" mewakili himpunan yang dikontrak
  • sebuah "node penerusan" adalah proksi untuk supernode yang mengetahui cara "membatalkan" pembuatannya.
  • Node penerusan mempunyai tiga referensi: ke supernodenya, ke node "eksterior", dan ke node "interiornya".
  • Sebuah supernode memiliki daftar semua node penerusnya.

Kontraksi:

Pertimbangkan komponen G Anda yang terhubung.

  • Buat "supernode" yang mewakili komponen yang terhubung ini.

  • Untuk setiap node di G, mungkin ada edge yang terhubung ke node bukan di G. Panggil edge tersebut e1, e2, e3, ...

  • Buat node penerusan F1, F2, F3... untuk masing-masing sisi tersebut.

  • Sekarang untuk masing-masing sisi tersebut, misalkan e1 berasal dari A1 (bukan di G) ke B1 (di G). Hapus tepi A1-B1 dari grafik, tambahkan tepi A1-F1. A1 menjadi simpul luar dari F1, dan B1 menjadi simpul dalam dari F1.

Ekspansi justru sebaliknya:

  • Untuk setiap node penerus F di supernode, hapus tepi dari node eksterior, tambahkan tepi dari node eksterior ke node interior kembali, dan hapus semua node penerus.

  • Hapus supernodenya

Bagian yang sulit akan muncul dalam mengimplementasikan operasi grafik. Jika Anda bertanya "apa tetangga Anda" dari node penerus, permintaan tersebut harus diteruskan ke supernode, dan supernode harus menjawab "semua node eksterior dari semua node penerusan saya". Dan seterusnya.

person Eric Lippert    schedule 01.04.2018
comment
Saya bertanya-tanya apakah akan lebih mudah untuk memiliki node penerusan internal ke supernode daripada duduk di sekitarnya. Dengan begitu, semua node lain akan melihat dirinya terhubung ke supernode dan Anda tidak lagi mengalami masalah penerusan operasi. Anda masih memerlukan node penerus untuk menghubungkan node internal ke tepi eksternal tetapi node penerus hanya perlu ikut berperan jika Anda memperluas supernode atau melakukan transisi dari internal ke eksternal (Atau sebaliknya). - person Wearwolf; 03.04.2018
comment
@Wearwolf: Tentu, ada banyak cara untuk mengatasi masalah ini. Namun intinya adalah: (1) di suatu tempat terdapat struktur data yang mengetahui tautan apa yang dulu ada, dan dapat memulihkannya, dan (2) apa pun bentuknya, tampak seperti simpul dari sudut pandang tepi yang masuk. - person Eric Lippert; 03.04.2018