Hidupku bersama Boost Graph Library

Artikel, bagian pertama yang disajikan di sini, berisi berbagai pertimbangan penulis, terakumulasi selama pengembangan panjang sistem khusus untuk mencari koneksi sosial, berdasarkan Boost Graph Library (BGL). Bagian (teknis) ini merangkum tayangan penulis tentang bekerja dengan perpustakaan ini, mengangkat masalah instrumentasi saat membuat aplikasi grafik, dan menyentuh beberapa masalah praktis metaprogramming di C ++.

BGL dan dimakan dengan apa

Pustaka template BGL mungkin diketahui oleh pengembang mana pun yang mengalami tugas grafik. Muncul di Boost 1.18.1 pada tahun 2000, ia segera mendapatkan ulasan yang disetujui dari genre klasik seperti Alexander Stepanov. Panduan perpustakaan, yang disusun oleh Jeremy Sik, Lai-Kwan Lee dan Andrew Lamsdane, diterbitkan dalam bahasa Rusia pada tahun 2006 oleh Peter (asli - Jeremy G. Siek, Lie-Quan Lee dan Andrew Lumsdaine, "The Boost Graph Library", 2001 , Addison-Wesley). Perpustakaan diperbarui secara intensif dan dikembangkan hampir sampai akhir 2013 (Boost 1.55.0). Secara khusus, pada tahun 2005 pengumuman versi terdistribusi (PBGL) muncul, yang telah dimasukkan dalam Boost sejak versi 1.40 pada tahun 2009 dan hingga hari ini tetap menjadi semacam standar de facto untuk komputasi grafik pada cluster berkinerja tinggi, dalam hal apa pun, di dunia akademik. Sejauh sejarah komitmen dapat dinilai, hingga 2005, pengembang utama perpustakaan adalah Jeremy Sik, setelah 2005 - Douglas Gregor, dan secara umum di berbagai waktu sejumlah besar orang yang beragam bekerja di perpustakaan. Publikasi yang ditujukan untuknya telah berulang kali muncul di habr.com: pertama-tama, serangkaian artikel oleh Vadim Androsov harus dicatat: [ 1 , 2 , 3 ]. Jadi, pada prinsipnya, literatur yang baik dan beragam dikhususkan untuk perpustakaan, tetapi dokumentasinya sendiri, juga, secara umum, cukup luas, agak menderita karena fakta bahwa:

1. Daftar isi dan bagian root, yang mengklaim menyediakan daftar lengkap entitas kunci, belum berubah sejak 2001. Misalnya, penulis baris-baris ini, yang secara naif meyakini bahwa:

   BGL saat ini menyediakan dua kelas grafik dan adaptor daftar tepi:
   
   adjacency_list
   adjacency_matrix
   edge_list

   , setelah beberapa waktu saya terkejut menemukan representasi compressed_sparse_row_graph (sparse matrix) diimplementasikan pada tahun 2005. Kisah serupa terjadi dengan algoritma Bron-Kerbosch. Jangan percaya daftar isi, gunakan pencarian langsung di file header;
   
2. Tidak ada daftar komentar tunggal dari kategori internal perpustakaan (container_category, parallel_edge_traits, iterator_stability, dll., Dll) yang diperlukan untuk mengimplementasikan tampilan Anda sendiri. Masalah dengan memahami apa yang terjadi menyusul, tampaknya, semua pengguna perpustakaan yang ingin menggali lebih dalam, yang mengarah pada penampilan "semacam kode kerja," yang membutuhkan banyak waktu dan upaya untuk membawanya ke keadaan lengkap: lihat, misalnya, diskusi khas .

Jumlah kategori dan berbagai pemilih, termasuk yang sangat mirip, begitu besar sehingga penulis sendiri kadang-kadang bingung di dalamnya. Misalnya, dalam konstruktor dari compressed_sparse_row_graph yang telah disebutkan di atas, dalam versi saat ini ada kesalahan sistematis yang menyebabkan crash ketika mencoba menyalin daftar kedekatan yang tidak diarahkan:



Dapat dicatat di sini pada kesempatan bahwa pengujian penuh dari mekanisme yang fleksibel tersebut merupakan masalah yang terpisah, karena disertai dengan ledakan kombinatorial dari jumlah penggantian yang mungkin.

Harus dicatat dengan penyesalan bahwa saat ini pengembang utama tampaknya telah kehilangan minat untuk bekerja lebih lanjut di perpustakaan dan selama enam tahun terakhir, tidak berarti telah menghabiskan potensi pengembangannya dan bahkan tidak sepenuhnya membebaskan dirinya dari ketidakkonsistenan internal dan kesalahan langsung, ada dalam penerbangan bebas. Rencana yang disuarakan di wilayah 2011 untuk secara signifikan memperluas serangkaian metode dan mencakup area baru teori grafik (termasuk dengan menambahkan dukungan partisi grafik internal untuk kemampuan membaca format METIS) tetap tidak terpenuhi. Tampaknya juga perpustakaan dapat memperoleh banyak manfaat (setidaknya dalam hal keterbacaan) dari meluasnya penggunaan produk baru yang menjadi standar setelah 2011.

