← Back to branch summary

~ubuntu-branches/ubuntu/utopic/tcm/utopic

« back to all changes in this revision

Viewing changes to src/dg/graph.c

  • Committer: Bazaar Package Importer
  • Author(s): Otavio Salvador
  • Date: 2003-07-03 20:08:21 UTC
  • Revision ID: james.westby@ubuntu.com-20030703200821-se4xtqx25e5miczi
Tags: upstream-2.20
Import upstream version 2.20

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/dg/graph.c
 
1
////////////////////////////////////////////////////////////////////////////////
 
2
//
 
3
// This file is part of Toolkit for Conceptual Modeling (TCM).
 
4
// (c) copyright 1995, Vrije Universiteit Amsterdam.
 
5
// Author: Frank Dehne (frank@cs.vu.nl).
 
6
//
 
7
// TCM is free software; you can redistribute it and/or modify
 
8
// it under the terms of the GNU General Public License as published by
 
9
// the Free Software Foundation; either version 2 of the License, or
 
10
// (at your option) any later version.
 
11
//
 
12
// TCM is distributed in the hope that it will be useful,
 
13
// but WITHOUT ANY WARRANTY; without even the implied warranty of
 
14
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
15
// GNU General Public License for more details.
 
16
//
 
17
// You should have received a copy of the GNU General Public License
 
18
// along with TCM; if not, write to the Free Software
 
19
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 
20
// 02111-1307, USA.
 
21
////////////////////////////////////////////////////////////////////////////////
 
22
#include "graph.h"
 
23
#include "node.h"
 
24
#include "edge.h"
 
25
#include "util.h"
 
26
#include "outputfile.h"
 
27
 
 
28
Graph::Graph() {
 
29
        nodes = new List<Node *>;
 
30
        edges = new List<Edge *>;
 
31
        nodeTypes = new int[static_cast<int>(MAX_TYPES)];
 
32
        edgeTypes = new int[static_cast<int>(MAX_TYPES)];
 
33
        int m = MAX_TYPES;
 
34
        for (int i=0;i<m;i++)
 
35
                for (int j=0;j<m;j++)
 
36
                        for (int k=0;k<m;k++)
 
37
                                connections [i][j][k]= False;
 
38
        counter = 1;
 
39
        indexPrefix = "";
 
40
}
 
41
 
 
42
Graph::~Graph() {
 
43
        nodes->clear();
 
44
        edges->clear();
 
45
        delete nodes;
 
46
        delete edges;
 
47
        delete[] nodeTypes;
 
48
        delete[] edgeTypes;
 
49
}
 
50
 
 
51
void Graph::AddNode(Node *node) {
 
52
        if (!HasNode(node)) nodes->add(node);}
 
53
 
 
54
void Graph::AddEdge(Edge *edge) {
 
55
        if (!HasEdge(edge)) edges->add(edge);}
 
56
 
 
57
bool Graph::CheckConnection(int subjecttype1, int subjecttype2, int edgetype) {
 
58
        return connections
 
59
                [Code::GetIndex(subjecttype1, nodeTypes)]
 
60
                [Code::GetIndex(subjecttype2, nodeTypes)]
 
61
                [Code::GetIndex(edgetype, edgeTypes)];
 
62
}
 
63
 
 
64
bool Graph::IsConnected(Subject *s1, Subject *s2) {
 
65
        return IsConnected(s1, s2, -1);
 
66
}
 
67
 
 
68
bool Graph::IsConnected(Subject *s1, Subject *s2, int t) {
 
69
        for (edges->first(); !edges->done(); edges->next()) {
 
70
                Edge *edge = edges->cur();
 
71
                if (!check(edge))
 
72
                        return False;
 
73
                if (edge->GetClassType()==t || t==-1) {
 
74
                        if (edge->IsDirected()) {
 
75
                                if (edge->GetSubject1()==s1 && 
 
76
                                    edge->GetSubject2()==s2)
 
77
                                        return True;
 
78
                        }
 
79
                        else
 
80
                                if (edge->PartOf(s1)&&edge->PartOf(s2))
 
81
                                        return True;
 
82
                }
 
83
        }
 
84
        return False;
 
85
}
 
