home *** CD-ROM | disk | FTP | other *** search
/ QBasic & Borland Pascal & C / Delphi5.iso / C / BC_502 / STDLIB.PAK / GRAPH.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1997-05-06  |  2.7 KB  |  100 lines
  1. /**************************************************************************
  2.  *
  3.  * graph.cpp - Graph program.  Section 9.3.2
  4.  *
  5.  * $Id: graph.cpp,v 1.4 1995/08/29 20:10:14 oberg Exp $
  6.  *
  7.  * $$RW_INSERT_HEADER "slyrs.cpp"
  8.  *
  9.  **************************************************************************/
  10.  
  11. # include <map>
  12. # include <vector>
  13. # include <queue>
  14. # include <iostream.h>
  15. # include <string>
  16. using namespace std;
  17.  
  18. typedef map<string, int, less<string> > stringVector;
  19. typedef map<string, stringVector, less<string> > graph;
  20.  
  21. struct DistancePair
  22. {
  23.     unsigned first;
  24.     string   second;
  25.     DistancePair() : first(0) {}
  26.     DistancePair(unsigned f, const string& s) : first(f), second(s) {}
  27.  
  28. bool operator< (const DistancePair& rhs) const
  29. {
  30.   return first < rhs.first;
  31. }
  32.  
  33. };
  34.  
  35. string pendleton("Pendleton");
  36. string pensacola("Pensacola");
  37. string peoria("Peoria");
  38. string phoenix("Phoenix");
  39. string pierre("Pierre");
  40. string pittsburgh("Pittsburgh");
  41. string princeton("Princeton");
  42. string pueblo("Pueblo");
  43.  
  44.  
  45.     graph cityMap;
  46.  
  47.  
  48. void shortestDistance(graph & cityMap, string & start, stringVector & distances)
  49. {
  50.     // process a priority queue of distances to nodes
  51.     priority_queue<DistancePair, vector<DistancePair>,
  52.             greater<DistancePair> > que;
  53.     que.push(DistancePair(0, start));
  54.     
  55.     while (! que.empty()) {
  56.             // pull nearest city from queue
  57.         int distance = que.top().first;
  58.         string city = que.top().second;
  59.         que.pop();
  60.             // if we haven't seen it already, process it
  61.         if (0 == distances.count(city)) {
  62.                 // then add it to shortest distance map
  63.             distances[city] = distance;
  64.                 // and put values into queue
  65.  
  66.             const stringVector& cities = cityMap[city];
  67.             stringVector::const_iterator start = cities.begin();
  68.             stringVector::const_iterator stop  = cities.end();
  69.             for (; start != stop; ++start)
  70.                 que.push(DistancePair(distance + (*start).second, (*start).first));
  71.             }
  72.         }
  73. }
  74.  
  75. int main() {
  76.     cout << "Graph example program, from Chapter 7" << endl;
  77.     cityMap[pendleton][phoenix] = 4;
  78.     cityMap[pendleton][pueblo] = 8;
  79.     cityMap[pensacola][phoenix] = 5;
  80.     cityMap[peoria][pittsburgh] = 5;
  81.     cityMap[peoria][pueblo] = 3;
  82.     cityMap[phoenix][peoria] = 4;
  83.     cityMap[phoenix][pittsburgh] = 10;
  84.     cityMap[phoenix][pueblo] = 3;
  85.     cityMap[pierre][pendleton] = 2;
  86.     cityMap[pittsburgh][pensacola] = 4;
  87.     cityMap[princeton][pittsburgh] = 2;
  88.     cityMap[pueblo][pierre] = 3;
  89.     
  90.     stringVector distances;
  91.     
  92.     shortestDistance(cityMap, pierre, distances);
  93.     stringVector::iterator where;
  94.     for (where = distances.begin(); where != distances.end(); ++where)
  95.         cout << "Distance to: " << (*where).first << ":" <<  (*where).second << endl;
  96.         
  97.     cout << "End of graph example program" << endl;
  98.     return 0;
  99. }
  100.