| /************************************************************************** |
| * |
| * graph.cpp - Example of a Graph built from STL's map. |
| * |
| * $Id$ |
| * |
| *************************************************************************** |
| * |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed |
| * with this work for additional information regarding copyright |
| * ownership. The ASF licenses this file to you under the Apache |
| * License, Version 2.0 (the "License"); you may not use this file |
| * except in compliance with the License. You may obtain a copy of |
| * the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or |
| * implied. See the License for the specific language governing |
| * permissions and limitations under the License. |
| * |
| * Copyright 1994-2006 Rogue Wave Software. |
| * |
| **************************************************************************/ |
| |
| #include <map> |
| #include <vector> |
| #include <queue> |
| #include <iostream> |
| #include <string> |
| |
| #include <examples.h> |
| |
| typedef |
| std::map<std::string, int, std::less<std::string>, |
| std::allocator<std::pair<const std::string, int> > > stringVector; |
| |
| typedef |
| std::map<std::string, stringVector, std::less<std::string>, |
| std::allocator<std::pair<const std::string, |
| stringVector > > > graph; |
| |
| typedef std::pair<unsigned,std::string> DistancePair; |
| |
| bool operator< (const DistancePair& lhs, const DistancePair& rhs) { |
| |
| return lhs.first < rhs.first; |
| } |
| |
| |
| bool operator> (const DistancePair& lhs, const DistancePair& rhs) { |
| |
| return lhs.first > rhs.first; |
| } |
| |
| |
| std::string pendleton ("Pendleton"); |
| std::string pensacola ("Pensacola"); |
| std::string peoria ("Peoria"); |
| std::string phoenix ("Phoenix"); |
| std::string pierre ("Pierre"); |
| std::string pittsburgh ("Pittsburgh"); |
| std::string princeton ("Princeton"); |
| std::string pueblo ("Pueblo"); |
| |
| void shortestDistance (graph& city_map, std::string& start_city, |
| stringVector& distances) { |
| |
| // Process a priority queue of distances to nodes. |
| std::priority_queue<DistancePair, |
| std::vector<DistancePair, |
| std::allocator<DistancePair> >, |
| std::greater<DistancePair> > que; |
| |
| que.push (DistancePair (0, start_city)); |
| |
| while (! que.empty ()) { |
| |
| // Pull nearest city from queue. |
| int distance = que.top ().first; |
| std::string city = que.top ().second; |
| que.pop (); |
| |
| // If we haven't seen it already, process it. |
| if (0 == distances.count (city)) |
| { |
| // Then add it to shortest distance map. |
| distances[city] = distance; |
| |
| // And put values into queue. |
| const stringVector& cities = city_map[city]; |
| stringVector::const_iterator start = cities.begin (); |
| stringVector::const_iterator stop = cities.end (); |
| |
| for (; start != stop; ++start) |
| que.push (DistancePair (distance + (*start).second, |
| (*start).first)); |
| } |
| } |
| } |
| |
| |
| // Global city map |
| graph cityMap; |
| |
| int main () { |
| |
| std::cout << "Graph example program " |
| << " - find shortest path in a directed graph." |
| << std::endl; |
| |
| cityMap[pendleton][phoenix] = 4; |
| cityMap[pendleton][pueblo] = 8; |
| cityMap[pensacola][phoenix] = 5; |
| cityMap[peoria][pittsburgh] = 5; |
| cityMap[peoria][pueblo] = 3; |
| cityMap[phoenix][peoria] = 4; |
| cityMap[phoenix][pittsburgh] = 10; |
| cityMap[phoenix][pueblo] = 3; |
| cityMap[pierre][pendleton] = 2; |
| cityMap[pittsburgh][pensacola] = 4; |
| cityMap[princeton][pittsburgh] = 2; |
| cityMap[pueblo][pierre] = 3; |
| |
| stringVector distances; |
| |
| shortestDistance (cityMap, pierre, distances); |
| stringVector::iterator where; |
| |
| std::cout << "Find the shortest path from : " |
| << pierre.c_str () << std::endl; |
| |
| for (where = distances.begin (); where != distances.end (); ++where) |
| std::cout << " Distance to: " << (*where).first << ":" |
| << (*where).second << std::endl; |
| |
| std::cout << "End of graph example program" << std::endl; |
| |
| return 0; |
| } |
| |
| |
| |
| |