86
 
 
87
bool Graph::IsConnected(Subject *s1, Subject *s2, const string *s) {
 
88
        return IsConnected(s1, s2, s, -1);
 
89
}
 
90
 
 
91
bool Graph::IsConnected(Subject *s1, Subject *s2, 
 
92
                const string *s, int t) {
 
93
        for (edges->first(); !edges->done(); edges->next()) {
 
94
                Edge *edge = edges->cur();
 
95
                if (!check(edge))
 
96
                        return False;
 
97
                if (*edge->GetName()==*s && 
 
98
                                (edge->GetClassType()==t || t==-1)) {
 
99
                        if (edge->IsDirected()) {
 
100
                                if (edge->GetSubject1()==s1 && 
 
101
                                    edge->GetSubject2()==s2)
 
102
                                        return True;
 
103
                        }
 
104
                        else
 
105
                                if (edge->PartOf(s1) && edge->PartOf(s2))
 
106
                                        return True;
 
107
                }
 
108
        }
 
109
        return False;
 
110
}
 
111
 
 
112
int Graph::GetConnected(List<Subject *> *l, Subject *s) {
 
113
        int c = l->count();
 
114
        for (edges->first(); !edges->done(); edges->next()) {
 
115
                Edge *edge = edges->cur();
 
116
                if (!check(edge))
 
117
                        break;
 
118
                Subject *n1 = edge->GetSubject1();
 
119
                Subject *n2 = edge->GetSubject2();
 
120
                if (edge->IsDirected()) {
 
121
                        if (n1==s && l->find(n2) == -1)
 
122
                        l->add(n2);
 
123
                }
 
124
                else {
 
125
                        if (n1==s && l->find(n2) == -1)
 
126
                                l->add(n2);
 
127
                        else if (n2==s && l->find(n1) == -1)
 
128
                                l->add(n1);
 
129
                }
 
130
        }
 
131
        return l->count()-c;
 
132
}
 
133
 
 
134
int Graph::CompleteSubjects(List<Subject *> *l) {
 
135
        int c = l->count();
 
136
        for (l->last(); !l->done(); l->prev()) {
 
137
                Subject *s = l->cur();
 
138
                if (check(s))
 
139
                        CompleteSubject(l, s);
 
140
        }
 
141
        return l->count()-c;
 
142
}
 
143
 
 
144
int Graph::CompleteSubject(List<Subject *> *l, Subject *s) {
 
145
        int c = l->count();
 
146
        List<Edge *> newEdges;
 
147
        for (edges->first(); !edges->done(); edges->next()) {
 
148
                Edge *edge = edges->cur();
 
149
                if (!check(edge))
 
150
                        break;
 
151
                if (edge->PartOf(s))
 
152
                        if (l->find(edge) == -1) {
 
153
                                newEdges.add(edge);
 
154
                                l->add(edge);
 
155
                        }
 
156
        }
 
157
        // complete newly added edges.
 
158
        for (newEdges.first(); !newEdges.done(); newEdges.next())
 
159
                CompleteSubject(l, newEdges.cur());
 
160
        return l->count()-c;
 
161
}
 
162
 
 
163
int Graph::CompleteSubject(List<Subject *> *l, Subject *s1, Subject *s2) {
 
164
        int c = l->count();
 
165
        for (edges->first(); !edges->done(); edges->next()) {
 
166
                Edge *edge = edges->cur();
 
167
                if (!check(edge))
 
168
                        break;
 
169
                if (edge->PartOf(s1) && edge->PartOf(s2))
 
170
                        if (l->find(edge) == -1)
 
171
                                l->add(edge);
 
172
        }
 
173
        return l->count()-c;
 
174
}
 
