cogobebi

#include <iostream>
#include <vector>

template <typename TipOznake>
class UsmjereniGraf;

template <typename TipOznake>
class Cvor;

template <typename TipOznake>
class GranaIterator;

template <typename TipOznake>
class UsmjereniGraf;

template <typename TipOznake>
class Grana {

    UsmjereniGraf<TipOznake>* graf;
    int polazni, dolazni;

    public:

        Grana (UsmjereniGraf<TipOznake> *graf, int polazni, int dolazni) :
            graf(graf), polazni(polazni), dolazni(dolazni) {}

        float dajTezinu() const {
            return graf->dajTezinuGrane(polazni, dolazni);
        }

        void postaviTezinu (float tezina) {
            graf->postaviTezinuGrane(polazni, dolazni, tezina);
        }

        TipOznake dajOznaku() const {
            return graf->dajOznakuGrane(polazni, dolazni);
        }

        void postaviOznaku (TipOznake oznaka) {
            return graf->postaviOznakuGrane(polazni, dolazni, oznaka);
        }

        Cvor<TipOznake> dajPolazniCvor() const {
            return graf->dajCvor(polazni);
        }

        Cvor<TipOznake> dajDolazniCvor() const {
            return graf->dajCvor(dolazni);
        }

};

template <typename TipOznake>
class Cvor {

    UsmjereniGraf<TipOznake>* graf;
    int redniBroj;

    public:
        Cvor (UsmjereniGraf<TipOznake>* graf, int redniBroj) : graf(graf), redniBroj(redniBroj) {}

        TipOznake dajOznaku() const {
            return graf->dajOznakuCvora(redniBroj);
        }

        void postaviOznaku(TipOznake oznaka) {
            graf->postaviOznakuCvora(redniBroj, oznaka);
        }

        int dajRedniBroj() const {
            return redniBroj;
        }

};

template <typename TipOznake>
class UsmjereniGraf {

    public:
        UsmjereniGraf(int brojCvorova) {}
        virtual ~UsmjereniGraf() {}
        virtual int dajBrojCvorova() = 0;
        virtual void postaviBrojCvorova(int brojCvorova) = 0;
        virtual void dodajGranu (int polazni, int dolazni, float tezina) = 0;
        virtual void obrisiGranu (int polazni, int dodajGranu) = 0;
        virtual void postaviTezinuGrane (int polazni, int dolazni, float tezina) = 0;
        virtual float dajTezinuGrane (int polazni, int dolazni) = 0;
        virtual bool postojiGrana (int polazni, int dolazni) = 0;
        virtual void postaviOznakuCvora (int cvor, TipOznake oznaka) = 0;
        virtual TipOznake dajOznakuCvora (int cvor) const = 0;
        virtual void postaviOznakuGrane (int polazni, int dolazni, TipOznake oznaka) = 0;
        virtual TipOznake dajOznakuGrane (int polazni, int dolazni)  = 0;

        Grana<TipOznake> dajGranu (int polazni, int dolazni) {
            return Grana<TipOznake>(this, polazni, dolazni);
        }

        Cvor<TipOznake> dajCvor (int cvor) {
            return Cvor<TipOznake>(this, cvor);
        }

        virtual GranaIterator<TipOznake> dajGranePocetak() = 0;
        virtual GranaIterator<TipOznake> dajGraneKraj() = 0;
        virtual GranaIterator<TipOznake> dajSljedecuGranu(int polazni, int dolazni) = 0;
};


template <typename TipOznake>
class GranaIterator {

    UsmjereniGraf<TipOznake>* graf;
    int polazni, dolazni;

    public:


        GranaIterator(UsmjereniGraf<TipOznake>* graf, int polazni, int dolazni) :
            graf(graf), polazni(polazni), dolazni(dolazni) {}

        Grana<TipOznake> operator*() {
            return Grana<TipOznake>(graf, polazni, dolazni);
        }


        bool operator == (const GranaIterator &iter) const {
            return (graf == iter.graf && polazni == iter.polazni && dolazni == iter.dolazni);
        }


        bool operator != (const GranaIterator &iter) const {
            return !(*this == iter);
        }


        GranaIterator& operator ++() {
            if (polazni == -1 && dolazni == -1) throw ("Iterator pokazuje iza kraja!");
            GranaIterator g = graf->dajSljedecuGranu(polazni, dolazni);
            polazni = g.polazni;
            dolazni = g.dolazni;
            return *this;
        }


        GranaIterator operator ++(int) {
            GranaIterator temp = *this;
            ++(*this);
            return temp;
        }

};


template <typename TipOznake>
class MatricaGraf : public UsmjereniGraf<TipOznake> {

