CXXGraph
v4.1.0
CXXGraph adalah pustaka C++ komprehensif yang mengelola algoritma grafik. Pustaka khusus header ini berfungsi sebagai alternatif dari Boost Graph Library (BGL).
Kami mencari:
Jika Anda tertarik, silakan hubungi kami di [email protected] atau berkontribusi pada proyek ini. Kami menunggumu!
| Selesai | Keterangan | Tanggal Penyelesaian |
|---|---|---|
| ✔️ | Rilis 0.4.0 | 7 Oktober 2022 |
| ✔️ | Rilis 0.5.0 | 23 Maret 2023 |
| ✔️ | Rilis Stabil Pertama 1.0.0 | 28 Maret 2023 |
| ✔️ | Rilis 1.0.1 | 7 Mei 2023 |
| ✔️ | Rilis 1.1.0 | 8 Mei 2023 |
| ✔️ | Rilis Stabil 2.0.0 | 1 Juni 2023 |
| ✔️ | Rilis Stabil 3.0.0 | 3 November 2023 |
| ✔️ | Rilis 3.1.0 | 9 Januari 2023 |
| Perkenalkan Hipergraf #122 | TBD | |
| Rilis Stabil 4.0.0 | TBD |
Untuk menginstal pada sistem Unix/Linux, jalankan perintah berikut dari baris perintah:
$ sudo tar xjf CXXGraph-{version}.tar.bz2
Untuk mencopot pemasangan:
$ sudo rm -f /usr/include/Graph.hpp /usr/include/CXXGraph*
Untuk menginstal pada sistem Fedora/CentOS/RedHat, jalankan perintah berikut dari baris perintah:
$ sudo rpm -ivh CXXGraph-{version}.noarch.rpm
Untuk mencopot pemasangan:
$ sudo rpm -e CXXGraph-{version}
Untuk menginstal pada sistem Debian/Ubuntu, jalankan perintah berikut dari baris perintah:
$ sudo dpkg -i CXXGraph_{version}.deb
Untuk mencopot pemasangan:
$ sudo apt-get remove CXXGraph
Untuk instalasi yang dikompilasi sendiri menggunakan CMake, jalankan perintah berikut dari baris perintah setelah kompilasi selesai:
$ sudo make install
Penjelasan Kelas dapat ditemukan di Bagian Kelas pada Dokumentasi Doxygen
Untuk menggunakan perpustakaan cukup letakkan file header di tempat yang Anda perlukan. Semudah itu!
Pekerjaan Sedang Berlangsung
Unit-Test memerlukan CMake 3.9 dan yang lebih baru, serta pustaka GoogleTest .
Tes Google
git clone https://github.com/google/googletest.git
cd googletest # Main directory of the cloned repository
mkdir -p build # Create a directory to hold the build output
cd build
cmake .. # Generate native build scripts for GoogleTest
make # Compile
sudo make install # Install in /usr/local/ by defaultDari direktori dasar:
mkdir -p build # Create a directory to hold the build output
cd build # Enter the build folder
cmake -DTEST=ON .. # Generate native build scripts for GoogleTest,
make # CompileSetelah build dikompilasi, jalankan "test_exe" yang dapat dieksekusi di direktori "build" dengan perintah berikut:
./test_exe
Tolok Ukur memerlukan CMake 3.9 dan yang lebih baru, pustaka GoogleTest , dan pustaka Google Benchmark .
Tolok Ukur Google
# Check out the library
$ git clone https://github.com/google/benchmark.git
# Google Benchmark requires GoogleTest as a dependency. Add the source tree as a subdirectory
$ git clone https://github.com/google/googletest.git benchmark/googletest
# Go to the library's root directory
$ cd benchmark
# Make a build directory to place the build output
$ cmake -E make_directory " build "
# Generate the build system files with CMake
$ cmake -E chdir " build " cmake -DCMAKE_BUILD_TYPE=Release ../
# If starting with CMake 3.13, you can use the following:
# cmake -DCMAKE_BUILD_TYPE=Release -S . -B "build"
# Build the library
$ cmake --build " build " --config Release
# Install the library
$ sudo cmake --build " build " --config Release --target installDari direktori dasar:
mkdir -p build # Create a directory to hold the build output
cd build # Enter the build folder
cmake -DBENCHMARK=ON .. # Generate native build scripts for Google Benchmark
make # CompileSetelah build dikompilasi, jalankan "benchmark" yang dapat dieksekusi di direktori "build" dengan perintah berikut:
./benchmark
Anda dapat memeriksa hasil benchmark menggunakan link ini.
Untuk membuat paket tarball, jalankan perintah berikut dari baris perintah:
# Enter Packaging Directory
$ cd packaging
# Execute the script to generate tarballs
$ ./tarballs.shUntuk membuat paket RPM, jalankan perintah berikut dari baris perintah:
# Enter Packaging Directory
$ cd packaging/rpm
# Execute the script to generate tarballs
$ ./make_rpm.shUntuk membuat paket deb, jalankan perintah berikut dari baris perintah:
# Enter Packaging Directory
$ cd packaging/deb
# Execute the script to generate tarballs
$ ./make_deb.shGrafik Algoritma Jalur Terpendek Dijkstras(Jalur Terpendek Dijkstra) [Algoritma Dijkstra] (https://www.interviewbit.com/blog/find-shortest-path-dijkstras-algorithm/) digunakan untuk mencari jalur terpendek dari node sumber ke semua node lain yang dapat dijangkau dalam grafik. Algoritme awalnya mengasumsikan semua node tidak dapat dijangkau dari node sumber tertentu sehingga kami menandai jarak semua node sebagai tak terhingga. (tak terhingga) dari simpul sumber (INF / tak terhingga menandakan tidak dapat dijangkau).
Spesialisasi panggilan dari algoritma dijkstra.
Ketika bobot tepi berupa bilangan bulat kecil (dibatasi oleh parameter C ), antrian khusus yang memanfaatkan fakta ini dapat digunakan untuk mempercepat algoritma Dijkstra. Algoritma pertama jenis ini adalah algoritma Dial (Dial 1969) untuk graf dengan bobot tepi bilangan bulat positif, yang menggunakan antrian bucket untuk memperoleh waktu berjalan O(|E|+|V|C) .(sumber wikipedia)
Di bawah ini adalah algoritma lengkap:
Di tautan ini Anda dapat menemukan ilustrasi langkah demi langkah.
Algoritma Prim Algoritma Prim adalah algoritma serakah yang mencari pohon merentang minimum untuk graf tak berarah berbobot. Artinya, ia menemukan subset dari sisi-sisi yang membentuk pohon yang mencakup setiap titik, dengan bobot total semua sisi pada pohon diminimalkan. Algoritme beroperasi dengan membangun pohon ini satu titik pada satu waktu, dari titik awal yang sembarang, pada setiap langkah menambahkan koneksi termurah dari pohon ke titik lainnya.
Tangga:
(Pencarian Pertama Luas) Algoritma Pencarian Pertama Luas(Pencarian Pertama Luas) Pencarian Pertama Luas , juga dikutip sebagai BFS , adalah Algoritma Traversal Grafik. Kompleksitas Waktu O(|V| + |E|) dengan V adalah jumlah simpul dan E adalah jumlah sisi pada grafik. Aplikasi Breadth First Search adalah :
Dan masih banyak lagi...
(Pencarian Pertama Kedalaman) Algoritma Pencarian Kedalaman Pertama (Pencarian Pertama Kedalaman) Pencarian Kedalaman Pertama , juga dikutip sebagai DFS , adalah Algoritma Traversal Grafik. Kompleksitas Waktu O(|V| + |E|) dengan V adalah jumlah simpul dan E adalah jumlah sisi pada graf. Penerapan Depth First Search adalah:
Dan masih banyak lagi...
Pencarian Pertama Terbaik Pencarian Pertama Terbaik adalah kelas algoritma pencarian yang melintasi grafik dengan menjelajahi node paling menjanjikan yang dipilih berdasarkan fungsi evaluasi. Kompleksitas waktu kasus terburuk adalah O(n * log n) dengan n adalah jumlah node dalam grafik.
Siklus (teori grafik)
Keberadaan siklus dalam graf berarah dan tidak berarah dapat ditentukan oleh apakah penelusuran depth-first (DFS) menemukan tepi yang menunjuk ke nenek moyang dari simpul saat ini (yang berisi tepi belakang). Semua tepi belakang yang dilewati DFS adalah bagian dari siklus. Dalam graf tak berarah, tepi ke induk suatu simpul tidak boleh dihitung sebagai tepi belakang, namun menemukan simpul lain yang telah dikunjungi akan menunjukkan tepi belakang. Dalam kasus graf tak berarah, hanya O(n) waktu yang diperlukan untuk menemukan siklus dalam graf n-simpul, karena paling banyak n − 1 sisi dapat berupa sisi pohon.
Banyak algoritme pengurutan topologi juga akan mendeteksi siklus, karena siklus tersebut merupakan hambatan bagi keberadaan tatanan topologi. Selain itu, jika graf berarah telah dibagi menjadi komponen-komponen yang terhubung kuat, siklus hanya ada di dalam komponen-komponen tersebut dan tidak ada di antara komponen-komponen tersebut, karena siklus-siklus tersebut terhubung kuat.
Untuk grafik berarah, algoritma berbasis pesan terdistribusi dapat digunakan. Algoritma ini mengandalkan gagasan bahwa pesan yang dikirim oleh sebuah simpul dalam suatu siklus akan kembali ke dirinya sendiri. Algoritme deteksi siklus terdistribusi berguna untuk memproses grafik berskala besar menggunakan sistem pemrosesan grafik terdistribusi pada cluster komputer (atau superkomputer).
Penerapan deteksi siklus mencakup penggunaan grafik tunggu untuk mendeteksi kebuntuan dalam sistem bersamaan.
Algoritma Bellman-Ford dapat digunakan untuk mencari jarak terpendek antara node sumber dan node target. Kompleksitas Waktu O(|V| . |E|) dimana V adalah jumlah simpul dan E adalah jumlah sisi pada graf yang lebih tinggi dari algoritma jalur terpendek Dijkstra. Kompleksitas waktu algoritma dijkstra adalah O(|E| + |V| log |v| ). Keunggulan Bellman-ford dibandingkan Dijkstra adalah dapat menangani graf dengan bobot sisi negatif. Selanjutnya, jika grafik berisi siklus berbobot negatif maka algoritma dapat mendeteksi dan melaporkan keberadaan siklus negatif.
Video ini memberikan gambaran bagus tentang implementasi algoritma. Kuliah MIT ini memberikan bukti kebenaran Bellman-Ford & kemampuannya mendeteksi siklus negatif. Aplikasi:
Algoritma Floyd Warshall
Kami menginisialisasi matriks solusi sama dengan matriks grafik masukan sebagai langkah pertama. Kemudian kami memperbarui matriks solusi dengan menganggap semua simpul sebagai simpul perantara. Idenya adalah untuk memilih satu per satu semua simpul dan memperbarui semua jalur terpendek yang mencakup simpul yang dipilih sebagai simpul perantara dalam jalur terpendek. Ketika kita memilih simpul nomor k sebagai simpul perantara, kita telah menganggap simpul {0, 1, 2, .. k-1} sebagai simpul perantara. Untuk setiap pasangan (i, j) dari simpul sumber dan simpul tujuan, terdapat dua kemungkinan kasus.
Reduksi Transitif
Algoritme ini digunakan untuk membuat grafik berarah dengan jangkauan yang sama dan memenuhi penutupan transitif, dengan sisi sesedikit mungkin. Lebih konkretnya, ini menciptakan grafik ekuivalen minimum dengan sisi sesedikit mungkin, menghilangkan jalur "hubungan pendek" melalui grafik.
Hal ini dilakukan dengan mengulangi setiap pasangan node, memeriksa apakah ada dua sisi yang mengarah keluar dari node pertama ATAU keluar dari node terakhir, menghapus tepi pasangan node jika ada.
Dalam pseudocode: foreach x in graph.vertices foreach y in graph.vertices foreach z in graph.vertices hapus edge xz jika edge xy dan yz ada
Implementasi kami memiliki gerbang if yang melakukan pemeriksaan awal untuk edge di banyak tempat, yang memberikan runtime sedikit lebih cepat daripada pseudocode kubik di sini.
Algoritma Kruskal dapat digunakan untuk mencari hutan merentang minimum suatu graf berbobot tepi tak berarah. Kompleksitas Waktu O(E log E) = O(E log V) dengan V adalah jumlah simpul dan E adalah jumlah sisi pada graf. Batasan kecepatan utama untuk algoritma ini adalah pengurutan tepi.
Untuk pemahaman cepat tentang prosedur algoritme, lihat video ini. Beberapa aplikasi kehidupan nyata adalah:
Algoritma lain untuk mencari hutan rentang minimum adalah algoritma Prim atau algoritma Borůvka.
Algoritma Borůvka merupakan algoritma serakah yang dapat digunakan untuk mencari pohon merentang minimum pada suatu graf, atau hutan merentang minimum pada kasus graf yang tidak terhubung.
Algoritme dimulai dengan mencari bobot minimum sisi yang datang ke setiap titik pada grafik, dan menambahkan semua sisi tersebut ke hutan. Kemudian, proses serupa diulangi dengan mencari tepi berbobot minimum dari setiap pohon yang dibangun sejauh ini ke pohon berbeda, dan menambahkan semua tepi tersebut ke dalam hutan. Setiap pengulangan proses ini mengurangi jumlah pohon, dalam setiap komponen grafik yang terhubung, hingga paling banyak setengah dari nilai sebelumnya, sehingga setelah banyak pengulangan secara logaritmik, proses tersebut selesai. Jika hal ini terjadi, kumpulan tepi yang ditambahkannya akan membentuk hutan bentang minimum.
Algoritma Borůvka terlihat mengambil O(log V) iterasi dari loop terluar hingga berakhir, dan oleh karena itu berjalan dalam waktu O(E log V), dimana E adalah jumlah sisi, dan V adalah jumlah simpul dalam G (dengan asumsi E ≥ V).
Definisi matematis dari soal: Misalkan G adalah himpunan titik-titik pada suatu graf dan n adalah suatu titik tertentu pada himpunan tersebut. Misalkan C adalah himpunan bagian tidak ketat dari G yang memuat n dan semua node yang dapat dijangkau dari n, dan misalkan C' menjadi komplemennya. Ada himpunan ketiga M, yang merupakan himpunan bagian tidak ketat dari C yang memuat semua simpul yang dapat dijangkau dari simpul mana pun di C'. Masalahnya adalah menemukan semua node milik C tetapi bukan milik M.
Algoritma yang saat ini diterapkan:
Aplikasi:
Algoritma ini digunakan dalam sistem pengumpulan sampah untuk memutuskan objek lain mana yang perlu dilepaskan, mengingat satu objek akan segera dilepaskan.
Algoritma Ford-Fulkerson merupakan algoritma serakah untuk mencari aliran maksimum dalam suatu jaringan aliran. Ide di balik algoritma ini adalah sebagai berikut: selama ada jalur dari sumber (simpul awal) ke wastafel (simpul akhir), dengan kapasitas yang tersedia di semua sisi jalur, kami mengirimkan aliran di sepanjang salah satu jalur. Lalu kita mencari jalan lain, dan seterusnya. Jalur dengan kapasitas yang tersedia disebut jalur augmenting.
Algoritma Kosaraju merupakan algoritma waktu linier untuk mencari komponen-komponen yang terhubung kuat pada suatu graf berarah. Hal ini didasarkan pada pemikiran bahwa jika seseorang dapat mencapai titik v yang dimulai dari titik u, maka ia harus dapat mencapai titik u yang dimulai dari titik v dan jika demikian, dapat dikatakan bahwa titik u dan v adalah sangat terhubung - mereka berada dalam sub-grafik yang sangat terhubung. Berikut ini contohnya:
1). Buat tumpukan kosong 'S' dan lakukan traversal DFS pada grafik. Dalam traversal DFS, setelah memanggil DFS rekursif untuk simpul yang berdekatan dari sebuah simpul, dorong simpul tersebut ke tumpukan. 2). Membalikkan arah semua busur untuk mendapatkan grafik transpos. 3). Satu demi satu munculkan sebuah simpul dari S sementara S tidak kosong. Biarkan simpul yang muncul menjadi 'v'. Ambil v sebagai sumber dan lakukan DFS (panggil DFSUtil(v)). DFS yang dimulai dari v mencetak komponen v yang terhubung kuat.
Algoritma Kahn menemukan pengurutan topologi dengan menghapus node dalam grafik yang tidak memiliki tepi masuk secara berulang. Ketika sebuah node dihapus dari grafik, node tersebut ditambahkan ke urutan topologi dan semua tepinya dihilangkan sehingga memungkinkan kumpulan node berikutnya tanpa tepi masuk untuk dipilih.
Algoritma Welsh Powell Coloring merupakan algoritma pewarnaan titik serakah. Algoritma ini juga digunakan untuk mencari bilangan kromatik suatu graf.
Algoritma Welsh Powell terdiri dari langkah-langkah berikut:
Algoritme mengembalikan hasil std::map<Node, int> yang menetapkan setiap node ke warna yang diurutkan berdasarkan bilangan bulat. Pengguna juga dapat menanyakan urutan kromatik minimum grafik dengan menanyakan nilai tertinggi dari peta yang dihasilkan.
std::map<Node, int > result = graph.welshPowellColoring();
auto chromatic_color = std::max_element(result.begin(), result.end(),
[]( const auto & lhs, const auto & rhs) {
return lhs. second < rhs. second ;
}Pewarnaan minimum dimulai dari 1, bukan 0.
Algoritme mengasumsikan grafik tidak berarah. Semua sumber dan inspirasi dihubungkan dalam deklarasi algoritma dan kasus uji.
Partisi potongan titik membagi sisi-sisi suatu graf menjadi partisi-partisi yang berukuran sama. Simpul-simpul yang menampung titik-titik ujung suatu sisi juga ditempatkan pada partisi yang sama dengan sisi itu sendiri. Namun, simpul-simpul tersebut tidak unik di seluruh partisi dan mungkin harus direplikasi (dipotong), karena distribusi tepinya di seluruh partisi yang berbeda.
Faktor replikasi mengkuantifikasi berapa banyak simpul yang direplikasi melalui komputer dibandingkan dengan jumlah simpul pada grafik masukan asli.
Algoritma ini adalah pemotongan simpul sederhana dalam mode Round-Robin. Dibutuhkan tepi grafik asli dan menugaskannya ke partisi, membaginya dalam ukuran yang sama (atau serupa). Algoritma ini tidak menangani optimasi pada replikasi vertex (Faktor Replikasi) tetapi hanya menyeimbangkan edge pada partisi.
Algoritme partisi serakah menggunakan seluruh riwayat penugasan tepi untuk membuat keputusan berikutnya. Algoritme menyimpan himpunan partisi A(v) yang mana setiap simpul v yang telah diamati telah ditetapkan dan ukuran partisi saat ini. Saat memproses tepi e ∈ E yang menghubungkan simpul vi, vj ∈ V , algoritme serakah mengikuti serangkaian aturan sederhana berikut:
Algoritma Tingkat Tinggi (adalah) Replikasi Pertama (HDRF) adalah algoritma pemotongan titik serakah seperti yang dijelaskan dalam makalah ini. Algoritma ini mencoba mengoptimalkan Faktor Replikasi dengan menggunakan riwayat penugasan tepi dan derajat titik tambahan. Dengan fungsi yang mempertimbangkan kedua faktor ini, hitung partisi terbaik untuk menetapkan tepi yang dianalisis. Replika yang dibuat didasarkan pada derajat dari simpul tersebut, dan simpul yang direplikasi kemungkinan besar adalah apa yang disebut "Hub-Node", yaitu simpul dengan derajat yang lebih tinggi.
Pemotongan Verteks yang Efisien dan Seimbang (EBV) adalah algoritma pemotongan simpul offline seperti yang dijelaskan dalam makalah ini. Algoritma ini mencoba untuk menyeimbangkan partisi sehubungan dengan jumlah tepi dan simpul dari setiap partisi dan Faktor Replikasi. Ini menerapkan rumus untuk mengevaluasi partisi yang menetapkan sisi yang juga mempertimbangkan jumlah total sisi dan simpul pada grafik. Rumus evaluasinya adalah sebagai berikut:
Nilai terendah diambil sebagai Id partisi.
Matriks Derajat adalah matriks persegi yang memberikan wawasan tentang konektivitas node dalam grafik. Untuk graf berarah, ini mencerminkan jumlah sisi masuk dan keluar untuk setiap node, sedangkan untuk graf tidak berarah, ini mewakili jumlah sisi yang datang ke setiap node.
Matriks Laplacian merupakan matriks persegi yang diturunkan dari matriks ketetanggaan dan matriks derajat suatu graf. Ini berperan penting dalam menganalisis berbagai properti grafik, seperti keterhubungan, jumlah pohon merentang, dan karakteristik spektral lainnya.
Matriks Transisi umumnya digunakan dalam studi Rantai Markov dan proses stokastik. Dalam konteks grafik, ini menunjukkan probabilitas transisi dari satu node ke node lainnya, sering kali berdasarkan bobot tepi atau kriteria yang telah ditentukan. Matriks ini dapat diterapkan di berbagai bidang seperti analisis jaringan, pembelajaran mesin, dan pengoptimalan.
Jika Anda ingin memberikan dukungan, Anda dapat membuat permintaan tarik atau melaporkan masalah . Jika Anda ingin mengubah kode, memperbaiki masalah, atau menerapkan fitur baru, silakan baca Panduan KONTRIBUSI kami.
Jika Anda ingin mendiskusikan fitur-fitur baru atau Anda mempunyai pertanyaan atau saran mengenai perpustakaan, silakan buka Diskusi atau cukup ngobrol
Situs Grafik CXX
Email: [email protected]
Profil GitHub
Untuk mendukung saya, tambahkan Bintang ke proyek atau ikuti saya
Untuk tetap mendapatkan informasi terbaru, tonton proyeknya
Kami direferensikan oleh:
Terima kasih kepada komunitas TheAlgorithms atas inspirasi algoritmanya.
Terima kasih kepada GeeksForGeeks untuk beberapa inspirasi algoritme.
Terima kasih kepada semua orang yang telah berkontribusi pada CXXGraph!
Jika Anda menggunakan perangkat lunak ini, harap ikuti petunjuk CITATION. Terima kasih!
Kami berpartisipasi di Hacktoberfest 2021. Terima kasih kepada semua kontributor!
Kami berpartisipasi di Hacktoberfest 2022. Terima kasih kepada semua kontributor!
Kami berpartisipasi di Hacktoberfest 2023. Terima kasih kepada semua kontributor!
Lihat Estimasi Nilai Proyek
@ZigRazor |
|---|