175
 
 
176
int Graph::CompleteEdges(List<Subject *> *l) {
 
177
        int c = l->count();
 
178
        List<Subject *> newEdges;
 
179
        for (l->last(); !l->done(); l->prev()) {
 
180
                Subject *subj;
 
181
                Subject *s = l->cur();
 
182
                if (check(s)) {
 
183
                        if (s->IsEdge()) {
 
184
                                subj = ((Edge *)s)->GetSubject1();
 
185
                                if (l->find(subj) == -1) {
 
186
                                        if (subj->IsEdge()) 
 
187
                                                newEdges.add(subj);     
 
188
                                        else
 
189
                                                l->add(subj);
 
190
                                }
 
191
                                subj = ((Edge *)s)->GetSubject2();
 
192
                                if (l->find(subj) == -1) {
 
193
                                        if (subj->IsEdge()) 
 
194
                                                newEdges.add(subj);     
 
195
                                        else
 
196
                                                l->add(subj);
 
197
                                }
 
198
                        }
 
199
                }
 
200
        }
 
201
        if (newEdges.count() > 0) {
 
202
                CompleteEdges(&newEdges);
 
203
                for (newEdges.first(); !newEdges.done(); newEdges.next())
 
204
                        if (l->find(newEdges.cur()) == -1)
 
205
                                l->add(newEdges.cur());
 
206
        }
 
207
        return l->count()-c;
 
208
}
 
209
 
 
210
int Graph::GetNodes(List<Subject *> *l) {
 
211
        int c = l->count();
 
212
        for (nodes->first(); !nodes->done(); nodes->next()) {
 
213
                if (check(nodes->cur() && !nodes->cur()->IsEdge()))
 
214
                        l->add(nodes->cur());
 
215
        }
 
216
        return l->count()-c;
 
217
}
 
218
 
 
219
int Graph::GetNodes(List<Subject *> *l, int t) {
 
220
        int c = l->count();
 
221
        for (nodes->first(); !nodes->done(); nodes->next()) {
 
222
                Subject *s = nodes->cur();
 
223
                if (check(s && !s->IsEdge())) {
 
224
                        if (s->GetClassType() == t)
 
225
                                l->add(s);
 
226
                }
 
227
        }
 
228
        return l->count()-c;
 
229
}
 
230
 
 
231
int Graph::GetNodes(List<Subject *> *l, const string *n) {
 
232
        int c = l->count();
 
233
        for (nodes->first(); !nodes->done(); nodes->next()) {
 
234
                Subject *s = nodes->cur();
 
235
                if (check(s && !s->IsEdge())) {
 
236
                        if (*s->GetName() == *n)
 
237
                                l->add(s);
 
238
                }
 
239
        }
 
240
        return l->count()-c;
 
241
}
 
242
 
 
243
int Graph::GetNodes(List<Subject *> *l, const string *n, int t) {
 
244
        int c = l->count();
 
245
        for (nodes->first(); !nodes->done(); nodes->next()) {
 
246
                Subject *s = nodes->cur();
 
247
                if (check(s && !s->IsEdge())) {
 
248
                        if (s->GetClassType() == t && *s->GetName() == *n)
 
249
                                l->add(s);
 
250
                }
 
251
        }
 
252
        return l->count()-c;
 
253
}
 
254
 
 
255
 
 
256
int Graph::GetEdges(List<Subject *> *l) {
 
257
        int c = l->count();
 
258
        for (edges->first(); !edges->done(); edges->next()) {
 
259
                Edge *e = edges->cur();
 
260
                if (check(e)) 
 
261
                        l->add(e);
 
262
        }
 
263
        return l->count()-c;
 
264
}
 
265
 
 
266
int Graph::GetEdges(List<Subject *> *l, int t) {
 
267
        int c = l->count();
 
268
        for (edges->first(); !edges->done(); edges->next()) {
 
269
                Edge *e = edges->cur();
 
270
                if (check(e)) {
 
271
                        if (e->GetClassType() == t)
 
272
                                l->add(e);
 
273
                }
 
274
        }
 
275
        return l->count()-c;
 
276
}
 
