tools/grxmlcompile/sub_grph.cpp - platform/external/srec - Git at Google

 /* FILE:		sub_grph.cpp
  *  DATE MODIFIED:	31-Aug-07
  *  DESCRIPTION:	Part of the  SREC graph compiler project source files.
  *
  *  Copyright 2007, 2008 Nuance Communciations, Inc.                               *
  *                                                                           *
  *  Licensed under the Apache License, Version 2.0 (the 'License');          *
  *  you may not use this file except in compliance with the License.         *
  *                                                                           *
  *  You may obtain a copy of the License at                                  *
  *      http://www.apache.org/licenses/LICENSE-2.0                           *
  *                                                                           *
  *  Unless required by applicable law or agreed to in writing, software      *
  *  distributed under the License is distributed on an 'AS IS' BASIS,        *
  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
  *  See the License for the specific language governing permissions and      *
  *  limitations under the License.                                           *
  *                                                                           *
  *---------------------------------------------------------------------------*/

 #include <iostream>
 #include <string>
 #include <assert.h>
 #include <cstdio>

 #include "sub_grph.h"


 static int checkEntry (int *itemList, int count, int item);

 static int checkEntry (int *itemList, int count, int item)
 {
     for (int ii= 0; ii < count; ii++)
         if (item == itemList[ii])
             return ii;
     return -1;
 }

 bool IsSlot (std::string label)
 {
         int count= label.size();
         int fPos= label.find_first_of ("___");
         int lPos= label.find_last_of ("___") + 1;
 	// std::cout << label << " " << count << " " << fPos << " " << lPos << std::endl;
         if (fPos >= 0 && lPos == count)
             return true;
         else
             return false;
 }


 void SubGraph::pushScope ()
 {
     opStack[popOp++]= lastScope;
     opStack[popOp++]= startId;
     opStack[popOp++]= endId;
     opStack[popOp++]= lastId;
     opStack[popOp++]= arg1;
     opStack[popOp++]= arg2;
     opStack[popOp++]= numArc;
     return;
 }

 void SubGraph::popScope ()
 {
     prevStartId= startId;
     prevEndId= endId;
     arcLoc= opStack[--popOp];
     arg2= opStack[--popOp];
     arg1= opStack[--popOp];
     lastId= opStack[--popOp];
     endId= opStack[--popOp];
     startId= opStack[--popOp];
     lastScope= opStack[--popOp];
     return;
 }

 void SubGraph::BeginScope (int scopeType, int newArg1, int newArg2)
 //  Begin a new scope
 //  Create nodes for item and /item but no transitions
 {
     pushScope();

     arg1= newArg1;
     arg2= newArg2;
     lastScope= scopeType;
     arcLoc= numArc;

     startId= NewVertexId();

     switch (scopeType) {
     case SCOPE_ITEM:
     case SCOPE_RULE:
     case SCOPE_COUNT:
     case SCOPE_REPEAT:
     case SCOPE_OPT:
         endId= -1;
         lastId= startId;
         break;
     case SCOPE_ONEOF:
         endId= NewVertexId();
         lastId= endId;
         break;
     default:
         printf ("Shouldn't be getting here\n");
     }
     return;
 }

 void SubGraph::EndScope ()
 //  End the current scope
 {
     int closeId= CloseScope();
     lastId= ConnectLastScope (startId, closeId);
 }

 int SubGraph::ConnectLastScope (int beginScopeId, int endScopeId)
 //  Connect up the child network to the parent
 {
     int begLabel, endLabel, begOutLabel, endOutLabel;

     if (endId == -1)
         endId= lastId;
     if (lastScope == SCOPE_RULE) {
         begLabel= BEGINRULE_LABEL;
         begOutLabel= BEGINRULE_LABEL;
         endLabel= ENDRULE_LABEL;
         endOutLabel= arg1;  //  For inserting into closing brace
     }
     else {
         begLabel= BEGINSCOPE_LABEL;
         begOutLabel= BEGINRULE_LABEL;
         endLabel= ENDSCOPE_LABEL;
         endOutLabel= ENDSCOPE_LABEL;
     }

     popScope();

     switch (lastScope) {
     case SCOPE_ITEM:
     case SCOPE_COUNT:
     case SCOPE_REPEAT:
     case SCOPE_OPT:
         (void) CreateArc (begLabel, begOutLabel, lastId, beginScopeId);
         lastId= NewVertexId();
         (void) CreateArc (endLabel, endOutLabel, endScopeId, lastId);
         break;
     case SCOPE_ONEOF:
         (void) CreateArc (begLabel, begOutLabel, startId, beginScopeId);
         (void) CreateArc (endLabel, endOutLabel, endScopeId, endId);
         break;
     case SCOPE_RULE:
         (void) CreateArc (begLabel, begOutLabel, lastId, beginScopeId);
         lastId= NewVertexId();
         (void) CreateArc (endLabel, ruleId, endScopeId, lastId);
         break;
     case SCOPE_ROOT:
         (void) CreateArc (begLabel, begOutLabel, lastId, beginScopeId);
         lastId= NewVertexId();
         (void) CreateArc (endLabel, endOutLabel, endScopeId, lastId);
         break;
     default:
         printf ("Shouldn't be getting here\n");
     }
     return lastId;
 }

 int SubGraph::CloseScope ()
 //  Closes the transitions and returns to the previous scope
 //  Special case for count and repeats
 {
     int ii, finalId, endLoc, blockCount;

     switch (lastScope) {
     case SCOPE_ITEM:
     case SCOPE_RULE:
     case SCOPE_ONEOF:
         break;
     case SCOPE_OPT:
         (void) CreateArc (NONE_LABEL, NONE_LABEL, startId, lastId);  // start to end
         break;
     case SCOPE_COUNT:
         endLoc= numArc;
         blockCount= numVertex - startId - 1;
 	    //  Special case, min-count= 0

         for (ii= 1; ii < arg1; ii++)
             CopyFastArcs (this, arcLoc, endLoc, ii * blockCount, -1, -1, -1, -1);
         finalId= lastId + (arg2 - 1) * blockCount;
         for ( ; ii < arg2; ii++) {
             CopyFastArcs (this, arcLoc, endLoc, ii * blockCount, -1, -1, -1, -1);
             (void) CreateArc (NONE_LABEL, NONE_LABEL, lastId + (ii - 1) * blockCount, finalId);
         }
 	    if (arg1 <= 0)
 	        (void) CreateArc (NONE_LABEL, NONE_LABEL, startId, finalId);  // start to end

         UpdateVertexCount (endLoc);
         lastId= finalId;
         break;
     case SCOPE_REPEAT:
         endLoc= numArc;
         blockCount= numVertex - startId - 1;
 #if 1
         for (ii= 1; ii < arg1; ii++)
             CopyFastArcs (this, arcLoc, endLoc, ii * blockCount, -1, -1, -1, -1);
         finalId= lastId + (arg1 - 1) * blockCount;

         // loop
         CopyFastArcs (this, arcLoc, endLoc, blockCount, startId, finalId, lastId, finalId);

         // start to end
         if (arg1 == 0)
             (void) CreateArc (NONE_LABEL, NONE_LABEL, startId, finalId);
 #else
         // loop
         CopyFastArcs (this, arcLoc, endLoc, blockCount, startId, lastId, lastId, lastId);
         UpdateVertexCount (endLoc);

         // second part
         blockCount= numVertex - startId;
         CopyFastArcs (this, arcLoc, endLoc, blockCount, startId, lastId, lastId, -1);
         UpdateVertexCount (endLoc);

         // once
         finalId= lastId + blockCount;
         blockCount= numVertex - startId;
         if (arg1 <= 1)
             CopyFastArcs (this, arcLoc, endLoc, blockCount, startId, startId, lastId, finalId);

         // start to end
         if (arg1 == 0)
             (void) CreateArc (NONE_LABEL, NONE_LABEL, startId, finalId);
 #endif

         UpdateVertexCount (endLoc);
         lastId= finalId;
         break;
     default:
         printf ("Shouldn't be getting here\n");
     }
     return lastId;
 }

 int SubGraph::AddItem (int inputLabel, int tagLabel)
 {
     int newId;

     switch (lastScope) {
     case SCOPE_RULE:
         arg1= tagLabel;
     case SCOPE_ITEM:
     case SCOPE_OPT:
     case SCOPE_COUNT:
     case SCOPE_REPEAT:
         newId= NewVertexId();
         (void) CreateArc (inputLabel, tagLabel, lastId, newId);
         lastId= newId;
         break;
     case SCOPE_ONEOF:
         (void) CreateArc (inputLabel, tagLabel, startId, endId);
         lastId= endId;
         break;
     default: ;
         printf ("Shouldn't be getting here\n");
     }
     return lastId;
 }

 int SubGraph::AddTag (int tagLabel)
 {
     int newId;

     switch (lastScope) {
     case SCOPE_RULE:
     case SCOPE_ITEM:
     case SCOPE_OPT:
     case SCOPE_COUNT:
     case SCOPE_REPEAT:
         newId= NewVertexId();
         (void) CreateArc (TAG_LABEL, tagLabel, lastId, newId);
         lastId= newId;
         break;
     case SCOPE_ONEOF:
         (void) CreateArc (TAG_LABEL, tagLabel, startId, endId);
         lastId= endId;
         break;
     default:
         printf ("Shouldn't be getting here\n");
     }
     return lastId;
 }

 void SubGraph::ExpandRules (SubGraph **subList, int *lookupList, int numSubs)
 {
     int initialId, finalId, ruleId, pos;

     for (int ii= 0; ii < numArc; ii++) {
         ruleId= arc[ii]->GetInput();
         if (ruleId < 0 && ruleId > NONE_LABEL) {
             initialId= arc[ii]->GetFromId();
             finalId= arc[ii]->GetToId();
             ruleId= checkEntry (lookupList, numSubs, -ruleId);
             assert (ruleId >= 0);
 	    // printf ("Expanding rule (%d) %s\n", -ruleId, subList[ruleId]->title);

             arc[ii]->AssignInput (DISCARD_LABEL);       //  Clear down the rule
 	    // printf ("------------------------");
 	    // subList[ruleId]->SortLanguage();
 	    // subList[ruleId]->Print();
 	    // printf ("------------------------////");
 	    pos= numArc;
             CopyFastArcs (subList[ruleId], 0, subList[ruleId]->numArc, numVertex,
                         subList[ruleId]->startId, initialId, subList[ruleId]->lastId, finalId);
 	    UpdateVertexCount (pos);
         }
     }
     UpdateVertexCount (0);
     SortLanguage ();
     return;
 }

 void SubGraph::UpdateVertexCount (int startLoc)
 {
     int vertId, maxVertId;

     maxVertId= -1;
     for (int ii= startLoc; ii < numArc; ii++) {
         vertId= arc[ii]->GetFromId();
         if (maxVertId < vertId)
             maxVertId= vertId;
         vertId= arc[ii]->GetToId();
         if (maxVertId < vertId)
             maxVertId= vertId;
     }
     maxVertId++;
     if (startLoc <= 0)       //  i.e. a fresh start
         numVertex= maxVertId;
     else if (numVertex < maxVertId)
         numVertex= maxVertId;
     return;
 }

 void SubGraph::AddTerminalConnections ()
 {
     //  Add terminal transition
     (void) CreateArc (TERMINAL_LABEL, NONE_LABEL, lastId, TERMINAL_LABEL);
     return;
 }

 void SubGraph::RemoveRuleConnections ()
 {
     AddTerminalConnections ();
     RemoveTagConnections (-1, -1);
     RemoveRuleStarts (-1, -1);
     RemoveRuleEnds (-1, -1);
     RemoveNulls (-1, -1);
     ClearRuleIds ();

     ClearDuplicateArcs ();
     RemoveUnvisitedArcs (startId, lastId);
     RemoveDiscardedArcs ();
     RenumberNodes ();
     UpdateVertexCount (0);

     SortLanguage ();
     return;
 }

 void SubGraph::RemoveRuleStarts (int startPoint, int endPoint)
 {
     if (startPoint == -1 && endPoint == -1) {
         startPoint= startId;
         endPoint= lastId;
     }

     int *nodeList= new int [numVertex];
     int *visitList= new int [numVertex];
     for (int ii= 0; ii < numVertex; ii++)
         visitList[ii]= 0;

     SortLanguage ();
     ProcessBegins (startPoint, endPoint, BEGINRULE_LABEL, nodeList, 0, visitList, numVertex);
     ClearLabelledConnections (BEGINRULE_LABEL);

     delete [] nodeList;
     delete [] visitList;
     return;
 }

 void SubGraph::RemoveRuleEnds (int startPoint, int endPoint)
 {
     if (startPoint == -1 && endPoint == -1) {
         startPoint= startId;
         endPoint= lastId;
     }

     int *nodeList= new int [numVertex];
     int *visitList= new int [numVertex];
     for (int ii= 0; ii < numVertex; ii++)
         visitList[ii]= 0;

     SortLanguageReverse ();
     ProcessEnds (endPoint, startPoint, ENDRULE_LABEL, nodeList, 0, visitList, numVertex);
     ClearLabelledConnections (ENDRULE_LABEL);

     delete [] nodeList;
     delete [] visitList;
     return;
 }

 void SubGraph::RemoveNulls (int startPoint, int endPoint)
 {
     if (startPoint == -1 && endPoint == -1) {
         startPoint= startId;
         endPoint= lastId;
     }

     int *nodeList= new int [numVertex];
     int *visitList= new int [numVertex];
     for (int ii= 0; ii < numVertex; ii++)
         visitList[ii]= 0;

     SortLanguage ();
     ProcessBegins (startPoint, endPoint, NONE_LABEL, nodeList, 0, visitList, numVertex);
     ClearLabelledConnections (NONE_LABEL);

     delete [] nodeList;
     delete [] visitList;
     return;
 }

 void SubGraph::RemoveInternalConnections ()
 {
     RemoveForwardConnections (-1, -1);
     RemoveBackwardConnections (-1, -1);
     ClearDuplicateArcs ();
     RemoveUnvisitedArcs (startId, lastId);
     RemoveDiscardedArcs ();
     RenumberNodes ();
     UpdateVertexCount (0);

     SortLanguage ();
     return;
 }

 void SubGraph::RemoveForwardConnections (int startPoint, int endPoint)
 {
     //  Code to pull up nodes for forward connecting transitions

     if (startPoint == -1 && endPoint == -1) {
         startPoint= startId;
         endPoint= lastId;
     }

     int *nodeList= new int [numVertex];
     int *visitList= new int [numVertex];
     for (int ii= 0; ii < numVertex; ii++)
         visitList[ii]= 0;

     SortLanguage ();
     ProcessBegins (startPoint, endPoint, BEGINSCOPE_LABEL, nodeList, 0, visitList, numVertex);
     ClearLabelledConnections (BEGINSCOPE_LABEL);
     RemoveDiscardedArcs ();

     delete [] nodeList;
     delete [] visitList;
     return;
 }

 void SubGraph::PullUpBegins (int currId, int baseId, int finalId, int procLabel,
                              int *nodeList, int currNum, int maxNum)
 {
     int rix;

     nodeList[currNum]= currId;
     rix= FindFromIndex (currId);
     if (rix < 0)
         return;
     while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) {
         if (arc[forwardList[rix]]->GetInput() == procLabel) {
             PullUpBegins (arc[forwardList[rix]]->GetToId(), baseId,
                                 finalId, procLabel, nodeList, currNum+1, maxNum);
         }
         else if (arc[forwardList[rix]]->GetInput() != DISCARD_LABEL)
             InheritArc (arc[forwardList[rix]], baseId);
         rix++;
     }
     return;
 }

 void SubGraph::ProcessBegins (int currId, int finalId, int procLabel,
                               int *nodeList, int currNum, int *visitMark, int maxNum)
 {
     int rix, nextId;

     nodeList[currNum]= currId;
     rix= FindFromIndex (currId);
     if (rix < 0) {
 	    visitMark[currId]= 1;
         return;
     }
     while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) {
         if (arc[forwardList[rix]]->GetInput() == procLabel) {
             PullUpBegins (arc[forwardList[rix]]->GetToId(), currId,
                         finalId, procLabel, nodeList, currNum, maxNum);
         }

         nextId= arc[forwardList[rix]]->GetToId();
         if (nextId >= 0 && nextId != finalId && checkEntry (nodeList, currNum, nextId) < 0
          && visitMark[nextId] == 0)
             ProcessBegins (nextId, finalId, procLabel, nodeList, currNum+1, visitMark, maxNum);
         rix++;
     }
     visitMark[currId]= 1;
     return;
 }

 void SubGraph::RemoveBackwardConnections (int startPoint, int endPoint)
 {
     //  Code to push back nodes for reverse connecting transitions

     if (startPoint == -1 && endPoint == -1) {
         startPoint= startId;
         endPoint= lastId;
     }

     int *nodeList= new int [numVertex];
     int *visitList= new int [numVertex];
     for (int ii= 0; ii < numVertex; ii++)
         visitList[ii]= 0;

     SortLanguageReverse ();
     ProcessEnds (endPoint, startPoint, ENDSCOPE_LABEL, nodeList, 0, visitList, numVertex);
     ClearLabelledConnections (ENDSCOPE_LABEL);
     RemoveDiscardedArcs ();

     delete [] nodeList;
     delete [] visitList;
     return;
 }

 void SubGraph::PullUpEnds (int currId, int baseId, int initialId, int procLabel,
                            int *nodeList, int currNum, int maxNum)
 {
     int rix;

     nodeList[currNum]= currId;
     rix= FindToIndex (currId);
     if (rix < 0)
         return;
     while (rix < sortRevNum && arc[backwardList[rix]]->GetToId() == currId) {
         if (arc[backwardList[rix]]->GetInput() == procLabel) {
             PullUpEnds (arc[backwardList[rix]]->GetFromId(), baseId,
                                 initialId, procLabel, nodeList, currNum+1, maxNum);
         }
         else if (arc[backwardList[rix]]->GetInput() != DISCARD_LABEL)
             InheritReverseArc (arc[backwardList[rix]], baseId);
         rix++;
     }
     return;
 }

 void SubGraph::ProcessEnds (int currId, int initialId, int procLabel,
                             int *nodeList, int currNum, int *visitMark, int maxNum)
 {
     int rix, nextId;

     nodeList[currNum]= currId;
     rix= FindToIndex (currId);
     if (rix < 0) {
 	visitMark[currId]= 1;
         return;
     }
     while (rix < sortRevNum && arc[backwardList[rix]]->GetToId() == currId) {
         if (arc[backwardList[rix]]->GetInput() == procLabel) {
             PullUpEnds (arc[backwardList[rix]]->GetFromId(), currId,
                         initialId, procLabel, nodeList, currNum, maxNum);
         }
         nextId= arc[backwardList[rix]]->GetFromId();
         if (nextId != initialId && checkEntry (nodeList, currNum, nextId) < 0
          && visitMark[nextId] == 0)
             ProcessEnds (nextId, initialId, procLabel, nodeList, currNum+1, visitMark, maxNum);
         rix++;
     }
     visitMark[currId]= 1;
     return;
 }

 void SubGraph::RemoveUnreachedConnections (int startPoint, int endPoint)
 {
     //  Obtain nodes with real transitions
     //  Code to pull up nodes for forward connecting transitions
     //  Code to push back nodes for reverse connecting transitions

     if (startPoint == -1 && endPoint == -1) {
         startPoint= startId;
         endPoint= lastId;
     }

     ClearDuplicateArcs ();
     RemoveUnvisitedArcs (startPoint, endPoint);
     RemoveDiscardedArcs ();
     RenumberNodes ();
     UpdateVertexCount (0);

     return;
 }

 void SubGraph::RemoveUnreachedConnectionsDebug (int startPoint, int endPoint)
 {
     //  Obtain nodes with real transitions
     //  Code to pull up nodes for forward connecting transitions
     //  Code to push back nodes for reverse connecting transitions

     if (startPoint == -1 && endPoint == -1) {
         startPoint= startId;
         endPoint= lastId;
     }

     // ClearDuplicateArcs ();
     RemoveUnvisitedArcs (startPoint, endPoint);
     RemoveDiscardedArcs ();
     // RenumberNodes ();
     UpdateVertexCount (0);

     return;
 }

 void SubGraph::ReduceArcsByEquivalence ()
 {
     int ii, *equivMap, *depthMap;

     //  Sort by Input, Output and to nodes
     SortLanguage ();
     SortLanguageReverse ();

     //  Calculate depth
     depthMap= new int [numVertex];
     for (ii= 0; ii < numVertex; ii++)
         depthMap[ii]= MAXNUM;
     if (lastId >= 0)
         ReverseDepthData (lastId, depthMap, 1);
     ReverseDepthOnTerminal (depthMap);
     for (ii= 0; ii < numVertex; ii++)
         if (depthMap[ii] == MAXNUM)
             depthMap[ii]= -1;

     //  Create equivalence list
     equivMap= new int [numVertex];
     for (ii= 0; ii < numVertex; ii++)
         equivMap[ii]= ii;

     //  Equivalence test to use equivalence list, duplicate transitions ignored
     //  Test nodes with same equivalence
     IdentifyEquivalence (depthMap, equivMap);

     //  On identification of an equivalence
     //      Update equivalence entry
     MapGraphVertices (equivMap);
     RemoveDiscardedArcs ();

     //  Sort for general access
     SortLanguage ();

     delete [] depthMap;
     delete [] equivMap;
     return;
 }

 void SubGraph::DeterminizeArcs ()
 {
     int ii;
     bool allDone;

     SortLanguage ();
     DetCache *cache= new DetCache;

     SetupVisitationCache ();
     assert (VisitationConsistencyCheck () == 0);
     printf ("Determinization\n");
     allDone= false;
     while (!allDone) {
         allDone= true;
         for (ii= 0; ii < numVertex; ii++) {
 	    if (QueryMinProperty(ii) == false) {
                 if (startId == ii || QueryNodeProperty(ii) > 0) {
                     DeterminizeAtVertex (ii, cache);
 		    SetMinProperty (ii);
         	    allDone= false;
 	            //printf ("    Node %d, Total %d, Arcs %d\n", ii, numVertex, numArc);
 	        }
                 assert (VisitationConsistencyCheck () == 0);
 		// hmm .. this seems harmless but ..
 		// printf("assert(0) in SubGraph::DeterminizeArcs() ii=%d allDone=%d\n", ii, allDone);
 		// assert (0);
             }
         }
     }

     ClearVisitationCache ();

     delete cache;
     return;
 }

 int SubGraph::IsDeterminized (int currId)
 {
     int count, rix, lastInput;

     count= 0;
     lastInput= -1;
     rix= FindFromIndex (currId);
     if (rix < 0)
         return -1;
     while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) {
         if (lastInput >= 0 && lastInput == arc[forwardList[rix]]->GetInput())
             count++;
         else
             lastInput= arc[forwardList[rix]]->GetInput();
         rix++;
     }
     return count;
 }

 void SubGraph::ReverseGraphForOutput ()
 {
     int     ii, incId, outId;

     assert (startId == 0);
     UpdateVertexCount (0);
     for (ii= 0; ii < numArc; ii++) {
         incId= arc[ii]->GetFromId();
         outId= arc[ii]->GetToId();
         if (outId == TERMINAL_LABEL) {
             arc[ii]->AssignFromId (0);
             arc[ii]->AssignInput (NONE_LABEL);
             arc[ii]->AssignOutput (NONE_LABEL);
             arc[ii]->AssignToId (incId);
         }
         else {
             arc[ii]->AssignFromId (outId);
             if (incId == 0)
                 arc[ii]->AssignToId (numVertex);
             else
                 arc[ii]->AssignToId (incId);
         }
     }
     (void) CreateArc (TERMINAL_LABEL, NONE_LABEL, numVertex, TERMINAL_LABEL);  //  Add terminal transition
     numVertex++;

     return;
 }

 void SubGraph::RemoveTagConnections (int startPoint, int endPoint)
 {
     //  Code to push back nodes for reverse connecting transitions

     if (startPoint == -1 && endPoint == -1) {
         startPoint= startId;
         endPoint= lastId;
     }

     int *nodeList= new int [numVertex];
     int *visitList= new int [numVertex];
     for (int ii= 0; ii < numVertex; ii++)
         visitList[ii]= 0;

     SortLanguageReverse ();
     ProcessTags (endPoint, startPoint, nodeList, 0, visitList, numVertex);
     ClearLabelledConnections (TAG_LABEL);
     RemoveDiscardedArcs ();

     delete [] nodeList;
     delete [] visitList;
     return;
 }

 bool SubGraph::PullUpTags (int currId, int baseId, int initialId,
                            int outTag, int *nodeList, int currNum, int maxNum)
 {
     int rix;
     bool hasCascade= false;

     nodeList[currNum]= currId;
     rix= FindToIndex (currId);
     if (rix < 0)
         return hasCascade;
     while (rix < sortRevNum && arc[backwardList[rix]]->GetToId() == currId) {
         if (arc[backwardList[rix]]->GetInput() == TAG_LABEL) {
             if (PullUpTags (arc[backwardList[rix]]->GetFromId(), baseId, initialId,
                 arc[backwardList[rix]]->GetOutput(), nodeList, currNum+1, maxNum))
                 CreateCopyWithOutput (arc[backwardList[rix]], NONE_LABEL);
             hasCascade= true;
         }
         else if (arc[backwardList[rix]]->GetInput() != DISCARD_LABEL)
             InheritReverseArcWithTag (arc[backwardList[rix]], baseId, outTag);
         rix++;
     }
     return hasCascade;
 }

 void SubGraph::ProcessTags (int currId, int initialId, int *nodeList, int currNum,
                             int *visitMark, int maxNum)
 {
     int rix, nextId;

     nodeList[currNum]= currId;
     rix= FindToIndex (currId);
     if (rix < 0) {
 	    visitMark[currId]= 1;
         return;
     }
     while (rix < sortRevNum && arc[backwardList[rix]]->GetToId() == currId) {
         if (arc[backwardList[rix]]->GetInput() == TAG_LABEL) {
             if (PullUpTags (arc[backwardList[rix]]->GetFromId(), currId, initialId,
                 arc[backwardList[rix]]->GetOutput(), nodeList, currNum, maxNum))
                 CreateCopyWithOutput (arc[backwardList[rix]], NONE_LABEL);
         }
         nextId= arc[backwardList[rix]]->GetFromId();
         if (nextId != initialId && checkEntry (nodeList, currNum, nextId) < 0
          && visitMark[nextId] == 0)
             ProcessTags (nextId, initialId, nodeList, currNum+1, visitMark, maxNum);
         rix++;
     }
     visitMark[currId]= 1;
     return;
 }
	/* FILE: sub_grph.cpp
	* DATE MODIFIED: 31-Aug-07
	* DESCRIPTION: Part of the SREC graph compiler project source files.
	*
	* Copyright 2007, 2008 Nuance Communciations, Inc. *
	* *
	* Licensed under the Apache License, Version 2.0 (the 'License'); *
	* you may not use this file except in compliance with the License. *
	* *
	* You may obtain a copy of the License at *
	* http://www.apache.org/licenses/LICENSE-2.0 *
	* *
	* Unless required by applicable law or agreed to in writing, software *
	* distributed under the License is distributed on an 'AS IS' BASIS, *
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
	* See the License for the specific language governing permissions and *
	* limitations under the License. *
	* *
	---------------------------------------------------------------------------/

	#include <iostream>
	#include <string>
	#include <assert.h>
	#include <cstdio>

	#include "sub_grph.h"


	static int checkEntry (int *itemList, int count, int item);

	static int checkEntry (int *itemList, int count, int item)
	{
	for (int ii= 0; ii < count; ii++)
	if (item == itemList[ii])
	return ii;
	return -1;
	}

	bool IsSlot (std::string label)
	{
	int count= label.size();
	int fPos= label.find_first_of ("___");
	int lPos= label.find_last_of ("___") + 1;
	// std::cout << label << " " << count << " " << fPos << " " << lPos << std::endl;
	if (fPos >= 0 && lPos == count)
	return true;
	else
	return false;
	}


	void SubGraph::pushScope ()
	{
	opStack[popOp++]= lastScope;
	opStack[popOp++]= startId;
	opStack[popOp++]= endId;
	opStack[popOp++]= lastId;
	opStack[popOp++]= arg1;
	opStack[popOp++]= arg2;
	opStack[popOp++]= numArc;
	return;
	}

	void SubGraph::popScope ()
	{
	prevStartId= startId;
	prevEndId= endId;
	arcLoc= opStack[--popOp];
	arg2= opStack[--popOp];
	arg1= opStack[--popOp];
	lastId= opStack[--popOp];
	endId= opStack[--popOp];
	startId= opStack[--popOp];
	lastScope= opStack[--popOp];
	return;
	}

	void SubGraph::BeginScope (int scopeType, int newArg1, int newArg2)
	// Begin a new scope
	// Create nodes for item and /item but no transitions
	{
	pushScope();

	arg1= newArg1;
	arg2= newArg2;
	lastScope= scopeType;
	arcLoc= numArc;

	startId= NewVertexId();

	switch (scopeType) {
	case SCOPE_ITEM:
	case SCOPE_RULE:
	case SCOPE_COUNT:
	case SCOPE_REPEAT:
	case SCOPE_OPT:
	endId= -1;
	lastId= startId;
	break;
	case SCOPE_ONEOF:
	endId= NewVertexId();
	lastId= endId;
	break;
	default:
	printf ("Shouldn't be getting here\n");
	}
	return;
	}

	void SubGraph::EndScope ()
	// End the current scope
	{
	int closeId= CloseScope();
	lastId= ConnectLastScope (startId, closeId);
	}

	int SubGraph::ConnectLastScope (int beginScopeId, int endScopeId)
	// Connect up the child network to the parent
	{
	int begLabel, endLabel, begOutLabel, endOutLabel;

	if (endId == -1)
	endId= lastId;
	if (lastScope == SCOPE_RULE) {
	begLabel= BEGINRULE_LABEL;
	begOutLabel= BEGINRULE_LABEL;
	endLabel= ENDRULE_LABEL;
	endOutLabel= arg1; // For inserting into closing brace
	}
	else {
	begLabel= BEGINSCOPE_LABEL;
	begOutLabel= BEGINRULE_LABEL;
	endLabel= ENDSCOPE_LABEL;
	endOutLabel= ENDSCOPE_LABEL;
	}

	popScope();

	switch (lastScope) {
	case SCOPE_ITEM:
	case SCOPE_COUNT:
	case SCOPE_REPEAT:
	case SCOPE_OPT:
	(void) CreateArc (begLabel, begOutLabel, lastId, beginScopeId);
	lastId= NewVertexId();
	(void) CreateArc (endLabel, endOutLabel, endScopeId, lastId);
	break;
	case SCOPE_ONEOF:
	(void) CreateArc (begLabel, begOutLabel, startId, beginScopeId);
	(void) CreateArc (endLabel, endOutLabel, endScopeId, endId);
	break;
	case SCOPE_RULE:
	(void) CreateArc (begLabel, begOutLabel, lastId, beginScopeId);
	lastId= NewVertexId();
	(void) CreateArc (endLabel, ruleId, endScopeId, lastId);
	break;
	case SCOPE_ROOT:
	(void) CreateArc (begLabel, begOutLabel, lastId, beginScopeId);
	lastId= NewVertexId();
	(void) CreateArc (endLabel, endOutLabel, endScopeId, lastId);
	break;
	default:
	printf ("Shouldn't be getting here\n");
	}
	return lastId;
	}

	int SubGraph::CloseScope ()
	// Closes the transitions and returns to the previous scope
	// Special case for count and repeats
	{
	int ii, finalId, endLoc, blockCount;

	switch (lastScope) {
	case SCOPE_ITEM:
	case SCOPE_RULE:
	case SCOPE_ONEOF:
	break;
	case SCOPE_OPT:
	(void) CreateArc (NONE_LABEL, NONE_LABEL, startId, lastId); // start to end
	break;
	case SCOPE_COUNT:
	endLoc= numArc;
	blockCount= numVertex - startId - 1;
	// Special case, min-count= 0

	for (ii= 1; ii < arg1; ii++)
	CopyFastArcs (this, arcLoc, endLoc, ii * blockCount, -1, -1, -1, -1);
	finalId= lastId + (arg2 - 1) * blockCount;
	for ( ; ii < arg2; ii++) {
	CopyFastArcs (this, arcLoc, endLoc, ii * blockCount, -1, -1, -1, -1);
	(void) CreateArc (NONE_LABEL, NONE_LABEL, lastId + (ii - 1) * blockCount, finalId);
	}
	if (arg1 <= 0)
	(void) CreateArc (NONE_LABEL, NONE_LABEL, startId, finalId); // start to end

	UpdateVertexCount (endLoc);
	lastId= finalId;
	break;
	case SCOPE_REPEAT:
	endLoc= numArc;
	blockCount= numVertex - startId - 1;
	#if 1
	for (ii= 1; ii < arg1; ii++)
	CopyFastArcs (this, arcLoc, endLoc, ii * blockCount, -1, -1, -1, -1);
	finalId= lastId + (arg1 - 1) * blockCount;

	// loop
	CopyFastArcs (this, arcLoc, endLoc, blockCount, startId, finalId, lastId, finalId);

	// start to end
	if (arg1 == 0)
	(void) CreateArc (NONE_LABEL, NONE_LABEL, startId, finalId);
	#else
	// loop
	CopyFastArcs (this, arcLoc, endLoc, blockCount, startId, lastId, lastId, lastId);
	UpdateVertexCount (endLoc);

	// second part
	blockCount= numVertex - startId;
	CopyFastArcs (this, arcLoc, endLoc, blockCount, startId, lastId, lastId, -1);
	UpdateVertexCount (endLoc);

	// once
	finalId= lastId + blockCount;
	blockCount= numVertex - startId;
	if (arg1 <= 1)
	CopyFastArcs (this, arcLoc, endLoc, blockCount, startId, startId, lastId, finalId);

	// start to end
	if (arg1 == 0)
	(void) CreateArc (NONE_LABEL, NONE_LABEL, startId, finalId);
	#endif

	UpdateVertexCount (endLoc);
	lastId= finalId;
	break;
	default:
	printf ("Shouldn't be getting here\n");
	}
	return lastId;
	}

	int SubGraph::AddItem (int inputLabel, int tagLabel)
	{
	int newId;

	switch (lastScope) {
	case SCOPE_RULE:
	arg1= tagLabel;
	case SCOPE_ITEM:
	case SCOPE_OPT:
	case SCOPE_COUNT:
	case SCOPE_REPEAT:
	newId= NewVertexId();
	(void) CreateArc (inputLabel, tagLabel, lastId, newId);
	lastId= newId;
	break;
	case SCOPE_ONEOF:
	(void) CreateArc (inputLabel, tagLabel, startId, endId);
	lastId= endId;
	break;
	default: ;
	printf ("Shouldn't be getting here\n");
	}
	return lastId;
	}

	int SubGraph::AddTag (int tagLabel)
	{
	int newId;

	switch (lastScope) {
	case SCOPE_RULE:
	case SCOPE_ITEM:
	case SCOPE_OPT:
	case SCOPE_COUNT:
	case SCOPE_REPEAT:
	newId= NewVertexId();
	(void) CreateArc (TAG_LABEL, tagLabel, lastId, newId);
	lastId= newId;
	break;
	case SCOPE_ONEOF:
	(void) CreateArc (TAG_LABEL, tagLabel, startId, endId);
	lastId= endId;
	break;
	default:
	printf ("Shouldn't be getting here\n");
	}
	return lastId;
	}

	void SubGraph::ExpandRules (SubGraph *subList, int lookupList, int numSubs)
	{
	int initialId, finalId, ruleId, pos;

	for (int ii= 0; ii < numArc; ii++) {
	ruleId= arc[ii]->GetInput();
	if (ruleId < 0 && ruleId > NONE_LABEL) {
	initialId= arc[ii]->GetFromId();
	finalId= arc[ii]->GetToId();
	ruleId= checkEntry (lookupList, numSubs, -ruleId);
	assert (ruleId >= 0);
	// printf ("Expanding rule (%d) %s\n", -ruleId, subList[ruleId]->title);

	arc[ii]->AssignInput (DISCARD_LABEL); // Clear down the rule
	// printf ("------------------------");
	// subList[ruleId]->SortLanguage();
	// subList[ruleId]->Print();
	// printf ("------------------------////");
	pos= numArc;
	CopyFastArcs (subList[ruleId], 0, subList[ruleId]->numArc, numVertex,
	subList[ruleId]->startId, initialId, subList[ruleId]->lastId, finalId);
	UpdateVertexCount (pos);
	}
	}
	UpdateVertexCount (0);
	SortLanguage ();
	return;
	}

	void SubGraph::UpdateVertexCount (int startLoc)
	{
	int vertId, maxVertId;

	maxVertId= -1;
	for (int ii= startLoc; ii < numArc; ii++) {
	vertId= arc[ii]->GetFromId();
	if (maxVertId < vertId)
	maxVertId= vertId;
	vertId= arc[ii]->GetToId();
	if (maxVertId < vertId)
	maxVertId= vertId;
	}
	maxVertId++;
	if (startLoc <= 0) // i.e. a fresh start
	numVertex= maxVertId;
	else if (numVertex < maxVertId)
	numVertex= maxVertId;
	return;
	}

	void SubGraph::AddTerminalConnections ()
	{
	// Add terminal transition
	(void) CreateArc (TERMINAL_LABEL, NONE_LABEL, lastId, TERMINAL_LABEL);
	return;
	}

	void SubGraph::RemoveRuleConnections ()
	{
	AddTerminalConnections ();
	RemoveTagConnections (-1, -1);
	RemoveRuleStarts (-1, -1);
	RemoveRuleEnds (-1, -1);
	RemoveNulls (-1, -1);
	ClearRuleIds ();

	ClearDuplicateArcs ();
	RemoveUnvisitedArcs (startId, lastId);
	RemoveDiscardedArcs ();
	RenumberNodes ();
	UpdateVertexCount (0);

	SortLanguage ();
	return;
	}

	void SubGraph::RemoveRuleStarts (int startPoint, int endPoint)
	{
	if (startPoint == -1 && endPoint == -1) {
	startPoint= startId;
	endPoint= lastId;
	}

	int *nodeList= new int [numVertex];
	int *visitList= new int [numVertex];
	for (int ii= 0; ii < numVertex; ii++)
	visitList[ii]= 0;

	SortLanguage ();
	ProcessBegins (startPoint, endPoint, BEGINRULE_LABEL, nodeList, 0, visitList, numVertex);
	ClearLabelledConnections (BEGINRULE_LABEL);

	delete [] nodeList;
	delete [] visitList;
	return;
	}

	void SubGraph::RemoveRuleEnds (int startPoint, int endPoint)
	{
	if (startPoint == -1 && endPoint == -1) {
	startPoint= startId;
	endPoint= lastId;
	}

	int *nodeList= new int [numVertex];
	int *visitList= new int [numVertex];
	for (int ii= 0; ii < numVertex; ii++)
	visitList[ii]= 0;

	SortLanguageReverse ();
	ProcessEnds (endPoint, startPoint, ENDRULE_LABEL, nodeList, 0, visitList, numVertex);
	ClearLabelledConnections (ENDRULE_LABEL);

	delete [] nodeList;
	delete [] visitList;
	return;
	}

	void SubGraph::RemoveNulls (int startPoint, int endPoint)
	{
	if (startPoint == -1 && endPoint == -1) {
	startPoint= startId;
	endPoint= lastId;
	}

	int *nodeList= new int [numVertex];
	int *visitList= new int [numVertex];
	for (int ii= 0; ii < numVertex; ii++)
	visitList[ii]= 0;

	SortLanguage ();
	ProcessBegins (startPoint, endPoint, NONE_LABEL, nodeList, 0, visitList, numVertex);
	ClearLabelledConnections (NONE_LABEL);

	delete [] nodeList;
	delete [] visitList;
	return;
	}

	void SubGraph::RemoveInternalConnections ()
	{
	RemoveForwardConnections (-1, -1);
	RemoveBackwardConnections (-1, -1);
	ClearDuplicateArcs ();
	RemoveUnvisitedArcs (startId, lastId);
	RemoveDiscardedArcs ();
	RenumberNodes ();
	UpdateVertexCount (0);

	SortLanguage ();
	return;
	}

	void SubGraph::RemoveForwardConnections (int startPoint, int endPoint)
	{
	// Code to pull up nodes for forward connecting transitions

	if (startPoint == -1 && endPoint == -1) {
	startPoint= startId;
	endPoint= lastId;
	}

	int *nodeList= new int [numVertex];
	int *visitList= new int [numVertex];
	for (int ii= 0; ii < numVertex; ii++)
	visitList[ii]= 0;

	SortLanguage ();
	ProcessBegins (startPoint, endPoint, BEGINSCOPE_LABEL, nodeList, 0, visitList, numVertex);
	ClearLabelledConnections (BEGINSCOPE_LABEL);
	RemoveDiscardedArcs ();

	delete [] nodeList;
	delete [] visitList;
	return;
	}

	void SubGraph::PullUpBegins (int currId, int baseId, int finalId, int procLabel,
	int *nodeList, int currNum, int maxNum)
	{
	int rix;

	nodeList[currNum]= currId;
	rix= FindFromIndex (currId);
	if (rix < 0)
	return;
	while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) {
	if (arc[forwardList[rix]]->GetInput() == procLabel) {
	PullUpBegins (arc[forwardList[rix]]->GetToId(), baseId,
	finalId, procLabel, nodeList, currNum+1, maxNum);
	}
	else if (arc[forwardList[rix]]->GetInput() != DISCARD_LABEL)
	InheritArc (arc[forwardList[rix]], baseId);
	rix++;
	}
	return;
	}

	void SubGraph::ProcessBegins (int currId, int finalId, int procLabel,
	int nodeList, int currNum, int visitMark, int maxNum)
	{
	int rix, nextId;

	nodeList[currNum]= currId;
	rix= FindFromIndex (currId);
	if (rix < 0) {
	visitMark[currId]= 1;
	return;
	}
	while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) {
	if (arc[forwardList[rix]]->GetInput() == procLabel) {
	PullUpBegins (arc[forwardList[rix]]->GetToId(), currId,
	finalId, procLabel, nodeList, currNum, maxNum);
	}

	nextId= arc[forwardList[rix]]->GetToId();
	if (nextId >= 0 && nextId != finalId && checkEntry (nodeList, currNum, nextId) < 0
	&& visitMark[nextId] == 0)
	ProcessBegins (nextId, finalId, procLabel, nodeList, currNum+1, visitMark, maxNum);
	rix++;
	}
	visitMark[currId]= 1;
	return;
	}

	void SubGraph::RemoveBackwardConnections (int startPoint, int endPoint)
	{
	// Code to push back nodes for reverse connecting transitions

	if (startPoint == -1 && endPoint == -1) {
	startPoint= startId;
	endPoint= lastId;
	}

	int *nodeList= new int [numVertex];
	int *visitList= new int [numVertex];
	for (int ii= 0; ii < numVertex; ii++)
	visitList[ii]= 0;

	SortLanguageReverse ();
	ProcessEnds (endPoint, startPoint, ENDSCOPE_LABEL, nodeList, 0, visitList, numVertex);
	ClearLabelledConnections (ENDSCOPE_LABEL);
	RemoveDiscardedArcs ();

	delete [] nodeList;
	delete [] visitList;
	return;
	}

	void SubGraph::PullUpEnds (int currId, int baseId, int initialId, int procLabel,
	int *nodeList, int currNum, int maxNum)
	{
	int rix;

	nodeList[currNum]= currId;
	rix= FindToIndex (currId);
	if (rix < 0)
	return;
	while (rix < sortRevNum && arc[backwardList[rix]]->GetToId() == currId) {
	if (arc[backwardList[rix]]->GetInput() == procLabel) {
	PullUpEnds (arc[backwardList[rix]]->GetFromId(), baseId,
	initialId, procLabel, nodeList, currNum+1, maxNum);
	}
	else if (arc[backwardList[rix]]->GetInput() != DISCARD_LABEL)
	InheritReverseArc (arc[backwardList[rix]], baseId);
	rix++;
	}
	return;
	}

	void SubGraph::ProcessEnds (int currId, int initialId, int procLabel,
	int nodeList, int currNum, int visitMark, int maxNum)
	{
	int rix, nextId;

	nodeList[currNum]= currId;
	rix= FindToIndex (currId);
	if (rix < 0) {
	visitMark[currId]= 1;
	return;
	}
	while (rix < sortRevNum && arc[backwardList[rix]]->GetToId() == currId) {
	if (arc[backwardList[rix]]->GetInput() == procLabel) {
	PullUpEnds (arc[backwardList[rix]]->GetFromId(), currId,
	initialId, procLabel, nodeList, currNum, maxNum);
	}
	nextId= arc[backwardList[rix]]->GetFromId();
	if (nextId != initialId && checkEntry (nodeList, currNum, nextId) < 0
	&& visitMark[nextId] == 0)
	ProcessEnds (nextId, initialId, procLabel, nodeList, currNum+1, visitMark, maxNum);
	rix++;
	}
	visitMark[currId]= 1;
	return;
	}

	void SubGraph::RemoveUnreachedConnections (int startPoint, int endPoint)
	{
	// Obtain nodes with real transitions
	// Code to pull up nodes for forward connecting transitions
	// Code to push back nodes for reverse connecting transitions

	if (startPoint == -1 && endPoint == -1) {
	startPoint= startId;
	endPoint= lastId;
	}

	ClearDuplicateArcs ();
	RemoveUnvisitedArcs (startPoint, endPoint);
	RemoveDiscardedArcs ();
	RenumberNodes ();
	UpdateVertexCount (0);

	return;
	}

	void SubGraph::RemoveUnreachedConnectionsDebug (int startPoint, int endPoint)
	{
	// Obtain nodes with real transitions
	// Code to pull up nodes for forward connecting transitions
	// Code to push back nodes for reverse connecting transitions

	if (startPoint == -1 && endPoint == -1) {
	startPoint= startId;
	endPoint= lastId;
	}

	// ClearDuplicateArcs ();
	RemoveUnvisitedArcs (startPoint, endPoint);
	RemoveDiscardedArcs ();
	// RenumberNodes ();
	UpdateVertexCount (0);

	return;
	}

	void SubGraph::ReduceArcsByEquivalence ()
	{
	int ii, equivMap, depthMap;

	// Sort by Input, Output and to nodes
	SortLanguage ();
	SortLanguageReverse ();

	// Calculate depth
	depthMap= new int [numVertex];
	for (ii= 0; ii < numVertex; ii++)
	depthMap[ii]= MAXNUM;
	if (lastId >= 0)
	ReverseDepthData (lastId, depthMap, 1);
	ReverseDepthOnTerminal (depthMap);
	for (ii= 0; ii < numVertex; ii++)
	if (depthMap[ii] == MAXNUM)
	depthMap[ii]= -1;

	// Create equivalence list
	equivMap= new int [numVertex];
	for (ii= 0; ii < numVertex; ii++)
	equivMap[ii]= ii;

	// Equivalence test to use equivalence list, duplicate transitions ignored
	// Test nodes with same equivalence
	IdentifyEquivalence (depthMap, equivMap);

	// On identification of an equivalence
	// Update equivalence entry
	MapGraphVertices (equivMap);
	RemoveDiscardedArcs ();

	// Sort for general access
	SortLanguage ();

	delete [] depthMap;
	delete [] equivMap;
	return;
	}

	void SubGraph::DeterminizeArcs ()
	{
	int ii;
	bool allDone;

	SortLanguage ();
	DetCache *cache= new DetCache;

	SetupVisitationCache ();
	assert (VisitationConsistencyCheck () == 0);
	printf ("Determinization\n");
	allDone= false;
	while (!allDone) {
	allDone= true;
	for (ii= 0; ii < numVertex; ii++) {
	if (QueryMinProperty(ii) == false) {
	if (startId == ii \|\| QueryNodeProperty(ii) > 0) {
	DeterminizeAtVertex (ii, cache);
	SetMinProperty (ii);
	allDone= false;
	//printf (" Node %d, Total %d, Arcs %d\n", ii, numVertex, numArc);
	}
	assert (VisitationConsistencyCheck () == 0);
	// hmm .. this seems harmless but ..
	// printf("assert(0) in SubGraph::DeterminizeArcs() ii=%d allDone=%d\n", ii, allDone);
	// assert (0);
	}
	}
	}

	ClearVisitationCache ();

	delete cache;
	return;
	}

	int SubGraph::IsDeterminized (int currId)
	{
	int count, rix, lastInput;

	count= 0;
	lastInput= -1;
	rix= FindFromIndex (currId);
	if (rix < 0)
	return -1;
	while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) {
	if (lastInput >= 0 && lastInput == arc[forwardList[rix]]->GetInput())
	count++;
	else
	lastInput= arc[forwardList[rix]]->GetInput();
	rix++;
	}
	return count;
	}

	void SubGraph::ReverseGraphForOutput ()
	{
	int ii, incId, outId;

	assert (startId == 0);
	UpdateVertexCount (0);
	for (ii= 0; ii < numArc; ii++) {
	incId= arc[ii]->GetFromId();
	outId= arc[ii]->GetToId();
	if (outId == TERMINAL_LABEL) {
	arc[ii]->AssignFromId (0);
	arc[ii]->AssignInput (NONE_LABEL);
	arc[ii]->AssignOutput (NONE_LABEL);
	arc[ii]->AssignToId (incId);
	}
	else {
	arc[ii]->AssignFromId (outId);
	if (incId == 0)
	arc[ii]->AssignToId (numVertex);
	else
	arc[ii]->AssignToId (incId);
	}
	}
	(void) CreateArc (TERMINAL_LABEL, NONE_LABEL, numVertex, TERMINAL_LABEL); // Add terminal transition
	numVertex++;

	return;
	}

	void SubGraph::RemoveTagConnections (int startPoint, int endPoint)
	{
	// Code to push back nodes for reverse connecting transitions

	if (startPoint == -1 && endPoint == -1) {
	startPoint= startId;
	endPoint= lastId;
	}

	int *nodeList= new int [numVertex];
	int *visitList= new int [numVertex];
	for (int ii= 0; ii < numVertex; ii++)
	visitList[ii]= 0;

	SortLanguageReverse ();
	ProcessTags (endPoint, startPoint, nodeList, 0, visitList, numVertex);
	ClearLabelledConnections (TAG_LABEL);
	RemoveDiscardedArcs ();

	delete [] nodeList;
	delete [] visitList;
	return;
	}

	bool SubGraph::PullUpTags (int currId, int baseId, int initialId,
	int outTag, int *nodeList, int currNum, int maxNum)
	{
	int rix;
	bool hasCascade= false;

	nodeList[currNum]= currId;
	rix= FindToIndex (currId);
	if (rix < 0)
	return hasCascade;
	while (rix < sortRevNum && arc[backwardList[rix]]->GetToId() == currId) {
	if (arc[backwardList[rix]]->GetInput() == TAG_LABEL) {
	if (PullUpTags (arc[backwardList[rix]]->GetFromId(), baseId, initialId,
	arc[backwardList[rix]]->GetOutput(), nodeList, currNum+1, maxNum))
	CreateCopyWithOutput (arc[backwardList[rix]], NONE_LABEL);
	hasCascade= true;
	}
	else if (arc[backwardList[rix]]->GetInput() != DISCARD_LABEL)
	InheritReverseArcWithTag (arc[backwardList[rix]], baseId, outTag);
	rix++;
	}
	return hasCascade;
	}

	void SubGraph::ProcessTags (int currId, int initialId, int *nodeList, int currNum,
	int *visitMark, int maxNum)
	{
	int rix, nextId;

	nodeList[currNum]= currId;
	rix= FindToIndex (currId);
	if (rix < 0) {
	visitMark[currId]= 1;
	return;
	}
	while (rix < sortRevNum && arc[backwardList[rix]]->GetToId() == currId) {
	if (arc[backwardList[rix]]->GetInput() == TAG_LABEL) {
	if (PullUpTags (arc[backwardList[rix]]->GetFromId(), currId, initialId,
	arc[backwardList[rix]]->GetOutput(), nodeList, currNum, maxNum))
	CreateCopyWithOutput (arc[backwardList[rix]], NONE_LABEL);
	}
	nextId= arc[backwardList[rix]]->GetFromId();
	if (nextId != initialId && checkEntry (nodeList, currNum, nextId) < 0
	&& visitMark[nextId] == 0)
	ProcessTags (nextId, initialId, nodeList, currNum+1, visitMark, maxNum);
	rix++;
	}
	visitMark[currId]= 1;
	return;
	}