// -*- C++ -*-
// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING. If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.
// As a special exception, you may use this file as part of a free
// software library without restriction. Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License. This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
/**
* @file priority_queue_dijkstra_example.cpp
* A basic example showing how to cross reference a vector and a
* priority-queue for modify.
*/
/**
* This example shows how to cross-reference priority queues
* and a vector. I.e., using a vector to
* map keys to entries in a priority queue, and using the priority
* queue to map entries to the vector. The combination
* can be used for fast modification of keys.
*
* As an example, a very simple form of Diskstra's algorithm is used. The graph
* is represented by an adjacency matrix. Nodes and vertices are size_ts, and
* it is assumed that the minimal path between any two nodes is less than 1000.
*/
#include
#include
#include
using namespace std;
using namespace pb_ds;
using namespace pb_ds;
// The value type of the priority queue.
// The first entry is the node's id, and the second is the distance.
typedef std::pair pq_value;
// Comparison functor used to compare priority-queue value types.
struct pq_value_cmp : public binary_function
{
inline bool
operator()(const pq_value& r_lhs, const pq_value& r_rhs) const
{
// Note that a value is considered smaller than a different value
// if its distance is* larger*. This is because by STL
// conventions, "larger" entries are nearer the top of the
// priority queue.
return r_rhs.second < r_lhs.second;
}
};
int main()
{
enum
{
// Number of vertices is hard-coded in this example.
num_vertices = 5,
// "Infinity".
graph_inf = 1000
};
// The edge-distance matrix.
// For example, the distance from node 0 to node 1 is 5, and the
// distance from node 1 to node 0 is 2.
const size_t a_a_edge_legnth[num_vertices][num_vertices] =
{
{0, 5, 3, 7, 6},
{2, 0, 2, 8, 9},
{2, 1, 0, 8, 0},
{1, 8, 3, 0, 2},
{2, 3, 4, 2, 0}
};
// The priority queue type.
typedef pb_ds::priority_queue< pq_value, pq_value_cmp> pq_t;
// The priority queue object.
pq_t p;
// This vector contains for each node, a find-iterator into the
// priority queue.
vector a_it;
// First we initialize the data structures.
// For each node, we push into the priority queue a value
// identifying it with a distance of infinity.
for (size_t i = 0; i < num_vertices; ++i)
a_it.push_back(p.push(pq_value(i, graph_inf)));
// Now we take the initial node, in this case 0, and modify its
// distance to 0.
p.modify(a_it[0], pq_value(0, 0));
// The priority queue contains all vertices whose final distance has
// not been determined, so to finish the algorithm, we must loop
// until it is empty.
while (!p.empty())
{
// First we find the node whose distance is smallest.
const pq_value& r_v = p.top();
const size_t node_id = r_v.first;
const size_t dist = r_v.second;
// This is the node's final distance, so we can print it out.
cout << "The distance from 0 to " << node_id
<< " is " << dist << endl;
// Now we go over the node's neighbors and "relax" the
// distances, if applicable.
for (size_t neighbor_i = 0; neighbor_i < num_vertices; ++neighbor_i)
{
// Potentially, the distance to the neighbor is the distance
// to the currently-considered node + the distance from this
// node to the neighbor.
const size_t pot_dist = dist + a_a_edge_legnth[node_id][neighbor_i];
// "Relax" the distance (if appropriate) through modify.
if (pot_dist < a_it[neighbor_i]->second)
p.modify(a_it[neighbor_i], pq_value(neighbor_i, pot_dist));
}
// Done with the node, so we pop it.
p.pop();
}
return 0;
}