277
 
 
278
int Graph::GetEdges(List<Subject *> *l, const string *n) {
 
279
        int c = l->count();
 
280
        for (edges->first(); !edges->done(); edges->next()) {
 
281
                Edge *e = edges->cur();
 
282
                if (check(e)) {
 
283
                        if (*e->GetName() == *n)
 
284
                                l->add(e);
 
285
                }
 
286
        }
 
287
        return l->count()-c;
 
288
}
 
289
 
 
290
int Graph::GetEdges(List<Subject *> *l, const string *n, int t) {
 
291
        int c = l->count();
 
292
        for (edges->first(); !edges->done(); edges->next()) {
 
293
                Edge *e = edges->cur();
 
294
                if (check(e)) {
 
295
                        if (e->GetClassType() == t && *e->GetName() == *n)
 
296
                                l->add(e);
 
297
                }
 
298
        }
 
299
        return l->count()-c;
 
300
}
 
301
 
 
302
 
 
303
int Graph::GetEdgesFrom(List<Subject *> *l, Subject *s) {
 
304
        int c = l->count();
 
305
        for (edges->first(); !edges->done(); edges->next()) {
 
306
                Edge *e = edges->cur();
 
307
                if (check(e)) {
 
308
                        if (e->IsDirected() && e->GetSubject1() == s)
 
309
                                l->add(e);
 
310
                        else if (!e->IsDirected() && (e->PartOf(s)))
 
311
                                l->add(e);
 
312
                }
 
313
        }
 
314
        return l->count()-c;
 
315
}
 
316
 
 
317
int Graph::GetEdgesFrom(List<Subject *> *l, Subject *s, int t) {
 
318
        int c = l->count();
 
319
        for (edges->first(); !edges->done(); edges->next()) {
 
320
                Edge *e = edges->cur();
 
321
                if (check(e)) {
 
322
                        if (e->GetClassType() == t) {
 
323
                                if (e->IsDirected() && e->GetSubject1() == s)
 
324
                                        l->add(e);
 
325
                                else if (!e->IsDirected() && (e->PartOf(s)))
 
326
                                        l->add(e);
 
327
                        }
 
328
                }
 
329
        }
 
330
        return l->count()-c;
 
331
}
 
332
 
 
333
int Graph::GetEdgesFrom(List<Subject *> *l, Subject *s, const string *n) {
 
334
        int c = l->count();
 
335
        for (edges->first(); !edges->done(); edges->next()) {
 
336
                Edge *e = edges->cur();
 
337
                if (check(e)) {
 
338
                        if (*e->GetName() == *n) {
 
339
                                if (e->IsDirected() && e->GetSubject1() == s)
 
340
                                        l->add(e);
 
341
                                else if (!e->IsDirected() && (e->PartOf(s)))
 
342
                                        l->add(e);
 
343
                        }
 
344
                }
 
345
        }
 
346
        return l->count()-c;
 
347
}
 
348
 
 
349
int Graph::GetEdgesFrom(List<Subject *> *l, Subject *s, const string *n, int t) {
 
350
        int c = l->count();
 
351
        for (edges->first(); !edges->done(); edges->next()) {
 
352
                Edge *e = edges->cur();
 
353
                if (check(e)) {
 
354
                        if (e->GetClassType() == t && *e->GetName() == *n) {
 
355
                                if (e->IsDirected() && e->GetSubject1() == s)
 
356
                                        l->add(e);
 
357
                                else if (!e->IsDirected() && (e->PartOf(s)))
 
358
                                        l->add(e);
 
359
                        }
 
360
                }
 
361
        }
 
362
        return l->count()-c;
 
363
}
 
364
 
 
365
int Graph::GetEdgesTo(List<Subject *> *l, Subject *s) {
 
366
        int c = l->count();
 
367
        for (edges->first(); !edges->done(); edges->next()) {
 
368
                Edge *e = edges->cur();
 
369
                if (check(e)) {
 
370
                        if (e->IsDirected() && e->GetSubject2() == s)
 
371
                                l->add(e);
 
372
                        else if (!e->IsDirected() && (e->PartOf(s)))
 
373
                                l->add(e);
 
374
                }
 
375
        }
 
376
        return l->count()-c;
 
377
}
 
