Graph menggunakan Adjacent Matrix dan Traversal DFS - Deep First Search

Latihan Graph Menggunakan Adjacent Matrix dan Traversal DFS - Deep First Search Secara Recursive DFS

1:  #include <iostream> 
2:  using namespace std; 
3:  int e = 7;     //jumlah edge 
4:  int n = 5;     //jumlah vertex/node 
5:  bool mat[5][5] = { false };     //matrix 2D untuk menyimpan graph 
6:  int result[5]; 
7:  int idxResult = 0; 
8:  bool isInResult(int n) { 
9:       for (int i = 0; i < idxResult; i++) { 
10:            if (n == result[i])return true; 
11:       } 
12:       return false; 
13:  } 
14:  void addToResult(int n) { 
15:       result[idxResult] = n; 
16:       idxResult++; 
17:  } 
18:  void DFS(int parent) { 
19:       if (!isInResult(parent)) {               //cek di Result sebelumnya 
20:            addToResult(parent); 
21:            for (int i = 0; i < n; i++) {     //mencari childs from parent 
22:                 if (mat[parent][i] == true) { 
23:                      DFS(i);                         //memasukkan setiap child ke DFS 
24:                 } 
25:            } 
26:       } 
27:  } 
28:  int main() {     //Undirected Graph 
29:       int v1[] = { 1,1,2,2,2,3,4 };     //hubungan antar vertex 
30:       int v2[] = { 2,5,3,4,5,4,5 }; 
31:       for (int i = 0; i < e; i++) {          //memasukkan undirected graph kedalam matrix 
32:            mat[v1[i] - 1][v2[i] - 1] = true; 
33:            mat[v2[i] - 1][v1[i] - 1] = true; 
34:       } 
35:       for (int i = 0; i < n; i++) {          //menampilkan matriks graph 
36:            for (int j = 0; j < n; j++) { 
37:                 cout << mat[i][j] << " "; 
38:            } 
39:            cout << endl; 
40:       } cout << endl; 
41:       int firstVertex = 0;     //inisialisasi vertex awal 
42:       DFS(firstVertex); 
43:       for (int i = 0; i &lt; n; i++) { 
44:            cout << result[i] + 1 << " "; 
45:       } cout << endl; 
46:       system("pause"); 
47:  } 

Special thanks to Samsung Academy SRIN Lecturer:
1. Pak Risman Adnan Mattotorang
2. Mas Leonardi
3. Mas Gilang
4. Mas Susanto Tedja

Graph menggunakan Adjacent List dan Traversal BFS - Bread First Search

Latihan Graph Menggunakan Adjacent List (Linked List) dan Traversal BFS - Bread First Search Menggunakan Queue


