#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;
}
}