xref: /external/srec/tools/grxmlcompile/sub_grph.cpp

/* 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;
}