378
 
 
379
int Graph::GetEdgesTo(List<Subject *> *l, Subject *s, int t) {
 
380
        int c = l->count();
 
381
        for (edges->first(); !edges->done(); edges->next()) {
 
382
                Edge *e = edges->cur();
 
383
                if (check(e)) {
 
384
                        if (e->GetClassType() == t) {
 
385
                                if (e->IsDirected() && e->GetSubject2() == s)
 
386
                                        l->add(e);
 
387
                                else if (!e->IsDirected() && (e->PartOf(s)))
 
388
                                        l->add(e);
 
389
                        }
 
390
                }
 
391
        }
 
392
        return l->count()-c;
 
393
}
 
394
 
 
395
int Graph::GetEdgesTo(List<Subject *> *l, Subject *s, const string *n) {
 
396
        int c = l->count();
 
397
        for (edges->first(); !edges->done(); edges->next()) {
 
398
                Edge *e = edges->cur();
 
399
                if (check(e)) {
 
400
                        if (*e->GetName() == *n) {
 
401
                                if (e->IsDirected() && e->GetSubject2() == s)
 
402
                                        l->add(e);
 
403
                                else if (!e->IsDirected() && (e->PartOf(s)))
 
404
                                        l->add(e);
 
405
                        }
 
406
                }
 
407
        }
 
408
        return l->count()-c;
 
409
}
 
410
 
 
411
int Graph::GetEdgesTo(List<Subject *> *l, Subject *s, const string *n, int t) {
 
412
        int c = l->count();
 
413
        for (edges->first(); !edges->done(); edges->next()) {
 
414
                Edge *e = edges->cur();
 
415
                if (check(e)) {
 
416
                        if (e->GetClassType() == t && *e->GetName() == *n) {
 
417
                                if (e->IsDirected() && e->GetSubject2() == s)
 
418
                                        l->add(e);
 
419
                                else if (!e->IsDirected() && (e->PartOf(s)))
 
420
                                        l->add(e);
 
421
                        }
 
422
                }
 
423
        }
 
424
        return l->count()-c;
 
425
}
 
426
 
 
427
int Graph::GetEdges(List<Subject *> *l, Subject *s1, Subject *s2) {
 
428
        int c = l->count();
 
429
        for (edges->first(); !edges->done(); edges->next()) {
 
430
                Edge *e = edges->cur();
 
431
                if (check(e)) {
 
432
                        if (e->GetSubject1() == s1 && e->GetSubject2() == s2)
 
433
                                l->add(e);
 
434
                        else if (!e->IsDirected() && s1 != s2 && 
 
435
                                        e->GetSubject1() == s2 &&
 
436
                                        e->GetSubject2() == s1)
 
437
                                l->add(e);
 
438
                }
 
439
        }
 
440
        return l->count()-c;
 
441
}
 
442
 
 
443
int Graph::GetEdges(List<Subject *> *l, Subject *s1, Subject *s2, int t) {
 
444
        int c = l->count();
 
445
        for (edges->first(); !edges->done(); edges->next()) {
 
446
                Edge *e = edges->cur();
 
447
                if (check(e)) {
 
448
                        if (e->GetClassType()==t) {
 
449
                                if (e->GetSubject1() == s1 && 
 
450
                                    e->GetSubject2() == s2)
 
451
                                        l->add(e);
 
452
                                else if (!e->IsDirected() && s1 != s2 && 
 
453
                                    e->GetSubject1() == s2 && 
 
454
                                    e->GetSubject2() == s1)
 
455
                                        l->add(e);
 
456
                        }
 
457
                }
 
458
        }
 
459
        return l->count()-c;
 
460
}
 
