PB161 Jazyk C++ - záverecný príklad N

Hledání nejkratsí cesty

Zadání:

Vytvorte trídu, která bude reprezentovat , nezáporne ohodnocený graf (sít mest), a implementujte metodu hledání minimální cesty z daného uzlu (mesta) do vsech ostatních a k ní program podle následujících pozadavku.

Vstupní data:

Predpokládejte, ze graf je ulozen v textovém souboru, kde jednotlivé rádky obsahují informaci následujícího tvaru:

která urcuje vzdálenost z mestaA do mestaB. Vzdálenosti jsou celocíselné, jednotlivé vstupní polozky jsou oddeleny bílým znakem nebo jejich kombinací.

Pozadavky:

• Program nacte vsechny rádky ze souboru zadaného na príkazové rádce. Jako dalsí parametry z príkazového rádku budou zadány názvy 1 nebo 2 mest - výchozí a koncové. Program vypíse zadaná mesta a minimální vzdálenost mezi nimi. Pokud bude zadáno jediné mesto, vypíse vsechna mesta (do kterých existuje cesta ze zadaného mesta) vcetne príslusné minimální vzdálenosti.
• Protoze názvy mest mohou být dlouhé, povolte na príkazovém rádku zadávat pouze jejich zacátky, pokud tento zacátek identifikuje mesto jednoznacne. Povolte také zadávat zde názvy malými i velkými písmeny.
• Kontrolujte správnost volání a prípadné chyby ohlaste s nenulovým výsledkovým kódem. Za chybu povazujte i to, kdyz mesto zadané na príkazovém rádku není obsazeno ve vstupních datech. S jiným nenulovým výsledkovým kódem indikujte (po vypsání chybové zprávy) prípad, kdy neexistuje mezi zadanými 2 mesty cesta.

Poznámky:

• Graf povazujte za neorientovaný (tj. cesta z A do B soucasne znamená cestu z B do A)
• strongdpokládejte, ze název mesta neobsahuje mezeru. Víceslovné názvy budou zapisovány s vlozeným znakem, napr. Usti-nad-Labem, Vlachovo_Brezi.
• Program muze být pomerne krátký, pokud vyuzijete mozností, které poskytuje STL (standardní sablonová knihovna). Speciálne upozornuji na kontejnery map a priority_queue . Dále pripomínám, ze typ hodnoty v kontejneru map muze být i slozitejsí struktura.
• Úlohu zadal: Lubomír Markovic

Riešenie:

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <iomanip>
using namespace std;

class graf
{
 private:
  struct udaje{string cesta;int vzdialenost;};
  string z_mesta,do_mesta;
  int pocet_miest,vzdialenost;
  multimap<string,string> mesta;
  multimap<string,udaje>cesty_z_mesta;
  multimap<string,int> dlzka_cesty;
  multimap<string,string>::iterator tm;
  multimap<string,int>::iterator td_c;
  multimap<string,udaje>::iterator tczm;

 public:
  graf(){};
  graf(const graf& a);
  ~graf(){};

  int read(char * file);                 //nacitanie vstupneho grafu
  int find(string from,string to);       //najde from->to
  void write_out_ways();                 //vypise cesty

 private:
  bool control(string from,string to);   //ci obsahuje subor mesta
  bool find(string from);      //najde vsetky mesta kam sa da dostat

};

graf::graf(const graf& a):mesta(a.mesta),dlzka_cesty(a.dlzka_cesty)
     {pocet_miest=a.pocet_miest;}

