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