461
 
 
462
int Graph::GetEdges(List<Subject *> *l, Subject *s1, Subject *s2, const string *n) {
 
463
        int c = l->count();
 
464
        for (edges->first(); !edges->done(); edges->next()) {
 
465
                Edge *e = edges->cur();
 
466
                if (check(e)) {
 
467
                        if (*e->GetName()==*n) {
 
468
                                if (e->GetSubject1() == s1 && 
 
469
                                    e->GetSubject2() == s2)
 
470
                                        l->add(e);
 
471
                                else if (!e->IsDirected() && s1 != s2 && 
 
472
                                    e->GetSubject1() == s2 && 
 
473
                                    e->GetSubject2() == s1)
 
474
                                        l->add(e);
 
475
                        }
 
476
                }
 
477
        }
 
478
        return l->count()-c;
 
479
}
 
480
 
 
481
int Graph::GetEdges(List<Subject *> *l, Subject *s1, Subject *s2, const string *n, int t) {
 
482
        int c = l->count();
 
483
        for (edges->first(); !edges->done(); edges->next()) {
 
484
                Edge *e = edges->cur();
 
485
                if (check(e)) {
 
486
                        if (*e->GetName()==*n && e->GetClassType() == t) {
 
487
                                if (e->GetSubject1() == s1 && 
 
488
                                    e->GetSubject2() == s2)
 
489
                                        l->add(e);
 
490
                                else if (!e->IsDirected() && s1 != s2 && 
 
491
                                    e->GetSubject1() == s2 && 
 
492
                                    e->GetSubject2() == s1)
 
493
                                        l->add(e);
 
494
                        }
 
495
                }
 
496
        }
 
497
        return l->count()-c;
 
498
}
 
499
 
 
500
int Graph::CountNodes() {
 
501
        return nodes->count();
 
502
}
 
503
 
 
504
int Graph::CountNodes(int t) {
 
505
        List<Subject *> s;
 
506
        return GetNodes(&s, t);
 
507
}
 
508
 
 
509
int Graph::CountNodes(const string *n) {
 
510
        List<Subject *> s;
 
511
        return GetNodes(&s, n);
 
512
}
 
513
 
 
514
int Graph::CountNodes(const string *n, int t) {
 
515
        List<Subject *> s;
 
516
        return GetNodes(&s, n, t);
 
517
}
 
518
 
 
519
int Graph::CountEdges() {
 
520
        return edges->count();
 
521
}
 
522
 
 
523
int Graph::CountEdges(int t) {
 
524
        List<Subject *> e;
 
525
        return GetEdges(&e, t);
 
526
}
 
527
 
 
528
int Graph::CountEdges(const string *n) {
 
529
        List<Subject *> e;
 
530
        return GetEdges(&e, n);
 
531
}
 
532
 
 
533
int Graph::CountEdges(const string *n, int t) {
 
534
        List<Subject *> e;
 
535
        return GetEdges(&e, n, t);
 
536
}
 
537
 
 
538
int Graph::CountEdgesFrom(Subject *s) {
 
539
        List<Subject *> e;
 
540
        return GetEdgesFrom(&e, s);
 
541
}
 
542
 
 
543
int Graph::CountEdgesFrom(Subject *s, const string *n) {
 
544
        List<Subject *> e;
 
545
        return GetEdgesFrom(&e, s, n);
 
546
}
 
547
 
 
548
int Graph::CountEdgesFrom(Subject *s, int t) {
 
549
        List<Subject *> e;
 
550
        return GetEdgesFrom(&e, s, t);
 
551
}
 
552
 
 
553
int Graph::CountEdgesFrom(Subject *s, const string *n, int t) {
 
554
        List<Subject *> e;
 
555
        return GetEdgesFrom(&e, s, n, t);
 
556
}
 
557
 
 
558
int Graph::CountEdgesTo(Subject *s) {
 
559
        List<Subject *> e;
 
560
        return GetEdgesTo(&e, s);
 
561
}
 
562
 
 
563
int Graph::CountEdgesTo(Subject *s, const string *n) {
 
564
        List<Subject *> e;
 
565
        return GetEdgesTo(&e, s, n);
 
566
}
 
