API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jan 17th, 2018
135
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 11.54 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. template <typename TipOznake>
  5. class UsmjereniGraf;
  6.  
  7. template <typename TipOznake>
  8. class Cvor {
  9. UsmjereniGraf<TipOznake> *graf;
  10. int redni_broj;
  11. public:
  12. Cvor(UsmjereniGraf<TipOznake> *graf, int redni_broj) : graf(graf), redni_broj(redni_broj) {}
  13. TipOznake dajOznaku() const { return graf->dajOznakuCvora(redni_broj); }
  14. void postaviOznaku(TipOznake oznaka) { graf->postaviOznakuCvora(redni_broj, oznaka); }
  15. int dajRedniBroj() const { return redni_broj; }
  16. };
  17.  
  18. template <typename TipOznake>
  19. class Grana {
  20. UsmjereniGraf<TipOznake> *graf;
  21. int polazni, dolazni;
  22. public:
  23. Grana(UsmjereniGraf<TipOznake> *graf, int polazni, int dolazni) : graf(graf), polazni(polazni), dolazni(dolazni) {}
  24. float dajTezinu() const { return graf->dajTezinuGrane(polazni, dolazni); }
  25. void postaviTezinu(float tezina) { graf->postaviTezinuGrane(polazni, dolazni, tezina); }
  26. TipOznake dajOznaku() const { return graf->dajOznakuGrane(polazni, dolazni); }
  27. void postaviOznaku(TipOznake oznaka) { graf->postaviOznakuGrane(polazni, dolazni, oznaka); }
  28. Cvor<TipOznake> dajPolazniCvor() const { return graf->dajCvor(polazni); }
  29. Cvor<TipOznake> dajDolazniCvor() const { return graf->dajCvor(dolazni); }
  30. };
  31.  
  32.  
  33. template <typename TipOznake>
  34. class GranaIterator {
  35. friend class UsmjereniGraf<TipOznake>;
  36. UsmjereniGraf<TipOznake> *graf;
  37. int polazni, dolazni;
  38. bool zadnja;
  39. public:
  40. GranaIterator(UsmjereniGraf<TipOznake> *graf, int polazni, int dolazni) : graf(graf), polazni(polazni), dolazni(dolazni), zadnja(false) {}
  41.  
  42. GranaIterator(const GranaIterator &g){
  43. graf = g.graf;
  44. polazni = g.polazni;
  45. dolazni = g.dolazni;
  46. }
  47.  
  48. GranaIterator &operator=(const GranaIterator &g){
  49. if(g != *this){
  50. graf = g.graf;
  51. polazni = g.polazni;
  52. dolazni = g.dolazni;
  53. }
  54. return *this;
  55. }
  56.  
  57. Grana<TipOznake> operator*() { return Grana<TipOznake>(graf, polazni, dolazni); }
  58.  
  59. bool operator==(const GranaIterator &iter) const{
  60. if(graf == iter.graf && polazni == iter.polazni && dolazni == iter.dolazni && zadnja == iter.zadnja) return true;
  61. return false;
  62. }
  63.  
  64. bool operator!=(const GranaIterator &iter) const{
  65. if(graf == iter.graf && polazni == iter.polazni && dolazni == iter.dolazni && zadnja == iter.zadnja) return false;
  66. return true;
  67. }
  68.  
  69. GranaIterator& operator++(){
  70. if(zadnja == true){
  71. zadnja = false;
  72. return *this;
  73. }
  74. if(polazni == graf->dajBrojCvorova() -1 && dolazni == graf->dajBrojCvorova() -1) throw "Kraj petlje";
  75. int tmp_polazni(polazni);
  76. int tmp_dolazni(dolazni);
  77.  
  78. if(tmp_dolazni < graf->dajBrojCvorova() - 1) tmp_dolazni++;
  79. else if(tmp_dolazni == graf->dajBrojCvorova() -1) { tmp_polazni++; tmp_dolazni = 0; }
  80.  
  81. for(int i = tmp_polazni; i < graf->dajBrojCvorova(); i++){
  82. for(int j = tmp_dolazni; j < graf->dajBrojCvorova(); j++){
  83. if(graf->postojiGrana(i, j)){
  84. dolazni = j;
  85. polazni = i;
  86. if(*this == graf->dajGraneKraj()) zadnja = true;
  87. return *this;
  88. }
  89. }
  90. tmp_dolazni = 0;
  91. }
  92. throw "Kraj grafa";
  93. }
  94. GranaIterator operator++(int){
  95. if(zadnja == true){
  96. zadnja = false;
  97. return *this;
  98. }
  99. if(polazni == graf->dajBrojCvorova() -1 && dolazni == graf->dajBrojCvorova() -1) throw "Kraj petlje";
  100. GranaIterator g(*this);
  101. int tmp_polazni(polazni);
  102. int tmp_dolazni(dolazni);
  103.  
  104.  
  105. if(tmp_dolazni < graf->dajBrojCvorova() - 1) tmp_dolazni++;
  106. else if(tmp_dolazni == graf->dajBrojCvorova() -1) { tmp_polazni++; tmp_dolazni = 0; }
  107.  
  108. for(int i = tmp_polazni; i < graf->dajBrojCvorova(); i++){
  109. for(int j = tmp_dolazni; j < graf->dajBrojCvorova(); j++){
  110. if(graf->postojiGrana(i, j)){
  111. dolazni = j;
  112. polazni = i;
  113. if(*this == graf->dajGraneKraj()) zadnja = true;
  114. return g;
  115. }
  116. }
  117. tmp_dolazni = 0;
  118. }
  119. throw "Kraj grafa";
  120. }
  121. };
  122.  
  123. template <typename TipOznake>
  124. class UsmjereniGraf{
  125. public:
  126. UsmjereniGraf(int brCvorova) {}
  127. virtual ~UsmjereniGraf() {}
  128. UsmjereniGraf(const UsmjereniGraf &g) {}
  129. //UsmjereniGraf operator=(const UsmjereniGraf &g);
  130. virtual int dajBrojCvorova() const = 0;
  131. virtual void postaviBrojCvorova(int noviBrojCvorova) = 0;
  132. virtual void dodajGranu(int polazni, int dolazni, float tezina = 0) = 0;
  133. virtual void obrisiGranu(int polazni, int dolazni) = 0;
  134. virtual void postaviTezinuGrane(int polazni, int dolazni, float tezina) = 0;
  135. virtual float dajTezinuGrane(int polazni, int dolazni) = 0;
  136. virtual bool postojiGrana(int polazni, int dolazni) = 0;
  137. virtual void postaviOznakuCvora(int brojCvora, TipOznake oznaka) = 0;
  138. virtual TipOznake dajOznakuCvora(int brojCvora) = 0;
  139. virtual void postaviOznakuGrane(int polazni, int dolazni, TipOznake oznaka) = 0;
  140. virtual TipOznake dajOznakuGrane(int polazni, int dolazni) = 0;
  141. virtual Cvor<TipOznake> dajCvor(int broj_cvorova) = 0;
  142. virtual Grana<TipOznake> dajGranu(int polazni, int dolazni) = 0;
  143. virtual GranaIterator<TipOznake> dajGranePocetak() = 0;
  144. virtual GranaIterator<TipOznake> dajGraneKraj() = 0;
  145. };
  146.  
  147. template <typename TipOznake>
  148. class MatricaGraf : public UsmjereniGraf<TipOznake> {
  149. std::vector<std::vector<float>> cvorovi;
  150. std::vector<std::vector<TipOznake>> oznaka_grane;
  151. std::vector<std::vector<bool>> grana_postoji;
  152. std::vector<TipOznake> oznaka_cvora;
  153. int broj_grana;
  154. public:
  155.  
  156. MatricaGraf(int brCvorova) : cvorovi(brCvorova, std::vector<float>(brCvorova, 0.)), oznaka_grane(brCvorova, std::vector<TipOznake>(brCvorova)),
  157. grana_postoji(brCvorova, std::vector<bool>(brCvorova, false)), oznaka_cvora(brCvorova), UsmjereniGraf<TipOznake>(brCvorova) {}
  158.  
  159. void postaviBrojCvorova(int noviBrojCvorova){
  160. if(noviBrojCvorova < cvorovi.size())
  161. throw "Nije moguce smanjiti graf";
  162. cvorovi.resize(noviBrojCvorova);
  163. oznaka_cvora.resize(noviBrojCvorova);
  164. oznaka_grane.resize(noviBrojCvorova);
  165. grana_postoji.resize(noviBrojCvorova);
  166.  
  167. for(int i = 0; i < noviBrojCvorova; i++){
  168. cvorovi[i].resize(noviBrojCvorova);
  169. oznaka_grane[i].resize(noviBrojCvorova);
  170. grana_postoji[i].resize(noviBrojCvorova);
  171. }
  172. }
  173.  
  174. int dajBrojCvorova() const { return cvorovi.size(); }
  175.  
  176. void dodajGranu(int polazni, int dolazni, float tezina = 0){
  177. if(polazni > cvorovi.size() || polazni < 0 || dolazni > cvorovi.size() || dolazni < 0) throw "Neispravni parametri";
  178. grana_postoji[polazni][dolazni] = true;
  179. cvorovi[polazni][dolazni] = tezina;
  180. broj_grana++;
  181. }
  182.  
  183. void obrisiGranu(int polazni, int dolazni){
  184. if(polazni > cvorovi.size() || polazni < 0 || dolazni > cvorovi.size() || dolazni < 0) throw "Neispravni parametri";
  185. if(grana_postoji[polazni][dolazni]){
  186. grana_postoji[polazni][dolazni] = false;
  187. broj_grana--;
  188. cvorovi[polazni][dolazni] = 0;
  189. }
  190. }
  191.  
  192. void postaviTezinuGrane(int polazni, int dolazni, float tezina){
  193. if(polazni > cvorovi.size() || polazni < 0 || dolazni > cvorovi.size() || dolazni < 0) throw "Neispravni parametri";
  194. if(!grana_postoji[polazni][dolazni]) throw "Grana ne postoji";
  195. cvorovi[polazni][dolazni] = tezina;
  196. }
  197.  
  198. float dajTezinuGrane(int polazni, int dolazni){
  199. if(polazni > cvorovi.size() || polazni < 0 || dolazni > cvorovi.size() || dolazni < 0) throw "Neispravni parametri";
  200. if(!grana_postoji[polazni][dolazni]) throw "Grana ne postoji";
  201. return cvorovi[polazni][dolazni];
  202. }
  203.  
  204. bool postojiGrana(int polazni, int dolazni){
  205. if(polazni > cvorovi.size() || polazni < 0 || dolazni > cvorovi.size() || dolazni < 0) throw "Neispravni parametri";
  206. return grana_postoji[polazni][dolazni];
  207. }
  208.  
  209. void postaviOznakuCvora(int brojCvora, TipOznake oznaka){
  210. if(brojCvora < 0 || brojCvora > cvorovi.size() - 1) throw "Neispravan parametar";
  211. oznaka_cvora[brojCvora] = oznaka;
  212. }
  213.  
  214. TipOznake dajOznakuCvora(int brojCvora){
  215. if(brojCvora < 0 || brojCvora > cvorovi.size() - 1) throw "Neispravan parametar";
  216. return oznaka_cvora[brojCvora];
  217. }
  218.  
  219. void postaviOznakuGrane(int polazni, int dolazni, TipOznake oznaka){
  220. if(polazni > cvorovi.size() || polazni < 0 || dolazni > cvorovi.size() || dolazni < 0) throw "Neispravni parametri";
  221. if(!grana_postoji[polazni][dolazni]) throw "Ne postoji grana";
  222. oznaka_grane[polazni][dolazni] = oznaka;
  223. }
  224.  
  225. TipOznake dajOznakuGrane(int polazni, int dolazni){
  226. if(polazni > cvorovi.size() || polazni < 0 || dolazni > cvorovi.size() || dolazni < 0) throw "Neispravni parametri";
  227. if(!grana_postoji[polazni][dolazni]) throw "Ne postoji grana";
  228. return oznaka_grane[polazni][dolazni];
  229. }
  230.  
  231. Cvor<TipOznake> dajCvor(int broj_cvorova){
  232. if(broj_cvorova < 0 || broj_cvorova > cvorovi.size() - 1) throw "Neispravan parametar";
  233. return Cvor<TipOznake>(this, broj_cvorova);
  234. }
  235.  
  236. Grana<TipOznake> dajGranu(int polazni, int dolazni){
  237. if(polazni > cvorovi.size() || polazni < 0 || dolazni > cvorovi.size() || dolazni < 0) throw "Neispravni parametri";
  238. if(!grana_postoji[polazni][dolazni]) throw "Ne postoji grana";
  239. return Grana<TipOznake>(this, polazni, dolazni);
  240. }
  241.  
  242. GranaIterator<TipOznake> dajGranePocetak(){
  243. for(int i = 0; i < cvorovi.size(); i++){
  244. for(int j = 0; j < cvorovi.size(); j++){
  245. if(grana_postoji[i][j]) return GranaIterator<TipOznake>(this, i, j);
  246. }
  247. }
  248. throw "Ne postoji grana";
  249. }
  250.  
  251. GranaIterator<TipOznake> dajGraneKraj(){
  252. for(int i = grana_postoji.size() - 1; i >= 0; i--)
  253. for(int j = grana_postoji.size() - 1; j >= 0; j--)
  254. if(grana_postoji[i][j]) return GranaIterator<TipOznake>(this, i, j);
  255. throw "Ne postoji grana";
  256. }
  257. };
  258.  
  259. int main() {
  260.  
  261. try {
  262. UsmjereniGraf<bool> *g = new MatricaGraf<bool>(3);
  263. g->dodajGranu(0, 1, 2.5);
  264. g->dodajGranu(1, 0, 1.2);
  265. g->dodajGranu(1, 2, 0.1);
  266. g->dodajGranu(0, 0, 3.14);
  267. for (GranaIterator<bool> iter = g->dajGranePocetak();
  268. iter != g->dajGraneKraj(); ++iter)
  269. std::cout << (*iter).dajPolazniCvor().dajRedniBroj() << " "
  270. << (*iter).dajDolazniCvor().dajRedniBroj() << " "
  271. << (*iter).dajTezinu() << std::endl;
  272. delete g;
  273. } catch (const char izuzetak[]) {
  274. std::cout << izuzetak << std::endl;
  275. }
  276. return 0;
  277. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!