1:  #include <iostream>; 
2:  using namespace std; 
3:   
4:  struct node { 
5:       int value; 
6:       node *next; 
7:  }; 
8:   
9:  struct linkedList { 
10:       node *head=NULL; 
11:       node *tail=NULL; 
12:   
13:       void addList(int n) { 
14:            node *node_isi = new node(); 
15:            node_isi->value = n; 
16:            node_isi->next = NULL; 
17:   
18:            if (head == NULL) { 
19:                 head = node_isi; 
20:                 tail = node_isi; 
21:            } 
22:            else { 
23:                 tail->next = node_isi; 
24:                 tail = node_isi; 
25:            } 
26:   
27:       } 
28:   
29:       bool isEmpty() { 
30:            return head == NULL; 
31:       } 
32:  }; 
33:   
34:  struct queue { 
35:       node *head = NULL; 
36:       node *tail = NULL; 
37:   
38:       void enqueue(int n) { 
39:            node *node_isi = new node(); 
40:            node_isi->value = n; 
41:            node_isi->next = NULL; 
42:   
43:            if (head == NULL) { 
44:                 head = node_isi; 
45:                 tail = node_isi; 
46:            } 
47:            else { 
48:                 tail->next = node_isi; 
49:                 tail = node_isi; 
50:            } 
51:       } 
52:   
53:       int dequeue() { 
54:            node *buff = head; 
55:            head = head->next; 
56:            int result_dequeue = buff->value; 
57:            delete buff; 
58:            return result_dequeue; 
59:       } 
60:   
61:       bool isEmpty() { 
62:            return head == NULL; 
63:       } 
64:  }; 
65:   
66:  int result[5]; 
67:  int idxResult = 0; 
68:  void addToResult(int n) { 
69:       result[idxResult] = n; 
70:       idxResult++; 
71:  } 
72:  bool isInResult(int n) { 
73:       for (int i = 0; i < idxResult; i++) { 
74:            if (n == result[i]) return true; 
75:       } 
76:       return false; 
77:  } 
78:   
79:  int main() { 
80:   
81:       int n = 5; 
82:       int e = 7; 
83:       int v1[] = {1,1,2,2,2,3,4}; 
84:       int v2[] = {2,5,3,4,5,4,5}; 
85:       linkedList mat[5], buff; 
86:       queue antrian; 
87:   
88:       for (int i = 0; i < e; i++) { 
89:            mat[v1[i]-1].addList(v2[i]); 
90:            mat[v2[i]-1].addList(v1[i]); 
91:       } 
92:   
93:       cout << "Hasil adjacent list" << endl; 
94:       for (int i = 0; i < n; i++) {               //untuk cek isi adjacent list      
95:            buff = mat[i]; 
96:            cout << "List (" << i+1 << "): "; 
97:            while (!buff.isEmpty()) { 
98:                 cout << buff.head->value << " "; 
99:                 buff.head = buff.head->next; 
100:            } 
101:            cout << endl; 
102:       } 
103:   
104:       int firstque=0; 
105:       int parent; 
106:       antrian.enqueue(firstque); 
107:   
108:       while (!antrian.isEmpty()) { 
109:            parent = antrian.dequeue(); 
110:            if (!isInResult(parent)) { 
111:                 addToResult(parent); 
112:                 buff=mat[parent];
113:                 while (!buff.isEmpty()) { 
114:                      antrian.enqueue((buff.head->value)-1); 
115:                      buff.head = buff.head->next; 
116:                 } 
117:            } 
118:       } 
119:   
120:       cout << endl << "Hasil BFS" << endl; 
121:       for (int i = 0; i < n; i++) { 
122:            cout << result[i]+1 << " "; 
123:       } 
124:       cout << endl; 
125:   
126:       system("pause"); 
127:       return 0; 
128:  } 

Special thanks to Samsung Academy SRIN Lecturer:
1. Pak Risman Adnan Mattotorang
2. Mas Leonardi
3. Mas Gilang
4. Mas Susanto Tedja

Tes Algorithm

(note: late publish)

Tes Algorithm

Baik. Waktu pengerjaan 3 jam. Kalo gak salah ingat, kira-kira begini soalnya (kata-kata yang Saya gunakan tidak sama persis ya..):

Untuk mengetahui volume dari suatu danau, suatu perusahaan menggunakan data dari citra digital dua dimensi (2D). Dengan ukuran matriks (NxN).

Nilai "0" merepresentasikan tanah (land) dan nilai "1" merepresentasikan air (water). Volume (kedalaman) air pada suatu posisi tergantung posisi air tersebut terhadap tanah yang terdekat. Semakin jauh posisi air tersebut terhadap tanah berarti semakin dalam (volume semakin besar). Jika posisi air tepat disebelah tanah maka volumenya adalah 1, jika posisi air selisih satu piksel terhadap tanah maka volumenya 2, begitu seterusnya. Perhatikan bahwa posisi air terhadap tanah ditinjau dari arah utara, selatan, barat, timur (pada pembahasan ini Saya andaikan atas, bawah, kiri, kanan ---> dari representasi matriks 2D). Dan ingat dari ke empat arah tersebut kedalaman air ditentukan dari jarak yang "paling pendek" terhadap tanah.

oiya,, data digital (matriks 2D) dapat berisi lebih dari 1 danau, dan tepi-tepi dari matriks tersebut adalah tanah (0).