Dengan demikian, masalah memilih perpustakaan referensi untuk aplikasi grafik ketika melihat dari 2019 tidak terlihat sejelas yang kita inginkan, dan selama 5 tahun terakhir, ketidakpastian telah meningkat daripada menurun.

Situasi ini menyebabkan beberapa kesedihan, karena penciptaan mekanisme universal yang mirip dengan BGL, dengan sendirinya, adalah semacam prestasi intelektual, baik dalam hal kekuatan pendekatan dan kekayaan gudang senjata metode universal yang diterapkan (yang baik satu setengah ratus single-threaded dan beberapa lusin didistribusikan) perpustakaan, sejauh penulis garis-garis ini diketahui, masih tidak ada bandingannya.

Pada saat ini, hanya perpustakaan ini yang memungkinkan, pada prinsipnya, tanpa kehilangan kinerja, memaksakan perjanjian yang ketat pada penyajian data dan kehilangan kendali atas mekanisme internal perpustakaan itu sendiri, untuk sepenuhnya memisahkan algoritma grafik dan representasi grafik, menjadikan yang terakhir sepenuhnya independen dari penyajian metadata yang terkait dengan tepi dan simpul ( yang, pada prinsipnya, jelas merupakan cara yang paling benar dalam melakukan sesuatu).

Kata "secara fundamental" digunakan di sini karena suatu alasan. Mempertimbangkan situasi tertentu menggunakan contoh dari kelas compressed_sparse_row_graph yang telah lama menderita yang telah disebutkan di atas, kita dapat mencatat, misalnya, penyimpangan berikut dari standar tinggi:

1. Operator [] untuk daftar adjacency dan matriks jarang menangani properti internal dan eksternal tepi secara berbeda (Properti Internal dan Bundel): yang pertama mengembalikan hanya properti eksternal (internal hanya dapat diakses dengan property_map), yang kedua mengembalikan properti struktur pembingkaian yang berisi daftar properti yang umum.
2. Fungsi get untuk mendapatkan indeks tepi menggunakan boost :: property_map <compressed_sparse_row_graph, boost :: edge_index_t> :: type jatuh ke boost :: detail, dan tidak ke boost, seperti dalam semua kasus lainnya.

Akhirnya, dalam templat compressed_sparse_row_graph, spesialisasi untuk grafik yang tidak diarahkan (boost :: undirectedS) tetap tidak terpenuhi.

Dalam hal ini, ketika menggunakan properti edge_index (nomor seri tepi), kesulitan tambahan timbul karena fakta bahwa untuk daftar adjacency properti ini harus secara eksplisit ditetapkan sebagai internal dan dengan demikian dapat diubah secara sewenang-wenang, tetapi untuk grafik yang tidak diarahkan nilainya tidak tergantung pada arah. di mana tulang rusuk lewat. Untuk matriks jarang (selalu terarah), ini adalah properti_map konstan bawaan dari bentuk khusus (dihitung sebagai indeks dalam array tepi). Oleh karena itu, nilai untuk tepi yang datang (mewakili grafik tidak terarah) tidak dapat berubah dan akan selalu berbeda.

Semua perbedaan ini mengarah pada ketidakmungkinan "hanya mengganti representasi grafik dengan yang setara" ketika menjalankan fungsi algoritmik, yang secara signifikan merusak keunggulan utama perpustakaan. Dalam praktiknya, dalam kasus seperti itu, diperlukan spesialisasi kode berlebih, atau pemrosesan untuk mengecualikan elemen dengan perilaku berbeda, atau penyesuaian templat grafik sedemikian rupa sehingga mereka "berperilaku identik" dengan definisi atribut yang berbeda, atau, akhirnya, menghapus file individual dari perpustakaan dan pembuatannya. "Versi peningkatan pribadi."

Selain itu, ketidaknyamanan berikut, yang tidak begitu signifikan, dapat dicatat:

• Dimensi deskriptor internal representasi grafik memiliki dampak signifikan pada konsumsi memori yang diperlukan untuk menyimpan grafik, dan kadang-kadang memengaruhi kinerja algoritma.
  
  Beberapa tampilan (compressed_sparse_row_graph yang sama) memungkinkan Anda untuk mengontrol dimensi ini. Lainnya (adjacency_list) tidak memiliki parameter seperti itu dan selalu menggunakan bilangan bulat 64-bit (biasanya berlebihan), yang tidak dapat diganti tanpa memodifikasi kode;
  
