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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
using namespace std;
const int N=1400;
const int M=(N*(N-1))/2;
typedef struct coord{int abs; int ord;} coord;
void pointRandom(int n,coord point[]);
float distancexy(coord p1,coord p2);
void voisins(int n,int dmax,coord point[],vector<int> voisin[],int &m);
void voisins2arete(int n,vector<int>voisins[],int arete[][2]);
void affichageGraphique(int n,int m,coord point[],vector<int> voisins[],const char * name);
bool existe(int n,int dis[],bool traite[]);
int searchsmallest(int n, int dist[],bool traite[]);
void dijkstra(int n,vector<int> voisin[],coord point[],int pere[], int m);
int construireArbre(int n,vector<int> voisin[],int pere[]);
int
main()
{
int n; // Le nombre de points.
cout << "Entrer le nombre de points: ";
cin >> n;
int dmax=50; // La distance jusqu'a laquelle on relie deux points.
coord point[N]; // Les coordonnees des points.
vector<int> voisin[N];
vector<int> voisinbis[N]; // Les listes de voisins.
int arbre[N-1][2]; // Les aretes de l'arbre de Dijkstra.
int pere[N]; // La relation de filiation de l'arbre de Dijkstra.
int m; // Le nombre d'aretes
int arete[M][2]; // Les aretes du graphe
pointRandom(n,point);
voisins(n,dmax, point, voisin, m);
const char * filename = "affichage.ps";
affichageGraphique(n,m,point,voisin,filename);
cout<<"Graphe de base créé et exporté vers "<<filename<<endl;
dijkstra(n,voisin,point,pere,m);
construireArbre(n,voisinbis,pere);
const char * filename2 = "affichagefin.ps";
affichageGraphique(n,m,point,voisinbis,filename2);
return EXIT_SUCCESS;
}
void pointRandom(int n, coord point[]){
srand(time(NULL));
for (int i =0; i < n; i ++){
point[i].abs = rand()%612;
point[i].ord =rand()%792;
cout << "Created point "<<i<<" coords : "<< point[i].abs <<" : "<<point[i].ord<<endl;
}
}
float distancexy(coord p1,coord p2){
return sqrt((pow(p1.abs-p2.abs,2)+pow(p1.ord-p2.ord,2)));
}
void voisins (int n, int dmax, coord point[], vector<int> voisins[], int &m){
int arrete = 0;
for (int i = 0; i < n; i ++){
for (int j = i+1; j < n; j ++){
if ( sqrt(pow(point[i].abs-point[j].abs,2)+pow(point[i].ord-point[j].ord,2))<=dmax){
voisins[i].push_back(j);
voisins[j].push_back(i);
arrete++;
}
}
}
m=arrete;
}
void affichageGraphique(int n, int m, coord point[], vector<int> voisins[], const char * filename)
// Cree le fichier Exemple.ps qui affiche
// les points et l'arbre de Kruskal.
{
ofstream output;
output.open(filename,ios::out);
output << "%!PS-Adobe-3.0" << endl;
output << "%%BoundingBox: 0 0 612 792" << endl;
output << endl;
for(int i=0;i<n;i++)
{
output << point[i].abs << " " << point[i].ord << " 3 0 360 arc" <<endl;
output << "0 setgray" <<endl;
output << "fill" <<endl;
output << "stroke"<<endl;
output << endl;
}
output << endl;
for(int i=0;i<n;i++)
{
for (int j =0; j < voisins[i].size(); j ++){
if (voisins[i][j] >= i){
output << point[i].abs<<" "<<point[i].ord << " moveto"<<endl;
output<<point[voisins[i][j]].abs << " " << point[voisins[i][j]].ord << " lineto"<<endl;
output<< "stroke"<<endl;
output << endl;
}
}
}
output<<"showpage";
output<<endl;
}
bool existe(int n,int dis[],bool traite[]){
bool test = true;
bool ret = false;
int i = 0;
while (test && i < n){
if (!traite[i] && (dis[i]!=-1)){
test = false;
ret = true;
}
i++;
}
return ret;
}
int searchsmallest(int n, int dist[],bool traite[]){
int ret=-1;
int retdist = 10000;
for (int i = 0 ; i < n; i ++){
// cout<<"i :"<< i << " Dist de i "<< dist[i]<<" traite de i "<<traite[i]<<endl;
if (traite[i]==false){
if (dist[i]!= -1){
if (dist[i]<=retdist){
retdist=dist[i];
ret =i;
}
}
}
}
// cout<<"Lancment du traitement de :" << ret<<endl;
return ret;
}
void dijkstra(int n, vector<int> voisin[], coord point[], int pere[], int m){
int d[n];
bool traite[n];
for (int i =0; i < n; i ++){
d[i]= -1;
traite[i]=false;
}
pere[0]=0;
d[0]=0;
while (existe(n,d,traite)){
int current = searchsmallest(n,d,traite);
//cout<<"C'est ti-par avec current = "<< current <<endl;
traite[current]=true;
// cout<<"traite current : " << traite[current]<<endl;
for (int i =0; i < voisin[current].size();i ++){
int x = current;
int y = voisin[current][i];
//cout<<"Traitement de l'arete "<<x<<";"<<y<<endl;
//cout << d[y] << "versus " << d[x]<< " + " <<distancexy(point[x],point[y])<<endl;
if (!traite[y] && ((d[y]==-1) || (d[y]>(d[x]+distancexy(point[x],point[y]))))){
d[y]=d[x]+distancexy(point[x],point[y]);
pere[y]=x;
}
}
}
}
int construireArbre(int n,vector<int> voisin[],int pere[]){
for ( int i = 0; i < n; i ++){
voisin[i].push_back(pere[i]);
voisin[pere[i]].push_back(i);
}
return n;
}
|