//======================= nacitanie vstupneho grafu ============================
int graf::read(char *file)
{
 string mesto1,mesto2,pom;

 ifstream in(file,ios::in);
 if(!in) return 1;

 for(;;)
    {
     if(!(in>>mesto1>>mesto2>>vzdialenost)) break;
     for(unsigned int i=0;i<mesto1.length();i++) mesto1[i]=toupper(mesto1[i]);
     for(unsigned int i=0;i<mesto2.length();i++) mesto2[i]=toupper(mesto2[i]);

     
     if(mesto1>mesto2){string pom;pom=mesto1;mesto1=mesto2;mesto2=pom;}
     mesta.insert(make_pair(mesto1,mesto2));
     mesta.insert(make_pair(mesto2,mesto1));
     dlzka_cesty.insert(make_pair(mesto1+" "+mesto2,vzdialenost));


     if(mesto1==mesto2) return 2;
     if(vzdialenost<1)  return 2;

    }
 in.close();

 mesto2=mesto1="";pocet_miest=0;   //spocitat pocet miest
  for(tm=mesta.begin();tm!=mesta.end();++tm)
    {mesto2=tm->first;
     if(mesto2!=mesto1) pocet_miest++;
     mesto1=mesto2;
    }
                                             //odstranenie duplicitnych ciest
 for(td_c=dlzka_cesty.begin();td_c!=dlzka_cesty.end();td_c++)
  {mesto1=td_c->first;vzdialenost=td_c->second;
   if(mesto1==mesto2)
    {--td_c;
     if(td_c->second >=vzdialenost) dlzka_cesty.erase(td_c++);
     else dlzka_cesty.erase(++td_c);
      
     }
   mesto2=mesto1;
  }  

 return 0;
}

//============================= hladanie cesty =================================
bool graf::find(string from)
{
 for(tczm=cesty_z_mesta.begin();tczm!=cesty_z_mesta.end();tczm++)  
//vynulovanie
   cesty_z_mesta.erase(tczm);

 bool chyba=false;
 udaje najdene,nacitane;
 int *uzol=new int[pocet_miest],cislo_uzlu=0,
     *cislo_na_uzle=new int[pocet_miest],kontrola;
 for(int i=0;i<pocet_miest;i++) cislo_na_uzle[i]=0;

 string *across,mesto1,mesto2;
 across=new string[pocet_miest];

 across[0]=z_mesta;
//----------------- hlavny cyklus hladania ------------------------------------ 
 for(;;)
  {kontrola=1;
   if(cislo_uzlu<0 ||cislo_uzlu==pocet_miest) break;
   if(across[0]!=z_mesta)break;
   
   mesto1=across[cislo_uzlu];

   tm=mesta.find(mesto1);
   for(int i=0;i<cislo_na_uzle[cislo_uzlu];i++) ++tm;
   if(tm==mesta.end())
     {cislo_na_uzle[cislo_uzlu]=0;
      across[cislo_uzlu]="";
      cislo_uzlu--;
      cislo_na_uzle[cislo_uzlu]++;
      continue;
     }
   if(tm->first!=mesto1)
     {cislo_na_uzle[cislo_uzlu]=0;
      across[cislo_uzlu]="";
      cislo_uzlu--;
      cislo_na_uzle[cislo_uzlu]++;
      continue;
     }
   //nasiel mesto1

   kontrola=0;
   for(int i=0;i<=cislo_uzlu;i++)
   
if(across[i]==tm->second){cislo_na_uzle[cislo_uzlu]++;kontrola=1;break;}

   if(kontrola) continue;
   
   cislo_uzlu++;
   across[cislo_uzlu]=tm->second;
      
   //---------------------------------nasiel nejaku cestu-----------------------
   {
     chyba=true;
     vzdialenost=0;
     
 
     for(int i=1;i<=cislo_uzlu;i++) //najdenie dlzky cesty  
     {
      if(across[i-1]<across[i])
       td_c=dlzka_cesty.find(across[i-1]+" "+across[i]);
      else
       td_c=dlzka_cesty.find(across[i]+" "+across[i-1]);

      vzdialenost+=td_c->second;
     }
 
     najdene.cesta=across[0];
     for(int i=1;i<pocet_miest && across[i]!="";i++)
       najdene.cesta+=" -> "+across[i];   
     
     najdene.vzdialenost=vzdialenost;
     
     tczm=cesty_z_mesta.find(z_mesta+" "+tm->second);
     if(tczm==cesty_z_mesta.end())
       cesty_z_mesta.insert(make_pair(z_mesta+" "+tm->second,najdene));
     else  // jedna cesta uz bola najdena (treba porovnat vzdialenosti)
       {
         nacitane=tczm->second;
         if(nacitane.vzdialenost>najdene.vzdialenost)
          {
           cesty_z_mesta.erase(tczm);
           cesty_z_mesta.insert(make_pair(z_mesta+" "+tm->second,najdene));
          }
       }
    }
   
//---------------------------------------------------------------------------
  }

 delete[] across;
 delete[] uzol;
 delete[] cislo_na_uzle;
 return chyba;

}
//==============================================================================
int graf::find(string from,string to)
{
 if (!control(from,to)) return 1;
 if (!find(z_mesta))    return 2;

 if(do_mesta!="")
 for(tczm=cesty_z_mesta.begin();tczm!=cesty_z_mesta.end();tczm++)
   {
    if(tczm->first!=z_mesta+" "+do_mesta) cesty_z_mesta.erase(tczm);
   }
   
 if(!cesty_z_mesta.size()) return 2;
   

 return 0;
}

