Revision: 62057
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at January 31, 2013 06:16 by DSTG_Kwan
Initial Code
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; } }
Initial URL
Initial Description
Program izraÄunava najkraći put u zadanom grafu.
Initial Title
DSTG_Projekt_Tin
Initial Tags
Initial Language
Java