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
29static int checkEntry (int *itemList, int count, int item);
30
31static 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
39bool 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
52void 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
64void 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
78void 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
110void SubGraph::EndScope ()
111//  End the current scope
112{
113    int closeId= CloseScope();
114    lastId= ConnectLastScope (startId, closeId);
115}
116
117int 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
168int 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
244int 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
269int 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
293void 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
322void 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
343void SubGraph::AddTerminalConnections ()
344{
345    //  Add terminal transition
346    (void) CreateArc (TERMINAL_LABEL, NONE_LABEL, lastId, TERMINAL_LABEL);
347    return;
348}
349
350void 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
369void 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
390void 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
411void 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
432void 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
446void 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
470void 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
491void 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
518void 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
542void 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
563void 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
589void 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
609void 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
629void 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
670void 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
706int 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
725void 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
754void 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
778bool 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
802void 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