Cara merepresentasikan grafik dengan beberapa tepi diizinkan antara node dan tepi yang secara selektif dapat menghilang

Saya mencoba mencari tahu seperti apa struktur data yang digunakan untuk memodelkan beberapa penggunaan jaringan hipotetis dan ideal.

Dalam skenario saya, sejumlah pengguna yang bermusuhan satu sama lain semua mencoba membentuk jaringan komputer di mana semua koneksi potensial diketahui. Komputer yang perlu disambungkan satu pengguna mungkin tidak sama dengan komputer yang harus disambungkan oleh pengguna lain; pengguna 1 mungkin perlu menghubungkan komputer A, B dan D sedangkan pengguna 2 mungkin perlu menghubungkan komputer B, C dan E.

^{Gambar dihasilkan dengan bantuan NCTM Graph Creator}

Saya pikir inti dari ini akan menjadi grafik siklik tidak berarah, dengan node mewakili komputer dan tepi mewakili kabel Ethernet. Namun, karena sifat skenario, ada beberapa fitur yang tidak biasa yang mengesampingkan daftar adjacency dan matriks adjacency (setidaknya, tanpa modifikasi non-sepele):

1. ujung-ujungnya bisa menjadi penggunaan terbatas; yaitu, jika satu pengguna memperoleh koneksi jaringan tertentu, tidak ada pengguna lain yang dapat menggunakan koneksi itu
   • dalam contoh, pengguna hijau tidak dapat terhubung ke komputer A, tetapi pengguna merah telah terhubung B ke E meskipun tidak memiliki tautan langsung di antara mereka
2. dalam beberapa kasus, sepasang node tertentu akan dihubungkan oleh lebih dari satu sisi
   • dalam contoh, ada dua kabel independen yang berjalan dari D ke E, sehingga pengguna hijau dan biru sama-sama dapat menghubungkan mesin-mesin itu secara langsung; Namun, merah tidak bisa lagi membuat koneksi seperti itu
3. jika dua komputer dihubungkan oleh lebih dari satu kabel, setiap pengguna dapat memiliki tidak lebih dari satu kabel itu

Saya perlu melakukan beberapa operasi pada grafik ini, seperti:

• menentukan apakah ada pasangan komputer tertentu yang terhubung untuk pengguna tertentu
• mengidentifikasi jalur optimal bagi pengguna tertentu untuk menghubungkan komputer target
• mengidentifikasi koneksi komputer dengan latensi tertinggi untuk pengguna tertentu (yaitu jalur terpanjang tanpa bercabang)

Pikiran pertama saya adalah membuat koleksi semua tepian, tapi itu mengerikan untuk pencarian. Hal terbaik yang dapat saya pikirkan untuk dilakukan sekarang adalah memodifikasi daftar adjacency sehingga setiap item dalam daftar tidak hanya berisi panjang tepi tetapi juga biaya dan pemilik saat ini. Apakah ini pendekatan yang masuk akal? Dengan asumsi ruang bukan masalah, apakah masuk akal untuk membuat beberapa salinan grafik (satu untuk setiap pengguna) daripada satu grafik?

Dengan asumsi ruang bukan masalah, apakah masuk akal untuk membuat beberapa salinan grafik (satu untuk setiap pengguna) daripada satu grafik?

Menurut saya, Anda harus menggunakan apa yang dapat kami beri label "grafik berlapis", yaitu menambahkan kombinator untuk grafik, katakanlah @, sehingga:

• Jika A dan B adalah grafik maka A @ B juga merupakan grafik (yaitu dapat diumpankan ke algoritma perpustakaan grafik Anda).
• Himpunan simpul dalam A @ B adalah penyatuan simpul dalam A dan B.
• Himpunan tepi di A @ B adalah penyatuan tepi di A dan B.
• Struktur A @ B tidak memiliki simpul atau tepi, melainkan menggunakan A dan B sebagai wadah data.

Dengan grafik berlapis seperti itu, Anda dapat mendefinisikan K menjadi informasi umum yang tersedia dan R, G, B masing-masing informasi pribadi sehingga setiap pemain benar-benar melihat R @ K, G @ K, B @ K.

Untuk benar-benar mengimplementasikan ini, Anda dapat mencari pustaka grafik yang mengimplementasikan algoritma secara umum, yaitu sehingga algoritma jalur terpanjang dll. Ditentukan oleh representasi grafik Anda yang sebenarnya. Jadi, jika perpustakaan Anda mengatakan

ConcreteGraphAlgorithms = GenericAlgorithms(ConcreteGraphImplementation)

Anda dapat dengan mudah menggantinya dengan

LayeredGraphAlgorithms = GenericAlgorithms(LayeredGraphs(ConcreteGraphImplementation))

di mana Anda memasok LayeredGraphsdan meminjam sisanya dari perpustakaan.

Apa yang Anda butuhkan disebut "grafik yang dikaitkan". Dalam grafik yang dikaitkan, informasi (atribut) dilampirkan ke busur. Grafik yang ditimbang salah satu grafik yang paling sederhana.

Untuk mewakili grafik yang dikaitkan, Anda dapat menggunakan daftar adjacency dengan menambahkan kolom tambahan atau matriks adjacency dengan menambahkan lebih banyak informasi di setiap sel. Sebagian besar algoritma untuk grafik yang tidak dikaitkan akan berfungsi jika Anda memfilter busur, berdasarkan pada atribut. Banyak algoritma telah dikembangkan untuk grafik yang dikaitkan, jadi saya tidak akan menjelaskannya di sini.