    struct PodaciGrane {
        TipOznake oznaka;
        float tezina;
        bool postoji;
    };

    std::vector<std::vector<PodaciGrane>> matrica;
    std::vector<TipOznake> oznakeCvorova;

    public:

        MatricaGraf(int brojCvorova) : UsmjereniGraf<TipOznake>(brojCvorova) {
            postaviBrojCvorova(brojCvorova);
        }


        int dajBrojCvorova() {
            return matrica.size();
        }


        void postaviBrojCvorova(int brojCvorova) {
            if (brojCvorova < matrica.size()) throw ("Zabranjeno smanjenje broja cvorova!");

            PodaciGrane nepostojeca;
            nepostojeca.postoji = false;

            for (int i = 0; i < matrica.size(); i++)
                matrica[i].resize(brojCvorova, nepostojeca);

            std::vector<PodaciGrane> prazanRed(brojCvorova, nepostojeca);
            matrica.resize(brojCvorova, prazanRed);
            oznakeCvorova.resize(brojCvorova, TipOznake());
        }

        void dodajGranu (int polazni, int dolazni, float tezina) {
            PodaciGrane g;
            g.tezina = tezina;
            g.postoji = true;
            matrica[polazni][dolazni] = g;
        }


        void obrisiGranu (int polazni, int dolazni) {
            matrica[polazni][dolazni].postoji = false;
        }


        void postaviTezinuGrane (int polazni, int dolazni, float tezina) {
            matrica[polazni][dolazni].tezina = tezina;
        }


        float dajTezinuGrane (int polazni, int dolazni) {
            return matrica[polazni][dolazni].tezina;
        }


        bool postojiGrana (int polazni, int dolazni) {
            return matrica[polazni][dolazni].postoji;
        }


        void postaviOznakuCvora (int cvor, TipOznake oznaka) {
            oznakeCvorova[cvor] = oznaka;
        }


        TipOznake dajOznakuCvora (int cvor) const {
            return oznakeCvorova[cvor];
        }


        void postaviOznakuGrane (int polazni, int dolazni, TipOznake oznaka) {
            matrica[polazni][dolazni].oznaka = oznaka;
        }


        TipOznake dajOznakuGrane (int polazni, int dolazni) {
            return matrica[polazni][dolazni].oznaka;
        }


        GranaIterator<TipOznake> dajGranePocetak() {
            GranaIterator<TipOznake> it(this, 0, -1);
            return ++it;
        }


        GranaIterator<TipOznake> dajGraneKraj() {
            GranaIterator<TipOznake> it(this, -1, -1);
            return it;
        }


        GranaIterator<TipOznake> dajSljedecuGranu(int polazni, int dolazni) {
            for (int i = polazni; i < matrica.size(); i++) {
                for (int j = 0; j < matrica.size(); j++) {
                    if (i == polazni && j <= dolazni) continue;
                    if (matrica[i][j].postoji)
                        return GranaIterator<TipOznake>(this, i, j);
                }
            }
            return GranaIterator<TipOznake>(this, -1, -1);
        }
};


template <typename TipOznake>
void dfs (UsmjereniGraf<TipOznake>* &g, std::vector<Cvor<TipOznake>> &dfsPretraga, Cvor<TipOznake> cvor) {
    static std::vector<bool> posjeceni (g->dajBrojCvorova(), false);
    posjeceni[cvor.dajRedniBroj()] = true;

    dfsPretraga.push_back(cvor);

    int i = cvor.dajRedniBroj();
    for (int j = 0; j < g->dajBrojCvorova(); j++)
        if (g->postojiGrana(i, j) && !posjeceni[j]) dfs(g, dfsPretraga, g->dajCvor(j));

}


template <typename TipOznake>
void bfs (UsmjereniGraf<TipOznake>* &g, std::vector<Cvor<TipOznake>> &bfsPretraga, Cvor<TipOznake> cvor) {
    static std::vector<bool> posjeceni (g->dajBrojCvorova(), false);

    std::vector<bool> susjedi(g->dajBrojCvorova(), false);

    int i = cvor.dajRedniBroj();

    if (!posjeceni[i]) {
        bfsPretraga.push_back(cvor);
        posjeceni[i] = true;
    }

    for (int j = 0; j < g->dajBrojCvorova(); j++) {
        if (g->postojiGrana(i, j)) {
            if (!posjeceni[j]) {
                bfsPretraga.push_back(g->dajCvor(j));
                posjeceni[j] = true;
                susjedi[j] = true;
            }
        }
    }

    for (int j = 0; j < posjeceni.size(); j++) {
        if (susjedi[j]) {
            bfs(g, bfsPretraga, g->dajCvor(j));
        }
    }

}