Posted By

DSTG_Kwan on 01/31/13

Tagged

Versions (?)

Last Edited at 01/31/13 06:16am

Statistics

Viewed 133 times

Favorited by 0 user(s)

DSTG_Projekt_Tin

/ Published in: Java

Program izraÄunava najkraÄ‡i put u zadanom grafu.

Highlighted TextExpand

package org.foi.dstg.tikomlino;
import java.util.Iterator;
import java.util.Map;

/**
 *
 * @author tinkomlinovic
 */
public class Dijkstra {

public void izvrsiAlgoritam(Map<String, Vrh> vrhovi) {
        
        try {
        boolean ponovi = true;
        while (ponovi) {
            Iterator i = vrhovi.entrySet().iterator();
            boolean sviSuZavrsili = true;
            while (i.hasNext()) {
                Map.Entry trenutniVrhEntry = (Map.Entry) i.next();
                Vrh v = (Vrh) trenutniVrhEntry.getValue();
                if (!v.isZavrsio()) {
                    sviSuZavrsili = false;
                }
            }
            if (sviSuZavrsili) {
                ponovi = false;
            }
            vrhovi = korak(vrhovi);

}
        Iterator it = vrhovi.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry vrhoviEntry = (Map.Entry) it.next();
            Vrh vrh = (Vrh) vrhoviEntry.getValue();
            System.out.println("Vrh: " + vrh.getNaziv() + ", Udaljenost: " + vrh.getNajkraciPut() + ", Vrh preko kojeg je dobio oznaku: " + vrh.getVrhPrekoKojegJeDobioOznaku());
        }
        }
        catch (Exception e){
            System.out.println("Greska u datoteci");
        }
    }

private Map<String, Vrh> korak(Map<String, Vrh> vrhovi) {
        Iterator iterator = vrhovi.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry vrhEntry = (Map.Entry) iterator.next();
            String nazivVrha = (String) vrhEntry.getKey();
            Vrh vrh = (Vrh) vrhEntry.getValue();

if (!vrh.isZavrsio()) {
                Map<String, Integer> susjedniVrhovi = vrh.getUdaljenostSusjednogVrha();
                Iterator i = susjedniVrhovi.entrySet().iterator();
                while (i.hasNext()) {
                    Map.Entry susjedniVrhEntry = (Map.Entry) i.next();
                    String nazivSusjednogVrha = (String) susjedniVrhEntry.getKey();
                    Vrh susjedniVrh = vrhovi.get(nazivSusjednogVrha);
                    if (susjedniVrh.isZavrsio()) {
                        int udaljenostOdSusjednogVrha = (Integer) susjedniVrhEntry.getValue();
                        int udaljenostSusjednogVrhaOdPocetnogVrha = susjedniVrh.getNajkraciPut();
                        if (vrh.getNajkraciPut() > udaljenostOdSusjednogVrha + udaljenostSusjednogVrhaOdPocetnogVrha) {
                            vrh.setNajkraciPut(udaljenostOdSusjednogVrha + udaljenostSusjednogVrhaOdPocetnogVrha);
                            vrh.setVrhPrekoKojegJeDobioOznaku(nazivSusjednogVrha);

}
                    }
                }
                vrhovi.put(nazivVrha, vrh);
            }

}

Iterator i = vrhovi.entrySet().iterator();
        int najmanjaUdaljenost = Integer.MAX_VALUE;
        Vrh vrhKojiZavrsava = null;

while (i.hasNext()) {
            Map.Entry vrhEntry = (Map.Entry) i.next();
            Vrh vrh = (Vrh) vrhEntry.getValue();
            if (vrh.getNajkraciPut() < najmanjaUdaljenost && !vrh.isZavrsio()) {
                najmanjaUdaljenost = vrh.getNajkraciPut();
                vrhKojiZavrsava = vrh;
            }

}
        if (vrhKojiZavrsava != null) {
            vrhKojiZavrsava.setZavrsio(true);

vrhovi.put(vrhKojiZavrsava.getNaziv(), vrhKojiZavrsava);
        }

return vrhovi;
    }
}

package org.foi.dstg.tikomlino.files;

import java.io.BufferedInputStream;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author tinkomlinovic
 */
public class FileReader {

public List<String> readFile(String path) {
        //Todo promijniti hardkodiranu adresu u path
        File file = new File(path);
        FileInputStream fis = null;
        BufferedInputStream bis = null;
        DataInputStream dis = null;
        List<String> redovi = new ArrayList<String>();

try {
            fis = new FileInputStream(file);

// Here BufferedInputStream is added for fast reading.
            bis = new BufferedInputStream(fis);
            dis = new DataInputStream(bis);
            // dis.available() returns 0 if the file does not have more lines.
            while (dis.available() != 0) {

// this statement reads the line from the file and print it to
                // the console.
                redovi.add(dis.readLine());
            }
            // dispose all the resources after using them.
            fis.close();
            bis.close();
            dis.close();

} catch (FileNotFoundException e) {
            System.out.println("Neispravna datoteka!");
        } catch (IOException e) {
            System.out.println("Neispravna datoteka!");
        }
        return redovi;
    }
}

