GTK+ IOStream
Beta
<< GTK+ >> add C++ IOStream operators to GTK+. Now with extra abilities ... like network serialisation
Main Page
Namespaces
Classes
Files
Examples
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Macros
Pages
mffm
possible.future.additions
Dijkstra
dijkstra.H
Go to the documentation of this file.
1
/* Copyright 2000-2012 Matt Flax <flatmax@flatmax.org>
2
This file is part of GTK+ IOStream class set
3
4
GTK+ IOStream is free software; you can redistribute it and/or modify
5
it under the terms of the GNU General Public License as published by
6
the Free Software Foundation; either version 2 of the License, or
7
(at your option) any later version.
8
9
GTK+ IOStream is distributed in the hope that it will be useful,
10
but WITHOUT ANY WARRANTY; without even the implied warranty of
11
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12
GNU General Public License for more details.
13
14
You have received a copy of the GNU General Public License
15
along with GTK+ IOStream
16
*/
17
#ifndef DIJKSTRA_H_
18
#define DIJKSTRA_H_
19
20
class
Dijkstra
{
21
int
*
visited
;
22
int
**
pathLengths
;
23
int
**
roadLengths
;
24
int
**
lastLoc
;
25
int
N
;
26
27
void
dumpArrays
(
int
**
roadLengths
,
int
Nin) {
28
N
=Nin;
29
cout<<
"Visited = ["
;
30
for
(
int
i=0; i<
N
; i++)
31
cout<<
visited
[i]<<
", "
;
32
cout<<
"]"
<<endl;
33
cout<<
"a\tb\tc\td\te\tf\tg\th\ti\tj"
;
34
cout<<
"\t || "
;
35
cout<<
"a\tb\tc\td\te\tf\tg\th\ti\tj"
<<endl;
36
cout<<
"1\t2\t3\t4\t5\t6\t7\t8\t9\t10"
;
37
cout<<
"\t || "
;
38
cout<<
"1\t2\t3\t4\t5\t6\t7\t8\t9\t10"
<<endl;
39
for
(
int
i=0; i<
N
; i++) {
40
for
(
int
j=0; j<
N
; j++)
41
cout<<
pathLengths
[i][j]<<
'\t'
;
42
cout<<
" || "
;
43
for
(
int
j=0; j<
N
; j++)
44
cout<<
lastLoc
[i][j]<<
'\t'
;
45
cout<<
'\n'
;
46
}
47
48
cout<<
'\n'
<<endl;
49
}
50
51
public
:
52
53
Dijkstra
(
int
Nin) {
54
pathLengths
=NULL;
55
roadLengths
=NULL;
56
lastLoc
=NULL;
57
visited
=NULL;
58
N
=Nin;
59
cout<<
"N "
<<
N
<<endl;
60
pathLengths
=
new
int
*[
N
];
61
if
(!
pathLengths
) {
62
cerr<<
"couldn't create path lengths"
<<endl;
63
return
;
64
}
65
for
(
int
i=0; i<
N
; i++)
66
pathLengths
[i]=NULL;
67
68
for
(
int
i=0; i<
N
; i++) {
69
pathLengths
[i] =
new
int
[
N
];
70
if
(!
pathLengths
[i]) {
71
cerr<<
"couldn't create path lengths"
<<endl;
72
return
;
73
}
74
}
75
roadLengths
=
new
int
*[
N
];
76
if
(!
roadLengths
) {
77
cerr<<
"couldn't create road lengths"
<<endl;
78
return
;
79
}
80
for
(
int
i=0; i<
N
; i++)
81
roadLengths
[i]=NULL;
82
83
for
(
int
i=0; i<
N
; i++) {
84
roadLengths
[i] =
new
int
[
N
];
85
if
(!
roadLengths
[i]) {
86
cerr<<
"couldn't create road lengths"
<<endl;
87
return
;
88
}
89
}
90
91
lastLoc
=
new
int
*[
N
];
92
if
(!
lastLoc
) {
93
cerr<<
"couldn't create last lengths"
<<endl;
94
return
;
95
}
96
for
(
int
i=0; i<
N
; i++)
97
lastLoc
[i]=NULL;
98
99
for
(
int
i=0; i<
N
; i++) {
100
lastLoc
[i] =
new
int
[
N
];
101
if
(!
lastLoc
[i]) {
102
cerr<<
"couldn't create last lengths"
<<endl;
103
return
;
104
}
105
}
106
107
visited
=
new
int
[
N
];
108
if
(!
visited
) {
109
cerr<<
"couldn't create visited"
<<endl;
110
return
;
111
}
112
}
113
114
~Dijkstra
(
void
) {
115
if
(
pathLengths
)
116
for
(
int
i=0; i<
N
; i++) {
117
if
(
pathLengths
[i]) {
118
delete
[]
pathLengths
[i];
119
pathLengths
[i]=NULL;
120
}
121
}
122
if
(
pathLengths
)
123
delete
[]
pathLengths
;
124
pathLengths
=NULL;
125
126
127
if
(
roadLengths
)
128
for
(
int
i=0; i<
N
; i++) {
129
if
(
roadLengths
[i]) {
130
delete
[]
roadLengths
[i];
131
roadLengths
[i]=NULL;
132
}
133
}
134
if
(
roadLengths
)
135
delete
[]
roadLengths
;
136
roadLengths
=NULL;
137
138
if
(
lastLoc
)
139
for
(
int
i=0; i<
N
; i++) {
140
if
(
lastLoc
[i]) {
141
delete
[]
lastLoc
[i];
142
lastLoc
[i]=NULL;
143
}
144
}
145
if
(
lastLoc
)
146
delete
[]
lastLoc
;
147
lastLoc
=NULL;
148
149
if
(
visited
)
150
delete
[]
visited
;
151
visited
=NULL;
152
}
153
154
void
setVisited
(
int
*vis) {
155
for
(
int
i=0; i<
N
; i++)
156
visited
[i] = vis[i];
157
}
158
void
setPathLengths
(
int
pl,
int
i,
int
j) {
159
pathLengths
[i][j]=pl;
160
}
161
void
setRoadLengths
(
int
pl,
int
i,
int
j) {
162
roadLengths
[i][j]=pl;
163
}
164
void
setLastLoc
(
int
pl,
int
i,
int
j) {
165
lastLoc
[i][j]=pl;
166
}
167
168
void
findShortestPath
() {
169
// breadth first search
170
unsigned
int
lastLength;
171
for
(
int
j=0; j<
N
; j++)
// initialise the first path lengths
172
pathLengths
[0][j]=
roadLengths
[0][j];
173
visited
[0]=1;
174
for
(
int
i=1; i<
N
; i++) {
175
for
(
int
j=0; j<
N
; j++)
// initialise the current path lengths
176
pathLengths
[i][j]=
pathLengths
[i-1][j];
177
visited
[i]=1;
178
lastLength=
pathLengths
[i-1][i];
179
for
(
int
j=0; j<
N
; j++)
180
if
(!
visited
[j] & i!=j) {
181
if
(lastLength+
roadLengths
[i][j]<
pathLengths
[i-1][j]) {
182
pathLengths
[i][j]=lastLength+
roadLengths
[i][j];
183
lastLoc
[i][j]=i;
184
}
185
}
else
186
visited
[i] =0;
187
dumpArrays
(
roadLengths
, N);
188
}
189
}
190
};
191
#endif // DIJKSTRA_H_
Generated on Tue Jun 4 2013 11:03:27 for GTK+ IOStream by
1.8.3.1