1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
| // PriorityQueueBench.cpp*: définit le point d'entrée pour l'application console.
//
#include "math.h"
#include <stdlib.h>
#include <cstdio>
#include <iostream>
#include <algorithm> // std::random_shuffle
#include <ctime> // std::time
#include <cstdlib> // std::rand, std::srand
#include <vector>
#include <climits>
#include <queue>
#include <chrono>
using namespace std;
vector < vector <int> > graph;
vector < vector <int> > weight;
vector < int> cost;
int N;
struct cmp {
bool operator()(const int &lhs, const int &rhs) const {
return cost[lhs] > cost[rhs];
}
};
int min(const int a, const int b) {
if (a<b)
return a;
return b;
}
struct mypq :public priority_queue<int, vector<int>, cmp> {
void clear() {
//size_t prevsize = c.size();
c.clear();
//c.reserve(prevsize * 2u + 1u);
}
};
mypq pq;
int dijkstra(const int from, const int to) {
vector <bool> visited(N, false);
visited[from] = true;
cost[from] = 0;
pq.push(from);
while (!pq.empty() && !visited[to]) {
int current = pq.top();
pq.pop();
visited[current] = true;
for (int i = 0; i<graph[current].size(); i++) {
if (!visited[graph[current][i]]) {
cost[graph[current][i]] = min(cost[graph[current][i]], cost[current] + weight[current][i]);
pq.push(graph[current][i]);
}
}
}
return cost[to];
}
void resetGlobals() {
graph.clear();
weight.clear();
//Initialize structure:
for (int i = 0; i < N; i++) {
graph.push_back(vector <int>());
weight.push_back(vector <int>());
cost.push_back(INT_MAX);
}
}
/****************************************************************************/
/* Core Program */
/****************************************************************************/
int main(void) {
/***********************************
*DECLARATIONS AND INITS
***********************************/
int i, j, n_sims;
int *A, *rand_idx;
N = 25; // size of network
n_sims = 200;
/* initialize random seed: */
std::srand(unsigned(std::time(0)));
//assign rand_idx and shuffle the nodes values:
rand_idx = (int*)malloc(N * sizeof(int));
for (i = 0; i < N; i++)
rand_idx[i] = i; //fill vector.
std::random_shuffle(&rand_idx[0], &rand_idx[N]); //then shuffle
//Adjacency matrix (linear index):
A = (int*)calloc(N * N, sizeof(int));
for (int k = 0; k < n_sims; k++) {
resetGlobals();
std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
//Fill adjacency matrix 'A' with random values:
for (i = 0; i < N; i++) {
//randomly fill the adjacency matrix:
for (j = 0; j < N; j++) {
A[i + j * N] = (rand() % 4 == 1) ? 1 : 0;//one chance over 5 (possibly no connected node is ok)
}
}
//Fill the structure:
for (i = 0; i < N; i++) {
//rempli les liens (ici pour le noeud 'a' met un lien vers 'b',
//autrement dit pousse les noeuds connect�s dans 'a'):
for (j = 0; j < N; j++) { //nrows * 2 ?
if (A[i + j * N] == 1) {
graph[i].push_back(j);
weight[i].push_back(1); //ajoute le poids. (idem ici)
}
}
}
//Then perform the search for inflow and outflow nodes (find requested distance):
for (i = 0; i < N; i++) {
//for earch values of 'R', compute the distance with other nodes in 'R':
//search for distance 'distance' in other nodes using dijkstra's algorithm:
for (j = 0; j < N; j++) {
if (rand_idx[i] < j && rand_idx[i] != N - 1) { //only read the upper triangular part and omit the last line.
const int cur_dis = dijkstra(rand_idx[i], j);
//je me sers de cur_dis dans le code non minimal ici:
//s'il rencontre un certain critère de distance, on s'arrête
//et on est content.
}
}
}
//we browsed 'A' without finding the requested distance, thus assign '-1' to outputs
//(utilise l'interface MEX pour matlab normallement (non utilisée dans cet exemple minimal)
/*plhs[0] = mxCreateDoubleScalar(-1.0); //in
plhs[1] = mxCreateDoubleScalar(-1.0); //out
plhs[2] = mxCreateDoubleScalar(-1.0); //fdistance*/
pq.clear();
std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
std::cout << "Iteration "<< k << "; duration = " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << std::endl;
}
free(rand_idx);
free(A);
return 1;
} |
Fuite mémoire avec le HEAP et Priority Queue
Répondre avec citation
Partager