枝刈りの幅優先探索について

[n4o847]

prune をしたあと stateList に同じ状態が複数入っていることがあるのが謎で色々見てみたんですが、 removeUnreachableState の中の

https://github.com/n4o847/seccamp-redos/blob/153cfb431283ae32b90ef2bb9e573a4a921c7cac/src/pruning.ts#L93-L109

で visited を queue から出してから true にしていますが、 queue に入れるときに true にしなければいけないのでは？と思いました

あと visited は Set に置き換えられると思います。

[n4o847]

プルリクのときに気づかなかった……

 while (queue.length !== 0) {
   const source = queue.shift()!;
   newStateList.push(source);

   if (pnfa.acceptingStateSet.has(source)) {
     newAcceptingStateSet.add(source);
   }

   for (const [_, dests] of pnfa.transitions.getTransitions(source)) {
     for (const dest of dests) {
       if (!visited.has(dest)) {
         visited.add(dest);
         queue.push(dest);
       }
     }
   }
 }

みたいな修正で良ければこっちでやっておきます

と思ったけど newStateList.push(source) の位置があってるかわからん……

[n4o847]

終了条件が無いから newStateList.push(source) はどこでもいいのか（ですか？）

[yapatta]

これ、pushしたときにtrueにしないと同じStateが複数pushされますね、誠に申し訳ないです、vizで二重辺になってたのそう言うことか あと、この実装だと最初のinitialStateたちをすべてvisited trueにする必要がありそうです。

[yapatta]

てかもっと簡単な方法があって

 while (queue.length !== 0) { 
   const source = queue.shift()!; 
   ここに既に訪れてたらcontinueを入れる
   visited.set(source, true); 
   newStateList.push(source); 

   if (pnfa.acceptingStateSet.has(source)) { 
     newAcceptingStateSet.add(source); 
   } 

   for (const [_, dests] of pnfa.transitions.getTransitions(source)) { 
     for (const dest of dests) { 
       if (!visited.get(dest)!) { 
         queue.push(dest); 
       } 
     } 
   } 
 } 

[n4o847]

あと、この実装だと最初のinitialStateたちをすべてvisited trueにする必要がありそうです。

たしかに（そしたら yuziroppe さんに任せたほうが良いのか、良いですか…？）

てかもっと簡単な方法があって

たしかに？

でもそれだと訪問判定２回やるの無駄感ありませんか

[yapatta]

ううう、二回やるの無駄感、たしかに、、、、 自分で書いたコードですし、責任持って直します！報告ありがとうございます