Representasi jalur yang kompak dalam grafik

Saya memiliki subset dari jalur sederhana dalam grafik. Panjang jalan dibatasi oleh . $d$

Apa cara yang paling ringkas (berdasarkan ingatan) saya dapat mewakili jalur sedemikian rupa sehingga tidak ada jalur lain selain yang dipilih yang diwakili?

Perhatikan bahwa saya ingin menggunakan representasi ini dalam algoritme yang akan berulang melalui subset lintasan ini berulang-ulang dan bahwa saya ingin menjadi cukup cepat, jadi misalnya, saya tidak dapat menggunakan algoritma kompresi standar apa pun.

Satu representasi yang muncul di benak saya adalah mewakili mereka sebagai satu set pohon. Saya menduga bahwa jumlah pohon yang optimal adalah NP-hard? Representasi apa lagi yang baik?

graphs data-structures Memilih
sumber

Saat "beralih melalui subset ini", informasi manakah tentang setiap jalur yang Anda butuhkan? Panjangnya? Node yang dikunjungi? Persimpangan dengan jalur lain? ... Mungkin ada

banyak, jadi Anda harus siap untuk "tidak terlalu cepat" jika Anda perlu menyimpan seluruh jalur.

2^{d}

$2^d$

Raphael

G

$G$

P

$P$

G

$G$

P

$P$

G

$G$

Yah, bahkan penyatuan dua jalur sederhana yang saling terpisah dapat membuat siklus, jadi menghitung MST akan membuat Anda kehilangan salah satu jalur yang saya kira. Tetapi hal di atas mungkin memberi Anda beberapa ide.

Juho

k

$k$

ada beberapa kemungkinan menggunakan FSM untuk mewakili jalur dan kemudian seseorang dapat melakukan operasi dasar seperti serikat, persimpangan, pengurangan, dll ... dan juga operasi "kompresi" untuk meminimalkan FSM dipahami dengan baik / optimal dan efisien. belum melihat ini dilakukan dalam sebuah makalah tetapi mengusulkannya pada masalah lain yang agak mirip ...

vzn

Jawaban:

Trie mungkin melakukan trik: http://en.wikipedia.org/wiki/Trie

Labeli setiap sisi grafik Anda dengan huruf. Kemudian tambahkan string yang mewakili jalur melalui grafik Anda ke trie. Untuk memenuhi persyaratan bahwa "tidak ada jalur lain selain yang dipilih yang diwakili", Anda dapat membiarkan semua simpul dari trie kosong, dan memberi label pada tepi, kecuali ketika tepi yang mengarah dari akar ke puncak mewakili salah satu jalur Anda, lalu beri label titik dengan sesuatu. Bangku, jumlah jalur di bawah beberapa pemesanan, dll.

Setelah trie dibangun, ada algoritme untuk mengompresnya menjadi representasi optimal (atau mendekati optimal). (lihat artikel Wikipedia yang ditautkan.)

John Connor yang asli
sumber

Menarik. Namun, trie hadir dengan serangkaian spesifikasi yang jauh lebih besar yang tidak terlalu saya pedulikan (pencarian cepat, asosiasi dengan kunci, dll.) Jadi saya ingin tahu apakah sesuatu yang lebih baik adalah mungkin ...

Memilih

Mungkin Anda harus melihat struktur data yang ringkas . Mereka adalah struktur data yang berusaha untuk menyimpan informasi dalam ruang yang dekat dengan informasi-teoretis batas bawah sambil tetap mempertahankan kemampuan untuk melakukan operasi pada mereka.

Ada struktur seperti itu untuk pohon, kamus, dll. Saya tidak ingat ada yang akan melakukan persis apa yang Anda inginkan, tetapi mungkin kombinasi atau modifikasi dari mereka akan membantu Anda.

Jakub Kotowski
sumber

Bergantung pada kerumitan dan pemrosesan sebelum / sesudah yang diperlukan untuk algoritme Anda, mungkin opsi paling sederhana adalah caranya. Anda dapat dengan mudah menggambarkannya sebagai array, dan menyimpannya dikompresi dalam HDF5. Pustaka ini dilengkapi dengan beberapa algoritma kompresi cepat, sehingga membaca dan menulis data terkompresi mungkin lebih cepat daripada tidak terkompresi.

Berikut ini beberapa plotnya:

Waktu akses berurutan per elemen untuk EArray 15 GB dan potongan yang berbeda:

Kecepatan dekompresi menggunakan Blosc on PyTables: masukkan deskripsi gambar di sini

Dan, jika mereka terikat dalam panjang, Anda bisa menyimpannya di sebuah meja, dan dengan demikian mungkin mendapatkan sedikit lebih banyak ruang. Dan ketika mengambilnya dari memori, Anda sudah memilikinya dalam bentuk yang sangat nyaman untuk menerapkan algoritma Anda.

Davidmh
sumber