1 |
424 |
jeremybenn |
// -*- C++ -*-
|
2 |
|
|
|
3 |
|
|
// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
|
4 |
|
|
//
|
5 |
|
|
// This file is part of the GNU ISO C++ Library. This library is free
|
6 |
|
|
// software; you can redistribute it and/or modify it under the terms
|
7 |
|
|
// of the GNU General Public License as published by the Free Software
|
8 |
|
|
// Foundation; either version 3, or (at your option) any later
|
9 |
|
|
// version.
|
10 |
|
|
|
11 |
|
|
// This library is distributed in the hope that it will be useful, but
|
12 |
|
|
// WITHOUT ANY WARRANTY; without even the implied warranty of
|
13 |
|
|
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
14 |
|
|
// General Public License for more details.
|
15 |
|
|
|
16 |
|
|
// You should have received a copy of the GNU General Public License
|
17 |
|
|
// along with this library; see the file COPYING3. If not see
|
18 |
|
|
// <http://www.gnu.org/licenses/>.
|
19 |
|
|
|
20 |
|
|
|
21 |
|
|
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
|
22 |
|
|
|
23 |
|
|
// Permission to use, copy, modify, sell, and distribute this software
|
24 |
|
|
// is hereby granted without fee, provided that the above copyright
|
25 |
|
|
// notice appears in all copies, and that both that copyright notice
|
26 |
|
|
// and this permission notice appear in supporting documentation. None
|
27 |
|
|
// of the above authors, nor IBM Haifa Research Laboratories, make any
|
28 |
|
|
// representation about the suitability of this software for any
|
29 |
|
|
// purpose. It is provided "as is" without express or implied
|
30 |
|
|
// warranty.
|
31 |
|
|
|
32 |
|
|
/**
|
33 |
|
|
* @file priority_queue_dijkstra_example.cpp
|
34 |
|
|
* A basic example showing how to cross reference a vector and a
|
35 |
|
|
* priority-queue for modify.
|
36 |
|
|
*/
|
37 |
|
|
|
38 |
|
|
/**
|
39 |
|
|
* This example shows how to cross-reference priority queues
|
40 |
|
|
* and a vector. I.e., using a vector to
|
41 |
|
|
* map keys to entries in a priority queue, and using the priority
|
42 |
|
|
* queue to map entries to the vector. The combination
|
43 |
|
|
* can be used for fast modification of keys.
|
44 |
|
|
*
|
45 |
|
|
* As an example, a very simple form of Diskstra's algorithm is used. The graph
|
46 |
|
|
* is represented by an adjacency matrix. Nodes and vertices are size_ts, and
|
47 |
|
|
* it is assumed that the minimal path between any two nodes is less than 1000.
|
48 |
|
|
*/
|
49 |
|
|
|
50 |
|
|
|
51 |
|
|
|
52 |
|
|
#include <vector>
|
53 |
|
|
#include <iostream>
|
54 |
|
|
#include <ext/pb_ds/priority_queue.hpp>
|
55 |
|
|
|
56 |
|
|
using namespace std;
|
57 |
|
|
using namespace __gnu_pbds;
|
58 |
|
|
|
59 |
|
|
// The value type of the priority queue.
|
60 |
|
|
// The first entry is the node's id, and the second is the distance.
|
61 |
|
|
typedef std::pair<size_t, size_t> pq_value;
|
62 |
|
|
|
63 |
|
|
// Comparison functor used to compare priority-queue value types.
|
64 |
|
|
struct pq_value_cmp : public binary_function<pq_value, pq_value, bool>
|
65 |
|
|
{
|
66 |
|
|
inline bool
|
67 |
|
|
operator()(const pq_value& r_lhs, const pq_value& r_rhs) const
|
68 |
|
|
{
|
69 |
|
|
// Note that a value is considered smaller than a different value
|
70 |
|
|
// if its distance is* larger*. This is because by STL
|
71 |
|
|
// conventions, "larger" entries are nearer the top of the
|
72 |
|
|
// priority queue.
|
73 |
|
|
return r_rhs.second < r_lhs.second;
|
74 |
|
|
}
|
75 |
|
|
};
|
76 |
|
|
|
77 |
|
|
int main()
|
78 |
|
|
{
|
79 |
|
|
enum
|
80 |
|
|
{
|
81 |
|
|
// Number of vertices is hard-coded in this example.
|
82 |
|
|
num_vertices = 5,
|
83 |
|
|
// "Infinity".
|
84 |
|
|
graph_inf = 1000
|
85 |
|
|
};
|
86 |
|
|
|
87 |
|
|
// The edge-distance matrix.
|
88 |
|
|
// For example, the distance from node 0 to node 1 is 5, and the
|
89 |
|
|
// distance from node 1 to node 0 is 2.
|
90 |
|
|
const size_t a_a_edge_legnth[num_vertices][num_vertices] =
|
91 |
|
|
{
|
92 |
|
|
{0, 5, 3, 7, 6},
|
93 |
|
|
{2, 0, 2, 8, 9},
|
94 |
|
|
{2, 1, 0, 8, 0},
|
95 |
|
|
{1, 8, 3, 0, 2},
|
96 |
|
|
{2, 3, 4, 2, 0}
|
97 |
|
|
};
|
98 |
|
|
|
99 |
|
|
// The priority queue type.
|
100 |
|
|
typedef __gnu_pbds::priority_queue< pq_value, pq_value_cmp> pq_t;
|
101 |
|
|
|
102 |
|
|
// The priority queue object.
|
103 |
|
|
pq_t p;
|
104 |
|
|
|
105 |
|
|
// This vector contains for each node, a find-iterator into the
|
106 |
|
|
// priority queue.
|
107 |
|
|
vector<pq_t::point_iterator> a_it;
|
108 |
|
|
|
109 |
|
|
// First we initialize the data structures.
|
110 |
|
|
|
111 |
|
|
// For each node, we push into the priority queue a value
|
112 |
|
|
// identifying it with a distance of infinity.
|
113 |
|
|
for (size_t i = 0; i < num_vertices; ++i)
|
114 |
|
|
a_it.push_back(p.push(pq_value(i, graph_inf)));
|
115 |
|
|
|
116 |
|
|
// Now we take the initial node, in this case 0, and modify its
|
117 |
|
|
// distance to 0.
|
118 |
|
|
p.modify(a_it[0], pq_value(0, 0));
|
119 |
|
|
|
120 |
|
|
// The priority queue contains all vertices whose final distance has
|
121 |
|
|
// not been determined, so to finish the algorithm, we must loop
|
122 |
|
|
// until it is empty.
|
123 |
|
|
while (!p.empty())
|
124 |
|
|
{
|
125 |
|
|
// First we find the node whose distance is smallest.
|
126 |
|
|
const pq_value& r_v = p.top();
|
127 |
|
|
const size_t node_id = r_v.first;
|
128 |
|
|
const size_t dist = r_v.second;
|
129 |
|
|
|
130 |
|
|
// This is the node's final distance, so we can print it out.
|
131 |
|
|
cout << "The distance from 0 to " << node_id
|
132 |
|
|
<< " is " << dist << endl;
|
133 |
|
|
|
134 |
|
|
// Now we go over the node's neighbors and "relax" the
|
135 |
|
|
// distances, if applicable.
|
136 |
|
|
for (size_t neighbor_i = 0; neighbor_i < num_vertices; ++neighbor_i)
|
137 |
|
|
{
|
138 |
|
|
// Potentially, the distance to the neighbor is the distance
|
139 |
|
|
// to the currently-considered node + the distance from this
|
140 |
|
|
// node to the neighbor.
|
141 |
|
|
const size_t pot_dist = dist + a_a_edge_legnth[node_id][neighbor_i];
|
142 |
|
|
|
143 |
|
|
if (a_it[neighbor_i] == a_it[0])
|
144 |
|
|
continue;
|
145 |
|
|
|
146 |
|
|
// "Relax" the distance (if appropriate) through modify.
|
147 |
|
|
if (pot_dist < a_it[neighbor_i]->second)
|
148 |
|
|
p.modify(a_it[neighbor_i], pq_value(neighbor_i, pot_dist));
|
149 |
|
|
}
|
150 |
|
|
|
151 |
|
|
// Done with the node, so we pop it.
|
152 |
|
|
a_it[node_id] = a_it[0];
|
153 |
|
|
p.pop();
|
154 |
|
|
}
|
155 |
|
|
|
156 |
|
|
return 0;
|
157 |
|
|
}
|