Input program:

-jumlah pengetesan matriks

-ukuran matriks N (ingat matriks berukuran NxN)

-nilai matriks

output program:

-"#[pengukuran ke] [volume]

contoh (ini agak lupa) hehe
input:
2                -->ket: jumlah pengetesan = 2
4                -->ket: ukuran matriks 4x4
0 0 0 0                -->ket: matriks 4x4
0 1 1 0
0 1 1 0                -->ket: perhatikan bahwa posisi air memiliki kedalaman yang sama yaitu 1, jadi total adalah 4x1=4
0 0 0 0
7                              -->ket: ukuran matriks 7x7
0 0 0 0 0 0 0            -->ket: matriks 7x7
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 1 1 1 1 1 0            -->ket: perhatikan bahwa air memiliki 8 posisi dengan kedalaman 1 dan 1 posisi dengan kedalaman 3
0 0 0 1 0 0 0                sehingga total adalah (8x1) + (1x3) = 11
0 0 0 1 0 0 0
0 0 0 0 0 0 0

output:
#1 4                  -->ket: hasil pengukuran matriks pertama
#2 11                -->ket: hasil pengukuran matriks kedua

Naaaahhh, ini adalah jawaban setelah Saya kerjakan dikosan hehe. Tes udah lewat eh kok malah dapat jawabannya. Alhamdulillah mudah-mudahan benar (paling tidak dari beberapa pengujian yang Saya coba hasilnya sesuai :p )... mungkin efek sudah kenyang hahaha.. halah ngelesss hahaha

Sebenernya alur codingnya sih hampir sama dengan saat Saya ngerjakan tadi saat tes. Bedanya disini sudah Saya bikin function terpisah dengan kode utama sehingga mudah untuk penelusuran kesalahan. Dan bedanya lagi di sini Saya ada menggunakan sintax "while" karena Saya lupa sintax caranya exit dari for.hahaha --> inilah yang membuat tadi pas tess bingung... huuuuuufttt.. Mudah mudahan tulisan ini bisa terupload kalo sdh larut malam.

#include <iostream>

using namespace std;
int matriks[100][100];
int T, N, volumeN, kedalaman_pertitik;
int fungsi_min(int a, int b, int c, int d);
int fungsi_cek(int j, int k);
int main()
{
    cin >> T;   //jumlah pengetesan matriks
    for(int i=0; i<T; i++){
    cin >> N;   //ukuran matriks
        for(int j=0; j<N; j++){
            for (int k=0; k<N; k++){
            cin >> matriks[j][k];
            }
        }
    volumeN=0;
    for(int j=1; j<(N-1); j++){
        for (int k=1; k<(N-1); k++){
            if (matriks[j][k]==1){
                kedalaman_pertitik=fungsi_cek(j,k);
                volumeN=volumeN+kedalaman_pertitik;
            }
        }
    }

    cout << "#"<< i+1 << " "<< volumeN << endl;
    }
return 0;
}


int fungsi_cek(int j, int k)
{
int kiri=1, kanan=1, atas=1, bawah=1;
int l,m;
//cek kiri
l=j;
m=k;
while(matriks[l-1][m]==1){
    kiri++;
    l--;
}

//cek kanan
l=j;
m=k;
while(matriks[l+1][m]==1){
    kanan++;
    l++;
}

//cek atas
l=j;
m=k;
while(matriks[l][m-1]==1){
    atas++;
    m--;
}

//cek bawah
l=j;
m=k;
while(matriks[l][m+1]==1){
    bawah++;
    m++;
}

return fungsi_min(kiri,kanan,atas,bawah);
}

int fungsi_min(int a, int b, int c, int d)
{
int nilai_min=a;

if(nilai_min>b) nilai_min=b;
if(nilai_min>c) nilai_min=c;
if(nilai_min>d) nilai_min=d;

return nilai_min;
}

Berikut adalah printscreen hasil runningnya

Attention: Code ini menggunakan compiler cpp (code::blocks under Ubuntu Linux 14.04)

