| /* FILE: sub_min.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" |
| |
| #define SYMBOL_COMPARE(x,y) (arc[x]->CompareSymbol(arc[y])) |
| #define COMPARE(x,y) (arc[x]->Compare(arc[y])) |
| |
| // Minimization to facilitate moving output symbols - mainly for phoneme networks |
| // Check partial merge |
| // Move the output symbol if only one node |
| |
| /* |
| 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; |
| } |
| */ |
| |
| void SubGraph::ViewNode (int currId) |
| { |
| int rix; |
| |
| printf ("Node: %d\n", currId); |
| rix= FindFromIndex (currId); |
| if (rix < 0) |
| return; |
| while (rix < numArc && arc[forwardList[rix]]->GetFromId() == currId) { |
| arc[forwardList[rix]]->Print(); |
| rix++; |
| } |
| return; |
| } |
| |
| |
| bool SubGraph::EquivalenceTestForward (int firstId, int secondId, int *equivMap) |
| { |
| int fix, six, fnxt, snxt, tof, tos, count; |
| |
| assert (firstId != secondId); |
| fix= FindFromIndex (firstId); |
| six= FindFromIndex (secondId); |
| if (fix < 0 || six < 0) |
| return false; |
| |
| count= 0; |
| do { |
| |
| // Move to next valid transitions |
| while (fix < numArc && arc[forwardList[fix]]->GetFromId() == firstId |
| && arc[forwardList[fix]]->GetToId() == DISCARD_LABEL) |
| fix++; |
| if (fix < numArc && arc[forwardList[fix]]->GetFromId() == firstId) |
| fnxt= arc[forwardList[fix]]->GetFromId(); |
| else |
| fnxt= -1; |
| |
| while (six < numArc && arc[forwardList[six]]->GetFromId() == secondId |
| && arc[forwardList[six]]->GetToId() == DISCARD_LABEL) |
| six++; |
| if (six < numArc && arc[forwardList[six]]->GetFromId() == secondId) |
| snxt= arc[forwardList[six]]->GetFromId(); |
| else |
| snxt= -1; |
| |
| if (fnxt != firstId && snxt != secondId) |
| return true; |
| else if (fnxt != firstId || snxt != secondId) |
| return false; |
| |
| tos= arc[forwardList[six]]->GetToId(); |
| tof= arc[forwardList[fix]]->GetToId(); |
| // printf ("Debug inner %d %d, %d %d\n", tof, tos, equivMap[tof], equivMap[tos]); |
| // if (tof >= 0) bogus assert |
| // assert (tof == equivMap[tof]); |
| // if (tos >= 0) |
| // assert (tos == equivMap[tos]); |
| |
| // Test |
| if (!arc[forwardList[fix]]->HasSameLabels (arc[forwardList[six]]) |
| || tos != tof) |
| return false; |
| count++; |
| |
| fix++; |
| six++; |
| |
| } while (fnxt >= 0 && snxt >= 0); |
| |
| return false; |
| } |
| |
| void SubGraph::IdentifyEquivalence (int *depthMap, int *equivMap) |
| { |
| int ii, jj, dd, maxDepth, count, itCnt; |
| |
| maxDepth= 0; |
| for (ii= 0; ii < numVertex; ii++) { |
| if (maxDepth < depthMap[ii]) |
| maxDepth= depthMap[ii]; |
| } |
| |
| itCnt= 0; |
| do { |
| count= 0; |
| for (dd= 0; dd <= maxDepth; dd++) |
| for (ii= 0; ii < numVertex; ii++) |
| if (depthMap[ii] == dd && ii == equivMap[ii]) { |
| CheckForChangeAndResort (ii, equivMap); |
| for (jj= ii+1; jj < numVertex; jj++) |
| if (depthMap[jj] == dd && jj == equivMap[jj]) { |
| // Equivalence test |
| CheckForChangeAndResort (jj, equivMap); |
| // printf ("Try %d %d, ", ii, jj); |
| if (EquivalenceTestForward (ii, jj, equivMap)) { |
| equivMap[jj]= ii; |
| // printf ("Merged %d %d\n", ii, jj); |
| count++; |
| } |
| } |
| } |
| |
| itCnt++; |
| // printf ("Total %d mergers\n", count); |
| } while (count > 0 && itCnt < MAXITS); |
| |
| return; |
| } |
| |
| void SubGraph::CheckForChangeAndResort (int currId, int *mapList) |
| { |
| int rix, rixBegin, nextId; |
| bool needSort; |
| |
| needSort= false; |
| rixBegin= rix= FindFromIndex (currId); |
| if (rix < 0) |
| return; |
| while (rix < numArc && arc[forwardList[rix]]->GetFromId() == currId) { |
| nextId= arc[forwardList[rix]]->GetToId(); |
| if (nextId >= 0 && mapList[nextId] != nextId) { |
| needSort= true; |
| arc[forwardList[rix]]->AssignToId(mapList[nextId]); |
| } |
| rix++; |
| } |
| |
| // Resort |
| if (needSort) |
| RemoveDuplicatesAtNode (rixBegin, rix); |
| |
| return; |
| } |
| |
| void SubGraph::DeterminizeAtVertex (int baseId, DetCache *cache) |
| { |
| int fix, six, firstId, secondId, vertEnd; |
| |
| fix= FindFromIndex (baseId); |
| if (fix < 0) |
| return; |
| |
| // Remove duplicates |
| vertEnd= fix; |
| six= -1; |
| while (vertEnd < sortNum && arc[forwardList[vertEnd]]->GetFromId() == baseId) { |
| vertEnd++; |
| } |
| vertEnd++; |
| |
| // Iteration over first node |
| firstId= -1; |
| while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == baseId) { |
| |
| // Iterator for firstId |
| while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == baseId |
| && (arc[forwardList[fix]]->GetToId() == firstId |
| || arc[forwardList[fix]]->GetInput() == TERMINAL_LABEL |
| || arc[forwardList[fix]]->GetInput() == DISCARD_LABEL)) |
| fix++; |
| |
| // Terminal Condition |
| if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != baseId) |
| break; |
| else |
| firstId= arc[forwardList[fix]]->GetToId(); |
| |
| // Iteration over second node |
| six= fix; |
| secondId= firstId; |
| while (six < sortNum && arc[forwardList[six]]->GetFromId() == baseId) { |
| |
| // Iterator for secondId |
| while (six < sortNum && arc[forwardList[six]]->GetFromId() == baseId |
| && (arc[forwardList[six]]->GetToId() == secondId |
| || arc[forwardList[six]]->GetInput() == TERMINAL_LABEL |
| || arc[forwardList[six]]->GetInput() == DISCARD_LABEL)) |
| six++; |
| |
| // Terminal condition |
| if (six >= sortNum || arc[forwardList[six]]->GetFromId() != baseId) |
| break; |
| else |
| secondId= arc[forwardList[six]]->GetToId(); |
| |
| // Now we have both Ids worked out |
| assert (firstId >= 0); |
| assert (secondId >= 0); |
| assert (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL); |
| assert (arc[forwardList[six]]->GetInput() != DISCARD_LABEL); |
| |
| if (PairwiseDeterminize (baseId, firstId, fix, secondId, six, cache) > 0) { |
| SortLanguageAtSortIndices (fix, vertEnd); |
| |
| // Are we done with the first node? |
| while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == baseId |
| && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL) |
| fix++; |
| |
| // Terminal condition |
| if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != baseId |
| || arc[forwardList[fix]]->GetToId() != firstId) |
| break; |
| } |
| } |
| } |
| return; |
| } |
| |
| int SubGraph::PairwiseDeterminize (int baseId, int firstId, int fixStart, int secondId, |
| int sixStart, DetCache *cache) |
| { |
| int fix, six, fmiss, smiss, nmatch, symTst, newId; |
| bool isCached; |
| |
| fix= fixStart; |
| six= sixStart; |
| |
| assert (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL); |
| assert (arc[forwardList[six]]->GetInput() != DISCARD_LABEL); |
| |
| // Count |
| isCached= false; |
| fmiss= smiss= nmatch= 0; |
| newId= -1; |
| while (six < sortNum && fix < sortNum) { |
| |
| assert (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL); |
| assert (arc[forwardList[six]]->GetInput() != DISCARD_LABEL); |
| |
| symTst= SYMBOL_COMPARE (forwardList[fix], forwardList[six]); |
| if (symTst == 0) { |
| if (newId == -1) { |
| newId= cache->QueryEntry (firstId, secondId); |
| if (newId < 0) |
| newId= NewVertexId (); |
| else |
| isCached= true; |
| // printf ("Forming %d with %d and %d at %d\n", newId, firstId, secondId, baseId); |
| } |
| |
| // Assign second to new Vertex |
| arc[forwardList[six]]->AssignToId (newId); |
| |
| // Assign first to DISCARD Index |
| arc[forwardList[fix]]->AssignInput (DISCARD_LABEL); |
| |
| // Increment to next |
| do { |
| fix++; |
| } while (fix < sortNum && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL); |
| if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != baseId |
| || arc[forwardList[fix]]->GetToId() != firstId) |
| fix= sortNum; |
| |
| do { |
| six++; |
| } while (six < sortNum && arc[forwardList[six]]->GetInput() == DISCARD_LABEL); |
| if (six >= sortNum || arc[forwardList[six]]->GetFromId() != baseId |
| || arc[forwardList[six]]->GetToId() != secondId) |
| six= sortNum; |
| |
| nmatch++; |
| } |
| else if (symTst < 0) { |
| do { |
| fix++; |
| } while (fix < sortNum && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL); |
| if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != baseId |
| || arc[forwardList[fix]]->GetToId() != firstId) |
| fix= sortNum; |
| fmiss++; |
| } |
| else if (symTst > 0) { |
| do { |
| six++; |
| } while (six < sortNum && arc[forwardList[six]]->GetInput() == DISCARD_LABEL); |
| if (six >= sortNum || arc[forwardList[six]]->GetFromId() != baseId |
| || arc[forwardList[six]]->GetToId() != secondId) |
| six= sortNum; |
| smiss++; |
| } |
| } |
| |
| // SortLanguageAtSortIndices (fixStart, fix); |
| |
| if (newId >= 0) { |
| if (isCached == false) { |
| // numLast= numArc; |
| MergeVertices (newId, firstId, secondId); |
| cache->AddEntry (newId, firstId, secondId); |
| // UpdateVisitationCache (numLast); |
| } |
| assert (nmatch > 0); |
| } |
| |
| // Update fan-in count |
| if (nmatch > 0) { |
| // printf ("Merging %d %d to create %d\n", firstId, secondId, newId); |
| for (int ii= 0; ii < nmatch; ii++) { |
| // IncNodeProperty (newId); |
| IncVisitationCache (newId); |
| DecVisitationCache (firstId); |
| DecVisitationCache (secondId); |
| } |
| } |
| return nmatch; |
| } |
| |
| void SubGraph::MergeVertices (int newId, int firstId, int secondId) |
| { |
| int fix, six, symTst, numStart; |
| NUANArc *arcOne; |
| |
| numStart= numArc; |
| fix= FindFromIndex (firstId); |
| six= FindFromIndex (secondId); |
| if (fix < 0 || six < 0) { |
| if (fix >= 0) |
| while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == firstId) { |
| if (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL) |
| InheritArc (arc[forwardList[fix]], newId); |
| fix++; |
| } |
| else if (six >= 0) |
| while (six < sortNum && arc[forwardList[six]]->GetFromId() == secondId) { |
| if (arc[forwardList[six]]->GetInput() != DISCARD_LABEL) |
| InheritArc (arc[forwardList[six]], newId); |
| six++; |
| } |
| } |
| else { |
| while (six < sortNum && fix < sortNum) { |
| |
| symTst= SYMBOL_COMPARE (forwardList[fix], forwardList[six]); |
| |
| if (symTst == 0) { |
| if (arc[forwardList[fix]]->GetToId() == firstId |
| && arc[forwardList[six]]->GetToId() == secondId) { |
| arcOne= InheritArc (arc[forwardList[fix]], newId); |
| arcOne->AssignToId (newId); |
| } |
| else if (arc[forwardList[fix]]->GetToId() |
| == arc[forwardList[six]]->GetToId()) { |
| InheritArc (arc[forwardList[fix]], newId); |
| } |
| else { |
| InheritArc (arc[forwardList[fix]], newId); |
| InheritArc (arc[forwardList[six]], newId); |
| } |
| |
| // Increment to next |
| do { |
| fix++; |
| } while (fix < sortNum && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL); |
| if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != firstId |
| || arc[forwardList[fix]]->GetFromId() != firstId) |
| fix= sortNum; |
| |
| do { |
| six++; |
| } while (six < sortNum && arc[forwardList[six]]->GetInput() == DISCARD_LABEL); |
| if (six >= sortNum || arc[forwardList[six]]->GetFromId() != secondId) |
| six= sortNum; |
| } |
| else if (symTst < 0) { |
| InheritArc (arc[forwardList[fix]], newId); |
| do { |
| fix++; |
| } while (fix < sortNum && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL); |
| if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != firstId |
| || arc[forwardList[fix]]->GetFromId() != firstId) |
| fix= sortNum; |
| } |
| else if (symTst > 0) { |
| InheritArc (arc[forwardList[six]], newId); |
| do { |
| six++; |
| } while (six < sortNum && arc[forwardList[six]]->GetInput() == DISCARD_LABEL); |
| if (six >= sortNum || arc[forwardList[six]]->GetFromId() != secondId |
| || arc[forwardList[six]]->GetFromId() != secondId) |
| six= sortNum; |
| } |
| } |
| |
| while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == firstId) { |
| if (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL) |
| InheritArc (arc[forwardList[fix]], newId); |
| fix++; |
| } |
| |
| while (six < sortNum && arc[forwardList[six]]->GetFromId() == secondId) { |
| if (arc[forwardList[six]]->GetInput() != DISCARD_LABEL) |
| InheritArc (arc[forwardList[six]], newId); |
| six++; |
| } |
| } |
| |
| // Update the sort list |
| UpdateSortForLanguage (); |
| // RemoveDuplicatesAtNode (numStart, numArc); |
| // ViewNode (newId); |
| assert (CheckSort()); |
| |
| // printf ("Merging %d %d to create %d\n", firstId, secondId, newId); |
| |
| return; |
| } |
| |
| void SubGraph::SetupVisitationCache () |
| { |
| int ii; |
| |
| CreateNodeProperty (); |
| for (ii= 0; ii < numArc; ii++) |
| if (arc[ii]->GetInput() != DISCARD_LABEL && arc[ii]->GetToId() >= 0) |
| IncNodeProperty (arc[ii]->GetToId()); |
| return; |
| } |
| |
| void SubGraph::ClearVisitationCache () |
| { |
| DeleteNodeProperty (); |
| return; |
| } |
| |
| void SubGraph::UpdateVisitationCache (int startNo) |
| { |
| int ii; |
| |
| for (ii= startNo; ii < numArc; ii++) |
| if (arc[ii]->GetInput() != DISCARD_LABEL && arc[ii]->GetToId() >= 0) { |
| IncNodeProperty (arc[ii]->GetToId()); |
| // std::cout << " (" << arc[ii]->GetToId() << " " << QueryNodeProperty (arc[ii]->GetToId()) << ") "; |
| } |
| // std::cout << std::endl; |
| return; |
| } |
| |
| void SubGraph::DecVisitationCache (int currId) |
| { |
| int rix; |
| |
| DecNodeProperty (currId); |
| // std::cout << " [" << currId << " " << QueryNodeProperty (currId) << "] "; |
| if (QueryNodeProperty (currId) <= 0) { |
| // std::cout << " [" << currId << "] "; |
| rix= FindFromIndex (currId); |
| if (rix < 0) |
| return; |
| while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) { |
| if (arc[forwardList[rix]]->GetInput() != DISCARD_LABEL |
| && arc[forwardList[rix]]->GetToId() >= 0) { |
| if (arc[forwardList[rix]]->GetFromId() == arc[forwardList[rix]]->GetToId()) |
| DecNodeProperty (currId); |
| else if (QueryNodeProperty (arc[forwardList[rix]]->GetToId()) > 0) |
| DecVisitationCache (arc[forwardList[rix]]->GetToId()); |
| } |
| rix++; |
| } |
| } |
| return; |
| } |
| |
| void SubGraph::IncVisitationCache (int currId) |
| { |
| int rix; |
| |
| if (QueryNodeProperty (currId) <= 0) { |
| IncNodeProperty (currId); |
| // std::cout << " (" << currId << ") "; |
| rix= FindFromIndex (currId); |
| if (rix < 0) |
| return; |
| while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) { |
| if (arc[forwardList[rix]]->GetInput() != DISCARD_LABEL |
| && arc[forwardList[rix]]->GetToId() >= 0) { |
| // IncNodeProperty (arc[forwardList[rix]]->GetToId()); |
| // if (currId != arc[forwardList[rix]]->GetToId()) |
| IncVisitationCache (arc[forwardList[rix]]->GetToId()); |
| } |
| rix++; |
| } |
| } |
| else |
| IncNodeProperty (currId); |
| // std::cout << " (" << currId << " " << QueryNodeProperty (currId) << ") "; |
| return; |
| } |
| |
| int SubGraph::VisitationConsistencyCheck () |
| { |
| int ii, failCount; |
| |
| int *nodeCount= new int [numVertex]; |
| |
| UpdateVertexCount (0); |
| |
| // std::cout << "Count: "; |
| for (ii= 0; ii <numVertex; ii++) { |
| // std::cout << ii << " (" << vertexProp[ii] << ") "; |
| nodeCount[ii]= 0; |
| } |
| // std::cout << std::endl; |
| for (ii= 0; ii <numArc; ii++) |
| if (arc[ii]->GetInput() != DISCARD_LABEL && arc[ii]->GetToId() >= 0 |
| && (vertexProp[arc[ii]->GetFromId()] > 0 || arc[ii]->GetFromId() == startId)) |
| nodeCount[arc[ii]->GetToId()]++; |
| failCount= 0; |
| // std::cout << "Failure list: "; |
| for (ii= 0; ii <numVertex; ii++) |
| if (vertexProp[ii] != nodeCount[ii]) { |
| // std::cout << ii << " (" << vertexProp[ii] << " " << nodeCount[ii] << ") "; |
| failCount++; |
| } |
| // std::cout << std::endl; |
| |
| // return failCount; |
| delete [] nodeCount; |
| |
| return 0; |
| } |
