Floyd Warshall dalam JAVA

package floydwarshall;

import java.util.Random;

public class Warshall {

int n=5;

int [][]dist=new int[n][n]; 

public static void main(String[]args) {

    Warshall xx=new Warshall();

    xx.play();

}

void play(){

    Warshall xx=new Warshall();

    int i, j,k;

for (i = 0; i < n; ++i){

for (j = 0; j < n; ++j){

dist[i][j]=xx.getRandomNumberInRange(1,9);

                        System.out.print(dist[i][j]+" ");

                }

                 System.out.println("");

        }

//xx.floyd_warshall();

//=================================================================

for (k = 0; k < n; ++k) {

for (i = 0; i < n; ++i)

for (j = 0; j < n; ++j)

/* If i and j are different nodes and if 

the paths between i and k and between

k and j exist, do */

if ((dist[i][k] * dist[k][j] != 0) && (i != j))

/* See if you can't get a shorter path

between i and j by interspacing

k somewhere along the current

path */

if ((dist[i][k] + dist[k][j] < dist[i][j]) ||(dist[i][j] == 0))

dist[i][j] = dist[i][k] + dist[k][j];

}

        

        

System.out.println("\n++++++++++++++++++++++++++++++++++++++++++");       

for (i = 0; i < n; ++i){

for (j = 0; j < n; ++j){

                        System.out.print(dist[i][j]+" ");

                }

                 System.out.println("");

        }

}

int getRandomNumberInRange(int min, int max) {

if (min >= max) {

throw new IllegalArgumentException("max must be greater than min");

}

Random r = new Random();

       

int c=r.nextInt((max - min) + 1) + min;

        return c;

}

}

nilai 1000 diasumsikan nilai tak hingga(~) yang berarti arah ke lokasi tsb tidak tersedia....

Download Source Code

Java Code Unique Random

int[]arRandom ;
jumsoal=10;

 void bacaRandom(){
     arRandom = uniqueRandomArray(jumsoal);
        for(int i = 0; i<jd; i++){
            Log.v("R",i+"."+arRandom[i]);
        }
    }
   
    public static int[] uniqueRandomArray(int n){
        int [] A = new int[n];
        for(int i = 0; i< A.length; ){
            if(i == A.length){
                break;
            }
            int b = (int)(Math.random() *n) + 1;
            if(f(A,b) == false){
                A[i++] = b;
            }
        }
        return A;
    }
    public static boolean f(int[] A, int n){
        for(int i=0; i<A.length; i++){
            if(A[i] == n){
                return true;
            }
        }
        return false;
    }

Leveninstein Java

Levenshtein distance digunakan untuk mengukur nilai kesamaan atau kemiripan
antara dua buah kata (string).

Jarak Levenshtein diperoleh dengan mencari cara termudah untuk mengubah suatu string.
Secara umum, operasi mengubah yang diperbolehkan untuk keperluan ini adalah:

adapun langkahnya adalah sbb:
+memasukkan karakter ke dalam string,
+menghapus sebuah karakter dari suatu string,
+mengganti karakter string dengan karakter lain.

Untuk menghitung jarak, digunakan matriks

(n+1) x (m+1)

di mana n adalah panjang string s1 dan m adalah panjang string s2.

Dua buah string yang akan digunakan sebagai contoh adalah RONALDINHO dengan ROLANDO.

Jika dilihat sekilas, kedua string tersebut memiliki jarak 6.
Berarti untuk mengubah string RONALDINHO menjadi ROLANDO diperlukan 6 operasi, yaitu:

Mensubtitusikan  N dengan L ( RONALDINHO -> ROLALDINHO )
Mensubtitusikan L dengan N ( ROLALDINHO -> ROLANDINHO )
Mensubtitusikan I dengan O ( ROLANDINHO -> ROLANDONHO )
Menghapus O ( ROLANDONHO -> ROLANDONH )
Menghapus H ( ROLANDONH -> ROLANDON )
Menghapus N ( ROLANDON -> ROLANDO )

Dengan menggunakan representasi matriks dapat dilihat pada tabel di bawah.

Pada Tabel 1, elemen baris 1 kolom 1 (M[1,1]) adalah
jumlah operasi yang diperlukan untuk mengubah substring dari kata ROLANDO yang diambil mulai dari karakter awal sebanyak 1 (R) ke substring dari kata RONALDINHO yang diambil mulai dari karakter awal sebanyak 1 (R).

Sementara M[3,5] adalah jumlah operasi antara ROL (substring yang diambil mulai dari karakter awal sebanyak 3) dengan RONAL (substring yang diambil mulai dari karakter awal sebanyak 5).

Hal ini disimpulkan bahwa elemen M[p,q] adalah jumlah operasi antara substring kata pertama yang diambil mulai dari awal sebanyak p dengan substring kata kedua yang diambil dari awal sebanyak q.

Dengan demikian, matriks pada Tabel diatas dapat diisi seperti pada Tabel dibawah ini.

Elemen terakhir (kanan bawah) adalah elemen yang nilainya menyatakan jarak kedua string yang dibandingkan. Lalu untuk menghitung nilai kemiripan menggunakan rumus:
Elemen terakhir (kanan bawah) adalah elemen yang nilainya menyatakan jarak kedua string yang dibandingkan.

Lalu untuk menghitung nilai kemiripan menggunakan rumus:

Sim = Similarity/ nilai kemiripan
Dis = jarak Levenshtein
MaxLength = nilai string terpanjang
Jika nilai similarity adalah 1, maka kedua string yang dibandingkan sama.

Di lain hal, jika similarity 0, maka kedua string yang dibandingkan tidak sama.

package javaleveninstein;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import sun.rmi.runtime.Log;

public class JavaLeveninstein {