• Terlepas dari kenyataan bahwa penulis perpustakaan menyediakan sangat, sangat banyak, beberapa primitif jelas diperlukan tidak termasuk dalam perpustakaan. Misalnya, tidak ada fungsi seperti reverse_edge yang melakukan inversi tepi.
  
  Implementasi fungsi-fungsi tersebut, tentu saja, tergantung pada representasi grafik: dalam hal ini, ia dapat diimplementasikan dengan pertukaran sepele elemen-elemen suatu pasangan, pencarian yang kurang lebih efisien dengan wadah, atau tidak sama sekali. Sulit bagi pengguna akhir untuk memahami semua ragam pilihan ini, terutama karena, menurut ideologi perpustakaan, anggota internal deskriptor seharusnya tidak menarik baginya.
  
• Demikian juga, beberapa skrip yang jauh dari tidak berharga jatuh dari perpustakaan. Misalnya, Anda dapat menentukan predikat tepi yang menggunakan filtered_graph untuk mengubah grafik yang tidak diarahkan menjadi grafik yang diarahkan, tetapi tidak ada cara untuk membawa transformasi ini menjadi perhatian perpustakaan. Karenanya, algoritma reguler untuk grafik berarah tidak akan dikompilasi dengan objek seperti itu, dan algoritma untuk grafik tidak berarah tidak akan berfungsi dengan benar dengannya.
  
  Di suatu tempat di lingkungan adalah topik dukungan untuk grafik non-directional teknis yang memiliki penanda arah layanan di tepi. Namun, peningkatan perhatian terhadap pandangan ini mungkin karena sifat khusus dari tugas-tugas yang diselesaikan penulis, dan minat luas dalam mendukung objek-objek tersebut tidak jelas.
  
• Adapun fungsi reverse_edge, diambil sebagai contoh di atas, sama sekali tidak ada opsi yang luar biasa bahwa fungsi yang diinginkan ada di suatu tempat di perut perpustakaan, tetapi untuk beberapa alasan menerima nama yang tidak jelas. Ini mengarah ke masalah berikut, yang pada pandangan pertama tidak serius, tetapi secara signifikan memperlambat pekerjaan dengan pustaka templat yang kompleks (tidak hanya BGL, meskipun jelas di antara para pemimpin berdasarkan kriteria ini): bekerja dengan sistem luas fungsi yang terkait secara implisit tanpa mengetik parameter eksplisit dan dengan semantik penggunaan yang tidak jelas (seringkali yang kurang transparan daripada yang dipikirkan dengan baik) secara fisik sulit, dan lingkungan pengembangan yang ada tidak memberikan dukungan apa pun pada pengembang:
  
  
  
  Bahkan, asisten otomatis:
  
  
  1. Dirancang terutama untuk dukungan OOP, ketika satu set fungsi terikat ke objek di sebelah kanan sesuai dengan tipenya. Dengan fungsi global yang dapat di sebelah kiri jenis (apalagi satu set jenis), mereka membantu jauh lebih buruk bahkan jika semua jenis diketahui.
  2. Mereka bahkan tidak bisa bekerja dengan template sederhana. Versi asisten visual yang digunakan oleh penulis, di depannya memiliki definisi kelas template dengan parameter default, menawarkan untuk menentukan "substitusi uji" agar dapat menghasilkan petunjuk untuk kelas. Jika Anda bertemu dengannya, sama sekali tidak ada yang terjadi.
  3. Selain itu, mereka kurang mampu memahami kualifikasi metaprogram, bahkan yang paling sederhana, seperti enable_if.
  4. Tentang skenario tipikal: “kita berada di dalam fungsi templat yang dipanggil dari jumlah tak terbatas dari panjang tak tentu rantai fungsi lain, termasuk templat”, mustahil untuk berbicara tanpa air mata. Dalam hal ini, vim benar-benar tetap menjadi sahabat programmer.
  
  Aspek lain dari situasi yang sama dapat diilustrasikan menggunakan baris pertama dari fragmen kode yang ditunjukkan pada gambar sebelumnya. Pembaca diundang untuk menyelesaikan pertanyaan “boost time time” vs “CRT current time” dan bandingkan hasilnya. Ya, boost :: date_time (sekarang sebagian dipindahkan ke std) memungkinkan untuk melakukan banyak hal kompleks dengan benar, sementara CRT memungkinkan Anda melakukan beberapa operasi sepele secara tidak benar, tetapi dalam situasi rumah tangga sehari-hari yang umum, CRT lebih nyaman dari semua sudut pandang, dan yang polinomial konstruksi form posix_time :: second_clock :: local_time (contoh yang lembut) cenderung berubah menjadi hieroglif yang berkeliaran di program. Menghilangkan pengembang akses ke perpustakaan pribadi hieroglif tersebut dan kecepatan pengembangan akan menjadi nol .
  
  Boost :: string_algo memungkinkan untuk melakukan apa pun dengan string, tetapi, jujur, masing-masing operasi yang tidak sepele disertai dengan sesi membaca kembali dokumentasi untuk menyegarkan logika umum perpustakaan, nama-nama predikat, serta latihan terpisah untuk mengetahui kompatibilitas parameter. Situasi serupa terjadi dengan operasi tokenization di boost :: regexp, dengan logika internal yang sempurna dari yang terakhir.
  
  Jika situasi seperti itu terjadi dengan pustaka yang paling umum digunakan, tidak mengherankan bahwa BGL, sebagai pustaka yang lebih khusus, di mana, misalnya, ada fungsi make_property_map_function dan make_function_property_map yang tidak terkait satu sama lain, serta fungsi pengambilan sakramental yang dimuat ke sembarang jumlah argumen dalam jenis apa pun menimbulkan masalah yang sama, tetapi dalam bentuk hipertrofi. Ya, tugas apa pun dapat diselesaikan oleh rantai panggilan get, tetapi, sayangnya, tidak setiap rantai menyelesaikan masalah ini.
  
  Membaca kode seperti itu bisa mudah dan menyenangkan, bahkan mungkin terlihat seperti sinopsis dari algoritma yang ditulis secara formal dalam bahasa alami, tetapi ketika menulisnya, ketidakmungkinan mengganti kata dengan sinonim, dll. Manifestasi dari kekakuan, tidak seperti biasanya untuk yang asli.
  
