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/*
36static int checkEntry (int *itemList, int count, int item);
37
38static 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
47void 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
63bool 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
120void 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
157void 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
182void 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
257int 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
357void 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
457void 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
468void SubGraph::ClearVisitationCache ()
469{
470    DeleteNodeProperty ();
471    return;
472}
473
474void 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
487void 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
512void 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
538int 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