Posted By

DSTG_Kwan on 01/31/13


Tagged


Versions (?)

DSTG_Projekt_Tin


 / Published in: Java
 

Program izračunava najkraći put u zadanom grafu.

  1. package org.foi.dstg.tikomlino;
  2. import java.util.Iterator;
  3. import java.util.Map;
  4.  
  5. /**
  6.  *
  7.  * @author tinkomlinovic
  8.  */
  9. public class Dijkstra {
  10.  
  11. public void izvrsiAlgoritam(Map<String, Vrh> vrhovi) {
  12.  
  13. try {
  14. boolean ponovi = true;
  15. while (ponovi) {
  16. Iterator i = vrhovi.entrySet().iterator();
  17. boolean sviSuZavrsili = true;
  18. while (i.hasNext()) {
  19. Map.Entry trenutniVrhEntry = (Map.Entry) i.next();
  20. Vrh v = (Vrh) trenutniVrhEntry.getValue();
  21. if (!v.isZavrsio()) {
  22. sviSuZavrsili = false;
  23. }
  24. }
  25. if (sviSuZavrsili) {
  26. ponovi = false;
  27. }
  28. vrhovi = korak(vrhovi);
  29.  
  30. }
  31. Iterator it = vrhovi.entrySet().iterator();
  32. while (it.hasNext()) {
  33. Map.Entry vrhoviEntry = (Map.Entry) it.next();
  34. Vrh vrh = (Vrh) vrhoviEntry.getValue();
  35. System.out.println("Vrh: " + vrh.getNaziv() + ", Udaljenost: " + vrh.getNajkraciPut() + ", Vrh preko kojeg je dobio oznaku: " + vrh.getVrhPrekoKojegJeDobioOznaku());
  36. }
  37. }
  38. catch (Exception e){
  39. System.out.println("Greska u datoteci");
  40. }
  41. }
  42.  
  43. private Map<String, Vrh> korak(Map<String, Vrh> vrhovi) {
  44. Iterator iterator = vrhovi.entrySet().iterator();
  45. while (iterator.hasNext()) {
  46. Map.Entry vrhEntry = (Map.Entry) iterator.next();
  47. String nazivVrha = (String) vrhEntry.getKey();
  48. Vrh vrh = (Vrh) vrhEntry.getValue();
  49.  
  50. if (!vrh.isZavrsio()) {
  51. Map<String, Integer> susjedniVrhovi = vrh.getUdaljenostSusjednogVrha();
  52. Iterator i = susjedniVrhovi.entrySet().iterator();
  53. while (i.hasNext()) {
  54. Map.Entry susjedniVrhEntry = (Map.Entry) i.next();
  55. String nazivSusjednogVrha = (String) susjedniVrhEntry.getKey();
  56. Vrh susjedniVrh = vrhovi.get(nazivSusjednogVrha);
  57. if (susjedniVrh.isZavrsio()) {
  58. int udaljenostOdSusjednogVrha = (Integer) susjedniVrhEntry.getValue();
  59. int udaljenostSusjednogVrhaOdPocetnogVrha = susjedniVrh.getNajkraciPut();
  60. if (vrh.getNajkraciPut() > udaljenostOdSusjednogVrha + udaljenostSusjednogVrhaOdPocetnogVrha) {
  61. vrh.setNajkraciPut(udaljenostOdSusjednogVrha + udaljenostSusjednogVrhaOdPocetnogVrha);
  62. vrh.setVrhPrekoKojegJeDobioOznaku(nazivSusjednogVrha);
  63.  
  64. }
  65. }
  66. }
  67. vrhovi.put(nazivVrha, vrh);
  68. }
  69.  
  70. }
  71.  
  72.  
  73. Iterator i = vrhovi.entrySet().iterator();
  74. int najmanjaUdaljenost = Integer.MAX_VALUE;
  75. Vrh vrhKojiZavrsava = null;
  76.  
  77. while (i.hasNext()) {
  78. Map.Entry vrhEntry = (Map.Entry) i.next();
  79. Vrh vrh = (Vrh) vrhEntry.getValue();
  80. if (vrh.getNajkraciPut() < najmanjaUdaljenost && !vrh.isZavrsio()) {
  81. najmanjaUdaljenost = vrh.getNajkraciPut();
  82. vrhKojiZavrsava = vrh;
  83. }
  84.  
  85. }
  86. if (vrhKojiZavrsava != null) {
  87. vrhKojiZavrsava.setZavrsio(true);
  88.  
  89. vrhovi.put(vrhKojiZavrsava.getNaziv(), vrhKojiZavrsava);
  90. }
  91.  
  92. return vrhovi;
  93. }
  94. }
  95.  
  96.  
  97. package org.foi.dstg.tikomlino.files;
  98.  
  99. import java.io.BufferedInputStream;
  100. import java.io.DataInputStream;
  101. import java.io.File;
  102. import java.io.FileInputStream;
  103. import java.io.FileNotFoundException;
  104. import java.io.IOException;
  105. import java.util.ArrayList;
  106. import java.util.List;
  107.  
  108. /**
  109.  *
  110.  * @author tinkomlinovic
  111.  */
  112. public class FileReader {
  113.  
  114. public List<String> readFile(String path) {
  115. //Todo promijniti hardkodiranu adresu u path
  116. File file = new File(path);
  117. FileInputStream fis = null;
  118. BufferedInputStream bis = null;
  119. DataInputStream dis = null;
  120. List<String> redovi = new ArrayList<String>();
  121.  
  122. try {
  123. fis = new FileInputStream(file);
  124.  
  125. // Here BufferedInputStream is added for fast reading.
  126. bis = new BufferedInputStream(fis);
  127. dis = new DataInputStream(bis);
  128. // dis.available() returns 0 if the file does not have more lines.
  129. while (dis.available() != 0) {
  130.  
  131. // this statement reads the line from the file and print it to
  132. // the console.
  133. redovi.add(dis.readLine());
  134. }
  135. // dispose all the resources after using them.
  136. fis.close();
  137. bis.close();
  138. dis.close();
  139.  
  140. } catch (FileNotFoundException e) {
  141. System.out.println("Neispravna datoteka!");
  142. } catch (IOException e) {
  143. System.out.println("Neispravna datoteka!");
  144. }
  145. return redovi;
  146. }
  147. }
  148.  
  149.  
  150. package org.foi.dstg.tikomlino.files;
  151.  
  152. import java.util.HashMap;
  153. import java.util.List;
  154. import java.util.Map;
  155. import java.util.regex.Matcher;
  156. import java.util.regex.Pattern;
  157. import org.foi.dstg.tikomlino.Vrh;
  158.  
  159. /**
  160.  *
  161.  * @author tinkomlinovic
  162.  */
  163. public class Parser {
  164.  
  165. public Map<String, Vrh> parseRows(List<String> redovi) {
  166. Map<String, Vrh> vrhovi = new HashMap<String, Vrh>();
  167. int i = 0;
  168. String prviVrh = "";
  169.  
  170. for (String red : redovi) {
  171. if (i == 0) {
  172. Pattern p = Pattern.compile("[a-z,0-9,A-Z]*");
  173. Matcher m = p.matcher(red);
  174. if (m.find()) {
  175. prviVrh = red;
  176. i++;
  177. }
  178. else {
  179. System.out.println("Geska u datoteci");
  180. System.exit(0);
  181. }
  182. }
  183. else {
  184. Pattern p = Pattern.compile("[a-z,0-9,A-Z]*,[a-z,0-9,A-Z]*,[0-9]*");
  185. Matcher m = p.matcher(red);
  186. //Regex je u redu
  187. if (m.find()) {
  188. String[] razdvojeniRed = red.split(",\\s*");
  189. String naziv1 = razdvojeniRed[0];
  190. String naziv2 = razdvojeniRed[1];
  191. int udaljenost = Integer.parseInt(razdvojeniRed[2]);
  192.  
  193. //Prvi vrh
  194. if (vrhovi.containsKey(naziv1)) {
  195. Vrh vrh = vrhovi.get(naziv1);
  196. vrhovi.remove(naziv1);
  197. vrh.dodajSusjedniVrh(naziv2, udaljenost);
  198. vrhovi.put(naziv1, vrh);
  199. } else {
  200. Vrh vrh = new Vrh();
  201. vrh.setNaziv(naziv1);
  202. vrh.dodajSusjedniVrh(naziv2, udaljenost);
  203. if (naziv1.equals(prviVrh)){
  204. vrh.setZavrsio(true);
  205. vrh.setNajkraciPut(0);
  206. vrh.setZadnji(false);
  207. }
  208. else{
  209. vrh.setZavrsio(false);
  210. vrh.setNajkraciPut(Integer.MAX_VALUE);
  211. }
  212. vrhovi.put(naziv1, vrh);
  213. }
  214.  
  215. } else {
  216. System.out.println("Neispravna datoteka");
  217. System.exit(0);
  218. }
  219.  
  220. }
  221. }
  222. return vrhovi;
  223.  
  224. }
  225. }
  226.  
  227.  
  228. package org.foi.dstg.tikomlino;
  229.  
  230. import java.util.HashMap;
  231. import java.util.Map;
  232. import org.foi.dstg.tikomlino.files.FileReader;
  233. import org.foi.dstg.tikomlino.files.Parser;
  234.  
  235. /**
  236.  *
  237.  * @author tinkomlinovic
  238.  */
  239. public class Main {
  240.  
  241. /**
  242.   * @param args the command line arguments
  243.   */
  244. public static void main(String[] args) {
  245. Map<String, Vrh> vrhovi;
  246. FileReader fileReader = new FileReader();
  247. Parser parser = new Parser();
  248. if (args.length == 1){
  249. vrhovi = parser.parseRows(fileReader.readFile(args[0]));
  250. Dijkstra dijkstra = new Dijkstra();
  251. dijkstra.izvrsiAlgoritam(vrhovi);
  252. }
  253. else {
  254. System.out.println("Neispravna datoteka!");
  255. }
  256. }
  257. }
  258.  
  259.  
  260. package org.foi.dstg.tikomlino;
  261.  
  262. import java.util.HashMap;
  263. import java.util.Map;
  264.  
  265. /**
  266.  *
  267.  * @author tinkomlinovic
  268.  */
  269. public class Vrh {
  270. private String naziv;
  271. private Map<String, Integer> udaljenostSusjednogVrha = new HashMap<String, Integer>();
  272. private int najkraciPut;
  273. private String vrhPrekoKojegJeDobioOznaku;
  274. private boolean zavrsio; //false - zavrsio
  275. private boolean zadnji; // true - zadnji vrh koji je dobio oznaku
  276.  
  277. public String getNaziv() {
  278. return naziv;
  279. }
  280.  
  281. public void setNaziv(String naziv) {
  282. this.naziv = naziv;
  283. }
  284.  
  285. public Map<String, Integer> getUdaljenostSusjednogVrha() {
  286. return udaljenostSusjednogVrha;
  287. }
  288.  
  289. public void dodajSusjedniVrh (String naziv, int udaljenost){
  290. udaljenostSusjednogVrha.put(naziv, udaljenost);
  291. }
  292.  
  293. public int getNajkraciPut() {
  294. return najkraciPut;
  295. }
  296.  
  297. public void setNajkraciPut(int najkraciPut) {
  298. this.najkraciPut = najkraciPut;
  299. }
  300.  
  301. public boolean isZavrsio() {
  302. return zavrsio;
  303. }
  304.  
  305. public void setZavrsio(boolean konacnaOznaka) {
  306. this.zavrsio = konacnaOznaka;
  307. }
  308.  
  309. public String getVrhPrekoKojegJeDobioOznaku() {
  310. return vrhPrekoKojegJeDobioOznaku;
  311. }
  312.  
  313. public void setVrhPrekoKojegJeDobioOznaku(String vrhPrekoKojegJeDobioOznaku) {
  314. this.vrhPrekoKojegJeDobioOznaku = vrhPrekoKojegJeDobioOznaku;
  315. }
  316.  
  317. public boolean isZadnji() {
  318. return zadnji;
  319. }
  320.  
  321. public void setZadnji(boolean zadnji) {
  322. this.zadnji = zadnji;
  323. }
  324.  
  325. }

Report this snippet  

You need to login to post a comment.