//====================== hladanie existencie miest =============================

bool graf::control(string from,string to)  
  {
   string pom1,pom2;
//------------------------------------------------------------------------------
// kontrola ci obsahuje from
   for(tm=mesta.begin();tm!=mesta.end();tm++)
    { if( ((tm->first).find(from))==0)
       {
        if(tm->first.length()<from.length()) continue;
        if(tm->first==from) {pom1=tm->first;break;}
        if(pom1.length()==0) pom1=tm->first;
        else if( pom1!=tm->first) return false;
       }
    }
   if(pom1=="") return false;

//------------------------------------------------------------------------------
// kontrola ci obsahuje "to"

   if(to!="")
   for(tm=mesta.begin();tm!=mesta.end();tm++)
    { if( ((tm->first).find(to))==0)
       {
        if(tm->first.length()<from.length()) continue;
        if(tm->first==to) {pom2=tm->first;break;}
        if(pom2.length()==0) pom2=tm->first;
        else if( pom2!=tm->first) return false;
       }
    }
   if(to!="" && pom2=="") return false;

   z_mesta=pom1;
   do_mesta=pom2;

   return true;
  }
//======================= vypis najkratsej cesty ===============================
void graf::write_out_ways()
{
 udaje nacitane;
 if(do_mesta!="")
    cout<<"Cesta: "<<z_mesta<<" -> "<<do_mesta<<endl;
 else
    cout<<"Cesty z mesta"<<" \""<<z_mesta<<"\""<<endl;

 cout<<"\n"<<setw(67)<<left<<setfill(' ')<<"Cesta";
 cout<<"Vzdialenost"<<endl;
 cout<<setfill('=')<<setw(80)<<""<<endl;
 for(tczm=cesty_z_mesta.begin();tczm!=cesty_z_mesta.end();tczm++)
  {
   nacitane=tczm->second;
   cout<<setw(70)<<left<<setfill(' ')<<nacitane.cesta;
   cout<<"  ("<<nacitane.vzdialenost<<')'<<endl;
   cout<<setfill('-')<<setw(80)<<""<<endl;
  }
  
}
//=================================MAIN=========================================

int control;
int main(int argc, char *argv[])
{
 if (argc>=3) //- - - - - - - osetrenie parametrov - - - - - - - - -
  {
   ifstream input(argv[1]);
   if (!input)
      {cout<<"Nepodarilo sa otvorit vstupny subor."<<endl;return 2;}
   else input.close();
  }
 else
  {
   cout<<"\nZadaj spravne parametre:\n\n"
       <<" graf \"subor_s_grafom\" \"z_mesta\" \"do_mesta\"\n"
       <<"  -pamameter \"do_mesta\" je nepovinny\n"<<endl;
   return 1;
  }
//-----------------------parametre su OK ---------------------------------------

 cout<<"\nGraf je zadany v subore: "
     <<"\""<<argv[1]<<"\""<<endl;

 string a=argv[2],b;
 
 if(argc>=4)
   b=argv[3];
 else
   b="";
   
 for(unsigned int i=0;i<a.length();i++) a[i]=toupper(a[i]);
 for(unsigned int i=0;i<b.length();i++) b[i]=toupper(b[i]);
 
 
 graf siet;
 control=siet.read(argv[1]);
 if(control) 
  {
   cout<<"Nekonzistencia vstupnych dat!"<<endl;
   return control+10;
  }
  
 graf siet2=siet;
 
  control=siet2.find(a,b);
  if(control)
   {if(control==2) cout<<"Cesta nenexistuje!"<<endl;
    if(control==1) cout<<"Mesto nebolo najdene v grafe, upresnite nazov!"<<endl;
    return control+20;
    }
                          //return 22-nenasiel cestu
                          //return 21-nenasiel mesto
  else 
  siet2.write_out_ways();   

 return 0;
}