Fungsi jalur ritsleting Clojure tidak lengkap?

EDIT #2: Seluruh pertanyaan dan eksplorasi ini didasarkan pada hilangnya gagasan mendasar tentang ritsleting; bahwa mereka mewakili perspektif dalam struktur data dari sudut pandang node tertentu. Jadi ritsleting adalah - setiap saat - sepasang simpul saat ini dan tampilan pohon lainnya dari sudut pandang simpul tersebut. Awalnya saya mencoba membuat struktur yang benar-benar baru dari ritsleting, padahal selama ini hanya ritsleting itu sendiri yang saya perlukan. Saya akan meninggalkan semua ini untuk anak cucu, dengan harapan bahwa orang lain akan terbantu olehnya (atau lebih tepatnya ini berfungsi sebagai peringatan bagi penerusnya!).

Pertanyaan awal:

Saya mencoba menggunakan ritsleting untuk memanipulasi pohon. Masalah spesifiknya adalah saya perlu membuat rute runtime antara dua node yang cocok dengan kriteria arbitrer di pohon arbitrer.

Saya pikir saya bisa menggunakan fungsi path untuk mendapatkan rute ke suatu lokasi dengan memanggil path di lokasi saat ini. Namun jalur yang dikembalikan tampaknya menghilangkan langkah terakhir yang diperlukan untuk sampai ke sana.

Misalnya:

(def test-zip (vector-zip [0 [1] [2 [3 [4] 5 [6 [7] [8]]]]]))
(-> test-zip 
    down right right down 
    right down right right
    node)

memberi 5, tapi

(-> test-zip 
    down right right down 
    right down right right
    path)

memberi

[[0 [1] [2 [3 [4] 5 [6 [7] [8]]]]] [2 [3 [4] 5 [6 [7] [8]]]] [3 [4] 5 [6 [7] [8]]]]

yang lokasinya tidak sama (efek dari tiga langkah terakhir tidak ada, down right right).

Sepertinya fungsi jalur hanya membawa Anda ke lokasi induk di pohon, mengabaikan saudara kandung antara Anda dan lokasi sebenarnya.

Apakah saya melewatkan inti dari fungsi path? Saya berasumsi bahwa dengan adanya pohon dan jalan, menerapkan jalan pada pohon tersebut akan membawa Anda ke lokasi asli jalan tersebut, bukan sebagian di sana.

PEMBARUAN: Saya telah menggunakan definisi fungsi berikut untuk mengkompilasi jalur node dari lokasi awal ke lokasi akhir:

(defn lca-path [start-loc end-loc]
  (let [sczip (z/root start-loc)
        start-path (z/path start-loc)
        start-node (z/node start-loc)
        end-path (z/path end-loc)
        end-node (z/node end-loc)
        lca-path (filter (set start-path) end-path)
        lca-node [(last lca-path)]
        lca-to-start (conj (vec (drop (count lca-path) start-path)) start-node)
        lca-to-end (conj (vec (drop (count lca-path) end-path)) end-node)
        ]

    (concat (reverse lca-to-start) lca-node lca-to-end))
  )

Cukup banyak dipengaruhi oleh obrolan dengan @Mark Fisher, terima kasih!


person Oliver Mooney    schedule 08.05.2015    source sumber


Jawaban (1)


Saya pikir Anda benar, itu adalah induk yang dituju, dan ini dikonfirmasi dengan melihat di situs ini, path mengembalikan "semua subpohon dari akar pohon hingga tepat di atas lokasi saat ini".

Untuk struktur Anda, pohonnya adalah:

   A
 / | \
0  o  B
   | / \
   1 2  C __
       /|\  \
      3 o 5  o
        |   /|\
        4  6 o o
             | |
             7 8

Jadi 3 node yang bertanda A, B, C tersebut merupakan node induk yang mengarah ke induk dari 5 node tersebut, yaitu:

A: [0 [1] [2 [3 [4] 5 [6 [7] [8]]]]]
B: [2 [3 [4] 5 [6 [7] [8]]]]
C: [3 [4] 5 [6 [7] [8]]]

itulah hasil yang Anda peroleh.

EDIT: Saya membuat fungsi ini untuk mencari antara dua nilai dalam vektor dan mengembalikan path di antara keduanya. Apakah ini membantu? Saya bukan ahli ritsleting jadi ini pembelajaran bagi saya juga.

(defn between [v s e]
  (let [zv (zip/vector-zip v)
        find-loc (fn [zv l]
                   (loop [loc zv]
                     (if (= l (zip/node loc))
                       loc 
                       (if (zip/end? loc)
                           nil
                           (recur (zip/next loc))))))
        sv (zip/vector-zip (-> (find-loc zv s) zip/up zip/node))
        e-in-sv (find-loc sv e)
        path-s-e (when (some? e-in-sv)
                   (zip/path e-in-sv))]
    path-s-e))