    public static void main(String[] args) {

        String[]ark=new String[5];
            ark[0]="Tahajud";
            ark[1]="Iqomah";
            ark[2]="Adzan";
            ark[3]="Dluha";
            ark[4]="Fardhu";
     
        String    gabs="";
        for(int j=0;j<ark.length;j++){
            gabs=gabs+ark[j].toLowerCase()+" ";
            }
     
        String scari="pardu";
//++++++++++++++++++++++++++++++++++

    Leveninstein x=new Leveninstein();
    String[]ar=new String[1000];
    int r=0;
    String text=gabs;//.toLowerCase();//gab=kalimat halo apa kabar all
    String keyword=scari;
    String[] data = text.split(" ");
    List<Integer> dist = new ArrayList<Integer>();
    for (int i = 0; i < data.length; i++){
        dist.add(x.distance(data[i], keyword));
        System.out.println(i+":"+keyword+"="+x.distance(data[i],keyword));
    }
    Collections.sort(dist);

    for (int i = 0; i < data.length; i++){
        if (x.distance(data[i], keyword) == dist.get(0)){
            if(text.indexOf(data[i])>=0){
                ar[r]=data[i].toLowerCase();
                System.out.println( data[i] + " >> " + x.distance(data[i], keyword));
                r++;
            }
        }
    }//for


    String []arh=new String[1000];
    int ada=0;
    for (int i = 0; i < ark.length; i++) {
        String me = ark[i].toLowerCase();
        for (int j = 0; j < r; j++) {
            if (me.indexOf(ar[j]) >= 0 || me.indexOf(scari)>=0) {
                arh[ada]=ark[i];
                ada++;
                break;
            }
        }
    }
    System.out.println("III =="+ada);
    String[]arHasil=new String[ada];

    for (int i = 0; i < ada; i++){
        arHasil[i]=arh[i];
        System.out.println( arHasil[i]);
    }
     
     
     
     
        }//main
 
}

Download Source Code

Implementasi Leveninstein JAVA

package lp2maray.com;

public class Leveninstein {

    public static int distance(String a, String b){
        a = a.toLowerCase();
        b = b.toLowerCase();
        int[] costs = new int[b.length() + 1];
        for (int j = 0; j < costs.length; j++)
            costs[j] = j;

        for (int i = 1; i <= a.length(); i++) {
            costs[0] = i;
            int nw = i - 1;
            for (int j = 1; j <= b.length(); j++){
                int cj = Math.min(1 + Math.min(costs[j], costs[j - 1]),a.charAt(i - 1) == b.charAt(j - 1) ? nw : nw + 1);
                nw = costs[j];
                costs[j] = cj;
            }
        }
        return costs[b.length()];
    }

}


==========

btnCari.setOnClickListener(new OnClickListener(){
public void onClick(View v){textlength = edCari.getText().length();

  for (int i = 0; i < jd; i++) {
        Element e = (Element) nl.item(i);
        String l_nama=parser.getValue(e, KEY_nama);
        String l_deskripsi=parser.getValue(e, KEY_deskripsi);
        gabs=gabs+l_nama.toLowerCase()+" ";
    }


text_sort.clear();
image_sort.clear();
String scari=edCari.getText().toString().toLowerCase();
//++++++++++++++++++++++++++++++++++

    Leveninstein x=new Leveninstein();
    String[]ar=new String[1000];
    int r=0;
    String text=gabs;//.toLowerCase();//gab=kalimat halo apa kabar all
    String keyword=scari;
    String[] data = text.split(" ");
    List<Integer> dist = new ArrayList<Integer>();
    for (int i = 0; i < data.length; i++){
        dist.add(x.distance(data[i], keyword));
        Log.v("COMP",i+":"+keyword+"="+x.distance(data[i],keyword));
    }
    Collections.sort(dist);

    for (int i = 0; i < data.length; i++){
        if (x.distance(data[i], keyword) == dist.get(0)){
            if(text.indexOf(data[i])>=0){
                ar[r]=data[i].toLowerCase();
                Log.v("MAYBE", data[i] + " >> " + x.distance(data[i], keyword));

                r++;
            }
        }
    }//for


    arrNama2=new String[1000];
    arrDes2=new String[1000];
    arrGbr2=new int[1000];

    text_sort.clear();
    image_sort.clear();
    int ada=0;
    for (int i = 0; i < arrNama.length; i++) {
        String me = arrNama[i].toLowerCase();
        for (int j = 0; j < r; j++) {
            if (me.indexOf(ar[j]) >= 0 || me.indexOf(scari)>=0) {
                arrNama2[ada]=arrNama[i];
                arrDes2[ada]=arrDes[i];
                arrGbr2[ada]=arrGbr[i];
                Log.v("BC",arrNama2[ada]);
                ada++;
                break;
            }
        }
    }
    Log.v("III","=="+ada);
    arrNama3=new String[ada];
    arrDes3=new String[ada];
    arrGbr3=new int[ada];

    for (int i = 0; i < ada; i++){
arrNama3[i]=arrNama2[i];
        Log.v("CC",arrNama3[i]);
arrDes3[i]=arrDes2[i];
arrGbr3[i]=arrGbr2[i];
}

listview.setAdapter(new MyCustomAdapter(arrNama3, arrGbr3));
listview.setOnItemClickListener(new OnItemClickListener() {
  @Override
  public void onItemClick(AdapterView<?> a, View v, int p, long id) {
               Intent i = new Intent(pencarian.this, detail.class);
               i.putExtra("istilah", arrNama3[p]);
               i.putExtra("deskripsi", arrDes3[p]);
               startActivity(i);
               Toast.makeText(pencarian.this,arrNama3[p]+ " ....", Toast.LENGTH_LONG).show();
        }
       });
}});