Bayangkan situasi yang khas di tahun pertama: Anda membaca
tentang algoritma Dinits , mengimplementasikannya, tetapi tidak berhasil, dan Anda tidak tahu mengapa. Solusi standar adalah memulai debugging dalam langkah-langkah, setiap kali menggambar keadaan grafik saat ini di selembar kertas, tetapi ini sangat merepotkan. Saya mencoba untuk memperbaiki situasi sebagai bagian dari proyek semester di Rekayasa Perangkat Lunak, dan dalam sebuah posting saya akan memberi tahu Anda bagaimana saya berakhir dengan plug-in untuk Visual Studio. Anda dapat mengunduhnya di
sini , kode sumber dan dokumentasi dapat ditemukan di
sini . Berikut adalah screenshot dari grafik yang diperoleh untuk algoritma Dinits.
Tentang diri saya
Nama saya Olga, saya lulus dari tahun ketiga dengan jurusan "Matematika Terapan dan Ilmu Komputer" di St. Petersburg HSE dengan gelar di bidang Rekayasa Perangkat Lunak. Sebelum masuk universitas, saya tidak terlibat dalam pemrograman.
Penelitian: persyaratan
Di pekerjaan penelitian praktik semester fakultas kami. Biasanya ini terjadi seperti ini: pada awal semester ada presentasi karya penelitian - perwakilan dari berbagai perusahaan menawarkan semua jenis proyek. Kemudian siswa memilih proyek favorit mereka, pengawas memilih siswa favorit mereka, dan sebagainya. Pada akhirnya, setiap siswa menemukan proyek untuk dirinya sendiri.
Tetapi ada cara lain: Anda dapat secara mandiri menemukan penyelia dan proyek, dan kemudian meyakinkan kurator bahwa proyek ini benar-benar dapat menjadi R&D penuh. Untuk melakukan ini, buktikan bahwa:
- Anda akan melakukan sesuatu yang baru. Tentu saja, proyek tersebut mungkin memiliki analog, tetapi opsi Anda harus memiliki beberapa keunggulan dibandingkan mereka.
- Tugasnya seharusnya cukup sulit, yaitu, pekerjaan harus ada selama satu semester, dan bukan untuk sehari. Pada saat yang sama, perlu bahwa proyek itu benar-benar dilakukan dalam satu semester.
- Proyek Anda harus bermanfaat bagi dunia. Artinya, ketika ditanya mengapa ini perlu, Anda seharusnya tidak menjawab: "Ya, saya perlu melakukan semacam riset."
Saya memilih cara kedua. Hal pertama yang harus dilakukan setelah saya setuju dengan penyelia adalah menemukan topik proyek. Daftar ide termasuk: pemeriksa gaya kode untuk Lua, debugger yang memungkinkan Anda untuk menghitung ekspresi di bagian, dan alat untuk olimpiade / pelatihan pemrograman, yang memungkinkan Anda untuk memvisualisasikan apa yang terjadi dalam kode. Yaitu, visualizer untuk struktur data arbitrer yang dikombinasikan dengan debugger. Sebagai contoh, seseorang menulis
pohon Cartesius , dan dalam proses simpul, tepi, simpul saat ini dan seterusnya ditarik. Pada akhirnya, saya memutuskan untuk memikirkan opsi ini.
Rencana kerja proyek
Pekerjaan saya pada proyek terdiri dari tahapan-tahapan berikut:
- Studi tentang bidang studi diperlukan untuk memahami apakah masalah ini telah diselesaikan (maka topik proyek harus diubah), analog apa yang ada, apa keuntungan dan kerugian yang mereka miliki yang bisa saya perhitungkan dalam pekerjaan saya.
- Menentukan fungsionalitas spesifik yang akan dimiliki alat yang dibuat. Tema proyek dinyatakan secara abstrak, dan ini diperlukan untuk memastikan bahwa tugasnya cukup rumit, tetapi pada saat yang sama dapat diselesaikan dalam satu semester.
- Membuat antarmuka pengguna prototipe diperlukan untuk menunjukkan bagaimana alat yang dibuat dapat digunakan. Itu menambahkan bahkan lebih spesifik daripada serangkaian fitur yang dijelaskan oleh kata-kata.
- Pilihan ketergantungan - Anda perlu memahami bagaimana semuanya akan diatur dari sudut pandang pengembang dan memutuskan alat yang akan digunakan dalam proses penulisan kode.
- Membuat prototipe (proof-of-concept) , yaitu, contoh minimal di mana sebagian besar akan di-hardcode. Dengan contoh ini, saya harus berurusan dengan semua alat yang akan saya gunakan, dan juga belajar bagaimana menyelesaikan semua kesulitan yang muncul di sepanjang jalan, sehingga versi final sudah ditulis dengan "bersih."
- Bekerja pada bagian konten , yaitu, pengembangan dan implementasi logika alat.
- Diperlukan perlindungan proyek agar dapat dengan cepat berbicara tentang pekerjaan yang dilakukan dan untuk memberikan kesempatan untuk mengevaluasinya kepada semua orang, bahkan orang-orang yang tidak mencari-cari dalam subjek. Ini adalah pelatihan sebelum kelulusan. Pada saat yang sama, sebuah proyek yang dibuat dengan baik tidak menjamin bahwa laporan tersebut akan menjadi baik, karena memerlukan keterampilan lain, misalnya, kemampuan untuk berbicara kepada publik.
Saya selalu melakukan perencanaan dengan penyelia saya. Kami juga selalu menemukan dan mendiskusikan semua ide yang muncul di sepanjang jalan. Selain itu, penyelia memberi saya saran tentang kode dan membantu dengan manajemen waktu. Tentang semua masalah teknis (bug yang tidak bisa dipahami, dll.) Saya juga selalu melaporkan, tetapi paling sering saya berhasil menyelesaikannya sendiri.
Subjek penelitian
Sebagai permulaan, kepemimpinan kita seharusnya diyakinkan bahwa topik ini layak menjadi pekerjaan penelitian saya. Dan mulai dari titik pertama: pencarian analog.
Ternyata, ada banyak analog. Tetapi kebanyakan dari mereka dirancang untuk visualisasi memori. Artinya, mereka akan melakukan pekerjaan yang bagus dengan visualisasi pohon Cartesian, tetapi mereka tidak dapat memahami bahwa
tumpukan pada array tidak boleh digambarkan sebagai array, tetapi sebagai pohon. Ini termasuk
gdbgui ,
Debugger Tampilan Data , plug-in untuk Eclipse
jGRASP, dan plug-in untuk
Visualizer Struktur Data Studio Visual. Yang terakhir ini juga dibuat untuk masalah pemrograman olimpiade, tetapi hanya dapat memvisualisasikan struktur data pada pointer.
Ada beberapa alat lagi:
Algojammer untuk python (dan kami ingin plus, sebagai bahasa paling populer di kalangan olympiadniki) dan alat
Lens dikembangkan pada 1994. Yang terakhir, dilihat dari deskripsi, melakukan hampir apa yang diperlukan, tetapi, sayangnya, itu dibuat di bawah Sun OS 4.1.3 (sistem operasi dari 1992). Jadi, terlepas dari ketersediaan kode sumber, diputuskan untuk tidak membuang waktu pada arkeologi yang meragukan ini.
Jadi, setelah beberapa penelitian ditemukan bahwa Tula, yang akan melakukan apa yang kita inginkan, dan pada saat yang sama bekerja pada mesin-mesin modern, belum ada di alam.
Definisi Fungsi
Langkah kedua adalah membuktikan bahwa tugas ini cukup rumit, tetapi bisa dilakukan. Untuk melakukan ini, perlu mengusulkan sesuatu yang lebih spesifik daripada "Saya ingin gambar yang indah, dan semuanya menjadi jelas darinya segera".
Dalam proyek ini, kami memutuskan untuk berkonsentrasi pada memvisualisasikan hanya grafik: ada banyak algoritma pada grafik yang dapat diimplementasikan dengan cara yang berbeda, dan bahkan jika dipersempit, tugas masih tetap non-sepele.
Juga kurang lebih jelas bahwa alat tersebut entah bagaimana harus diintegrasikan dengan debugger. Kita harus dapat melihat nilai-nilai variabel dan ekspresi, dan menggambar gambar yang sudah jadi dari nilai-nilai ini.
Setelah itu, perlu untuk membuat bahasa tertentu yang memungkinkan kita untuk membuat grafik sesuai dengan kondisi program saat ini seperti yang kita inginkan. Selain grafik itu sendiri, perlu menyediakan kemampuan untuk mengubah warna simpul dan tepi, menambahkan label sewenang-wenang kepada mereka dan mengubah properti lainnya. Dengan demikian, ide pertama adalah:
- Tentukan apa yang kita miliki simpul, misalnya, angka dari 0 hingga n.
- Tentukan keberadaan tepi antara simpul menggunakan kondisi Boolean. Dalam hal ini, ujung-ujungnya dari tipe yang berbeda, dan masing-masing tipe memiliki set properti sendiri.
- Selanjutnya, kita dapat mendefinisikan properti vertex seperti warna, juga menggunakan kondisi Boolean.
- Ikuti langkah-langkah dengan debugger: semua ekspresi dihitung, semua kondisi diperiksa, dan, tergantung pada ini, grafik dibuat.
Prototipe Antarmuka Pengguna
Saya menggambar prototipe antarmuka pengguna di
NinjaMock . Ini diperlukan untuk lebih memahami bagaimana tampilan antarmuka dari sudut pandang pengguna, dan tindakan apa yang perlu dilakukan. Jika ada masalah dengan prototipe, kita akan memahami bahwa ada beberapa inkonsistensi logis, dan ide ini harus dibuang. Untuk kesetiaan, saya mengambil beberapa algoritma. Gambar di bawah ini menunjukkan contoh bagaimana saya membayangkan pengaturan visualisasi
DFS dan
algoritma Floyd .
Seperti yang saya bayangkan pengaturan untuk DFS. Grafik disimpan sebagai daftar adjacency, sehingga tepi antara simpul i dan j ditentukan oleh kondisi g[i].find() != g[i].end() (pada kenyataannya, agar tidak menggandakan tepi, perlu untuk memeriksa bahwa i <= j ). Jalur DFS ditampilkan secara terpisah: p[j] == i . Tepi ini akan berorientasi.
Saya berasumsi bahwa untuk algoritma Floyd, akan perlu untuk menggambar hitam tepi nyata yang disimpan dalam array c , dan abu-abu - jalur terpendek yang ditemukan pada tahap ini, disimpan dalam array d . Untuk setiap tepi dan jalur terpendek, bobotnya tertulis.Pemilihan Ketergantungan
Untuk langkah selanjutnya, perlu dipahami bagaimana melakukan semua ini. Pertama-tama, diperlukan integrasi dengan debugger. Hal pertama yang terlintas dalam pikiran ketika kata "debugger" adalah gdb, tetapi kemudian Anda harus membuat seluruh antarmuka grafis dari awal, yang sangat sulit bagi siswa untuk melakukannya dalam satu semester. Ide jelas kedua adalah membuat plugin untuk beberapa lingkungan pengembangan yang ada. Sebagai opsi, saya mempertimbangkan QTCreator, CLion dan Visual Studio.
Opsi CLion segera dibuang, karena, pertama, ia telah menutup kode sumber, dan kedua, semuanya sangat buruk dengan dokumentasi (dan tidak ada yang membutuhkan kesulitan tambahan). QTCreator, tidak seperti Visual Studio, adalah cross-platform dan open source, dan karena itu, pada awalnya kami memutuskan untuk memikirkannya.
Namun ternyata, QTCreator tidak diadaptasi dengan baik untuk ekstensi menggunakan plugin. Langkah pertama dalam membuat plugin untuk QTCreator adalah membangun dari sumber. Butuh saya satu setengah minggu. Pada akhirnya, saya mengirim dua laporan bug (
di sana -
sini ) mengenai proses perakitan. Ya, itulah upaya yang dilakukan untuk membangun QTCreator hanya untuk mengetahui bahwa debugger di QTCreator tidak memiliki API publik. Saya kembali ke opsi lain, yaitu Visual Studio.
Dan ini ternyata menjadi keputusan yang tepat: Visual Studio tidak hanya memiliki API yang hebat, tetapi juga dokumentasi yang sangat baik untuk itu.
_debugger.GetExpression(...).Value ekspresi disederhanakan dengan memanggil
_debugger.GetExpression(...).Value . Visual Studio juga menyediakan kemampuan untuk beralih di atas bingkai, dan mengevaluasi ekspresi dalam konteks salah satu dari mereka. Untuk melakukan ini, ubah properti
CurrentStackFrame ke yang diperlukan. Anda juga dapat melacak pembaruan untuk kontes debugger untuk menggambar ulang gambar saat berubah.
Tentu saja, tidak seharusnya saya terlibat dalam visualisasi grafik dari awal - ada banyak perpustakaan khusus untuk ini. Yang paling terkenal dari mereka adalah
Graphviz , dan kami berencana untuk menggunakannya pada awalnya. Tetapi untuk plug-in untuk Visual Studio, akan lebih logis untuk menggunakan perpustakaan untuk C #, karena saya akan menulis di atasnya. Saya mencari Google sedikit dan menemukan perpustakaan
MSAGL : ia memiliki semua fungsi yang diperlukan dan memiliki antarmuka yang sederhana dan intuitif.
Bukti konsep
Sekarang, memiliki mekanisme untuk menghitung ekspresi sewenang-wenang di satu sisi dan perpustakaan untuk memvisualisasikan grafik di sisi lain, perlu membuat prototipe. Prototipe pertama dibuat untuk DFS, kemudian
algoritma Dinits,
algoritma Kuhn ,
pencarian komponen yang terhubung ganda , pohon Cartesian, dan
SNM diambil sebagai contoh. Saya mengambil implementasi lama dari algoritma ini dari tahun pertama hingga tahun kedua, membuat plug-in baru, menggambar grafik yang sesuai dengan tugas ini (semua nama variabel di-hardcode). Berikut adalah contoh grafik yang saya dapatkan untuk algoritma Kuhn:
Pada grafik ini, tepi pencocokan saat ini ditampilkan dalam warna ungu, deks dfs saat ini ditampilkan dalam warna merah, simpul yang dikunjungi berwarna abu-abu, tepi rantai bergantian yang bukan dari pencocokan ditampilkan dalam warna merah.Saya menganggap itu diperbolehkan untuk sedikit mengubah kode algoritma untuk membuatnya lebih mudah untuk divisualisasikan. Misalnya, dalam kasus pohon Cartesian, ternyata lebih mudah untuk menambahkan semua node yang dibuat ke vektor daripada memotong pohon di dalam plugin.
Penemuan yang tidak menyenangkan adalah bahwa debugger di Visual Studio tidak mendukung metode dan fungsi panggilan dari STL. Ini berarti bahwa tidak mungkin untuk memeriksa keberadaan elemen dalam wadah menggunakan
std::find , seperti yang diasumsikan semula. Masalah ini dapat diselesaikan baik dengan membuat fungsi yang ditentukan pengguna, atau dengan menduplikasi properti "elemen yang terkandung dalam wadah" dalam array Boolean.
Di plugin percobaan saya, sesuatu seperti yang berikut terjadi (jika grafik disimpan sebagai daftar adjacency):
- Pertama, perulangan
for dari 0 ke _debugger.GetExpression("n").Value , yang menambahkan semua simpul ke grafik, masing-masing dengan nomornya sendiri.
- Lalu ada dua bersarang
for _debugger.GetExpression($"g[{i}].size()").Value , yang pertama untuk i - dari 0 ke n , yang kedua untuk j - dari 0 ke _debugger.GetExpression($"g[{i}].size()").Value , dan tepi {i, _debugger.GetExpression($"g[{i}][{j}]").Value} .
- Jika diperlukan, beberapa informasi tambahan ditambahkan ke label simpul dan tepi. Misalnya, nilai array
d , yang bertanggung jawab untuk jarak ke simpul yang dipilih.
- Jika algoritma didasarkan pada dfs, maka satu loop melewati semua frame, dan semua simpul dalam stack (
stackFrame.FunctionName.Equals("dfs") && stackFrame.Arguments.Item(1) == v ) disorot dengan warna abu-abu.
- Kemudian, untuk setiap
i dari 0 hingga n , yang menunjukkan jumlah simpul, beberapa kondisi diperiksa, dan jika mereka puas, maka beberapa properti berubah di puncak, paling sering warnanya.
Pada saat itu, saya menulis kode “seperlunya”, tanpa mencoba membuat skema umum untuk semua algoritma, atau menulis kode setidaknya entah bagaimana dengan indahnya. Pembuatan setiap plugin baru dimulai dengan copy-paste yang sebelumnya.
Konfigurasi grafik
Setelah penelitian, perlu dibuat skema umum yang dapat diterapkan untuk semua algoritma. Hal pertama yang diperkenalkan adalah indeks untuk simpul dan tepi. Setiap indeks memiliki nama dan rentang akhir yang unik, dihitung menggunakan
_debugger.GetExpression . Untuk mengakses nilai indeks, gunakan namanya yang dikelilingi oleh __ (mis. __X__). Ekspresi dengan tempat untuk menggantikan nilai indeks, serta nama fungsi saat ini (__CURRENT_FUNCTION__) dan nilai argumennya (__ARG1__, __ARG2__, ...), disebut template.
Indeks diganti untuk setiap titik atau tepi, dan setelah itu dihitung dalam debugger. Templat digunakan untuk menyaring beberapa nilai indeks (jika grafik disimpan sebagai matriks adjacency
c , maka indeks akan a dan b dari 0 ke n, dan templat untuk validasi adalah
c[__a__][__b__] ). Batas-batas rentang indeks juga merupakan templat, karena mungkin berisi indeks sebelumnya.
Grafik dapat memiliki berbagai jenis simpul dan tepi. Misalnya, dalam hal mencari pencocokan maksimum dalam grafik bipartit, setiap fraksi dapat diindeks secara terpisah. Oleh karena itu, konsep keluarga diperkenalkan untuk simpul dan tepi. Untuk setiap keluarga, pengindeksan dan semua properti ditentukan secara independen. Dalam hal ini, ujung-ujungnya dapat menghubungkan simpul dari keluarga yang berbeda.
Anda bisa menetapkan properti spesifik ke keluarga vertex atau edge yang akan diterapkan secara selektif ke elemen dalam keluarga. Properti ini diterapkan jika kondisinya terpenuhi. Kondisi terdiri dari templat yang mengevaluasi
true atau
false , dan ekspresi reguler untuk nama fungsi. Kondisi diperiksa baik hanya untuk bingkai kaca saat ini, atau untuk semua bingkai kaca (dan kemudian dianggap terpenuhi jika dipenuhi setidaknya satu).
Properti sangat beragam. Untuk simpul: label, isi warna, warna batas, lebar tepi, bentuk, gaya tepi (misalnya, garis putus-putus). Untuk tepi: label, warna, lebar, gaya, orientasi (Anda dapat menentukan dua panah - dari awal hingga akhir atau sebaliknya; dalam hal ini, bisa ada dua panah pada saat yang sama).
Penting bahwa setiap kali grafik digambar dari awal, dan keadaan sebelumnya tidak diperhitungkan dengan cara apa pun. Ini bisa menjadi masalah jika grafik berubah secara dinamis selama algoritme - simpul dan tepi dapat secara dramatis mengubah posisi mereka, dan kemudian sulit untuk memahami apa yang terjadi.
Penjelasan terperinci tentang konfigurasi grafik dapat ditemukan di
sini .
Antarmuka pengguna
Dengan antarmuka, saya memutuskan untuk tidak terlalu repot. Jendela utama dengan pengaturan (
ToolWindow ) berisi textarea untuk
konfigurasi berseri dalam JSON dan daftar keluarga vertex dan edge. Setiap keluarga memiliki jendela sendiri dengan pengaturan, dan setiap properti dalam keluarga memiliki satu jendela lagi (diperoleh tiga tingkat sarang). Grafik itu sendiri digambar dalam jendela terpisah. Tidak berfungsi untuk meletakkannya di ToolWindow, jadi saya mengirim
laporan bug ke pengembang MSAGL, tetapi mereka menjawab bahwa ini bukan kasus penggunaan target.
Laporan bug lain dikirim ke Visual Studio, karena TextBox kadang-kadang tergantung di jendela pengaturan tambahan.
Plugin
Untuk mengkonfigurasi grafik, plugin memiliki antarmuka pengguna dan kemampuan untuk (menonaktifkan) serialisasi konfigurasi dalam JSON. Skema umum interaksi semua komponen adalah sebagai berikut:
Biru menunjukkan komponen yang ada pada awalnya, abu-abu - yang saya buat. Ketika Visual Studio dimulai, ekstensi diinisialisasi (di sini komponen utama ditetapkan sebagai Utama). Pengguna mendapat kesempatan untuk menentukan konfigurasi melalui antarmuka. Setiap kali konteks debugger diubah, komponen utama diberitahu. Jika konfigurasi ditentukan dan program yang sedang di-debug dieksekusi, GraphRenderer diluncurkan. Dia menerima input konfigurasi dan dengan bantuan debugger membangun grafik di atasnya, yang kemudian ditampilkan di jendela khusus.
Contohnya
Akibatnya, saya membuat alat yang memungkinkan Anda untuk memvisualisasikan algoritma grafik dan membutuhkan perubahan kecil dalam kode. Ini telah diuji pada delapan tugas berbeda. Berikut adalah beberapa gambar yang dihasilkan:
Algoritma Ford-Bellman : titik di mana kita menghitung jalur terpendek ditunjukkan oleh sebuah rumah, jarak terpendek saat ini yang ditemukan untuk simpul adalah d, merah menunjukkan tepi sepanjang relaksasi dilewati.
Animasi dengan DFS - simpul saat ini ditampilkan dalam warna merah, simpul dalam tumpukan berwarna abu-abu, dan simpul yang dikunjungi lainnya berwarna hijau. Iga raspberry menunjukkan arah jalan pintas.Lebih banyak contoh algoritma tersedia di
sini.Perlindungan NIR
Untuk melindungi pekerjaan penelitian, siswa diwajibkan dalam tujuh menit untuk menceritakan tentang pekerjaan mereka selama satu semester. Pada saat yang sama, terlepas dari apakah topik itu diusulkan sebagai bagian dari presentasi karya penelitian atau siswa menemukannya sendiri, Anda harus dapat menjawab untuk membenarkan mengapa topik proyek berada di bawah persyaratan yang dijelaskan di awal. Biasanya, sebuah laporan disusun sebagai berikut: pertama ada motivasi, kemudian tinjauan analog, dikatakan tentang mengapa mereka tidak sesuai dengan kita, kemudian tujuan dan sasaran dirumuskan, dan kemudian masing-masing tugas dijelaskan bagaimana hal itu diselesaikan. Pada akhirnya ada slide dengan hasilnya, yang sekali lagi mengatakan bahwa tujuan telah tercapai dan semua tugas diselesaikan.
Karena saya sudah memutuskan pada motivasi dan ulasan analog pada tahap awal, saya hanya perlu mengumpulkan semua informasi dan mengompresnya menjadi tujuh menit. Pada akhirnya, saya berhasil, pertahanan berjalan lancar, saya diberi skor maksimal untuk penelitian.
Referensi