00001
00002
00003
00004
00005
00006
00007 #define GRAPHPREPROCESS_C
00008
00009 #include "graph_boyer.h"
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 int gp_CreateDFSTree (graphP theGraph)
00023 {
00024 stackP theStack = theGraph->theStack;
00025 int DFI = 0,
00026 I,
00027 uparent,
00028 u,
00029 e,
00030 J;
00031 if (theGraph == NULL)
00032 return NOTOK;
00033 if (theGraph->internalFlags & FLAGS_DFSNUMBERED)
00034 return OK;
00035
00036
00037
00038
00039
00040
00041 sp_ClearStack (theStack);
00042 for (I = 0; I < theGraph->N; I++)
00043 theGraph->G[I].visited = 0;
00044
00045
00046
00047 for (I = 0; I < theGraph->N && DFI < theGraph->N; I++)
00048
00049 {
00050 if (theGraph->V[I].DFSParent != NIL)
00051 continue;
00052 sp_Push2 (theStack, NIL, NIL);
00053 while (sp_NonEmpty (theStack))
00054
00055 {
00056 sp_Pop2 (theStack, uparent, e);
00057 u = uparent == NIL ? I : theGraph->G[e].v;
00058 if (!theGraph->G[u].visited)
00059
00060 {
00061 theGraph->G[u].visited = 1;
00062 theGraph->G[u].v = DFI++;
00063 theGraph->V[u].DFSParent = uparent;
00064 if (e != NIL)
00065
00066 {
00067 theGraph->G[e].type = EDGE_DFSCHILD;
00068
00069
00070
00071
00072
00073 theGraph->G[theGraph->G[e].link[0]].link[1] = theGraph->G[e].link[1];
00074 theGraph->G[theGraph->G[e].link[1]].link[0] = theGraph->G[e].link[0];
00075
00076
00077 theGraph->G[e].link[0] = theGraph->G[uparent].link[0];
00078 theGraph->G[e].link[1] = uparent;
00079
00080
00081 theGraph->G[uparent].link[0] = e;
00082 theGraph->G[theGraph->G[e].link[0]].link[1] = e;
00083 }
00084
00085
00086 J = theGraph->G[u].link[0];
00087 while (J >= theGraph->N)
00088
00089 {
00090 sp_Push2 (theStack, u, J);
00091 J = theGraph->G[J].link[0];
00092 }
00093 }
00094
00095 else
00096
00097 {
00098
00099
00100
00101
00102
00103
00104
00105
00106 if (theGraph->G[uparent].v < theGraph->G[u].v)
00107
00108 {
00109 theGraph->G[e].type = EDGE_FORWARD;
00110
00111
00112
00113
00114
00115
00116
00117
00118 theGraph->G[theGraph->G[e].link[0]].link[1] = theGraph->G[e].link[1];
00119 theGraph->G[theGraph->G[e].link[1]].link[0] = theGraph->G[e].link[0];
00120
00121
00122 theGraph->G[e].link[0] = uparent;
00123 theGraph->G[e].link[1] = theGraph->G[uparent].link[1];
00124
00125
00126 theGraph->G[uparent].link[1] = e;
00127 theGraph->G[theGraph->G[e].link[1]].link[0] = e;
00128 }
00129
00130 else if (theGraph->G[gp_GetTwinArc (theGraph, e)].type == EDGE_DFSCHILD)
00131 theGraph->G[e].type = EDGE_DFSPARENT;
00132
00133 else
00134 theGraph->G[e].type = EDGE_BACK;
00135 }
00136 }
00137 }
00138 theGraph->internalFlags |= FLAGS_DFSNUMBERED;
00139 return OK;
00140 }
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155 int gp_SortVertices (graphP theGraph)
00156 {
00157 int I,
00158 N,
00159 M,
00160 e,
00161 J,
00162 srcPos,
00163 dstPos;
00164 vertexRec tempV;
00165 graphNode tempG;
00166 if (theGraph == NULL)
00167 return NOTOK;
00168 if (!(theGraph->internalFlags & FLAGS_DFSNUMBERED))
00169 if (gp_CreateDFSTree (theGraph) != OK)
00170 return NOTOK;
00171
00172
00173 N = theGraph->N;
00174 M = theGraph->M;
00175
00176
00177
00178
00179 for (e = 0, J = 2 * N; e < M; e++, J += 2)
00180
00181 {
00182 theGraph->G[J].v = theGraph->G[theGraph->G[J].v].v;
00183 if (theGraph->G[J].link[0] < N)
00184 theGraph->G[J].link[0] = theGraph->G[theGraph->G[J].link[0]].v;
00185 if (theGraph->G[J].link[1] < N)
00186 theGraph->G[J].link[1] = theGraph->G[theGraph->G[J].link[1]].v;
00187 theGraph->G[J + 1].v = theGraph->G[theGraph->G[J + 1].v].v;
00188 if (theGraph->G[J + 1].link[0] < N)
00189 theGraph->G[J + 1].link[0] = theGraph->G[theGraph->G[J + 1].link[0]].v;
00190 if (theGraph->G[J + 1].link[1] < N)
00191 theGraph->G[J + 1].link[1] = theGraph->G[theGraph->G[J + 1].link[1]].v;
00192 }
00193
00194
00195 for (I = 0; I < N; I++)
00196 if (theGraph->V[I].DFSParent != NIL)
00197 theGraph->V[I].DFSParent = theGraph->G[theGraph->V[I].DFSParent].v;
00198
00199
00200
00201
00202
00203
00204
00205
00206 for (I = 0; I < N; I++)
00207 theGraph->G[I].visited = 0;
00208
00209
00210
00211
00212
00213
00214 for (I = 0; I < N; I++)
00215
00216 {
00217 srcPos = I;
00218 while (!theGraph->G[I].visited)
00219
00220 {
00221 dstPos = theGraph->G[I].v;
00222 tempG = theGraph->G[dstPos];
00223 tempV = theGraph->V[dstPos];
00224 theGraph->G[dstPos] = theGraph->G[I];
00225 theGraph->V[dstPos] = theGraph->V[I];
00226 theGraph->G[I] = tempG;
00227 theGraph->V[I] = tempV;
00228 theGraph->G[dstPos].visited = 1;
00229 theGraph->G[dstPos].v = srcPos;
00230 srcPos = dstPos;
00231 }
00232 }
00233
00234
00235 if (theGraph->internalFlags & FLAGS_SORTEDBYDFI)
00236 theGraph->internalFlags &= ~FLAGS_SORTEDBYDFI;
00237
00238 else
00239 theGraph->internalFlags |= FLAGS_SORTEDBYDFI;
00240 return OK;
00241 }
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253
00254
00255
00256
00257
00258
00259
00260
00261
00262
00263
00264
00265
00266 void gp_LowpointAndLeastAncestor (graphP theGraph)
00267 {
00268 stackP theStack = theGraph->theStack;
00269 int I,
00270 u,
00271 uneighbor,
00272 J,
00273 L,
00274 leastAncestor;
00275 sp_ClearStack (theStack);
00276 for (I = 0; I < theGraph->N; I++)
00277 theGraph->G[I].visited = 0;
00278
00279
00280
00281 for (I = 0; I < theGraph->N; I++)
00282
00283 {
00284 if (theGraph->G[I].visited)
00285 continue;
00286 sp_Push (theStack, I);
00287 while (sp_NonEmpty (theStack))
00288
00289 {
00290 sp_Pop (theStack, u);
00291 if (!theGraph->G[u].visited)
00292
00293 {
00294
00295
00296 theGraph->G[u].visited = 1;
00297 sp_Push (theStack, u);
00298
00299
00300 J = theGraph->G[u].link[0];
00301 while (J >= theGraph->N)
00302
00303 {
00304 if (theGraph->G[J].type == EDGE_DFSCHILD)
00305 sp_Push (theStack, theGraph->G[J].v);
00306
00307 else
00308 break;
00309 J = theGraph->G[J].link[0];
00310 }
00311 }
00312
00313 else
00314
00315 {
00316
00317
00318 L = leastAncestor = u;
00319
00320
00321 J = theGraph->G[u].link[0];
00322 while (J >= theGraph->N)
00323
00324 {
00325 uneighbor = theGraph->G[J].v;
00326 if (theGraph->G[J].type == EDGE_DFSCHILD)
00327
00328 {
00329 if (L > theGraph->V[uneighbor].Lowpoint)
00330 L = theGraph->V[uneighbor].Lowpoint;
00331 }
00332
00333 else if (theGraph->G[J].type == EDGE_BACK)
00334
00335 {
00336 if (leastAncestor > uneighbor)
00337 leastAncestor = uneighbor;
00338 }
00339
00340 else if (theGraph->G[J].type == EDGE_FORWARD)
00341 break;
00342 J = theGraph->G[J].link[0];
00343 }
00344
00345
00346 theGraph->V[u].leastAncestor = leastAncestor;
00347 theGraph->V[u].Lowpoint = leastAncestor < L ? leastAncestor : L;
00348 }
00349 }
00350 }
00351 }