##Code diatas belum tentu yang paling efisien, maklum hanya menuangkan isi kepala

Terimakasih. Semoga bermanfaat.

Salam berbagi..

Cara mengakses Serial Port menggunakan Matlab pada Linux Ubuntu 14.04 (Kasus komunikasi dgn Arduino)

Pada postingan sebelumnya Sy mencoba komunikasi dgn Arduino melalui Serial Port melalui Visual Basic. Kali ini Sy mencoba share tentang cara komunikasi Serial Port melalui Matlab di Linux Ubuntu 14.04.

Berikut adalah perintah yang umum digunakan pada Matlab untuk komunikasi melalui Serial Port.

%untuk inisialisasi Serial Port.
s = serial(portname,'BaudRate',baudrate,'terminator', 'LF');
%untuk membuka koneksi Serial Port
fopen(s);

%untuk kirim perintah ke mikro melalui Serial Port
perintah=char(strcat(frekuensi, {' '}, num2str(i) , {' '} , num2str(j)));   %Hanya contoh perintah
fprintf(s,perintah);   %untuk menulis perintah melalui Serial Port

%untuk membaca data melalui Serial Port
readbuffer=fscanf(s);

%untuk menutup koneksi apabila sudah selesai
fclose(s);
delete(s);
clear s;

Baris perintah (command) di atas akan bisa langsung digunakan pada OS berbasis windows dgn memasukkan portname='COM1' atau port yang lain.

Namun ternyata pada saat Sy coba dgn OS Ubuntu 14.04 dgn portname yang aktif adalah '/dev/ttyACM0' ternyata pada saat fopen(s) komunikasi tidak berhasil dan tampil kesalahan pada console Matlab. Bikin panik aja, apalagi saat saat genting.haha.. 

Setelah searching kesana kemari ternyata pada Matlab under Ubuntu, nama Portname harus diberi alias. Caranya dengan menambahkan kode berikut (termasuk tanda '-')

-Dgnu.io.rxtx.SerialPorts=/dev/ttyS0:/dev/ttyS1:/dev/ttyS2:/dev/ttyS3:/dev/ttyS4:/dev/ttyS5:/dev/USB0:/dev/USB1:/dev/USB2:/dev/USB3:/dev/USB4:/dev/USB5:/dev/ttyACM0:/dev/ttyACM1:/dev/ttyACM2:/dev/ttyACM3:/dev/ttyACM4:/dev/ttyACM5

kemudian disimpan dalam file bernama java.opts dan disimpan kedalam direktori aktif Matlab. Biasanya alamat direktori aktifnya adalah

/usr/local/MATLAB/R2012b/bin/glnxa64/

dengan catatan gnlxa64 adalah untuk 64 bit. Silahkan dicek lagi jika berbeda. Jangan lupa merestart aplikasi Matlab supaya bisa berfungsi. Alhamdulillah Serial Port sdh bisa terkoneksi.

Programmable Gain Amplifier (PGA) MCP6S21 menggunakan Arduino

PGA atau Programmable Gain Amplifier adalah OpAmp yang memiliki gain pada range tertentu dan dapat diprogram. Jika pada OpAmp biasa pensettingan gain dilakukan menggunakan konfigurasi resistor, maka pada PGA setting gain dilakukan dengan menggunakan software. Hal ini sangat berguna untuk pengukuran besaran analog atau pengaturan tegangan analog yang bersifat dinamis. Yang mana dibutuhkan besaran gain yang fleksibel sesuai kebutuhan.

Pada posting kali ini, PGA yang digunakan adalah MCP6S21 dari Microchip. MCP6S21 memiliki besaran gain +1, +2, +4, +5, +8, +10, +16 dan +32 dengan bandwith 2-12 MHz (typ). MCP6S21 hanya memiliki 1 (satu) channel input. MCP6S21 menggunakan komunikasi SPI untuk pengaturan gain maupun mode shutdown. Model PGA MCP6S21 tidak memiliki pin SO (MISO).

