Menentukan konektivitas untuk grafik yang sepenuhnya dinamis dengan penyisipan dan penghapusan vertex / subgraph

8

Saya mencari solusi untuk masalah berikut dan bertanya-tanya apakah ada yang bisa mengarahkan saya ke beberapa penelitian yang ada tentang topik ini. Saya datang dari aplikasi grafik dunia nyata jadi bersabarlah jika terminologi saya tidak tepat.

Saya memiliki sistem basis data di mana pengguna dapat menambah / menghapus / memindahkan objek dengan membuat / menghapus dan mengubah hubungan. Dengan demikian, saya dapat melihat objek sebagai simpul dalam grafik dan hubungan telah tepi dan tepi dapat ditimbang tergantung pada jenis hubungan (baik komposisi, asosiasi, atau agregasi).

Dari sudut pandang pengguna, menambahkan elemen baru dapat menjadi satu klik dan di bawah kap, program membuat grafik objek yang dihubungkan oleh hubungan. Grafik ini, kemudian ditambahkan ke grafik utama yang mendefinisikan seluruh database. Menghapus sebuah elemen, akan menjadi kebalikan dari tautan / tepian yang terputus dan grafik menjadi dua grafik terpisah di mana 1 adalah basis data, dan yang lainnya terdiri dari simpul yang dibentuk oleh elemen dan sub elemennya.

Saya perlu cara yang sangat cepat untuk menentukan kapan saya memiliki grafik disjoint dan kapan 2 grafik disjoint menjadi 1 lagi. Saya sempat melihat Holm, de Lichtenberg, dan Thorup ( 2001 ; pdf ). Sepertinya cara untuk pergi, tetapi penulis memang menyebutkan mereka hanya mempertimbangkan grafik dengan jumlah simpul tetap. Hanya bertanya-tanya apakah algoritma biasanya memperluas diri untuk menambah / menghapus simpul dengan hanya melakukan penambahan tepi secara bertahap? Atau apakah ada karya yang dirancang khusus untuk skenario seperti itu?

ds.algorithms graph-theory dynamic-algorithms Thuan Seah Tan
sumber

Jawaban:

4

Ini sama sekali bukan pertanyaan sepele. Salah satu masalah Anda akan menemukan algoritma untuk ini adalah keterputusan (pun intended) dari pekerjaan pada grafik dinamis. Karya Thorup et al. (Yang Anda sebutkan) mungkin merupakan awal terbaik untuk jenis hal yang Anda cari.

Anda juga dapat mencoba Bhadra & Ferreira , mereka mungkin mendapatkan sedikit di luar topik untuk apa yang Anda inginkan, tetapi mereka memiliki referensi ke materi lain yang bisa berguna.

Luke Mathieson
sumber
1

Pembaruan Vertex dapat ditangani dengan menggunakan pembaruan tepi sebagai berikut (Meskipun sedikit tidak efisien karena membuat deg (u) panggilan ke fungsi pembaruan tepi):

AddVertex(G,u,Adj(u)):- 
  /* Adj(u) is the vertices adjacent to u after adding u */  
  For each v in Adj(u) do 
    AddEdge(G, (u,v))

DeleteVertex(G,u):- 
  For each v in Adj(u) do
    DeleteEdge(G, (u,v))

Thorup et. Analisis waktu berjalan Al menyatakan bahwa waktu pembaruan mereka adalah waktu diamortisasi per tepi. Jadi, itu tidak secara langsung menyiratkan poli. hasil waktu pembaruan logaritmik di bawah pembaruan vertex.

Ada beberapa karya di mana operasi pembaruan mendukung penghapusan vertex / tambahan juga. Dalam [1] untuk masalah Dynamic All Pairs Shortest Paths, mereka pada dasarnya memungkinkan memperbarui insiden edge pada vertex dengan menentukan bobot baru. Kita bisa memperbarui semuanya ke + infinity untuk menghapus titik dan juga untuk menambahkan titik.

Anda mungkin menemukan referensi [2], dan [3] bermanfaat jika Anda baru memulai dengan algoritma grafik dinamis. [2] memberikan ide tingkat tinggi yang bagus tentang pendekatan saat ini untuk masalah konektivitas dinamis.

Referensi

  1. Pendekatan baru untuk dinamis Semua pasangan jalur terpendek, Demetrescu. et. Al, JACM 2004 Voume 51 edisi 6, 2004

  2. Slide of Talk on Dynamic Graph Algorithms oleh Dr. Surender Baswana dalam lokakarya "Kemajuan terbaru dalam struktur data dan algoritma" yang diadakan di IMSc, Chennai.

  3. Camil Demetrescu dan Pino Italiano, Grafik dinamis, Buku Pegangan tentang Struktur dan Aplikasi Data, Bab 36. Dinesh Mehta dan Sartaj Sahni (eds.), Seri Pers CRC, dalam Ilmu Komputer dan Informasi, Januari 2005. [Draf (pdf)]

rizwanhudda
sumber