567
 
 
568
int Graph::CountEdgesTo(Subject *s, int t) {
 
569
        List<Subject *> e;
 
570
        return GetEdgesTo(&e, s, t);
 
571
}
 
572
 
 
573
int Graph::CountEdgesTo(Subject *s, const string *n, int t) {
 
574
        List<Subject *> e;
 
575
        return GetEdgesTo(&e, s, n, t);
 
576
}
 
577
 
 
578
int Graph::CountEdges(Subject *s1, Subject *s2) {
 
579
        List<Subject *> e;
 
580
        return GetEdges(&e, s1, s2);
 
581
}
 
582
 
 
583
int Graph::CountEdges(Subject *s1, Subject *s2, const string *n) {
 
584
        List<Subject *> e;
 
585
        return GetEdges(&e, s1, s2, n);
 
586
}
 
587
 
 
588
int Graph::CountEdges(Subject *s1, Subject *s2, int t) {
 
589
        List<Subject *> e;
 
590
        return GetEdges(&e, s1, s2, t);
 
591
}
 
592
 
 
593
int Graph::CountEdges(Subject *s1, Subject *s2, const string *n, int t) {
 
594
        List<Subject *> e;
 
595
        return GetEdges(&e, s1, s2, n, t);
 
596
}
 
597
 
 
598
// PathExists members are implemented by David Jansen
 
599
// <dnjansen@cs.utwente.nl> on 28 September 2000.
 
600
bool Graph::PathExists(Subject *s1, Subject *s2) {
 
601
        return PathExists(s1, s2, 0, True);
 
602
}
 
603
 
 
604
bool Graph::PathExists(Subject *s1, Subject *s2, int t) {
 
605
        return PathExists(s1, s2, t, True);
 
606
}
 
607
 
 
608
bool Graph::UndirectedPathExists(Subject *s1, Subject *s2) {
 
609
        return PathExists(s1, s2, 0, False);
 
610
}
 
611
 
 
612
bool Graph::PathExists(Subject *s1, Subject *s2,                        
 
613
                       int edgetype, bool Directed) {             
 
614
        // The procedure looks for a path from s1 to s2, composed of  
 
615
        // edges of the given type (edgetype, Directed).             
 
616
        // It doesn't account for composed edges.                  
 
617
        List<Subject *> edgelist;                                
 
618
        if ( edgetype )                                   
 
619
                GetEdges(&edgelist, edgetype);            
 
620
        else                                               
 
621
                GetEdges(&edgelist);                      
 
622
 
 
623
        List<Subject *> visitsubj;                                   
 
624
        visitsubj.add(s1);                                            
 
625
        bool done;                                                    
 
626
        do {                                                        
 
627
                done = True;                                        
 
628
                for ( edgelist.first() ; ! edgelist.done() ; ) {        
 
629
                        Edge *edge = dynamic_cast<Edge *>(edgelist.cur());
 
630
                        if ( ! check(edge) )                        
 
631
                                // shouldn't happen.                
 
632
                                return False;                      
 
633
                        Subject *n1 = edge->GetSubject1();           
 
634
                        Subject *n2 = edge->GetSubject2();          
 
635
                        bool subj1 = True; 
 
636
                        if ( ! visitsubj.contains(n1) ) {
 
637
                                if ( Directed && edge->IsDirected()
 
638
                                  || ! visitsubj.contains(n2) ) {
 
639
                                        edgelist.next();
 
640
                                        continue;
 
641
                                }
 
642
                                subj1 = False;
 
643
                                Subject *tmp = n1;
 
644
                                n1 = n2;
 
645
                                n2 = tmp;
 
646
                        }
 
647
                        if ( n2 == s2 )                      
 
648
                                return True;                    
 
649
                        if ( ! subj1 || ! visitsubj.contains(n2) ) {
 
650
                                done = False;                 
 
651
                                visitsubj.add(n2);              
 
652
                        }                                       
 
653
                        edgelist.removecur();              
 
654
                }
 
655
        } while ( ! done );                                
 
656
        return False;                                   
 
657
}
 