Berbeda dengan tipe MCP6S26 yang memiliki 6 channel input dan MCP6S28 dengan 8 channel input sehingga dapat sekaligus berfungsi sebagai multiplexer. MCP6S26 dan MCP6S28 memiliki pin SO (MISO) sehingga memungkinkan konfigurasi daisy chain (cascade atau bersambung dengan menggunakan SPI yang sama)

Berikut adalah source code untuk mengatur gain dan mode shutdown pada PGA MCP6S21. Code ini dibuat berdasarkan datasheet dan referensi lain. Source code berikut memungkinkan merubah gain maupun mode shutdown melalui serial terminal. Sehingga bisa dikembangkan untuk komunikasi dengan program desktop lain (seperti VB, Delphi, C atau yang lain).

/*

Author: Muhammad Nurul Puji

muhammadpuji.its@gmail.com

6 Mar 2015

*/

#include <SPI.h>

/*

CS- to pin 10 (SS Pin)

SI- to pin 11 (MOSI Pin)

CLK - to pin 13 (SCK Pin)

*/

const int CS_PGA = 10;  //#define CS_PGA 10

char buff_char;

String buff_string = "";

int gain;

void setup()

{

  //setting SPI-PGA MCP6S2x

  pinMode(CS_PGA,OUTPUT);

  SPI.begin();

  SPI.setBitOrder(MSBFIRST);  //MSB first bit order

  SPI.setDataMode(SPI_MODE0);  //SPI Mode 0

  SPI.setClockDivider(SPI_CLOCK_DIV4);  //16MHZ/4=4MHZ

  

  //setting Serial

  Serial.begin(57600);

  delay(1);

  Serial.println("");

  Serial.println("Welcome Muhammad Nurul Puji");

  Serial.println("Silahkan masukkan nilai gain yang diinginkan");

  Serial.println("0--> +1; 1--> +2; 2--> +4; 3--> +5; 4--> +8; 5--> +10; 6--> +16; 7--> +32; Other--> Shutdown");

  Serial.println("");

  delay(1);

}

void loop()

{

  while(Serial.available()) {

    buff_char = Serial.read();

    buff_string.concat(buff_char);

    delay(1);  //delay ini sangat penting

  }  

  if(buff_string != ""){

    gain=buff_string.toInt();  

    if(gain<=7){

    PGA_set_gain(gain); 

    Serial.println("Gain is Changed");

    }

    else{

    PGA_shutdown();

    Serial.println("PGA is Shutdown");

    }
    buff_string="";

  }

}

//pengaturan set nilai gain pada PGA MCP6S21

void PGA_set_gain(int gain){

  int instruction = 0b01000000;  //untuk instruksi merubah gain

  digitalWrite(CS_PGA,LOW);

  SPI.transfer(instruction);   

  SPI.transfer(gain);    //set gain

  digitalWrite(CS_PGA,HIGH);

}

//untuk shutdown pada PGA MCP6s21

void PGA_shutdown(){

  int instruction = 0b00100000;  //untuk instruksi shutdown

  digitalWrite(CS_PGA,LOW);

  SPI.transfer(instruction);

  SPI.transfer(0);    //hanya untuk memenuhi aturan 16bit

  digitalWrite(CS_PGA,HIGH);

}

Prosedur PGA_set_gain() dan PGA_shutdown() dapat dikembangkan untuk PGA MCP6S26 maupun MCP6S26 baik mode single maupun mode daisy chain serta untuk pemilihan channel. Hal ini harus disesuaikan dengan datasheet.

