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