1 /* FILE: sub_min.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 #define SYMBOL_COMPARE(x,y) (arc[x]->CompareSymbol(arc[y]))
29 #define COMPARE(x,y) (arc[x]->Compare(arc[y]))
30
31 // Minimization to facilitate moving output symbols - mainly for phoneme networks
32 // Check partial merge
33 // Move the output symbol if only one node
34
35 /*
36 static int checkEntry (int *itemList, int count, int item);
37
38 static int checkEntry (int *itemList, int count, int item)
39 {
40 for (int ii= 0; ii < count; ii++)
41 if (item == itemList[ii])
42 return ii;
43 return -1;
44 }
45 */
46
ViewNode(int currId)47 void SubGraph::ViewNode (int currId)
48 {
49 int rix;
50
51 printf ("Node: %d\n", currId);
52 rix= FindFromIndex (currId);
53 if (rix < 0)
54 return;
55 while (rix < numArc && arc[forwardList[rix]]->GetFromId() == currId) {
56 arc[forwardList[rix]]->Print();
57 rix++;
58 }
59 return;
60 }
61
62
EquivalenceTestForward(int firstId,int secondId,int * equivMap)63 bool SubGraph::EquivalenceTestForward (int firstId, int secondId, int *equivMap)
64 {
65 int fix, six, fnxt, snxt, tof, tos, count;
66
67 assert (firstId != secondId);
68 fix= FindFromIndex (firstId);
69 six= FindFromIndex (secondId);
70 if (fix < 0 || six < 0)
71 return false;
72
73 count= 0;
74 do {
75
76 // Move to next valid transitions
77 while (fix < numArc && arc[forwardList[fix]]->GetFromId() == firstId
78 && arc[forwardList[fix]]->GetToId() == DISCARD_LABEL)
79 fix++;
80 if (fix < numArc && arc[forwardList[fix]]->GetFromId() == firstId)
81 fnxt= arc[forwardList[fix]]->GetFromId();
82 else
83 fnxt= -1;
84
85 while (six < numArc && arc[forwardList[six]]->GetFromId() == secondId
86 && arc[forwardList[six]]->GetToId() == DISCARD_LABEL)
87 six++;
88 if (six < numArc && arc[forwardList[six]]->GetFromId() == secondId)
89 snxt= arc[forwardList[six]]->GetFromId();
90 else
91 snxt= -1;
92
93 if (fnxt != firstId && snxt != secondId)
94 return true;
95 else if (fnxt != firstId || snxt != secondId)
96 return false;
97
98 tos= arc[forwardList[six]]->GetToId();
99 tof= arc[forwardList[fix]]->GetToId();
100 // printf ("Debug inner %d %d, %d %d\n", tof, tos, equivMap[tof], equivMap[tos]);
101 // if (tof >= 0) bogus assert
102 // assert (tof == equivMap[tof]);
103 // if (tos >= 0)
104 // assert (tos == equivMap[tos]);
105
106 // Test
107 if (!arc[forwardList[fix]]->HasSameLabels (arc[forwardList[six]])
108 || tos != tof)
109 return false;
110 count++;
111
112 fix++;
113 six++;
114
115 } while (fnxt >= 0 && snxt >= 0);
116
117 return false;
118 }
119
IdentifyEquivalence(int * depthMap,int * equivMap)120 void SubGraph::IdentifyEquivalence (int *depthMap, int *equivMap)
121 {
122 int ii, jj, dd, maxDepth, count, itCnt;
123
124 maxDepth= 0;
125 for (ii= 0; ii < numVertex; ii++) {
126 if (maxDepth < depthMap[ii])
127 maxDepth= depthMap[ii];
128 }
129
130 itCnt= 0;
131 do {
132 count= 0;
133 for (dd= 0; dd <= maxDepth; dd++)
134 for (ii= 0; ii < numVertex; ii++)
135 if (depthMap[ii] == dd && ii == equivMap[ii]) {
136 CheckForChangeAndResort (ii, equivMap);
137 for (jj= ii+1; jj < numVertex; jj++)
138 if (depthMap[jj] == dd && jj == equivMap[jj]) {
139 // Equivalence test
140 CheckForChangeAndResort (jj, equivMap);
141 // printf ("Try %d %d, ", ii, jj);
142 if (EquivalenceTestForward (ii, jj, equivMap)) {
143 equivMap[jj]= ii;
144 // printf ("Merged %d %d\n", ii, jj);
145 count++;
146 }
147 }
148 }
149
150 itCnt++;
151 // printf ("Total %d mergers\n", count);
152 } while (count > 0 && itCnt < MAXITS);
153
154 return;
155 }
156
CheckForChangeAndResort(int currId,int * mapList)157 void SubGraph::CheckForChangeAndResort (int currId, int *mapList)
158 {
159 int rix, rixBegin, nextId;
160 bool needSort;
161
162 needSort= false;
163 rixBegin= rix= FindFromIndex (currId);
164 if (rix < 0)
165 return;
166 while (rix < numArc && arc[forwardList[rix]]->GetFromId() == currId) {
167 nextId= arc[forwardList[rix]]->GetToId();
168 if (nextId >= 0 && mapList[nextId] != nextId) {
169 needSort= true;
170 arc[forwardList[rix]]->AssignToId(mapList[nextId]);
171 }
172 rix++;
173 }
174
175 // Resort
176 if (needSort)
177 RemoveDuplicatesAtNode (rixBegin, rix);
178
179 return;
180 }
181
DeterminizeAtVertex(int baseId,DetCache * cache)182 void SubGraph::DeterminizeAtVertex (int baseId, DetCache *cache)
183 {
184 int fix, six, firstId, secondId, vertEnd;
185
186 fix= FindFromIndex (baseId);
187 if (fix < 0)
188 return;
189
190 // Remove duplicates
191 vertEnd= fix;
192 six= -1;
193 while (vertEnd < sortNum && arc[forwardList[vertEnd]]->GetFromId() == baseId) {
194 vertEnd++;
195 }
196 vertEnd++;
197
198 // Iteration over first node
199 firstId= -1;
200 while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == baseId) {
201
202 // Iterator for firstId
203 while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == baseId
204 && (arc[forwardList[fix]]->GetToId() == firstId
205 || arc[forwardList[fix]]->GetInput() == TERMINAL_LABEL
206 || arc[forwardList[fix]]->GetInput() == DISCARD_LABEL))
207 fix++;
208
209 // Terminal Condition
210 if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != baseId)
211 break;
212 else
213 firstId= arc[forwardList[fix]]->GetToId();
214
215 // Iteration over second node
216 six= fix;
217 secondId= firstId;
218 while (six < sortNum && arc[forwardList[six]]->GetFromId() == baseId) {
219
220 // Iterator for secondId
221 while (six < sortNum && arc[forwardList[six]]->GetFromId() == baseId
222 && (arc[forwardList[six]]->GetToId() == secondId
223 || arc[forwardList[six]]->GetInput() == TERMINAL_LABEL
224 || arc[forwardList[six]]->GetInput() == DISCARD_LABEL))
225 six++;
226
227 // Terminal condition
228 if (six >= sortNum || arc[forwardList[six]]->GetFromId() != baseId)
229 break;
230 else
231 secondId= arc[forwardList[six]]->GetToId();
232
233 // Now we have both Ids worked out
234 assert (firstId >= 0);
235 assert (secondId >= 0);
236 assert (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL);
237 assert (arc[forwardList[six]]->GetInput() != DISCARD_LABEL);
238
239 if (PairwiseDeterminize (baseId, firstId, fix, secondId, six, cache) > 0) {
240 SortLanguageAtSortIndices (fix, vertEnd);
241
242 // Are we done with the first node?
243 while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == baseId
244 && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL)
245 fix++;
246
247 // Terminal condition
248 if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != baseId
249 || arc[forwardList[fix]]->GetToId() != firstId)
250 break;
251 }
252 }
253 }
254 return;
255 }
256
PairwiseDeterminize(int baseId,int firstId,int fixStart,int secondId,int sixStart,DetCache * cache)257 int SubGraph::PairwiseDeterminize (int baseId, int firstId, int fixStart, int secondId,
258 int sixStart, DetCache *cache)
259 {
260 int fix, six, fmiss, smiss, nmatch, symTst, newId;
261 bool isCached;
262
263 fix= fixStart;
264 six= sixStart;
265
266 assert (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL);
267 assert (arc[forwardList[six]]->GetInput() != DISCARD_LABEL);
268
269 // Count
270 isCached= false;
271 fmiss= smiss= nmatch= 0;
272 newId= -1;
273 while (six < sortNum && fix < sortNum) {
274
275 assert (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL);
276 assert (arc[forwardList[six]]->GetInput() != DISCARD_LABEL);
277
278 symTst= SYMBOL_COMPARE (forwardList[fix], forwardList[six]);
279 if (symTst == 0) {
280 if (newId == -1) {
281 newId= cache->QueryEntry (firstId, secondId);
282 if (newId < 0)
283 newId= NewVertexId ();
284 else
285 isCached= true;
286 // printf ("Forming %d with %d and %d at %d\n", newId, firstId, secondId, baseId);
287 }
288
289 // Assign second to new Vertex
290 arc[forwardList[six]]->AssignToId (newId);
291
292 // Assign first to DISCARD Index
293 arc[forwardList[fix]]->AssignInput (DISCARD_LABEL);
294
295 // Increment to next
296 do {
297 fix++;
298 } while (fix < sortNum && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL);
299 if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != baseId
300 || arc[forwardList[fix]]->GetToId() != firstId)
301 fix= sortNum;
302
303 do {
304 six++;
305 } while (six < sortNum && arc[forwardList[six]]->GetInput() == DISCARD_LABEL);
306 if (six >= sortNum || arc[forwardList[six]]->GetFromId() != baseId
307 || arc[forwardList[six]]->GetToId() != secondId)
308 six= sortNum;
309
310 nmatch++;
311 }
312 else if (symTst < 0) {
313 do {
314 fix++;
315 } while (fix < sortNum && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL);
316 if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != baseId
317 || arc[forwardList[fix]]->GetToId() != firstId)
318 fix= sortNum;
319 fmiss++;
320 }
321 else if (symTst > 0) {
322 do {
323 six++;
324 } while (six < sortNum && arc[forwardList[six]]->GetInput() == DISCARD_LABEL);
325 if (six >= sortNum || arc[forwardList[six]]->GetFromId() != baseId
326 || arc[forwardList[six]]->GetToId() != secondId)
327 six= sortNum;
328 smiss++;
329 }
330 }
331
332 // SortLanguageAtSortIndices (fixStart, fix);
333
334 if (newId >= 0) {
335 if (isCached == false) {
336 // numLast= numArc;
337 MergeVertices (newId, firstId, secondId);
338 cache->AddEntry (newId, firstId, secondId);
339 // UpdateVisitationCache (numLast);
340 }
341 assert (nmatch > 0);
342 }
343
344 // Update fan-in count
345 if (nmatch > 0) {
346 // printf ("Merging %d %d to create %d\n", firstId, secondId, newId);
347 for (int ii= 0; ii < nmatch; ii++) {
348 // IncNodeProperty (newId);
349 IncVisitationCache (newId);
350 DecVisitationCache (firstId);
351 DecVisitationCache (secondId);
352 }
353 }
354 return nmatch;
355 }
356
MergeVertices(int newId,int firstId,int secondId)357 void SubGraph::MergeVertices (int newId, int firstId, int secondId)
358 {
359 int fix, six, symTst, numStart;
360 NUANArc *arcOne;
361
362 numStart= numArc;
363 fix= FindFromIndex (firstId);
364 six= FindFromIndex (secondId);
365 if (fix < 0 || six < 0) {
366 if (fix >= 0)
367 while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == firstId) {
368 if (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL)
369 InheritArc (arc[forwardList[fix]], newId);
370 fix++;
371 }
372 else if (six >= 0)
373 while (six < sortNum && arc[forwardList[six]]->GetFromId() == secondId) {
374 if (arc[forwardList[six]]->GetInput() != DISCARD_LABEL)
375 InheritArc (arc[forwardList[six]], newId);
376 six++;
377 }
378 }
379 else {
380 while (six < sortNum && fix < sortNum) {
381
382 symTst= SYMBOL_COMPARE (forwardList[fix], forwardList[six]);
383
384 if (symTst == 0) {
385 if (arc[forwardList[fix]]->GetToId() == firstId
386 && arc[forwardList[six]]->GetToId() == secondId) {
387 arcOne= InheritArc (arc[forwardList[fix]], newId);
388 arcOne->AssignToId (newId);
389 }
390 else if (arc[forwardList[fix]]->GetToId()
391 == arc[forwardList[six]]->GetToId()) {
392 InheritArc (arc[forwardList[fix]], newId);
393 }
394 else {
395 InheritArc (arc[forwardList[fix]], newId);
396 InheritArc (arc[forwardList[six]], newId);
397 }
398
399 // Increment to next
400 do {
401 fix++;
402 } while (fix < sortNum && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL);
403 if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != firstId
404 || arc[forwardList[fix]]->GetFromId() != firstId)
405 fix= sortNum;
406
407 do {
408 six++;
409 } while (six < sortNum && arc[forwardList[six]]->GetInput() == DISCARD_LABEL);
410 if (six >= sortNum || arc[forwardList[six]]->GetFromId() != secondId)
411 six= sortNum;
412 }
413 else if (symTst < 0) {
414 InheritArc (arc[forwardList[fix]], newId);
415 do {
416 fix++;
417 } while (fix < sortNum && arc[forwardList[fix]]->GetInput() == DISCARD_LABEL);
418 if (fix >= sortNum || arc[forwardList[fix]]->GetFromId() != firstId
419 || arc[forwardList[fix]]->GetFromId() != firstId)
420 fix= sortNum;
421 }
422 else if (symTst > 0) {
423 InheritArc (arc[forwardList[six]], newId);
424 do {
425 six++;
426 } while (six < sortNum && arc[forwardList[six]]->GetInput() == DISCARD_LABEL);
427 if (six >= sortNum || arc[forwardList[six]]->GetFromId() != secondId
428 || arc[forwardList[six]]->GetFromId() != secondId)
429 six= sortNum;
430 }
431 }
432
433 while (fix < sortNum && arc[forwardList[fix]]->GetFromId() == firstId) {
434 if (arc[forwardList[fix]]->GetInput() != DISCARD_LABEL)
435 InheritArc (arc[forwardList[fix]], newId);
436 fix++;
437 }
438
439 while (six < sortNum && arc[forwardList[six]]->GetFromId() == secondId) {
440 if (arc[forwardList[six]]->GetInput() != DISCARD_LABEL)
441 InheritArc (arc[forwardList[six]], newId);
442 six++;
443 }
444 }
445
446 // Update the sort list
447 UpdateSortForLanguage ();
448 // RemoveDuplicatesAtNode (numStart, numArc);
449 // ViewNode (newId);
450 assert (CheckSort());
451
452 // printf ("Merging %d %d to create %d\n", firstId, secondId, newId);
453
454 return;
455 }
456
SetupVisitationCache()457 void SubGraph::SetupVisitationCache ()
458 {
459 int ii;
460
461 CreateNodeProperty ();
462 for (ii= 0; ii < numArc; ii++)
463 if (arc[ii]->GetInput() != DISCARD_LABEL && arc[ii]->GetToId() >= 0)
464 IncNodeProperty (arc[ii]->GetToId());
465 return;
466 }
467
ClearVisitationCache()468 void SubGraph::ClearVisitationCache ()
469 {
470 DeleteNodeProperty ();
471 return;
472 }
473
UpdateVisitationCache(int startNo)474 void SubGraph::UpdateVisitationCache (int startNo)
475 {
476 int ii;
477
478 for (ii= startNo; ii < numArc; ii++)
479 if (arc[ii]->GetInput() != DISCARD_LABEL && arc[ii]->GetToId() >= 0) {
480 IncNodeProperty (arc[ii]->GetToId());
481 // std::cout << " (" << arc[ii]->GetToId() << " " << QueryNodeProperty (arc[ii]->GetToId()) << ") ";
482 }
483 // std::cout << std::endl;
484 return;
485 }
486
DecVisitationCache(int currId)487 void SubGraph::DecVisitationCache (int currId)
488 {
489 int rix;
490
491 DecNodeProperty (currId);
492 // std::cout << " [" << currId << " " << QueryNodeProperty (currId) << "] ";
493 if (QueryNodeProperty (currId) <= 0) {
494 // std::cout << " [" << currId << "] ";
495 rix= FindFromIndex (currId);
496 if (rix < 0)
497 return;
498 while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) {
499 if (arc[forwardList[rix]]->GetInput() != DISCARD_LABEL
500 && arc[forwardList[rix]]->GetToId() >= 0) {
501 if (arc[forwardList[rix]]->GetFromId() == arc[forwardList[rix]]->GetToId())
502 DecNodeProperty (currId);
503 else if (QueryNodeProperty (arc[forwardList[rix]]->GetToId()) > 0)
504 DecVisitationCache (arc[forwardList[rix]]->GetToId());
505 }
506 rix++;
507 }
508 }
509 return;
510 }
511
IncVisitationCache(int currId)512 void SubGraph::IncVisitationCache (int currId)
513 {
514 int rix;
515
516 if (QueryNodeProperty (currId) <= 0) {
517 IncNodeProperty (currId);
518 // std::cout << " (" << currId << ") ";
519 rix= FindFromIndex (currId);
520 if (rix < 0)
521 return;
522 while (rix < sortNum && arc[forwardList[rix]]->GetFromId() == currId) {
523 if (arc[forwardList[rix]]->GetInput() != DISCARD_LABEL
524 && arc[forwardList[rix]]->GetToId() >= 0) {
525 // IncNodeProperty (arc[forwardList[rix]]->GetToId());
526 // if (currId != arc[forwardList[rix]]->GetToId())
527 IncVisitationCache (arc[forwardList[rix]]->GetToId());
528 }
529 rix++;
530 }
531 }
532 else
533 IncNodeProperty (currId);
534 // std::cout << " (" << currId << " " << QueryNodeProperty (currId) << ") ";
535 return;
536 }
537
VisitationConsistencyCheck()538 int SubGraph::VisitationConsistencyCheck ()
539 {
540 int ii, failCount;
541
542 int *nodeCount= new int [numVertex];
543
544 UpdateVertexCount (0);
545
546 // std::cout << "Count: ";
547 for (ii= 0; ii <numVertex; ii++) {
548 // std::cout << ii << " (" << vertexProp[ii] << ") ";
549 nodeCount[ii]= 0;
550 }
551 // std::cout << std::endl;
552 for (ii= 0; ii <numArc; ii++)
553 if (arc[ii]->GetInput() != DISCARD_LABEL && arc[ii]->GetToId() >= 0
554 && (vertexProp[arc[ii]->GetFromId()] > 0 || arc[ii]->GetFromId() == startId))
555 nodeCount[arc[ii]->GetToId()]++;
556 failCount= 0;
557 // std::cout << "Failure list: ";
558 for (ii= 0; ii <numVertex; ii++)
559 if (vertexProp[ii] != nodeCount[ii]) {
560 // std::cout << ii << " (" << vertexProp[ii] << " " << nodeCount[ii] << ") ";
561 failCount++;
562 }
563 // std::cout << std::endl;
564
565 // return failCount;
566 delete [] nodeCount;
567
568 return 0;
569 }
570