Thanks to Mas Rohmadi (http://rohmadi.my.id) atas pinjaman Oscilloscopnya :)

--

Referensi:

http://ww1.microchip.com/downloads/en/DeviceDoc/21117B.pdf (Datasheet)

http://forum.arduino.cc/index.php?topic=19775.0

Arduino Komunikasi serial dan pemisahan terhadap separator perintah

Berikut adalah penggunaan Arduino dengan komunikasi serial. Yang mana perintah dikirim dari pc melalui komunikasi serial. Perintah yang dikirim oleh pc memiliki format "data_1""separator""data_2". Disini separator yang digunakan adalah tanda "+". Misalnya pc mengirimkan perintah "12+3" maka Arduino harus memisahkan perintah tersebut menjadi data_1 dan data_2. Pada percobaan kali ini data_1 dan data_2 kemudian dijumlahkan.

Berikut adalah sourcecode yang digunakan: 

/*
Author: Muhammad Nurul Puji
muhammadpuji.its@gmail.com
16 Feb 2015
*/

char buff_char;
String buff_string = "";
float data_1, data_2, total;
String buff_data_1, buff_data_2;

void setup()
{
  Serial.begin(57600);
  delay(100);
  Serial.println("Welcome Muhammad Nurul Puji");
  Serial.println("");
  delay(1000);
}

void loop()
{
 
while(Serial.available()) {  //blok untuk menerima perintah serial    
    buff_char = Serial.read();
    buff_string.concat(buff_char);
    delay(1);  //delay ini sangat penting
  } 
 
 
  if(buff_string != ""){
    buff_data_1=(splitValue(buff_string, '+', 0));  //memisahkan string data dengan string separator "+"
    buff_data_2=(splitValue(buff_string, '+', 1));
   
    //char buff[buff_data_1.length()];               //mengubah string ke float
    //buff_data_1.toCharArray(buff,buff_data_1.length()+1);
    //data_1=atof(buff);
    data_1=buff_data_1.toInt();   //cara singkat mengubah string ke number
   
    //buff[buff_data_2.length()];                    //mengubah string ke float
    //buff_data_2.toCharArray(buff,buff_data_2.length()+1);
    //data_2=atof(buff); 
    data_2=buff_data_2.toInt();   //cara singkat mengubah string ke number   
    
    total = data_1 + data_2;
   
    Serial.print("Perintah awal adalah ");
    Serial.print(buff_string);  //bukan println karena perintah dikirim setelah ditekan enter
    Serial.print("Data 1 = ");
    Serial.println(data_1);
    Serial.print("Data 2 = ");
    Serial.println(data_2);
    Serial.print("Total data adalah ");
    Serial.println(total);
    Serial.println("");
   
    buff_string="";
  }
}

//Function untuk memisahkan data dengan separator
String splitValue(String data, char separator, int index){
  int found = 0;
  int strIndex[]={0, -1};
  int maxIndex = data.length()-1;
  for(int i=0; i<=maxIndex && found<=index; i++){
    if(data.charAt(i) == separator || i==maxIndex){
      found++;
      strIndex[0] = strIndex[1]+1;
      strIndex[1] = (i == maxIndex) ? i+1 : i;
    }
  }
  return found>index ? data.substring(strIndex[0], strIndex[1]) : "";
}

Referensi: dari postingan - postingan sebelumnya...........
--
Semoga bermanfaat

Source code untuk mengenali pola data string dan memisahkannya dalam masing-masing variabel

Berikut adalah beberapa code untuk mengenali pattern ato pola string kemudian data string tersebut dapat dipisah sesuai "separator" yg digunakan. Source code berikut sangat powerfull dan terpilih dari beberapa sumber.

Pemisahan pattern string sangat penting dalam pemberian perintah (command), misal dalam aplikasi mikrokontroler yg diperintah oleh PC (atau mikrokontroller lain) untuk kontrol pengambilan data. Sehingga dalam sekali kirim perintah bisa dimasukkan beberapa parameter yg diinginkan. Kemudian mikrokontroller bisa memisahkan parameter-parameter tsb dgn sourcecode berikut ini.

Excellent code....

Stackexchange.com

Stackoverflow.com

Github.com

--

Sumber referensi (dicopy tgl 15 Februari 2015)

http://arduino.stackexchange.com/questions/1013/how-do-i-split-an-incoming-string

http://stackoverflow.com/questions/9072320/split-string-into-string-array

https://github.com/ka1/sousVide/blob/master/arduino/TempYun/functions.ino#