Ia menemukan jalur antara induk dari nilai awal dan induk dari nilai akhir, dan Anda dapat menggunakannya seperti:

(def sov [0 [1] [2 [3 [4] 5 [6 [7] [8]]]]])
(between sov 2 6)
=> [[2 [3 [4] 5 [6 [7] [8]]]] [3 [4] 5 [6 [7] [8]]] [6 [7] [8]]]

Saya berjalan di pohon untuk menemukan induk dari nilai awal, dan kemudian membuat ritsleting baru dari induknya sehingga jalurnya dibatasi dari titik awal. Fungsi pembantu "find-loc" mengembalikan ritsleting untuk entri yang Anda cari, mis. "5" dalam vektor. sv kemudian menjadi vektor induk yang berisi nilai awal.

Jika tidak ada jalur, ia mengembalikan nihil, mis. antara 1 dan 4 Anda harus melintasi 2 elemen.

Ini adalah tanggapan atas komentar Anda karena harus menemukan nilai di simpul akhir (misalnya 5 di [3 [4] 5 [6 [7] [8]]]), yang menurut saya tidak perlu Anda lakukan, tetapi tanpa contoh nyata dari apa yang Anda lakukan, sulit untuk berkomentar pada.

BTW, mungkin ada cara yang jauh lebih baik untuk melintasi/menemukan nilai dalam vektor daripada fungsi khusus, tapi seperti yang saya katakan, ritsleting juga cukup baru bagi saya.

person Mark Fisher    schedule 08.05.2015
comment
Jadi, begitu Anda sampai ke subpohon induk, Anda harus mencari simpul yang diperlukan secara manual di turunan langsung dari subpohon terakhir? Mengingat node yang langsung turun adalah 3. [4], 5 dan [6 [7] [8]] itu pencarian yang tidak terlalu luas dalam kasus ini. Namun bukankah aneh jika jalur yang sama dikembalikan untuk keempat lokasi? Apakah ada cara idiomatis lain untuk menangkap rute ke suatu lokasi dengan ritsleting yang saya lewatkan? - person Oliver Mooney; 08.05.2015
comment
Saya ingin berbagi perjalanan dengan Anda dalam hal ini. Saya telah memperbarui jawaban saya untuk menyertakan pencari pada vektor Anda antara 2 poin. Apakah ini sesuai dengan apa yang ingin Anda capai? - person Mark Fisher; 08.05.2015
comment
Saya juga berpikir seperti ini karena Anda menggunakan ritsleting vektor sederhana daripada ritsleting khusus pada data Anda. - person Mark Fisher; 08.05.2015
comment
Bukankah ini menduplikasi fungsi fungsi path? Setelah Anda menemukan lokasi awal dan lokasi akhir, serta jalur panggilan pada keduanya, Anda dapat melakukan (filter (set start-path) end-path) untuk mendapatkan nenek moyang terendah dari kedua titik. Saya juga melakukan lca-to-start-parent (drop (count lca-loc) start-path) untuk mendapatkan jalur dari nenek moyang terendah ke titik awal, dan (drop (count lca-loc) end-path) untuk bagian lainnya ke titik akhir. Saya suka implementasi mandiri yang Anda miliki, dan bagaimana Anda bisa menggunakan implementasi serupa? untuk menavigasi ke lokasi induk... - person Oliver Mooney; 08.05.2015
comment
Baru saja melihat komentar Anda berikutnya - Saya sebenarnya menggunakan vektor sebagai contoh sederhana untuk memahami ritsleting, saya menggunakan ritsleting khusus untuk data aktual saya tetapi ingin mengesampingkannya sebagai faktor yang memperumit - person Oliver Mooney; 08.05.2015
comment
mungkin ya! Saya sendiri mencoba untuk lebih memahami masalah Anda dan berpikir saya akan berbagi. ada bagian yang bagus dalam Pemrograman Clojure tentang jalur antara 2 titik dalam labirin menggunakan ritsleting khusus menggunakan jalur (clojurebook.com). Saya pikir sifat pertanyaan Anda tentang adanya jalur yang sama ke jumlah elemen yang sama lebih merupakan properti dari penggunaan ritsleting vektor daripada masalah umum dengan ritsleting.... dan komentar ini bersinggungan dengan komentar Anda :) - person Mark Fisher; 08.05.2015
comment
Mungkin perlu diperhatikan juga bahwa kami berdua mengasumsikan nilai unik untuk node (benar dalam kasus saya) - person Oliver Mooney; 08.05.2015