← Back to branch summary

~ubuntu-branches/ubuntu/karmic/scilab/karmic

« back to all changes in this revision

Viewing changes to routines/metanet/paths.c

  • Committer: Bazaar Package Importer
  • Author(s): Torsten Werner
  • Date: 2002-03-21 16:57:43 UTC
  • Revision ID: james.westby@ubuntu.com-20020321165743-e9mv12c1tb1plztg
Tags: upstream-2.6
Import upstream version 2.6

Show diffs side-by-side

added added

removed removed

Lines of Context:
routines/metanet/paths.c
 
1
#include <stdio.h>
 
2
#include <string.h>
 
3
 
 
4
#ifdef __STDC__
 
5
#include <stdlib.h>
 
6
#else
 
7
#include <malloc.h>
 
8
#endif
 
9
 
 
10
 
 
11
#include "../machine.h"
 
12
 
 
13
extern void cerro();
 
14
 
 
15
static char str[80];
 
16
 
 
17
/* NodesToPath converts a vector with node numbers into a path:
 
18
   NODES = [Nn,...,N2,N1] =>
 
19
   PATH = [A1,A2,...,An-1] with Ai = (Ni,Ni+1)
 
20
   n = *psize + 1 
 
21
*/
 
22
void NodesToPath(nodes,p,psize,la,lp,ls)
 
23
int *nodes,*psize,*la,*lp,*ls;
 
24
int **p;
 
25
{
 
26
  int a,i,j,n1,n2;
 
27
  for (i = 1; i <= *psize; i++) {
 
28
    n1 = nodes[*psize-i+1]; n2 = nodes[*psize-i];
 
29
    a = 0;
 
30
    for (j = lp[n1-1]; j <= lp[n1]-1; j++) {
 
31
      if (n2 == ls[j-1]) {
 
32
        a = la[j-1];
 
33
        break;
 
34
      }
 
35
    }
 
36
    if (a == 0) {
 
37
      *psize = 0;
 
38
      return;
 
39
    }
 
40
    (*p)[i-1] = a;
 
41
  }
 
42
}
 
43
 
 
44
/* prevn2p_ computes a path from node i to node j from a
 
45
   vector describing the previous nodes in path:
 
46
   node i belongs to path if pln[i] > 0 
 
47
   pln[i] is then the previous node in the sequence 
 
48
*/
 
49
void C2F(prevn2p)(i,j,m,n,la,lp,ls,direct,pln,p,psize)
 
50
int *i,*j,*m,*n,*la,*lp,*ls,*pln,*psize;
 
51
int **p;
 
52
{
 
53
  int *nodes;
 
54
  int k,nn;
 
55
  if (*i < 0 || *i > *n) {
 
56
    sprintf(str,"Bad internal node number %d",*i);
 
57
    cerro(str);
 
58
    return;
 
59
  }
 
60
  if (*j < 0 || *j > *n) {
 
61
    sprintf(str,"Bad internal node number %d",*j);
 
62
    cerro(str);
 
63
    return;
 
64
  }
 
65
  if ((nodes = (int *)malloc((*m + 1) * sizeof(int))) == NULL) {
 
66
    cerro("Running out of memory");
 
67
    return;
 
68
  }
 
69
  nn = 0;
 
70
  nodes[nn++] = *j;
 
71
  k = 0;
 
72
  /* the first time, the test must be always verified for dealing with
 
73
     circuits */
 
74
  while (k != *i) {
 
75
    if (nn == 1) k = *j;
 
76
    k = pln[k-1];
 
77
    nodes[nn++] = k;
 
78
    if (k <= 0 || k > *n || nn > *n + 1) {
 
79
      /* there is no path */
 
80
      *psize = 0;
 
81
      return;
 
82
    }
 
83
  }
 
84
  *psize = nn - 1;
 
85
  if ((*p = (int *)malloc(*psize * sizeof(int))) == NULL) {
 
86
    cerro("Running out of memory");
 
87
    return;
 
88
  }
 
89
  NodesToPath(nodes,p,psize,la,lp,ls);
 
90
  free(nodes);
 
91
}
 
92
 
 
93
/* ns2p_ converts a node set into a path:
 
94
   NODES = [N1,N2,...,Nn] =>
 
95
   PATH = [A1,A2,...,An-1] with Ai = (Ni,Ni+1)
 
96
   *psize = *nsize - 1 
 
97
*/
 
98
void C2F(ns2p)(nodes,nsize,p,psize,la,lp,ls,n)
 
99
int *nodes,*nsize,*psize,*la,*lp,*ls,*n;
 
100
int **p;
 
101
{
 
102
  int a,i,j,n1,n2;
 
103
  *psize = *nsize - 1;
 
104
  if ((*p = (int *)malloc(*psize * sizeof(int))) == NULL) {
 
105
    cerro("Running out of memory");
 
106
    return;
 
107
  }
 
108
  for (i = 1; i <= *psize; i++) {
 
109
    n1 = nodes[i-1];
 
110
    if ((i == 1) && (n1 < 0 || n1 > *n)) {
 
111
      sprintf(str,"Bad internal node number %d",n1);
 
112
      cerro(str);
 
113
      return;
 
114
    }
 
115
    n2 = nodes[i];
 
116
    if (n2 < 0 || n2 > *n) {
 
117
      sprintf(str,"Bad internal node number %d",n2);
 
118
      cerro(str);
 
119
      return;
 
120
    }
 
121
    a = 0;
 
122
    for (j = lp[n1-1]; j <= lp[n1]-1; j++) {
 
123
      if (n2 == ls[j-1]) {
 
124
        a = la[j-1];
 
125
        break;
 
126
      }
 
127
    }
 
128
    if (a == 0) {
 
129
      *psize = 0;
 
130
      return;
 
131
    }
 
132
    (*p)[i-1] = a;
 
133
  }
 
134
}
 