• Secara umum, seseorang tidak dapat gagal untuk mengulangi dangkal, tetapi tidak menjadi kurang benar, pengamatan bahwa metaprogramming di C ++ secara harfiah didasarkan pada efek samping dari alat bahasa, tujuan asli yang berbeda, dan bahkan ide-ide paling sederhana berdasarkan Akibatnya, bahasa logam sulit untuk diungkapkan dan dibaca, dan menautkan kode templat ke sistem kuno dari file yang disertakan tidak membuat hidup lebih mudah bagi pengembang dan tidak mengurangi jumlah kode yang diproses oleh kompiler.
  
  (Di sisi lain, pemutakhiran boost dan std yang terjadi secara berkala membawa banyak konstruksi yang tidak sepele dan seringkali sangat berguna serta solusi tak terduga, yang benar-benar memungkinkan penulisan kode yang lebih jelas dan ringkas dengan biaya lebih rendah. Namun, aliran produk baru sangat luas, tidak sama dan terstruktur buruk sehingga yang paling penting tambahan ke pustaka standar, bahkan yang jelas seperti opsi / apply_visitor atau yang disebutkan di bawah ini, jika keuntungan konseptual dari aplikasi mereka dalam konteks proyek tertentu tidak relevan Sebagai bukti nyata, tanpa bantuan acara yang membahagiakan, mereka dapat kehilangan fokus untuk waktu yang lama, jika Anda tidak menghabiskan sebagian besar waktu kerja dengan langsung melacak produk-produk baru, mempelajari contoh-contoh non-sepele dari penggunaannya dan upaya mental untuk menerapkannya pada kode yang ada. untuk mengatasi masalah ini - untuk menjaga setiap lima programmer C ++ yang diprogram satu C ++ - ahli teori yang hanya sibuk dengan masalah prioritas produk baru, implementasinya tions dalam proyek dan praktisi pendidikan selektif. Kesimpulan: jangan mulai C ++ - proyek dengan pengembang lebih sedikit ).
  
• Akhirnya, secara objektif masalah paling serius yang terjadi ketika bekerja dengan kode boilerplate BGL . Misalkan kita menggunakan beberapa algoritma templat yang membuat suatu bagian melalui grafik dan mengambil representasi grafik G sebagai argumen. Dalam kasus khusus, representasi ini tergantung pada filter yang ditumpangkan pada simpul dan tepi $$$F_v$, $$$F_e$dan skema berat badan $$$W$. Untuk bekerja dengan grafik yang difilter, BGL menawarkan kelas template filter_graph yang disebutkan di atas, cara melampirkan skema bobot ke grafik itu adalah atas kebijakan pengguna. Functors mewakili $$$F_v$, $$$F_e$dan $$$W$dapat mencakup setidaknya beberapa tampilan berikut:
  
  
  • Langsung pembungkus untuk fungsi yang mewakili skema pembobotan dan predikat mewakili filter (perlahan, tanpa kehilangan inisialisasi);
  • Cache atas pembungkus ini, pemetaan edge / node deskriptor ke edge / node index, menangani bitmap dan array nilai (tanpa kehilangan inisialisasi, dengan peningkatan bertahap dalam kecepatan seperti yang digunakan);
  • Pemetaan langsung deskriptor node / tepi ke array nilai yang diisi (memerlukan inisialisasi, tetapi dapat dibangun berdasarkan representasi sebelumnya; kecepatan mencapai maksimum).
  
  Jadi, jika algoritma ini ditulis dalam gaya tradisional, tiga penyeleksi dengan setidaknya tiga cabang di masing-masing akan muncul di tubuhnya (dan kebutuhan untuk menyesuaikan tubuh ketika representasi baru muncul). Karena setiap percabangan dalam tubuh algoritma, yang mengeksekusi sejumlah besar kali ketika melewati grafik, menghasilkan kehilangan waktu yang nyata, keinginan untuk menghindari kerugian ini sambil mempertahankan kode dengan gaya tradisional yang sama dapat menyebabkan 27+ implementasi algoritma untuk berbagai kombinasi representasi.
  
  Gaya metaprogram harus menyelamatkan Anda dari masalah ini, memungkinkan Anda untuk mendukung satu metafungsi yang menggambarkan algoritma yang secara implisit menghasilkan semua implementasi yang diperlukan (dan juga, mungkin, beberapa, dan mungkin sejumlah besar yang tidak perlu jika struktur kode runtime tidak secara de facto menghasilkan beberapa kombinasi jenis, ), .
  
  , , inline- , –O2. - ( 1:3 1:5, – , , ).
  
  , . . , ( ) , «» «» . , . : «» «» , «» , «» .
  
  , : , 100% , , «» . ( , , - , , , , , ).
  
