API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jan 19th, 2020
90
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 13.97 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <stdexcept>
  3. #include <vector>
  4. #include <queue>
  5. #include <string>
  6. #include <list>
  7.  
  8. using std::vector;
  9. using std::list;
  10.  
  11. //Prekopiran kod iz 10. pripremne (klase cvor, grana, granaiterator, usmjereni graf, kao i dvije funkcije bfs i dfs)
  12. //Ovo kopirano jer sam vec jednom uradio pa da ne bih kucao dva puta isti kod
  13.  
  14. //Prvo navodimo prototipe kako ne bismo morali misliti na raspored generisanja klasa, a iste implementiramo ispod
  15. template<typename TipOznaka> class Cvor;
  16. template<typename TipOznaka> class Grana;
  17. template<typename TipOznaka> class GranaIterator;
  18.  
  19. template<typename TipOznaka>
  20. class UsmjereniGraf{
  21.     protected:
  22.         UsmjereniGraf(){}
  23.     public:
  24.         UsmjereniGraf(int){}
  25.         virtual ~UsmjereniGraf(){}
  26.        
  27.         virtual int dajBrojCvorova() const = 0;
  28.         virtual void postaviBrojCvorova(int) = 0;
  29.         virtual void dodajGranu(int, int, float = 0) = 0;
  30.         virtual void obrisiGranu(int, int) = 0;
  31.         virtual void postaviTezinuGrane(int, int, float = 0) = 0;
  32.         virtual float dajTezinuGrane(int, int) const = 0;
  33.         virtual bool postojiGrana(int, int) const = 0;
  34.         virtual void postaviOznakuCvora(int, TipOznaka) = 0;
  35.         virtual TipOznaka dajOznakuCvora(int) const = 0;
  36.         virtual void postaviOznakuGrane(int, int, TipOznaka) = 0;
  37.         virtual TipOznaka dajOznakuGrane(int, int) const = 0;
  38.         virtual Grana<TipOznaka> dajGranu(int polazni, int dolazni) = 0;
  39.         virtual Cvor<TipOznaka> dajCvor(int cvor) = 0;
  40.         GranaIterator<TipOznaka> dajGranePocetak() { return ++GranaIterator<TipOznaka>(this, 0, -1); }
  41.         GranaIterator<TipOznaka> dajGraneKraj() { return GranaIterator<TipOznaka>(this, dajBrojCvorova(), 0); }
  42. };
  43.  
  44. template<typename TipOznaka>
  45. class Grana{
  46.         UsmjereniGraf<TipOznaka>* graf;
  47.         int polazni, dolazni;
  48.     public:
  49.         Grana(UsmjereniGraf<TipOznaka>* graf, int polazni, int dolazni) : polazni(polazni), dolazni(dolazni), graf(graf){}
  50.    
  51.         float dajTezinu() const {return graf->dajTezinuGrane(polazni, dolazni);}
  52.         void postaviTezinu(float x){graf->postaviTezinuGrane(polazni, dolazni, x);}
  53.        
  54.         TipOznaka dajOznaku(){return graf->dajOznakuGrane(polazni, dolazni);}
  55.         void postaviOznaku(TipOznaka oznaka) const {graf->postaviOznakuGrane(polazni, dolazni, oznaka);}
  56.        
  57.         Cvor<TipOznaka> dajPolazniCvor(){return graf->dajCvor(polazni);}
  58.         Cvor<TipOznaka> dajDolazniCvor(){return graf->dajCvor(dolazni);}
  59. };
  60.  
  61. template<typename TipOznaka>
  62. class Cvor{
  63.         UsmjereniGraf<TipOznaka>* graf;
  64.         int redniBroj;
  65.     public:
  66.         Cvor(UsmjereniGraf<TipOznaka>* ug, int rb){graf = ug; redniBroj = rb;}
  67.         TipOznaka dajOznaku() const {return graf->dajOznakuCvora(redniBroj);}
  68.         void postaviOznaku(TipOznaka oznaka){graf->postaviOznakuCvora(redniBroj, oznaka);}
  69.         int dajRedniBroj() const {return redniBroj;}
  70. };
  71.  
  72.  
  73. template <typename TipOznaka>
  74. class GranaIterator {
  75.         UsmjereniGraf<TipOznaka>* graf;
  76.         int polazni, dolazni;
  77.     public:
  78.         GranaIterator(UsmjereniGraf<TipOznaka>* graf, int polazni, int dolazni) : graf(graf), polazni(polazni), dolazni(dolazni){}
  79.         Grana<TipOznaka> operator*() { return graf->dajGranu(polazni, dolazni); }
  80.         bool operator==(const GranaIterator &iter) const { return graf == iter.graf && polazni == iter.polazni && dolazni == iter.dolazni; }
  81.         bool operator!=(const GranaIterator &iter) const { return !(*this == iter); }
  82.         GranaIterator& operator++(){
  83.             do {
  84.                 if(dolazni+1>=graf->dajBrojCvorova()) dolazni=0,polazni++;
  85.                 else dolazni++;
  86.             } while(polazni<graf->dajBrojCvorova() && !graf->postojiGrana(polazni,dolazni));
  87.             return *this;
  88.         }
  89.        
  90.         GranaIterator operator++(int) {
  91.             if(polazni == -1 && dolazni == -1) throw std::logic_error("Iterator pokazuje iza kraja");
  92.             GranaIterator tmp(*this);
  93.             ++(*this);
  94.             return tmp;
  95.         }
  96.    
  97.     friend class Grana<TipOznaka>;
  98. };
  99.  
  100. template <typename Tip1, typename Tip2>
  101. class Mapa{
  102.     public:
  103.         Mapa(){}
  104.         virtual ~Mapa(){}
  105.        
  106.         virtual int brojElemenata() const { return 0; }
  107.         virtual Tip2 &operator [] (Tip1 kljuc) = 0;
  108.         virtual Tip2 operator [](Tip1 kljuc) const = 0;
  109.         virtual void obrisi(){}
  110.         virtual void obrisi(const Tip1 &kljuc) {}
  111. };
  112.  
  113. template <typename Tip1, typename Tip2>
  114. struct Par{
  115.     Tip1 kljuc;
  116.     Tip2 vrijednost;
  117. };
  118.  
  119. template <typename TipOznaka>
  120. struct Element{
  121.     TipOznaka oznaka;
  122.     int cvor;
  123.     float tezina;
  124. };
  125.  
  126. template <typename Tip1, typename Tip2>
  127. class HashMapaLan : public Mapa<Tip1, Tip2>{
  128.         int broj = 0;
  129.         vector<list<Par<Tip1, Tip2>>> mapa;
  130.         static const int kapacitet = 10000;
  131.        
  132.         unsigned int (*hash)(Tip1, unsigned int) = 0;
  133.         typename list<Par<Tip1, Tip2>>::iterator trazi(Tip1 kljuc);
  134.         typename list<Par<Tip1, Tip2>>::const_iterator trazi(Tip1 kljuc) const;
  135.     public:  
  136.         HashMapaLan() : mapa(kapacitet, list<Par<Tip1, Tip2>>()) {}
  137.        
  138.         int brojElemenata() const { return broj; }
  139.        
  140.         void obrisi();
  141.         void obrisi(const Tip1 &kljuc);
  142.         void definisiHashFunkciju(unsigned int (*fun)(Tip1, unsigned int)) {hash = fun;}
  143.        
  144.         Tip2 &operator [](Tip1 kljuc);
  145.         Tip2 operator [](Tip1 kljuc) const;
  146. };
  147.  
  148. template <typename TipOznaka>
  149. class ListaGraf : public UsmjereniGraf<TipOznaka>{
  150.         vector<list<Element<TipOznaka>>> L;
  151.         vector<TipOznaka> cvorOznake;
  152.        
  153.         void ispravanCvor(int) const;
  154.         void ispravnaGrana(int, int) const;
  155.         void existG(int, int) const;
  156.        
  157.         typename list<Element<TipOznaka>>::iterator findEl(int x, int y){
  158.             auto it(L[x].begin());
  159.             while(it != L[x].end()){
  160.                 if(y == it->cvor) return it;
  161.                 else if(y < it->cvor) return L[x].end();
  162.             }
  163.             return it;
  164.         }
  165.         typename list<Element<TipOznaka>>::const_iterator findEl(int x, int y) const{
  166.             auto it(L[x].begin());
  167.             while(it != L[x].end()){
  168.                 if(y == it->cvor) return it;
  169.                 else if(y < it->cvor) return L[x].end();
  170.             }
  171.             return it;
  172.         }
  173.     public:  
  174.         ListaGraf(int);
  175.         ~ListaGraf(){}
  176.         int dajBrojCvorova() const { return L.size(); }
  177.         void postaviBrojCvorova(int);
  178.         void dodajGranu(int, int, float = 0);
  179.         void obrisiGranu(int, int);
  180.         void postaviTezinuGrane(int, int, float = 0);
  181.         float dajTezinuGrane(int, int) const;
  182.         bool postojiGrana(int, int) const;
  183.         void postaviOznakuCvora(int, TipOznaka);
  184.         TipOznaka dajOznakuCvora(int) const;
  185.         void postaviOznakuGrane(int, int, TipOznaka);
  186.         TipOznaka dajOznakuGrane(int, int) const;
  187.         Grana<TipOznaka> dajGranu(int, int);
  188.         Cvor<TipOznaka> dajCvor(int);
  189. };
  190.  
  191. template<typename TipOznaka>
  192. void bfs(UsmjereniGraf<TipOznaka>* graf, vector<Cvor<TipOznaka>> &bfsP, Cvor<TipOznaka> cvor);
  193.  
  194. template<typename TipOznaka>
  195. void dfs(UsmjereniGraf<TipOznaka>* graf, vector<Cvor<TipOznaka>> &dfsP, Cvor<TipOznaka> cvor);
  196.  
  197. int main() {
  198.    
  199.     return 0;
  200. }
  201.  
  202. ////////////////////////////////////////////////////////////////////////////////
  203. ////////////////// IMPLEMENTACIJA HASH MAPE LAN ////////////////////////////////
  204.  
  205. template <typename Tip1, typename Tip2>
  206. typename list<Par<Tip1, Tip2>>::const_iterator HashMapaLan<Tip1, Tip2>::trazi(Tip1 kljuc) const{
  207.     if(!hash) throw std::domain_error("Izuzetak");
  208.     int indeks(hash(kljuc, mapa.size()));
  209.     auto iter(mapa[indeks].begin());
  210.     while(iter != mapa[indeks].end() && kljuc > iter->kljuc) iter++;
  211.     return iter;
  212. }
  213.  
  214. template <typename Tip1, typename Tip2>
  215. typename list<Par<Tip1, Tip2>>::iterator HashMapaLan<Tip1, Tip2>::trazi(Tip1 kljuc){
  216.     if(!hash) throw std::domain_error("Izuzetak");
  217.     int indeks(hash(kljuc, mapa.size()));
  218.     auto iter(mapa[indeks].begin());
  219.     while(iter != mapa[indeks].end() && kljuc > iter->kljuc) iter++;
  220.     return iter;
  221. }
  222.  
  223. template <typename Tip1, typename Tip2>
  224. void HashMapaLan<Tip1, Tip2>::obrisi(){
  225.     for(auto &clan : mapa)
  226.         clan.clear();
  227.     broj = 0;
  228. }
  229.  
  230. template <typename Tip1, typename Tip2>
  231. void HashMapaLan<Tip1, Tip2>::obrisi(const Tip1 &kljuc){
  232.     auto iter(trazi(kljuc));
  233.     int indeks(hash(kljuc, mapa.size()));
  234.     if(iter == mapa[indeks].end() || iter->kljuc != kljuc) throw std::domain_error("Izuzetak!");
  235.     auto iter2(iter++);
  236.     mapa[indeks].erase(iter2, iter);
  237.     broj--;
  238. }
  239.  
  240. template <typename Tip1, typename Tip2>
  241. Tip2 &HashMapaLan<Tip1, Tip2>::operator [](Tip1 kljuc){
  242.     auto iter(trazi(kljuc));
  243.     int indeks(hash(kljuc, mapa.size()));
  244.     if(iter == mapa[indeks].end() || iter->kljuc != kljuc){
  245.         Par<Tip1, Tip2> temp;
  246.         temp.kljuc = kljuc;
  247.         temp.vrijednost = Tip2();
  248.         iter = mapa[indeks].insert(iter, temp);
  249.         broj++;
  250.     }
  251.     return iter->vrijednost;
  252. }
  253.  
  254. template <typename Tip1, typename Tip2>
  255. Tip2 HashMapaLan<Tip1, Tip2>::operator [](Tip1 kljuc) const {
  256.     auto iter(trazi(kljuc));
  257.     int indeks(hash(kljuc, mapa.size()));
  258.     if(iter == mapa[indeks].end() || iter->kljuc != kljuc)
  259.         return Tip2();
  260.     return iter->vrijednost;
  261. }
  262.  
  263.  
  264.  
  265. template<typename TipOznaka>
  266. void dfs(UsmjereniGraf<TipOznaka>* graf, vector<Cvor<TipOznaka>> &dfsP, Cvor<TipOznaka> cvor){
  267.     cvor.postaviOznaku(1);
  268.     dfsP.push_back(cvor);
  269.     for(GranaIterator<TipOznaka> it = graf->dajGranePocetak(); it != graf->dajGraneKraj(); ++it){
  270.         Cvor<TipOznaka> susjed = (*it).dajDolazniCvor();
  271.         if((*it).dajPolazniCvor().dajRedniBroj() == cvor.dajRedniBroj() && susjed.dajOznaku() != 1)
  272.             dfs(graf, dfsP, susjed);
  273.     }
  274. }
  275.  
  276. template<typename TipOznaka>
  277. void bfs(UsmjereniGraf<TipOznaka>* graf, vector<Cvor<TipOznaka>> &bfsP, Cvor<TipOznaka> cvor){
  278.     cvor.postaviOznaku(1);
  279.     bfsP.push_back(cvor);
  280.     std::queue<Cvor<TipOznaka>> q;
  281.     q.push(cvor);
  282.     while(!q.empty()){
  283.         Cvor<TipOznaka> c=q.front();
  284.         q.pop();
  285.         for(GranaIterator<TipOznaka> it = graf->dajGranePocetak(); it != graf->dajGraneKraj(); it++){
  286.             Cvor<TipOznaka> susjed = (*it).dajDolazniCvor();
  287.             if((*it).dajPolazniCvor().dajRedniBroj() == c.dajRedniBroj() && susjed.dajOznaku() != 1){
  288.                 susjed.postaviOznaku(1);
  289.                 bfsP.push_back(susjed);
  290.                 q.push(susjed);
  291.             }
  292.         }
  293.     }
  294. }
  295.  
  296. ////////////////////////////////////////////////////////////////////////////////
  297. ////////////////// IMPLEMENTACIJA GRAFA POMOCU LISTE ///////////////////////////
  298.  
  299. template <typename TipOznaka>
  300. void ListaGraf<TipOznaka>::ispravanCvor(int redniBroj) const{
  301.     if(redniBroj < 0 || redniBroj >= dajBrojCvorova()) throw std::domain_error("Izuzetak!");
  302. }
  303.  
  304. template <typename TipOznaka>
  305. void ListaGraf<TipOznaka>::ispravnaGrana(int polazni, int dolazni) const{
  306.     ispravanCvor(polazni);
  307.     ispravanCvor(dolazni);
  308. }
  309.  
  310. template <typename TipOznaka>
  311. void ListaGraf<TipOznaka>::existG(int polazni, int dolazni) const{
  312.     ispravnaGrana(polazni, dolazni);
  313.     if(!postojiGrana(polazni, dolazni)) throw std::domain_error("Izuzetak");
  314. }
  315.  
  316. template <typename TipOznaka>
  317. ListaGraf<TipOznaka>::ListaGraf(int n){
  318.     if(n < 0) throw std::domain_error("Izuzetak");
  319.     L = vector<list<Element<TipOznaka>>>(n, list<Element<TipOznaka>>());
  320.     cvorOznake = vector<TipOznaka>(n);
  321. }
  322.  
  323. template <typename TipOznaka>
  324. Cvor<TipOznaka> ListaGraf<TipOznaka>::dajCvor(int cvor){
  325.     ispravanCvor(cvor);
  326.     return Cvor<TipOznaka>(this, cvor);
  327. }
  328.  
  329. template <typename TipOznaka>
  330. Grana<TipOznaka> ListaGraf<TipOznaka>::dajGranu(int polazni, int dolazni){
  331.     existG(polazni, dolazni);
  332.     return Grana<TipOznaka>(this, polazni, dolazni);
  333. }
  334.  
  335. template <typename TipOznaka>
  336. TipOznaka ListaGraf<TipOznaka>::dajOznakuGrane(int polazni, int dolazni) const{
  337.     existG(polazni, dolazni);
  338.     return findEl(polazni, dolazni)->oznaka;
  339. }
  340.  
  341. template <typename TipOznaka>
  342. void ListaGraf<TipOznaka>::postaviOznakuGrane(int polazni, int dolazni, TipOznaka o){
  343.     existG(polazni, dolazni);
  344.     findEl(polazni, dolazni)->oznaka = o;
  345. }
  346.  
  347. template <typename TipOznaka>
  348. TipOznaka ListaGraf<TipOznaka>::dajOznakuCvora(int cvor) const{
  349.     ispravanCvor(cvor);
  350.     return cvorOznake[cvor];
  351. }
  352.  
  353. template <typename TipOznaka>
  354. void ListaGraf<TipOznaka>::postaviOznakuCvora(int cvor, TipOznaka o){
  355.     ispravanCvor(cvor);
  356.     cvorOznake[cvor] = o;
  357. }
  358.  
  359. template <typename TipOznaka>
  360. bool ListaGraf<TipOznaka>::postojiGrana(int polazni, int dolazni) const {
  361.     ispravnaGrana(polazni, dolazni);
  362.     return findEl(polazni, dolazni) != L[polazni].end();
  363. }
  364.  
  365. template <typename TipOznaka>
  366. float ListaGraf<TipOznaka>::dajTezinuGrane(int polazni, int dolazni) const{
  367.     existG(polazni, dolazni);
  368.     return findEl(polazni, dolazni)->tezina;
  369. }
  370.  
  371. template <typename TipOznaka>
  372. void ListaGraf<TipOznaka>::postaviTezinuGrane(int polazni, int dolazni, float tezina){
  373.     existG(polazni, dolazni);
  374.     findEl(polazni, dolazni)->tezina = tezina;
  375. }
  376.  
  377. template <typename TipOznaka>
  378. void ListaGraf<TipOznaka>::obrisiGranu(int polazni, int dolazni){
  379.     existG(polazni, dolazni);
  380.     L[polazni].erase(findEl(polazni, dolazni));
  381. }
  382.  
  383. template <typename TipOznaka>
  384. void ListaGraf<TipOznaka>::dodajGranu(int polazni, int dolazni, float tezina){
  385.     ispravnaGrana(polazni, dolazni);
  386.     auto it(L[polazni].begin());
  387.     while(it != L[polazni].end() && dolazni > it->cvor)
  388.         it++;
  389.     Element<TipOznaka> tmp;
  390.     tmp.tezina = tezina;
  391.     tmp.oznaka = TipOznaka();
  392.     tmp.cvor = dolazni;
  393.     L[polazni].insert(it, tmp);
  394. }
  395.  
  396. template <typename TipOznaka>
  397. void ListaGraf<TipOznaka>::postaviBrojCvorova(int n){
  398.     if(n < dajBrojCvorova()) throw std::domain_error("Izuzetak!");
  399.     L.resize(n);
  400.     cvorOznake.resize(n);
  401. }
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!