package org.foi.dstg.tikomlino.files;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import org.foi.dstg.tikomlino.Vrh;

/**
 *
 * @author tinkomlinovic
 */
public class Parser {

public Map<String, Vrh> parseRows(List<String> redovi) {
        Map<String, Vrh> vrhovi = new HashMap<String, Vrh>();
        int i = 0;
                    String prviVrh = "";

for (String red : redovi) {
            if (i == 0) {
                Pattern p = Pattern.compile("[a-z,0-9,A-Z]*");
                Matcher m = p.matcher(red);
                if (m.find()) {
                    prviVrh = red;
                    i++;
                }
                  else {
                System.out.println("Geska u datoteci");
                System.exit(0);
            }
            }
            else {
            Pattern p = Pattern.compile("[a-z,0-9,A-Z]*,[a-z,0-9,A-Z]*,[0-9]*");
            Matcher m = p.matcher(red);
            //Regex je u redu
            if (m.find()) {
                String[] razdvojeniRed = red.split(",\\s*");
                String naziv1 = razdvojeniRed[0];
                String naziv2 = razdvojeniRed[1];
                int udaljenost = Integer.parseInt(razdvojeniRed[2]);

//Prvi vrh
                if (vrhovi.containsKey(naziv1)) {
                    Vrh vrh = vrhovi.get(naziv1);
                    vrhovi.remove(naziv1);
                    vrh.dodajSusjedniVrh(naziv2, udaljenost);
                    vrhovi.put(naziv1, vrh);
                } else {
                    Vrh vrh = new Vrh();
                    vrh.setNaziv(naziv1);
                    vrh.dodajSusjedniVrh(naziv2, udaljenost);
                    if (naziv1.equals(prviVrh)){
                        vrh.setZavrsio(true);
                        vrh.setNajkraciPut(0);
                        vrh.setZadnji(false);
                    }
                    else{
                    vrh.setZavrsio(false);
                    vrh.setNajkraciPut(Integer.MAX_VALUE);
                    }
                    vrhovi.put(naziv1, vrh);
                }

} else {
                System.out.println("Neispravna datoteka");
                System.exit(0);
            }

}
        }
        return vrhovi;

}
}

package org.foi.dstg.tikomlino;

import java.util.HashMap;
import java.util.Map;
import org.foi.dstg.tikomlino.files.FileReader;
import org.foi.dstg.tikomlino.files.Parser;

/**
 *
 * @author tinkomlinovic
 */
public class Main {

/**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Map<String, Vrh> vrhovi;
        FileReader fileReader = new FileReader();
        Parser parser = new Parser();
        if (args.length == 1){
        vrhovi = parser.parseRows(fileReader.readFile(args[0]));
        Dijkstra dijkstra = new Dijkstra();
        dijkstra.izvrsiAlgoritam(vrhovi);
        }
        else {
            System.out.println("Neispravna datoteka!");
        }
    }
}

package org.foi.dstg.tikomlino;

import java.util.HashMap;
import java.util.Map;

/**
 *
 * @author tinkomlinovic
 */
public class Vrh {
    private String naziv;
    private Map<String, Integer> udaljenostSusjednogVrha = new HashMap<String, Integer>();
    private int najkraciPut;
    private String vrhPrekoKojegJeDobioOznaku;
    private boolean zavrsio; //false - zavrsio
    private boolean zadnji; // true - zadnji vrh koji je dobio oznaku

public String getNaziv() {
        return naziv;
    }

public void setNaziv(String naziv) {
        this.naziv = naziv;
    }

public Map<String, Integer> getUdaljenostSusjednogVrha() {
        return udaljenostSusjednogVrha;
    }

public void dodajSusjedniVrh (String naziv, int udaljenost){
        udaljenostSusjednogVrha.put(naziv, udaljenost);
    }

public int getNajkraciPut() {
        return najkraciPut;
    }

public void setNajkraciPut(int najkraciPut) {
        this.najkraciPut = najkraciPut;
    }

public boolean isZavrsio() {
        return zavrsio;
    }

public void setZavrsio(boolean konacnaOznaka) {
        this.zavrsio = konacnaOznaka;
    }

public String getVrhPrekoKojegJeDobioOznaku() {
        return vrhPrekoKojegJeDobioOznaku;
    }

public void setVrhPrekoKojegJeDobioOznaku(String vrhPrekoKojegJeDobioOznaku) {
        this.vrhPrekoKojegJeDobioOznaku = vrhPrekoKojegJeDobioOznaku;
    }

public boolean isZadnji() {
        return zadnji;
    }

public void setZadnji(boolean zadnji) {
        this.zadnji = zadnji;
    }
    
}

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.