codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <vector> #include <list> #include <cassert> #include "Vector2D.h" #include "DugumTurKisaltmalari.h" template <class dugum_turu, class kenar_turu> class SeyrekGrafik { public: typedef kenar_turu KenarTuru; typedef dugum_turu DugumTuru; typedef std::vector <dugum_turu> Dugumler; typedef std::list <kenar_turu> KenarListe; typedef std::vector <KenarListe> Kenarlar; typedef typename KenarListe::const_iterator GecerliKenar; typedef typename KenarListe::iterator Gecerlikenar; private: // bu grafiği oluşturan düğümler Dugumler dugumler_; // bitişik kenar listesinden oluşan bir vektör topluluğu // ( her düğümün sıra numarası bu düğümle bağlantılı bir // kenar listesi ile ilişkili) Kenarlar kenarlar_; // grafiğimiz yönlü mu? bool yonluGrafikMi_; int sonrakiDugumNo_; // Eğer grafikte bir kenar yoksa true döndürür. Kenar // eklerden bir kenarın birden fazla oluşturulmasını // engellemek için kullanılır bool kenarTekMi (int nerden, int nereye) const; // Grafikteki tüm kenarları gezer ve geçersiz olan // kenarları kaldirir void gecersizKenarlariYokEt (); public: SeyrekGrafik (bool yonluGrafikMi) : sonrakiDugumNo_ (0), yonluGrafikMi_ (yonluGrafikMi) {} // Belirtilen sıradaki düğümü öğrenir const DugumTuru & dugumOgren (int no) const; // const olmayan versiyonu DugumTuru & dugumOgren (int no); const KenarTuru & kenarOgren (int nerden, int nereye) const; KenarTuru & kenarOgren (int nerden, int nereye); int sonrakiBostaDugumunNumarasiniOgren () const { return sonrakiDugumNo_; } // Grafiğe bir düğüm ekler ve eklenen düğümün sıra // numarasını döndürür int dugumEkle (dugum_turu dugum); // bir düğümü düğümün sıra numarasını // gecersiz_dugum_sira_numarasi' na eşitleyerek kaldırır void dugumKaldir (int dugum); // Bu işlev grafiğe bir kenar ekler. Bu işlev parametre // olarak geçilen kenarı grafiğe eklemeden önce geçerli // olduğundan emin olur. Eğer grafik yönlü grafikse // diğer taraftaki kenarı da otomatik olarak ekler. void kenarEkle (KenarTuru kenar); // grafikte nerden nereye ile belirtilen kenarı kaldırır // (varsa) Eğer grafik çift yönlüyse her iki yöndeki // kenarı da kaldırır void kenarKaldir (int nerden, int nereye); // bir kenar için gezinme maliyeti belirler void kenarMasrafiBelirle (int nerden, int nereye, double masraf); // bir grafikte aktif olsun olmasın tüm düğümlerin // sayısını verir int dugumSayisi () const { return dugumler_.size (); } // geçerli düğüm sayısını verir (--this method's // performance can be improved greatly by caching the // value--) int gecerliDugumSayisi () const { int sayac = 0; for (unsigned int i = 0; i < dugumler_.size (); ++i) if (dugumler_ [i].siraNo () != gecersiz_dugum_sira_numarasi) ++sayac; return sayac; } // grafikte bulunan tüm kenarların sayısını verir int kenarSayisi () const { int toplam = 0; for (Gecerlikenar gecerliKenar = kenarlar_.begin (); gecerliKenar != kenarlar_.end (); ++gecerliKenar) { toplam += gecerliKenar->size (); } return toplam; } // Eğer grafiğimiz yönlü grafikse true döndürür bool yonluMu () const { return yonluGrafikMi_; } // Eğer grafikte hiç düğüm yoksa true döndürür bool bosMu () const { return dugumler_.empty (); } // belirtilen sıradaki düğüm varsa true döndürür bool dugumVarMi (int siraNo) const; // eğer nereden nereye'yi birbirine bağlayan kenar // grafikte varsa true döndürür bool kenarVarMi (int nerden, int nereye) const; // bir giriş akımına ya da bir dosyaya grafikleri yazmak // ya da okumak için işlevler bool kaydet (const char * dosyaIsmi) const; bool kaydet (std:ofstream & akim) const; bool yukle (const char * dosyaIsmi); bool yukle (std::ifstream & akim); }; template <class dugum_turu, class kenar_turu> const dugum_turu & SeyrekGrafik <dugum_turu, kenar_turu>::dugumOgren (int no) const { assert ( (no < (int) dugumler_.size ()) && (no >= 0) && "<SeyrekGrafik::dugumOgren>: gecersiz dugum sira numarasi"); return dugumler_ [no]; } // const olmayan versiyonu template <class dugum_turu, class kenar_turu> dugum_turu & SeyrekGrafik <dugum_turu, kenar_turu>::dugumOgren (int no) { assert ( (no < (int) dugumler_.size ()) && (no >= 0) && "<SeyrekGrafik::dugumOgren>: gecersiz dugum sira numarasi"); return dugumler_ [no]; } template <class dugum_turu, class kenar_turu> const kenar_turu & SeyrekGrafik <dugum_turu, kenar_turu>::kenarOgren (int nerden, int nereye) const { assert ( (nerden < kenarlar_.size ()) && (nerden >= 0) && dugumler_ [nerden].dugumSiraNumarasi () != gecersiz_dugum_sira_numarasi && "<SeyrekGrafik::kenarOgren>: 'nerden' icin gecersiz sira numarasi"); assert ( (nereye < kenarlar_.size ()) && (nereye >= 0) && dugumler_ [nereye].dugumSiraNumarasi () != gecersiz_dugum_sira_numarasi && "<SeyrekGrafik::kenarOgren>: 'nereye' icin gecersiz sira numarasi"); for (typename KenarListe::const_iterator gecerliKenar = kenarlar_ [nerden].begin (); gecerliKenar != kenarlar_ [nereye].end (); ++gecerliKenar) { if (gecerliKenar->nereye () == nereye) return *gecerliKenar; } assert (0 && "<SeyrekGrafik::kenarOgren>: kenar yok"); } // const olmayan versiyonu template <class dugum_turu, class kenar_turu> kenar_turu & SeyrekGrafik <dugum_turu, kenar_turu>::kenarOgren (int nerden, int nereye) { assert ( (nerden < kenarlar_.size ()) && (nerden >= 0) && dugumler_ [nerden].siraNo () != gecersiz_dugum_sira_numarasi && "<SeyrekGrafik::kenarOgren>: 'nerden' icin gecersiz sira numarasi"); assert ( (nereye < kenarlar_.size ()) && (nereye >= 0) && dugumler_ [nereye].siraNo () != gecersiz_dugum_sira_numarasi && "<SeyrekGrafik::kenarOgren>: 'nereye' icin gecersiz sira numarasi"); for (GecerliKenar gecerliKenar = kenarlar_ [nerden].begin (); gecerliKenar != kenarlar_ [nereye].end (); ++gecerliKenar) { if (gecerliKenar->nereye () == nereye) return *gecerliKenar; } assert (0 && "<SeyrekGrafik::kenarOgren>: kenar yok"); } template <class dugum_turu, class kenar_turu> int SeyrekGrafik <dugum_turu, kenar_turu>::dugumEkle (dugum_turu dugum) { if (dugum.siraNo () < (int) dugumler_.size ()) { assert (dugumler_ [dugum.siraNo ()].siraNo () == gecersiz_dugum_sira_numarasi && "<SeyrekGrafik::dugumEkle>: ayni sira numarasiyla dugum eklemeye calisiyorum"); dugumler_ [dugum.siraNo ()] = dugum; return sonrakiDugumNo_; } else { assert (dugum.siraNo () == sonrakiDugumNo_ && "<SeyrekGrafik:dugumEkle>: gecersiz dugum sıra no"); dugumler_.push_back (dugum); kenarlar_.push_back (KenarListe ()); return sonrakiDugumNo_++; } } template <class dugum_turu, class kenar_turu> void SeyrekGrafik <dugum_turu, kenar_turu>::dugumKaldir (int dugum) { assert (dugum < (int) dugumler_.size && "<SeyrekGrafik:dugumEkle>: gecersiz dugum sira numarasi"); dugumler_ [dugum].siraNoDegistir (gecersiz_dugum_sira_numarasi); if (!yonluGrafikMi_) { for (Gecerlikenar gecerliKenar = kenarlar_[dugum].begin (); gecerliKenar != kenarlar_[dugum].end (); ++gecerliKenar) { for (Gecerlikenar gecK = kenarlar_[gecerliKenar->nereye ()].begin (); gecK != kenarlar_[gecerliKenar->nereye ()].end (); ++gecK) { if (gecK->nereye () == dugum) { gecK = kenarlar_[gecerliKenar->nereye ()].erase (gecK); break; } } } dugumler_ [dugum].temizle (); } else { gecersizKenarlariYokEt (); } } template <class dugum_turu, class kenar_turu> void SeyrekGrafik <dugum_turu, kenar_turu>::kenarEkle (KenarTuru kenar) { assert ( (kenar.nerden () < sonrakiDugumNo_) && (kenar.nereye () < sonrakiDugumNo_) && "<SeyrekGrafik::kenarEkle>: gecersiz dugum numarasi"); if ( (dugumler_ [kenar.nereye ()].siraNo () != gecersiz_dugum_sira_numarasi) && (dugumler_ [kenar.nerden ()].siraNo () != gecersiz_dugum_sira_numarasi)) { if (kenarTekMi (kenar.nerden (), kenar.nereye ())) { kenarlar_ [kenar.nerden ()].push_back (kenar); } if (!yonluGrafikMi_) { if (kenarTekMi (kenar.nerden (), kenar.nereye () )) { KenarTuru yeniKenar = kenar; yeniKenar.degistirNerden (kenar.nerden ()); yeniKenar.degistirNereye (kenar.nereye ()); kenarlar_ [kenar.nerden ()].push_back (yeniKenar); } } } } //------------------------------- KenarKaldir --------------------------------- // // Grafikten bir kenar kaldırır // //----------------------------------------------------------------------------- template <class dugum_turu, class kenar_turu> void SeyrekGrafik <dugum_turu, kenar_turu>::kenarKaldir (int nerden, int nereye) { assert ( (nerden < (int) dugumler_.size ()) && (nereye < (int) dugumler_.size ()) && "<SeyrekGrafik::kenarKaldir>: gecersiz dugum numarasi"); Gecerlikenar gecerliKenar; if (!yonluGrafikMi_) { for (gecerliKenar = kenarlar_ [nereye].begin (); gecerliKenar != kenarlar_ [nereye].end (); ++gecerliKenar) { if (gecerliKenar->nereye () == nerden) { gecerliKenar = kenarlar_ [nereye].erase (gecerliKenar); break; } } for (gecerliKenar = kenarlar_ [nerden].begin (); gecerliKenar != kenarlar_ [nerden].end (); ++gecerliKenar) { if (gecerliKenar->nereye () == nereye) { gecerliKenar = kenarlar_ [nerden].erase (gecerliKenar); break; } } } } //----------------------------- KenarMasrafiBelirle ---------------------------- // // Belirli bir kenar için masraf belirler // //----------------------------------------------------------------------------- template <class dugum_turu, class kenar_turu> void SeyrekGrafik <dugum_turu, kenar_turu>::kenarMasrafiBelirle (int nerden, int nereye, double masraf) { // verilen düğümlerin geçerli olduğundan emin ol assert ( (nerden < dugumler_.size ()) && (nereye < dugumler_.size ()) && "<SeyrekGrafik::kenarMasrafiBelirle>: gecersiz dugum numarasi"); // tüm komşuları ziyaret et ve bu düğüme bağlı tüm kenarları sil for (Gecerlikenar gecerliKenar = kenarlar_[nerden].begin (); gecerliKenar != kenarlar_[nerden].end (); ++gecerliKenar) { if (gecerliKenar->nereye () == nereye) { gecerliKenar->masrafBelirle (masraf); break; } } } //----------------------------- dugumVarMi --------------------------------- // // belirtilen sıra numarasındaki düğüm grafikte varsa true döndürür //-------------------------------------------------------------------------- template <class dugum_turu, class kenar_turu> bool SeyrekGrafik <dugum_turu, kenar_turu>::dugumVarMi (int siraNo) const { if ( (dugumler_ [siraNo].siraNo () == gecersiz_dugum_sira_numarasi) || (siraNo >= dugumler_.size ()) ) { return false; } else return true; } //----------------------------- kenarVarMi --------------------------------- // // eğer nereden nereye'yi birbirine bağlayan kenar grafikte // varsa true döndürür // -------------------------------------------------------------------------- template <class dugum_turu, class kenar_turu> bool SeyrekGrafik <dugum_turu, kenar_turu>::kenarVarMi (int nerden, int nereye) const; { if ( dugumVarMi (nerden) && dugumVarMi (nereye) ) { for (GecerliKenar gecerliKenar = kenarlar_ [nerden].begin (); gecerliKenar != kenarlar_ [nerden].end (); ++gecerliKenar) { if (gecerliKenar->nereye () == nereye) return true; } return false; } } //-------------------------------- Kaydet --------------------------------------- template <class dugum_turu, class kenar_turu> bool SeyrekGrafik <dugum_turu, kenar_turu>::kaydet (const char * dosyaIsmi) const; { // dosyayı aç ve geçerli olduğundan emin ol std::ofstream cikis (dosyaIsmi); if (!cikis) { throw std::runtime_error ("Dosyayi acamiyorum: " + std::string (dosyaIsmi)); return false; } }
Private
[
?
]
Run code
Submit