1 /* FILE: sub_grph.cpp
2 * DATE MODIFIED: 31-Aug-07
3 * DESCRIPTION: Part of the SREC graph compiler project source files.
4 *
5 * Copyright 2007, 2008 Nuance Communciations, Inc. *
6 * *
7 * Licensed under the Apache License, Version 2.0 (the 'License'); *
8 * you may not use this file except in compliance with the License. *
9 * *
10 * You may obtain a copy of the License at *
11 * http://www.apache.org/licenses/LICENSE-2.0 *
12 * *
13 * Unless required by applicable law or agreed to in writing, software *
14 * distributed under the License is distributed on an 'AS IS' BASIS, *
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
16 * See the License for the specific language governing permissions and *
17 * limitations under the License. *
18 * *
19 *---------------------------------------------------------------------------*/
20
21 #include <iostream>
22 #include <string>
23 #include <assert.h>
24 #include <cstdio>
25
26 #include "sub_grph.h"
27
28
29 static int checkEntry (int *itemList, int count, int item);
30
checkEntry(int * itemList,int count,int item)31 static int checkEntry (int *itemList, int count, int item)
32 {
33 for (int ii= 0; ii < count; ii++)
34 if (item == itemList[ii])
35 return ii;
36 return -1;
37 }
38
IsSlot(std::string label)39 bool IsSlot (std::string label)
40 {
41 int count= label.size();
42 int fPos= label.find_first_of ("___");
43 int lPos= label.find_last_of ("___") + 1;
44 // std::cout << label << " " << count << " " << fPos << " " << lPos << std::endl;
45 if (fPos >= 0 && lPos == count)
46 return true;
47 else
48 return false;
49 }
50
51
pushScope()52 void SubGraph::pushScope ()
53 {
54 opStack[popOp++]= lastScope;
55 opStack[popOp++]= startId;
56 opStack[popOp++]= endId;
57 opStack[popOp++]= lastId;
58 opStack[popOp++]= arg1;
59 opStack[popOp++]= arg2;
60 opStack[popOp++]= numArc;
61 return;
62 }
63
popScope()64 void SubGraph::popScope ()
65 {
66 prevStartId= startId;
67 prevEndId= endId;
68 arcLoc= opStack[--popOp];
69 arg2= opStack[--popOp];
70 arg1= opStack[--popOp];
71 lastId= opStack[--popOp];
72 endId= opStack[--popOp];
73 startId= opStack[--popOp];
74 lastScope= opStack[--popOp];
75 return;
76 }
77
BeginScope(int scopeType,int newArg1,int newArg2)78 void SubGraph::BeginScope (int scopeType, int newArg1, int newArg2)
79 // Begin a new scope
80 // Create nodes for item and /item but no transitions
81 {
82 pushScope();
83
84 arg1= newArg1;
85 arg2= newArg2;
86 lastScope= scopeType;
87 arcLoc= numArc;
88
89 startId= NewVertexId();
90
91 switch (scopeType) {
92 case SCOPE_ITEM:
93 case SCOPE_RULE:
94 case SCOPE_COUNT:
95 case SCOPE_REPEAT:
96 case SCOPE_OPT:
97 endId= -1;
98 lastId= startId;
99 break;
100 case SCOPE_ONEOF:
101 endId= NewVertexId();
102 lastId= endId;
103 break;
104 default:
105 printf ("Shouldn't be getting here\n");
106 }
107 return;
108 }
109
EndScope()110 void SubGraph::EndScope ()
111 // End the current scope
112 {
113 int closeId= CloseScope();
114 lastId= ConnectLastScope (startId, closeId);
115 }
116
ConnectLastScope(int beginScopeId,int endScopeId)117 int SubGraph::ConnectLastScope (int beginScopeId, int endScopeId)
118 // Connect up the child network to the parent
119 {
120 int begLabel, endLabel, begOutLabel, endOutLabel;
121
122 if (endId == -1)
123 endId= lastId;
124 if (lastScope == SCOPE_RULE) {
125 begLabel= BEGINRULE_LABEL;
126 begOutLabel= BEGINRULE_LABEL;
127 endLabel= ENDRULE_LABEL;
128 endOutLabel= arg1; // For inserting into closing brace
129 }
130 else {
131 begLabel= BEGINSCOPE_LABEL;
132 begOutLabel= BEGINRULE_LABEL;
133 endLabel= ENDSCOPE_LABEL;
134 endOutLabel= ENDSCOPE_LABEL;
135 }
136
137 popScope();
138
139 switch (lastScope) {
140 case SCOPE_ITEM:
141 case SCOPE_COUNT:
142 case SCOPE_REPEAT:
143 case SCOPE_OPT:
144 (void) CreateArc (begLabel, begOutLabel, lastId, beginScopeId);
145 lastId= NewVertexId();
146 (void) CreateArc (endLabel, endOutLabel, endScopeId, lastId);
147 break;
148 case SCOPE_ONEOF:
149 (void) CreateArc (begLabel, begOutLabel, startId, beginScopeId);
150 (void) CreateArc (endLabel, endOutLabel, endScopeId, endId);
151 break;
152 case SCOPE_RULE:
153 (void) CreateArc (begLabel, begOutLabel, lastId, beginScopeId);
154 lastId= NewVertexId();
155 (void) CreateArc (endLabel, ruleId, endScopeId, lastId);
156 break;
157 case SCOPE_ROOT:
158 (void) CreateArc (begLabel, begOutLabel, lastId, beginScopeId);
159 lastId= NewVertexId();
160 (void) CreateArc (endLabel, endOutLabel, endScopeId, lastId);
161 break;
162 default:
163 printf ("Shouldn't be getting here\n");
164 }
165 return lastId;
166 }
167
CloseScope()168 int SubGraph::CloseScope ()
169 // Closes the transitions and returns to the previous scope
170 // Special case for count and repeats
171 {
172 int ii, finalId, endLoc, blockCount;
173
174 switch (lastScope) {
175 case SCOPE_ITEM:
176 case SCOPE_RULE:
177 case SCOPE_ONEOF:
178 break;
179 case SCOPE_OPT:
180 (void) CreateArc (NONE_LABEL, NONE_LABEL, startId, lastId); // start to end
181 break;
182 case SCOPE_COUNT:
183 endLoc= numArc;
184 blockCount= numVertex - startId - 1;
185 // Special case, min-count= 0
186
187 for (ii= 1; ii < arg1; ii++)
188 CopyFastArcs (this, arcLoc, endLoc, ii * blockCount, -1, -1, -1, -1);
189 finalId= lastId + (arg2 - 1) * blockCount;
190 for ( ; ii < arg2; ii++) {
191 CopyFastArcs (this, arcLoc, endLoc, ii * blockCount, -1, -1, -1, -1);
192 (void) CreateArc (NONE_LABEL, NONE_LABEL, lastId + (ii - 1) * blockCount, finalId);
193 }
194 if (arg1 <= 0)
195 (void) CreateArc (NONE_LABEL, NONE_LABEL, startId, finalId); // start to end
196
197 UpdateVertexCount (endLoc);
198 lastId= finalId;
199 break;
200 case SCOPE_REPEAT:
201 endLoc= numArc;
202 blockCount= numVertex - startId - 1;
203 #if 1
204 for (ii= 1; ii < arg1; ii++)
205 CopyFastArcs (this, arcLoc, endLoc, ii * blockCount, -1, -1, -1, -1);
206 finalId= lastId + (arg1 - 1) * blockCount;
207
208 // loop
209 CopyFastArcs (this, arcLoc, endLoc, blockCount, startId, finalId, lastId, finalId);
210
211 // start to end
212 if (arg1 == 0)
213 (void) CreateArc (NONE_LABEL, NONE_LABEL, startId, finalId);
214 #else
215 // loop
216 CopyFastArcs (this, arcLoc, endLoc, blockCount, startId, lastId, lastId, lastId);
217 UpdateVertexCount (endLoc);
218
219 // second part
220 blockCount= numVertex - startId;
221 CopyFastArcs (this, arcLoc, endLoc, blockCount, startId, lastId, lastId, -1);
222 UpdateVertexCount (endLoc);
223
224 // once
225 finalId= lastId + blockCount;
226 blockCount= numVertex - startId;
227 if (arg1 <= 1)
228 CopyFastArcs (this, arcLoc, endLoc, blockCount, startId, startId, lastId, finalId);
229
230 // start to end
231 if (arg1 == 0)
232 (void) CreateArc (NONE_LABEL, NONE_LABEL, startId, finalId);
233 #endif
234
235 UpdateVertexCount (endLoc);
236 lastId= finalId;
237 break;
238 default:
239 printf ("Shouldn't be getting here\n");
240 }
241 return lastId;
242 }
243
AddItem(int inputLabel,int tagLabel)244 int SubGraph::AddItem (int inputLabel, int tagLabel)
245 {
246 int newId;
247
248 switch (lastScope) {
249 case SCOPE_RULE:
250 arg1= tagLabel;
251 case SCOPE_ITEM:
252 case SCOPE_OPT:
253 case SCOPE_COUNT:
254 case SCOPE_REPEAT:
255 newId= NewVertexId();
256 (void) CreateArc (inputLabel, tagLabel, lastId, newId);
257 lastId= newId;
258 break;
259 case SCOPE_ONEOF:
260 (void) CreateArc (inputLabel, tagLabel, startId, endId);
261 lastId= endId;
262 break;
263 default: ;
264 printf ("Shouldn't be getting here\n");
265 }
266 return lastId;
267 }
268
AddTag(int tagLabel)269 int SubGraph::AddTag (int tagLabel)
270 {
271 int newId;
272
273 switch (lastScope) {
274 case SCOPE_RULE:
275 case SCOPE_ITEM:
276 case SCOPE_OPT:
277 case SCOPE_COUNT:
278 case SCOPE_REPEAT:
279 newId= NewVertexId();
280 (void) CreateArc (TAG_LABEL, tagLabel, lastId, newId);
281 lastId= newId;
282 break;
283 case SCOPE_ONEOF:
284 (void) CreateArc (TAG_LABEL, tagLabel, startId, endId);
285 lastId= endId;
286 break;
287 default:
288 printf ("Shouldn't be getting here\n");
289 }
290 return lastId;
291 }
292
ExpandRules(SubGraph ** subList,int * lookupList,int numSubs)293 void SubGraph::ExpandRules (SubGraph **subList, int *lookupList, int numSubs)
294 {
295 int initialId, finalId, ruleId, pos;
296
297 for (int ii= 0; ii < numArc; ii++) {
298 ruleId= arc[ii]->GetInput();
299 if (ruleId < 0 && ruleId > NONE_LABEL) {
300 initialId= arc[ii]->GetFromId();
301 finalId= arc[ii]->GetToId();
302 ruleId= checkEntry (lookupList, numSubs, -ruleId);
303 assert (ruleId >= 0);
304 // printf ("Expanding rule (%d) %s\n", -ruleId, subList[ruleId]->title);
305
306 arc[ii]->AssignInput (DISCARD_LABEL); // Clear down the rule
307 // printf ("------------------------");
308 // subList[ruleId]->SortLanguage();
309 // subList[ruleId]->Print();
310 // printf ("------------------------////");
311 pos= numArc;
312 CopyFastArcs (subList[ruleId], 0, subList[ruleId]->numArc, numVertex,
313 subList[ruleId]->startId, initialId, subList[ruleId]->lastId, finalId);
314 UpdateVertexCount (pos);
315 }
316 }
317 UpdateVertexCount (0);
318 SortLanguage ();
319 return;
320 }
321
UpdateVertexCount(int startLoc)322 void SubGraph::UpdateVertexCount (int startLoc)
323 {
324 int vertId, maxVertId;
325
326 maxVertId= -1;
327 for (int ii= startLoc; ii < numArc; ii++) {
328 vertId= arc[ii]->GetFromId();
329 if (maxVertId < vertId)
330 maxVertId= vertId;
331 vertId= arc[ii]->GetToId();
332 if (maxVertId < vertId)
333 maxVertId= vertId;
334 }
335 maxVertId++;
336 if (startLoc <= 0) // i.e. a fresh start
337 numVertex= maxVertId;
338 else if (numVertex < maxVertId)
339 numVertex= maxVertId;
340 return;
341 }
342
AddTerminalConnections()343 void SubGraph::AddTerminalConnections ()
344 {
345 // Add terminal transition
346 (void) CreateArc (TERMINAL_LABEL, NONE_LABEL, lastId, TERMINAL_LABEL);
347 return;
348 }
349
RemoveRuleConnections()350 void SubGraph::RemoveRuleConnections ()
351 {
352 AddTerminalConnections ();
353 RemoveTagConnections (-1, -1);
354 RemoveRuleStarts (-1, -1);
355 RemoveRuleEnds (-1, -1);
356 RemoveNulls (-1, -1);
357 ClearRuleIds ();
358
359 ClearDuplicateArcs ();
360 RemoveUnvisitedArcs (startId, lastId);
361 RemoveDiscardedArcs ();
362 RenumberNodes ();
363 UpdateVertexCount (0);
364
365 SortLanguage ();
366 return;
367 }
368
RemoveRuleStarts(int startPoint,int endPoint)369 void SubGraph::RemoveRuleStarts (int startPoint, int endPoint)
370 {
371 if (startPoint == -1 && endPoint == -1) {
372 startPoint= startId;
373 endPoint= lastId;
374 }
375
376 int *nodeList= new int [numVertex];
377 int *visitList= new int [numVertex];
378 for (int ii= 0; ii < numVertex; ii++)
379 visitList[ii]= 0;
380
381 SortLanguage ();
382 ProcessBegins (startPoint, endPoint, BEGINRULE_LABEL, nodeList, 0, visitList, numVertex);
383 ClearLabelledConnections (BEGINRULE_LABEL);
384
385 delete [] nodeList;
386 delete [] visitList;
387 return;
388 }
389
RemoveRuleEnds(int startPoint,int endPoint)390 void SubGraph::RemoveRuleEnds (int startPoint, int endPoint)
391 {
392 if (startPoint == -1 && endPoint == -1) {
393 startPoint= startId;
394 endPoint= lastId;
395 }
396
397 int *nodeList= new int [numVertex];
398 int *visitList= new int [numVertex];
399 for (int ii= 0; ii < numVertex; ii++)
400 visitList[ii]= 0;
401
402 SortLanguageReverse ();
403 ProcessEnds (endPoint, startPoint, ENDRULE_LABEL, nodeList, 0, visitList, numVertex);
404 ClearLabelledConnections (ENDRULE_LABEL);
405
406 delete [] nodeList;
407 delete [] visitList;
408 return;
409 }
410
RemoveNulls(int startPoint,int endPoint)411 void SubGraph::RemoveNulls (int startPoint, int endPoint)
412 {
413 if (startPoint == -1 && endPoint == -1) {
414 startPoint= startId;
415 endPoint= lastId;
416 }
417
418 int *nodeList= new int [numVertex];
419 int *visitList= new int [numVertex];
420 for (int ii= 0; ii < numVertex; ii++)
421 visitList[ii]= 0;
422
423 SortLanguage ();
424 ProcessBegins (startPoint, endPoint, NONE_LABEL, nodeList, 0, visitList, numVertex);
425 ClearLabelledConnections (NONE_LABEL);
426
427 delete [] nodeList;
428 delete [] visitList;
429 return;
430 }
431
RemoveInternalConnections()432 void SubGraph::RemoveInternalConnections ()
433 {
434 RemoveForwardConnections (-1, -1);
435 RemoveBackwardConnections (-1, -1);
436 ClearDuplicateArcs ();
437 RemoveUnvisitedArcs (startId, lastId);
438 RemoveDiscardedArcs ();
439 RenumberNodes ();
440 UpdateVertexCount (0);
441
442 SortLanguage ();
443 return;
444 }
445
RemoveForwardConnections(int startPoint,int endPoint)446 void SubGraph::RemoveForwardConnections (int startPoint, int endPoint)
447 {
448 // Code to pull up nodes for forward connecting transitions
449
450 if (startPoint == -1 && endPoint == -1) {
451 startPoint= startId;
452 endPoint= lastId;
453 }
454
455 int *nodeList= new int [numVertex];
456 int *visitList= new int [numVertex];
457 for (int ii= 0; ii < numVertex; ii++)
458 visitList[ii]= 0;
459
460 SortLanguage ();
461 ProcessBegins (startPoint, endPoint, BEGINSCOPE_LABEL, nodeList, 0, visitList, numVertex);
462 ClearLabelledConnections (BEGINSCOPE_LABEL);
463 RemoveDiscardedArcs ();
464
465 delete [] nodeList;
466 delete [] visitList;
467 return;
468 }
469
PullUpBegins(int currId,int baseId,int finalId,int procLabel,int * nodeList,int currNum,int maxNum)470 void SubGraph::PullUpBegins (int currId, int baseId, int finalId, int procLabel,
471 int *nodeList, int currNum, int maxNum)
472 {
473 int rix;
474
475 nodeList[currNum]= currId;
476 rix= FindFromIndex (currId);
477 if (rix < 0)
478 return;
479 while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) {
480 if (arc[forwardList[rix]]->GetInput() == procLabel) {
481 PullUpBegins (arc[forwardList[rix]]->GetToId(), baseId,
482 finalId, procLabel, nodeList, currNum+1, maxNum);
483 }
484 else if (arc[forwardList[rix]]->GetInput() != DISCARD_LABEL)
485 InheritArc (arc[forwardList[rix]], baseId);
486 rix++;
487 }
488 return;
489 }
490
ProcessBegins(int currId,int finalId,int procLabel,int * nodeList,int currNum,int * visitMark,int maxNum)491 void SubGraph::ProcessBegins (int currId, int finalId, int procLabel,
492 int *nodeList, int currNum, int *visitMark, int maxNum)
493 {
494 int rix, nextId;
495
496 nodeList[currNum]= currId;
497 rix= FindFromIndex (currId);
498 if (rix < 0) {
499 visitMark[currId]= 1;
500 return;
501 }
502 while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) {
503 if (arc[forwardList[rix]]->GetInput() == procLabel) {
504 PullUpBegins (arc[forwardList[rix]]->GetToId(), currId,
505 finalId, procLabel, nodeList, currNum, maxNum);
506 }
507
508 nextId= arc[forwardList[rix]]->GetToId();
509 if (nextId >= 0 && nextId != finalId && checkEntry (nodeList, currNum, nextId) < 0
510 && visitMark[nextId] == 0)
511 ProcessBegins (nextId, finalId, procLabel, nodeList, currNum+1, visitMark, maxNum);
512 rix++;
513 }
514 visitMark[currId]= 1;
515 return;
516 }
517
RemoveBackwardConnections(int startPoint,int endPoint)518 void SubGraph::RemoveBackwardConnections (int startPoint, int endPoint)
519 {
520 // Code to push back nodes for reverse connecting transitions
521
522 if (startPoint == -1 && endPoint == -1) {
523 startPoint= startId;
524 endPoint= lastId;
525 }
526
527 int *nodeList= new int [numVertex];
528 int *visitList= new int [numVertex];
529 for (int ii= 0; ii < numVertex; ii++)
530 visitList[ii]= 0;
531
532 SortLanguageReverse ();
533 ProcessEnds (endPoint, startPoint, ENDSCOPE_LABEL, nodeList, 0, visitList, numVertex);
534 ClearLabelledConnections (ENDSCOPE_LABEL);
535 RemoveDiscardedArcs ();
536
537 delete [] nodeList;
538 delete [] visitList;
539 return;
540 }
541
PullUpEnds(int currId,int baseId,int initialId,int procLabel,int * nodeList,int currNum,int maxNum)542 void SubGraph::PullUpEnds (int currId, int baseId, int initialId, int procLabel,
543 int *nodeList, int currNum, int maxNum)
544 {
545 int rix;
546
547 nodeList[currNum]= currId;
548 rix= FindToIndex (currId);
549 if (rix < 0)
550 return;
551 while (rix < sortRevNum && arc[backwardList[rix]]->GetToId() == currId) {
552 if (arc[backwardList[rix]]->GetInput() == procLabel) {
553 PullUpEnds (arc[backwardList[rix]]->GetFromId(), baseId,
554 initialId, procLabel, nodeList, currNum+1, maxNum);
555 }
556 else if (arc[backwardList[rix]]->GetInput() != DISCARD_LABEL)
557 InheritReverseArc (arc[backwardList[rix]], baseId);
558 rix++;
559 }
560 return;
561 }
562
ProcessEnds(int currId,int initialId,int procLabel,int * nodeList,int currNum,int * visitMark,int maxNum)563 void SubGraph::ProcessEnds (int currId, int initialId, int procLabel,
564 int *nodeList, int currNum, int *visitMark, int maxNum)
565 {
566 int rix, nextId;
567
568 nodeList[currNum]= currId;
569 rix= FindToIndex (currId);
570 if (rix < 0) {
571 visitMark[currId]= 1;
572 return;
573 }
574 while (rix < sortRevNum && arc[backwardList[rix]]->GetToId() == currId) {
575 if (arc[backwardList[rix]]->GetInput() == procLabel) {
576 PullUpEnds (arc[backwardList[rix]]->GetFromId(), currId,
577 initialId, procLabel, nodeList, currNum, maxNum);
578 }
579 nextId= arc[backwardList[rix]]->GetFromId();
580 if (nextId != initialId && checkEntry (nodeList, currNum, nextId) < 0
581 && visitMark[nextId] == 0)
582 ProcessEnds (nextId, initialId, procLabel, nodeList, currNum+1, visitMark, maxNum);
583 rix++;
584 }
585 visitMark[currId]= 1;
586 return;
587 }
588
RemoveUnreachedConnections(int startPoint,int endPoint)589 void SubGraph::RemoveUnreachedConnections (int startPoint, int endPoint)
590 {
591 // Obtain nodes with real transitions
592 // Code to pull up nodes for forward connecting transitions
593 // Code to push back nodes for reverse connecting transitions
594
595 if (startPoint == -1 && endPoint == -1) {
596 startPoint= startId;
597 endPoint= lastId;
598 }
599
600 ClearDuplicateArcs ();
601 RemoveUnvisitedArcs (startPoint, endPoint);
602 RemoveDiscardedArcs ();
603 RenumberNodes ();
604 UpdateVertexCount (0);
605
606 return;
607 }
608
RemoveUnreachedConnectionsDebug(int startPoint,int endPoint)609 void SubGraph::RemoveUnreachedConnectionsDebug (int startPoint, int endPoint)
610 {
611 // Obtain nodes with real transitions
612 // Code to pull up nodes for forward connecting transitions
613 // Code to push back nodes for reverse connecting transitions
614
615 if (startPoint == -1 && endPoint == -1) {
616 startPoint= startId;
617 endPoint= lastId;
618 }
619
620 // ClearDuplicateArcs ();
621 RemoveUnvisitedArcs (startPoint, endPoint);
622 RemoveDiscardedArcs ();
623 // RenumberNodes ();
624 UpdateVertexCount (0);
625
626 return;
627 }
628
ReduceArcsByEquivalence()629 void SubGraph::ReduceArcsByEquivalence ()
630 {
631 int ii, *equivMap, *depthMap;
632
633 // Sort by Input, Output and to nodes
634 SortLanguage ();
635 SortLanguageReverse ();
636
637 // Calculate depth
638 depthMap= new int [numVertex];
639 for (ii= 0; ii < numVertex; ii++)
640 depthMap[ii]= MAXNUM;
641 if (lastId >= 0)
642 ReverseDepthData (lastId, depthMap, 1);
643 ReverseDepthOnTerminal (depthMap);
644 for (ii= 0; ii < numVertex; ii++)
645 if (depthMap[ii] == MAXNUM)
646 depthMap[ii]= -1;
647
648 // Create equivalence list
649 equivMap= new int [numVertex];
650 for (ii= 0; ii < numVertex; ii++)
651 equivMap[ii]= ii;
652
653 // Equivalence test to use equivalence list, duplicate transitions ignored
654 // Test nodes with same equivalence
655 IdentifyEquivalence (depthMap, equivMap);
656
657 // On identification of an equivalence
658 // Update equivalence entry
659 MapGraphVertices (equivMap);
660 RemoveDiscardedArcs ();
661
662 // Sort for general access
663 SortLanguage ();
664
665 delete [] depthMap;
666 delete [] equivMap;
667 return;
668 }
669
DeterminizeArcs()670 void SubGraph::DeterminizeArcs ()
671 {
672 int ii;
673 bool allDone;
674
675 SortLanguage ();
676 DetCache *cache= new DetCache;
677
678 SetupVisitationCache ();
679 assert (VisitationConsistencyCheck () == 0);
680 printf ("Determinization\n");
681 allDone= false;
682 while (!allDone) {
683 allDone= true;
684 for (ii= 0; ii < numVertex; ii++) {
685 if (QueryMinProperty(ii) == false) {
686 if (startId == ii || QueryNodeProperty(ii) > 0) {
687 DeterminizeAtVertex (ii, cache);
688 SetMinProperty (ii);
689 allDone= false;
690 //printf (" Node %d, Total %d, Arcs %d\n", ii, numVertex, numArc);
691 }
692 assert (VisitationConsistencyCheck () == 0);
693 // hmm .. this seems harmless but ..
694 // printf("assert(0) in SubGraph::DeterminizeArcs() ii=%d allDone=%d\n", ii, allDone);
695 // assert (0);
696 }
697 }
698 }
699
700 ClearVisitationCache ();
701
702 delete cache;
703 return;
704 }
705
IsDeterminized(int currId)706 int SubGraph::IsDeterminized (int currId)
707 {
708 int count, rix, lastInput;
709
710 count= 0;
711 lastInput= -1;
712 rix= FindFromIndex (currId);
713 if (rix < 0)
714 return -1;
715 while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) {
716 if (lastInput >= 0 && lastInput == arc[forwardList[rix]]->GetInput())
717 count++;
718 else
719 lastInput= arc[forwardList[rix]]->GetInput();
720 rix++;
721 }
722 return count;
723 }
724
ReverseGraphForOutput()725 void SubGraph::ReverseGraphForOutput ()
726 {
727 int ii, incId, outId;
728
729 assert (startId == 0);
730 UpdateVertexCount (0);
731 for (ii= 0; ii < numArc; ii++) {
732 incId= arc[ii]->GetFromId();
733 outId= arc[ii]->GetToId();
734 if (outId == TERMINAL_LABEL) {
735 arc[ii]->AssignFromId (0);
736 arc[ii]->AssignInput (NONE_LABEL);
737 arc[ii]->AssignOutput (NONE_LABEL);
738 arc[ii]->AssignToId (incId);
739 }
740 else {
741 arc[ii]->AssignFromId (outId);
742 if (incId == 0)
743 arc[ii]->AssignToId (numVertex);
744 else
745 arc[ii]->AssignToId (incId);
746 }
747 }
748 (void) CreateArc (TERMINAL_LABEL, NONE_LABEL, numVertex, TERMINAL_LABEL); // Add terminal transition
749 numVertex++;
750
751 return;
752 }
753
RemoveTagConnections(int startPoint,int endPoint)754 void SubGraph::RemoveTagConnections (int startPoint, int endPoint)
755 {
756 // Code to push back nodes for reverse connecting transitions
757
758 if (startPoint == -1 && endPoint == -1) {
759 startPoint= startId;
760 endPoint= lastId;
761 }
762
763 int *nodeList= new int [numVertex];
764 int *visitList= new int [numVertex];
765 for (int ii= 0; ii < numVertex; ii++)
766 visitList[ii]= 0;
767
768 SortLanguageReverse ();
769 ProcessTags (endPoint, startPoint, nodeList, 0, visitList, numVertex);
770 ClearLabelledConnections (TAG_LABEL);
771 RemoveDiscardedArcs ();
772
773 delete [] nodeList;
774 delete [] visitList;
775 return;
776 }
777
PullUpTags(int currId,int baseId,int initialId,int outTag,int * nodeList,int currNum,int maxNum)778 bool SubGraph::PullUpTags (int currId, int baseId, int initialId,
779 int outTag, int *nodeList, int currNum, int maxNum)
780 {
781 int rix;
782 bool hasCascade= false;
783
784 nodeList[currNum]= currId;
785 rix= FindToIndex (currId);
786 if (rix < 0)
787 return hasCascade;
788 while (rix < sortRevNum && arc[backwardList[rix]]->GetToId() == currId) {
789 if (arc[backwardList[rix]]->GetInput() == TAG_LABEL) {
790 if (PullUpTags (arc[backwardList[rix]]->GetFromId(), baseId, initialId,
791 arc[backwardList[rix]]->GetOutput(), nodeList, currNum+1, maxNum))
792 CreateCopyWithOutput (arc[backwardList[rix]], NONE_LABEL);
793 hasCascade= true;
794 }
795 else if (arc[backwardList[rix]]->GetInput() != DISCARD_LABEL)
796 InheritReverseArcWithTag (arc[backwardList[rix]], baseId, outTag);
797 rix++;
798 }
799 return hasCascade;
800 }
801
ProcessTags(int currId,int initialId,int * nodeList,int currNum,int * visitMark,int maxNum)802 void SubGraph::ProcessTags (int currId, int initialId, int *nodeList, int currNum,
803 int *visitMark, int maxNum)
804 {
805 int rix, nextId;
806
807 nodeList[currNum]= currId;
808 rix= FindToIndex (currId);
809 if (rix < 0) {
810 visitMark[currId]= 1;
811 return;
812 }
813 while (rix < sortRevNum && arc[backwardList[rix]]->GetToId() == currId) {
814 if (arc[backwardList[rix]]->GetInput() == TAG_LABEL) {
815 if (PullUpTags (arc[backwardList[rix]]->GetFromId(), currId, initialId,
816 arc[backwardList[rix]]->GetOutput(), nodeList, currNum, maxNum))
817 CreateCopyWithOutput (arc[backwardList[rix]], NONE_LABEL);
818 }
819 nextId= arc[backwardList[rix]]->GetFromId();
820 if (nextId != initialId && checkEntry (nodeList, currNum, nextId) < 0
821 && visitMark[nextId] == 0)
822 ProcessTags (nextId, initialId, nodeList, currNum+1, visitMark, maxNum);
823 rix++;
824 }
825 visitMark[currId]= 1;
826 return;
827 }
828