Struktur data untuk menyimpan tepi grafik

8

Saat ini saya sedang mengerjakan tesis master saya, dan ini tentang pengelompokan pada grafik. Saya bekerja dengan ide menggunakan semut untuk menyelesaikan masalah. Saat ini saya sedang mengerjakan implementasinya dan saya bertanya-tanya seberapa baik merepresentasikan tepi grafik.

Setiap sisi ditambah dengan informasi tertentu seperti nilai feromonnya dan berapa kali semut mengunjungi tepi itu. Saya akan bekerja dengan grafik tidak terarah, yang akhirnya menjadi sangat besar (lebih dari satu juta simpul) dan saya bertanya-tanya apa cara paling efisien bagi saya untuk menyimpan ujung-ujungnya dan mencarinya? Saya berpikir untuk tetap pada konvensi dan menyimpan titik akhir sesuai dengan yang memiliki id simpul lebih rendah untuk dan yang lebih tinggi untuk ( dan adalah titik akhir tepi dalam struktur data). Tapi saya bertanya-tanya bagaimana saya melakukan pencarian dalam kasus ini?v1v2v1v2

Ada pemetaan yang saya buat dari matriks adjacency ke array edge, tetapi itu hanya berfungsi jika grafik yang mendasarinya adalah grafik yang lengkap. Jadi saya datang ke sini untuk beberapa saran tentang bagaimana saya harus melanjutkan karena saya perlu pencarian saya menjadi efisien sementara pada saat yang sama saya tidak ingin meledakkan ruang penyimpanan untuk tepi karena grafik akan sangat besar.

graph-theory data-structures evolutionary-computing berlumpur
sumber
1
Apakah grafik Anda jarang atau padat? Karena jawabannya bergantung pada itu.
Bartosz Przybylski
Oh saya seharusnya menyebutkan itu, ya mereka sebagian besar grafik jarang. Pada dasarnya grafik saya akan bekerja dengan mewakili jaringan dunia nyata yang biasanya jarang. :)
berlumpur
Daftar kedekatan yang disortir?
Raphael

Jawaban:

5

Jika grafik Anda jarang, maka Anda harus menyimpannya menggunakan "daftar" kedekatan, meskipun Anda mungkin menginginkan sesuatu yang lebih efisien daripada daftar (atau mungkin tidak, tergantung penggunaan). Ini paling sederhana jika Anda menyimpan setiap sisi di kedua titik akhir. Ini dapat diimplementasikan dalam banyak cara, misalnya Anda dapat menyimpan semua data dalam beberapa array besar, dan menyimpan hanya pointer di "daftar" kedekatan.

Yuval Filmus
sumber
Sejauh ini saya telah menggunakan pendekatan daftar adjacency di mana untuk setiap simpul saya memiliki array tetangganya (setiap simpul adalah objek). Cara ini membantu karena setiap semut tahu tetangga dari setiap titik. Tetapi saya perlu memilih sisi mana yang akan dilintasi berikutnya, berdasarkan informasi feromon dan beberapa data lain yang akan saya hitung. Saya tidak ingin memperkenalkan duplikasi jadi saya bertanya-tanya apakah ada cara untuk mewakili setiap sisi secara individual tetapi dapat mengindeks mereka secara efisien pada saat yang sama, karena saya akan membutuhkan banyak pencarian untuk setiap sisi dalam setiap iterasi .
berlumpur
Sebagai contoh, berikut adalah pemetaan yang memungkinkan untuk indeks array tepi jika grafik telah lengkap. Dalam hal ini kita sudah tahu ukuran array edge akan n (n-1), di mana n adalah jumlah simpul. Jadi untuk menerjemahkan [x] [y] matriks adjacency ke dalam indeks array (idx) dapat sebagai berikut: jika x <= y maka idx = n * x - x * (x + 1) / 2 + (y - x - 1) selain itu idx = n * y - y * (y + 1) / 2 + (x - y - 1) Jadi katakanlah edge (5,11) atau (11,5) keduanya akan menerjemahkan ke indeks array yang sama. Tetapi karena saya tidak bekerja dengan grafik lengkap, saya tidak bisa memikirkan pemetaan.
berlumpur
2
Anda tetap bersikeras menggunakan struktur data yang hanya masuk akal untuk grafik padat. Untuk grafik yang jarang, pendekatannya selalu untuk menyimpan, entah bagaimana, untuk setiap simpul semua sisi insiden itu. Tidak ada duplikasi - data hanya disimpan di satu tempat; tetapi ada dua petunjuk untuk data. Pengindeksan cepat dapat diimplementasikan menggunakan pohon pencarian, tabel hash dan sebagainya. Ini akan memungkinkan Anda untuk mengimplementasikan cepat dan mudah-mudahan tanpa terlalu banyak ruang overhead. G[x][y]
Yuval Filmus