C++ Boost Graph Topological Sort

4 min read Jul 01, 2024

Topological Sort dengan Boost Graph Library

Boost Graph Library (BGL) adalah sebuah library C++ yang menyediakan berbagai macam algoritma dan struktur data untuk bekerja dengan graph. Salah satu algoritma yang tersedia di BGL adalah topological sort, yang digunakan untuk mengurutkan node dalam graph directed acyclic (DAG) sehingga setiap node berada di depan semua node yang memiliki edge mengarah ke node tersebut.

Dalam artikel ini, kita akan membahas bagaimana melakukan topological sort dengan BGL.

Pengertian Topological Sort

Topological sort adalah algoritma yang mengatur node-node dalam DAG menjadi urutan linear, di mana untuk setiap edge (u, v) dalam graph, node u muncul sebelum node v dalam urutan tersebut. Urutan ini menunjukkan ketergantungan antara node-node dalam graph, di mana node u harus diproses sebelum node v.

Contoh Aplikasi

Topological sort memiliki banyak aplikasi dalam berbagai bidang, seperti:

Perencanaan Proyek: Membangun jadwal proyek dengan urutan yang benar, di mana tugas yang tergantung pada tugas lain harus dilakukan setelahnya.
Kompilasi Program: Mengatur urutan kompilasi file source code yang saling bergantung.
Analisis Algoritma: Mengidentifikasi urutan langkah-langkah dalam algoritma yang saling bergantung.

Implementasi dengan Boost Graph Library

BGL menyediakan fungsi topological_sort untuk melakukan topological sort pada graph. Berikut adalah langkah-langkah implementasi:

Definisikan Graph: Pertama, kita perlu mendefinisikan graph kita menggunakan salah satu kelas graph yang tersedia di BGL, seperti adjacency_list atau vector_graph.
Tentukan Edge: Kita perlu menambahkan edge ke dalam graph dengan menggunakan fungsi add_edge.
Panggil topological_sort: Panggil fungsi topological_sort dengan graph sebagai parameter. Fungsi ini akan menghasilkan urutan node yang telah disortir secara topologis.

Berikut adalah contoh kode program yang menunjukkan implementasi topological sort dengan BGL:

#include 
#include 
#include 
#include 

using namespace std;
using namespace boost;

int main() {
  // Definisikan graph
  typedef adjacency_list Graph;
  Graph g;

  // Tambahkan edge
  add_edge(0, 1, g);
  add_edge(0, 2, g);
  add_edge(1, 3, g);
  add_edge(2, 3, g);

  // Lakukan topological sort
  vector sorted_nodes(num_vertices(g));
  topological_sort(g, &sorted_nodes[0]);

  // Cetak hasil sort
  cout << "Urutan Node yang Telah Disortir Secara Topologis: " << endl;
  for (int i = 0; i < sorted_nodes.size(); ++i) {
    cout << sorted_nodes[i] << " ";
  }
  cout << endl;

  return 0;
}

Kode program ini akan mencetak output berikut:

Urutan Node yang Telah Disortir Secara Topologis:
0 1 2 3

Kesimpulan

Boost Graph Library menyediakan fungsi topological_sort yang mudah digunakan untuk melakukan topological sort pada graph. Algoritma ini sangat berguna dalam berbagai aplikasi, seperti perencanaan proyek, kompilasi program, dan analisis algoritma.