658
 
 
659
 
 
660
/*
 
661
old and slow implementation.
 
662
bool Graph::PathExists(Subject *s1, Subject *s2,
 
663
                       int edgetype, bool Directed) {
 
664
        for (edges->first(); !edges->done(); edges->next()) {
 
665
                Edge *edge = edges->cur();
 
666
                if (edgetype > 0 && edge->GetClassType()!=edgetype)
 
667
                        continue;
 
668
                if (!check(edge))
 
669
                        return False;
 
670
                Subject *n1 = edge->GetSubject1();
 
671
                Subject *n2 = edge->GetSubject2();
 
672
                bool step = False;
 
673
                // directed: only n1 -> n2.
 
674
                if (n1 == s1 && edge->IsDirected()) {
 
675
                        step = True;
 
676
                }
 
677
                // undirected: both n1 -> n2 and n1 <- n2 allowed.
 
678
                else if ((!edge->IsDirected() || !Directed) &&
 
679
                           (n1 == s1 || n2 == s1)) {
 
680
                        step = True;
 
681
                        if (s1 == n2) {
 
682
                                Subject *tmp = n1;
 
683
                                n1 = n2;
 
684
                                n2 = tmp;
 
685
                        }
 
686
                }
 
687
                if (step) {
 
688
                        if (n2 == s2) {
 
689
                                path->add(edge);
 
690
                                return True;
 
691
                        }
 
692
                        else if (path->find(edge) == -1) {
 
693
                                path->add(edge);
 
694
                                if (PathExists(n2, s2, path, edgetype, Directed))
 
695
                                        return True;
 
696
                                path->remove(edge);
 
697
                                if (!edges->setcur(edge))
 
698
                                        error("%s %d: internal graph error\n", 
 
699
                                                __FILE__, __LINE__);
 
700
                        }
 
701
                        step = False;
 
702
                }
 
703
        }
 
704
        return False;
 
705
}
 
706
*/
 
707
 
 
708
void Graph::WriteSubjects(OutputFile *f) {
 
709
        (*f) << "# GRAPH NODES\n\n";
 
710
        for (nodes->first(); !nodes->done(); nodes->next()) {
 
711
                if (check(nodes->cur()))
 
712
                        nodes->cur()->Write(f);
 
713
        }
 
714
        (*f) << "# GRAPH EDGES\n\n";
 
715
        for (edges->first(); !edges->done(); edges->next()) {
 
716
                if (check(edges->cur()))
 
717
                        edges->cur()->Write(f);
 
718
        }
 
719
}
 
720
 
 
721
int Graph::CountIndex(const string *index, List<Subject *> *l) {
 
722
        int count = 0;
 
723
        for (l->first(); !l->done(); l->next()) {
 
724
                if (!l->cur()->IsEdge()) {
 
725
                        Node *node = (Node *)l->cur();
 
726
                        if (*node->GetIndex() == *index) {
 
727
                                count++;
 
728
                        }
 
729
                }
 
730
        }
 
731
        return count;
 
732
}
 
733
 
 
734
void Graph::GetIndex(string *s) {
 
735
        *s = *GetIndexPrefix();
 
736
        if (*s != "")
 
737
                *s += ".";
 
738
        if (GetCounter() > 0)
 
739
                *s += GetCounter();
 
740
}
 
741
 
 
742
void Graph::GetNextIndex(string *index) {
 
743
        GetIndex(index);
 
744
        // make index one higher, until a unique index is found.
 
745
        if (GetCounter() > 0) {
 
746
                SetCounter(0);
 
747
                List<Subject *> l;
 
748
                GetNodes(&l);
 
749
                do {
 
750
                        SetCounter(GetCounter()+1);
 
751
                        GetIndex(index);
 
752
                } while (CountIndex(index, &l) != 0);
 
753
        }
 
754
}
 
755
 
 
756
int Graph::CountIndexes(const string *index) {
 
757
        List<Subject *> l;
 
758
        GetNodes(&l);
 
759
        return CountIndex(index, &l);
 
760
}
 
761