• , , , . C++ , -, , .
  
  , , :
  
  

  void type_selector_fun(type_a a, type_b b, ...) { if (condition_1(a, b, ...)) { auto arg = get_type_1_obj(a, b, ...); run_calc(arg, a, b, ...); } else if (condition_1(a, b, ...)) { auto arg = get_type_2_obj(a, b, ...); run_calc(arg, a, b, ...); } else ... } 

  
  Itu dapat ditulis ulang agak lebih kompak menggunakan varian <...> dalam kira-kira bentuk berikut:
  
  

    void type_selector_fun(type_a a, type_b b, ...) { variant<type_1, type_2, ...> arg; if (condition_1(a, b, ...)) { arg = get_type_1_obj(a, b, ...); } else if ... ... apply_visitor([&](auto arg_){run_calc(arg_, a, b, ...); }, arg); } 

  
  Kerugian dari bentuk penulisan ini adalah kebutuhan untuk enumerasi eksplisit tipe type_1, type_2, ... dalam deklarasi varian. Tipe-tipe ini bisa merepotkan, merekam menggunakan declval / result_of_t bisa menjadi tidak rumit.
  
  Saat menggunakan apapun, tidak perlu mendaftar jenis, tetapi tidak ada cara untuk mendapatkan analog apply_visitor.
  
  Penggunaan beberapa fungsi template make_variant, yang memungkinkan Anda menulis kode dari tipe berikut, menyarankan sendiri:
  
  

    auto arg = make_variant ( bind(condition_1, a, b, ...), bind(get_type_1_obj, a, b, ...), bind(condition_2, a, b, ...), bind(get_type_2_obj, a, b, ...), ... ); 

  
  tetapi obatnya tidak terlihat lebih baik daripada penyakitnya.
  
  Secara umum, ada situasi khas untuk metaprogramming di C ++, ketika untuk mengekspresikan ide yang sangat sederhana, Anda harus menggunakan seluruh gudang alat bantu dengan hasil yang tidak terlalu memuaskan dalam hal keterbacaan dan kemudahan perekaman. Pada dasarnya, saya ingin dapat menulis sesuatu seperti berikut:
  
  

    //   variant<...>      //  ,   : type_1, type_2 etc. variant<auto...> get_type_obj(typa_a a, type_b b, ...) { if (condition_1(a, b, ...)) { return get_type_1_obj(a, b, ...); } else if (condition_2(a, b, ...)) { return get_type_2_obj(a, b, ...); } else ... } 

  
  atau bahkan:
  
  

    select_value_type(arg) { if (condition_1(a, b, ...)) { arg = get_type_1_obj(a, b, ...); } else ... ... } run_calc(arg, a, b, …); 

  
  Opsi terakhir, meskipun sepenuhnya dihilangkan dari gaya C ++, terlihat paling praktis, karena mungkin ada lebih dari satu variabel arg yang jenisnya dipilih, dan tidak ada alasan untuk mengantisipasi logika konstruksi mereka .
  