135
 
 
136
/* p2ns_ converts a path into a node set:
 
137
   PATH = [A1,A2,...,An] =>
 
138
   NODES = [N1,N2,...,Nn+1] => with Ai = (Ni,Ni+1)
 
139
   with *nsize = *psize + 1 
 
140
*/
 
141
void C2F(p2ns)(p,psize,nodes,nsize,la,lp,ls,direct,m,n)
 
142
int *p,*psize,*nsize,*la,*lp,*ls,*direct,*m,*n;
 
143
int **nodes;
 
144
{
 
145
  int ma,a,i,j,k,n1,n2;
 
146
  *nsize = *psize + 1;
 
147
  if ((*nodes = (int *)malloc(*nsize * sizeof(int))) == NULL) {
 
148
    cerro("Running out of memory");
 
149
    return;
 
150
  }
 
151
  if (*direct == 1) ma = *m; else ma = *m / 2;
 
152
  for (i = 1; i <= *psize; i++) {
 
153
    a = p[i-1];
 
154
    if (a < 0 || a > ma) {
 
155
      sprintf(str,"Bad internal arc number %d",a);
 
156
      cerro(str);
 
157
      return;
 
158
    }
 
159
    /* find nodes n1 and n2 of arc a */
 
160
    n1 = 0; n2 = 0;
 
161
    for (j = 1; j <= *n; j++) {
 
162
      for (k = lp[j-1]; k <= lp[j]-1; k++)
 
163
        if (la[k-1] == a) {
 
164
          n1 = j; n2 = ls[k-1];
 
165
          break;
 
166
        }
 
167
      if (n1 != 0) break;
 
168
    }
 
169
    if (n1 == 0) {
 
170
      *nsize = 0;
 
171
      return;
 
172
    }
 
173
    /* directed graph */
 
174
    if (*direct == 1) {
 
175
      if (i == 1) (*nodes)[i-1] = n1;
 
176
      if (i!= 1 && (*nodes)[i-1] != n1) {
 
177
        *nsize = 0;
 
178
        return;
 
179
      }
 
180
      (*nodes)[i] = n2;
 
181
    }
 
182
    /* undirected graph */
 
183
    else {
 
184
      if (i == 1) {
 
185
        (*nodes)[0] = n1; (*nodes)[1] = n2;
 
186
      }
 
187
      else if (i == 2) {
 
188
        if (n1 == (*nodes)[0]) {
 
189
          (*nodes)[0] = (*nodes)[1];
 
190
          (*nodes)[1] = n1;
 
191
          (*nodes)[2] = n2;
 
192
        }
 
193
        else if (n1 == (*nodes)[1]) {
 
194
          (*nodes)[2] = n2;
 
195
        }
 
196
        else if (n2 == (*nodes)[0]) {
 
197
          (*nodes)[0] = (*nodes)[1];
 
198
          (*nodes)[1] = n2;
 
199
          (*nodes)[2] = n1;
 
200
        }
 
201
        else if (n2 == (*nodes)[1]) {
 
202
          (*nodes)[2] = n1;
 
203
        }
 
204
        else {
 
205
          *nsize = 0;
 
206
          return;
 
207
        }
 
208
      }
 
209
      else {
 
210
        if (n1 == (*nodes)[i-1]) (*nodes)[i] = n2;
 
211
        else if (n2 == (*nodes)[i-1]) (*nodes)[i] = n1;
 
212
        else {
 
213
          *nsize = 0;
 
214
          return;
 
215
        }
 
216
      }
 
217
    }
 
218
  }
 
219
}
 
220
 
 
221
/* edge2st_ computes a spanning tree (root = node 1) from 
 
222
   an array alpha of connecting edge numbers */
 
223
 
 
224
void C2F(edge2st)(n,alpha,tree,treesize)
 
225
int *n,*alpha,*treesize;
 
226
int **tree;
 
227
{
 
228
  int i;
 
229
  *treesize = *n - 1;
 
230
  if ((*tree = (int *)malloc(*treesize * sizeof(int))) == NULL) {
 
231
    cerro("Running out of memory");
 
232
    return;
 
233
  }
 
234
  for (i = 1; i <= *n - 1; i++) {
 
235
    if (alpha[i] < 0) {
 
236
      *treesize=0;
 
237
      return;
 
238
    }
 
239
    (*tree)[i-1] = alpha[i];
 
240
  }
 
241
}
 
242
 
 
243
/* prevn2st_ computes a spanning tree (root = node i0) from
 
244
   a vector nodes describing the previous nodes in tree */
 
245
 
 
246
void C2F(prevn2st)(n,nodes,tree,treesize,la,lp,ls)
 
247
int *n,*nodes,*treesize,*la,*lp,*ls;
 
248
int **tree;
 
249
{
 
250
  int i,in,j,nt,indic;
 
251
  *treesize = *n - 1;
 
252
  if ((*tree = (int *)malloc(*treesize * sizeof(int))) == NULL) {
 
253
    cerro("Running out of memory");
 
254
    return;
 
255
  }
 
256
  nt = 0;
 
257
  indic=0;
 
258
  for (i = 1; i <= *n; i++) {
 
259
    in = nodes[i-1];
 
260
    if (in == 0) continue;
 
261
    /* arc (in,i) belongs to tree */
 
262
    indic=1;
 
263
    for (j = lp[in-1]; j <= lp[in]-1; j++) {
 
264
      if (ls[j-1] == i) {
 
265
        (*tree)[nt++] = la[j-1];
 
266
        break;
 
267
      }
 
268
    }
 
269
  }
 
270
  if (indic == 0) *treesize=0;
 
271
}