• Sisi lain dari situasi yang sama adalah penggunaan struktur bantu (misalnya, caching) yang mengimplementasikan skrip yang pantas menggunakan nama "variabel templat", tetapi berbeda dari ekstensi standar C ++ 14 dengan nama yang sama.
  
  Kode yang sesuai mungkin terlihat seperti ini:
  
  

    struct CacheHolder { boost::variant< container<T1>, container<T2>, // ... container<TN>> ct; template<typename T> struct result_type_selector { typedef typename if_c<is_compatible<T, T1>::value, T1, if_c<is_compatible<T, T2>::value, T2, // ... if_c<is_compatible<T, TN>::value, TN, std::decay_t<T>>>>::type type; }; template<typename T> auto get() const -> const container<typename result_type_selector<T>::type>& { return boost::get<container<typename result_type_selector<T>::type>>(ct); } }; 

  
  Di sini, seperti di atas, konstruksi panjang mengungkapkan ide sederhana untuk mengakses variabel yang mewakili cache dengan nama tertentu, terlepas dari dimensi nilai yang di-cache (secara transparan melewati kode panggilan).
  
  Untuk singkatnya, kode diberikan untuk kasus ketika hanya satu jenis dapat aktif, tetapi dalam praktiknya situasinya lebih umum ketika beberapa wadah dapat ada secara bersamaan (dapat dengan mudah diimplementasikan dalam gaya yang sama menggunakan tuple dan opsional).
  
  Implementasi fungsi get <...> mengasumsikan bahwa kode panggilan memiliki beberapa gagasan tentang nilai cache yang ingin diakses (misalnya, integer atau floating point).
  
  Yang tidak kalah umum adalah situasi di mana nilai tipe yang tepat tidak penting bagi pemanggil. Dalam hal ini, skrip select_value_type / apply_visitor dari paragraf sebelumnya direproduksi (disesuaikan dengan kemungkinan multiplisitas nilai, yang menyiratkan jenis tampilan dalam urutan prioritas yang menurun).
  
• Sampai sekarang, hampir tidak ada menyebutkan PBGL dalam teks ini. Ini dijelaskan oleh pengalaman penulis yang sangat sedikit bekerja dengan bagian perpustakaan ini (sehubungan dengan yang penulis sendiri, dengan skeptisisme tertentu, mengacu pada segala sesuatu yang ditulis di bawah ini dalam paragraf ini, dan meminta orang lain untuk melakukan hal yang sama). Bahkan, eksperimen semacam itu bermuara pada beberapa eksperimen, pada jenis masalah pencarian yang sama yang menunjukkan pada data praktis kehilangan versi terdistribusi ke solusi lokal 3-5 kali dalam memori dan 15-20 kali dalam kinerja keseluruhan (asal dari sosok yang menakutkan ini dijelaskan di sini dan juga dikomentari pada paragraf berikut) . Mengingat semakin kompleksnya bekerja dengan struktur terdistribusi, pilihan yang mendukung versi lokal terbukti dengan sendirinya dalam situasi seperti itu.
  
  Mari kita jelaskan mekanisme operasi PBGL menggunakan contoh khas dari algoritma delta-walking. Dalam versi paralel algoritma Dijkstra ini, antrian prioritas diganti dengan array "ember". Elemen yang jatuh ke dalam satu "ember" diproses secara paralel. Dalam bentuk aslinya, delta pacing adalah algoritma tipikal untuk sistem memori bersama.
  
  Dalam versi terdistribusi, hal berikut terjadi: di PBGL, saat memuat, grafik tersebar di antara proses, dan setiap proses memiliki rentang nomor vertex yang kontinu. Dengan demikian, dengan bilangan titik global, mudah untuk mengetahui prosesnya. Dengan demikian, setiap proses di setiap belokan algoritma menyimpan bagian dari "ember" yang berisi simpul yang dimiliki proses ini. Semua proses secara bersamaan memilih dan memproses simpul dari bagian mereka dari "ember" satu per satu, sambil mengirimkan pesan tentang kebutuhan untuk memperbarui "ember" berikut untuk proses yang memiliki simpul tetangga. Sangat mudah untuk melihat bahwa, peningkatan jumlah proses menyebabkan peningkatan jumlah pesan yang mereka kirim. Akibatnya, waktu eksekusi algoritma tidak hanya tidak berkurang, tetapi bahkan meningkat. Secara khusus, peluncuran beberapa proses MPI untuk menyelesaikan masalah ini pada satu mesin fisik dengan probabilitas tertentu hanya akan mengarah pada peningkatan beban prosesor total tanpa penambahan waktu.
  
  Perlu dicatat bahwa delta pacing adalah algoritma pencarian terdistribusi tercepat (dari tiga didukung oleh perpustakaan).
  
  Jadi, jika grafik sebelumnya tidak disiapkan, itu harus dibagi menjadi blok dengan ukuran maksimum, satu blok per mesin fisik. Dengan persiapan awal, yang kami maksud di sini adalah memberi nomor baru pada simpul grafik sehingga rentang angka kontinu yang digunakan oleh PBGL, jika mungkin, sesuai dengan subgraph yang terhubung secara longgar. Paket seperti METIS, paraMETIS, dan Zoltan digunakan untuk tujuan ini. Bekerja dengan grafik dinamis dalam mode ini sulit.
  
  Secara umum, menurut hasil percobaan yang dijelaskan, penulis mendapat kesan bahwa operasi normal kluster PBGL hanya dimungkinkan dengan peralatan komunikasi khusus, dan masuk akal untuk menggunakan mesin dengan jumlah minimum inti dan kinerja ulir maksimum sebagai simpul dari kluster tersebut. Para penulis Trinity dalam artikel mereka berpendapat bahwa penyimpanan terdistribusi mereka bekerja jauh lebih efisien - penulis merasa sulit untuk mengomentari pernyataan ini, tetapi, mengingat keadaan di atas, menemukan itu sangat mungkin: arsitektur PBGL menanggung segel yang berbeda dari waktu ketika mesin multi-core belum menerima distribusi luas.
  
  PBGL juga berbagi masalah dengan versi single-threaded: beberapa sinkronisasi kode, dokumentasi dan contoh, diperburuk oleh kompleksitas sistem yang lebih besar dan lebih sedikit pengguna yang mau berbagi pengalaman yang bermanfaat.
  

BGL dan hewan lainnya

Dengan mempertimbangkan daftar keluhan spesifik yang agak panjang, tidak pantas untuk bertanya: dapatkah penulis merekomendasikan BGL untuk proyek baru pada 2019. Jawabannya adalah ini: penulis percaya bahwa perpustakaan gaya dan aplikasi ini berdasarkan pada mereka harus memiliki masa depan . Adapun pilihan perpustakaan referensi untuk proyek tertentu, kita harus serius mempertimbangkan instrumentasi, tidak melupakan masalah yang tercantum di atas. Jawabannya, jelas, tergantung pada banyak keadaan, termasuk tetapi tidak terbatas pada yang tercantum dalam paragraf berikut:

• Apakah bekerja dengan grafik dalam suatu proyek adalah dasar dari fungsionalitas atau tugas opsional;
• Bisakah sebuah proyek mendapatkan keuntungan melalui penggunaan banyak representasi atau bekerja dengan algoritma yang diketik dengan cukup cukup untuk itu;
• Jenis konkurensi yang paling menguntungkan untuk proyek;
• Nuansa organisasi: keinginan untuk metaprogramming di C ++ di antara karyawan (terutama programmer matematika), dll.

Mungkin, penggunaan BGL dapat dibenarkan baik dalam kasus penggunaan satu kali yang sangat kecil (untuk mengusir atau menyalin sepotong kode kerja dan lupa), atau untuk sistem besar yang meningkatkan fleksibilitas akan membayar untuk entri yang berat dan biaya lainnya dari waktu ke waktu. Dalam kasus lain, masuk akal untuk mempelajari opsi lain dengan cermat.

Adapun alternatif yang mungkin, daftar mereka setidaknya mencakup item berikut :

Yang menarik secara umum adalah pertanyaan tentang klasifikasi berbagai produk perangkat lunak yang berorientasi untuk bekerja dengan grafik. Keragaman mereka, belum lagi jumlahnya, sangat besar. Tanpa berpura-pura menyelesaikan (dan bahkan mengoreksi secara formal) klasifikasi, kita dapat mencoba, bagaimanapun, untuk menyoroti bidang-bidang penting berikut dalam pengembangan aplikasi grafik:

1. Grafik DBMS (neo4j, dll.)
   
   Sistem semacam ini difokuskan untuk melakukan operasi transaksional pada grafik besar (disk terdistribusi). Meskipun API dari sistem seperti itu dapat sangat dikembangkan, kecepatan eksekusi dari algoritma grafik itu sendiri, sejauh yang dapat dinilai, bukanlah prioritas pertama. Sistem bahkan mungkin tidak mencoba memuat seluruh grafik ke dalam memori. Untuk modifikasi dan traversal grafik, bahasa deklaratif (SPARQL, Cypher, GREMLIN) didukung. Sangat penting untuk memastikan kesinambungan dengan sistem SQL tradisional.
2. Ekstensi grafik dari sistem pemrosesan data besar yang bekerja di peta / kurangi paradigma (GraphX ​​dalam Spark, Pegasus dan Giraph untuk Hadoop) dan sistem cluster independen ( MS Trinity / MS Graph Engine , GraphLab). Yang pertama melakukan operasi pada grafik mengimplementasikan model Google Pregel (tetapi tidak hanya itu) dan dapat dikonfigurasi untuk digunakan termasuk node komputasi paralel masif. Baik itu dan yang lain dapat digunakan, antara lain, sebagai dasar untuk proyek perangkat lunak perusahaan.
   
   Meskipun API sistem semacam itu bisa sangat dikembangkan (antara lain, GraphX ​​mendukung SPARQL dan Cypher), fokus utama ketika bekerja dengan mereka adalah menyelesaikan masalah infrastruktur. GraphX ​​dicirikan oleh data yang tidak dapat diubah dan bias dalam pipelining semua operasi. MS Trinity saat ini tidak menyertakan metode tingkat tinggi dan hanya menyediakan satu set primitif untuk bekerja dengan node dan edge. Sistem yang berjalan di atas Hadoop, pada prinsipnya, tidak banyak berguna untuk menyelesaikan masalah grafik arbitrer.
   
3. Sebenarnya pustaka alat universal yang menerapkan sekumpulan metode yang kurang lebih luas (BGL / PBGL, LEMON, dll.), Termasuk yang paralel secara masif (nvGraph, Gunrock).
   
   Berdasarkan pada mereka, sistem aplikasi dapat dibuat yang mengadaptasi algoritma grafik untuk area subjek tertentu.
4. Sistem dan perpustakaan yang berspesialisasi dalam masalah-masalah kompleks tertentu yang penting secara universal (METIS, paraMETIS, Zoltran: partisi grafik, GraphViz, Gephi: visualisasi, GraphBLAS: algoritma aljabar untuk bekerja dengan grafik, dll.).
   
   Banyak aplikasi grafik independen dapat ditetapkan secara kondisional ke kategori ini, analisis terperinci yang membutuhkan terlalu banyak waktu. Yang terakhir berisi aplikasi dari semua varietas yang mungkin: akademis dan komersial, pengguna tunggal dan multi pengguna, baru-baru ini muncul dan ada selama lebih dari satu dekade, dll.

Bagian aplikasi grafik yang tidak jelas tetapi signifikan difokuskan pada tugas Analisis Jaringan dan, sudah, Analisis Jaringan Sosial (Deteksi Komunitas). Anehnya, sistem Analisis Tautan (digunakan, sebagai aturan, oleh berbagai "pejuang kejahatan") jauh lebih jarang terjadi, yang memiliki kesamaan tertentu dengan sistem yang kami kembangkan. Dalam semua kasus, tanpa pemeriksaan khusus, sulit untuk menentukan sifat model data yang digunakan oleh berbagai sistem dan keterbatasan kinerja terkait, volume yang didukung, set operasi, dll.

Catatan

1. BGL bukan pustaka header murni, tetapi saat ini satu-satunya fungsi yang perlu dihubungkan adalah (agak opsional) bekerja dengan file GraphViz DOT. Oleh karena itu, dalam sebagian besar kasus, tidak perlu untuk menautkan dan menghubungkan otomatis dengan versi libbost-graph yang tepat untuk memasukkan header BGL dalam konfigurasi Boost tidak disediakan. Jadi, untuk konsistensi dengan pustaka libboost-regex yang digunakan oleh fungsi BGL non-header, lebih mudah untuk cukup memasukkan header boost \ regex.hpp dari kode proyek, bahkan jika yang terakhir tidak menggunakan ekspresi reguler.
2. Kekacauan tambahan diperkenalkan oleh keberadaan entitas yang kesetaraan nyata mendorong perburuan kucing hitam (mungkin tidak ada) di kamar gelap .
3. Sebelum melanjutkan ke deskripsinya (menggunakan contoh spesifik, di mana ia memanifestasikan dirinya sangat kuat dan tidak menyenangkan), kami mencatat bahwa penulis adalah salah satu dari sedikit orang yang beruntung yang bekerja dengan proyek yang dimuat dalam sistem operasi Windows yang kuat dan jalur kompilasi MSVC yang diselamatkan oleh Tuhan. Ada kemungkinan bahwa masalah yang diuraikan di bawah ini adalah artefak dari garis kompiler ini: berbagai keadaan tertentu menyulitkan untuk melakukan percobaan perbandingan dengan gcc / dentang di lingkungan * nix. Jika demikian, Anda hanya bisa memberi selamat kepada pengguna kompiler lain.
4. Untuk melunakkan yang dalam beberapa kasus, constexpr baru-baru ini muncul jika mungkin akan membantu.
5. Dalam kasus kami, ini menyebabkan perhatian khusus pada fungsi hemat-negara, yang memungkinkan debugging dengan nyaman, pertama-tama membawa sistem ke kondisi awal yang diinginkan dalam perakitan yang dioptimalkan.
6. Dalam praktik saya, karena berbagai alasan, ada kebutuhan untuk mengonversi parameter runtime menjadi argumen templat, dan cukup sering saya harus menggunakan cara yang sangat akurat dan sangat rumit (terinspirasi oleh implementasi sekarang dari boost typeof dan boost lambda untuk C ++ 98, yang langsung mengenai memperlakukan teknik pemrograman dalam C ++ sebagai solusi untuk rebus), di antaranya bintang bersinar seleksi argumen dengan membagi menjadi dua , tetapi, secara umum, masalah utama dengan operasi seperti itu selalu dikaitkan dengan ketidakmampuan untuk mengekspor Jenis yang dipilih di luar ruang lingkup, yang memunculkan pola eksotis.
7. ( — 80 4 50 200 , ) ( ) - . , . , 6-8 — , .
8. , . ( , - , . , , , , , , , ).
9. , , – , , «» (-- ..) . ( , ), , «» , — ( ). , , , - . , , : «» ( ) , «» ( ), , . . , - , « », . , « » ? , , , : – , , , , .
10. . , , .
11. «LIBNAME C++ graph» , stackoverflow. , BGL 500 [boost-graph].