檢查節點是否在有向圖的節點路徑中

我有一個有向圖。我想知道節點N是否總是在上層節點T的路徑中。我檢查它的方式是從入口節點開始並執行深度優先搜索。如果在任何路徑中看到節點N在節點T之前遇到，則假定它不總是在其路徑中。檢查節點是否在有向圖的節點路徑中

舉例來說，在附圖中，入口節點爲entry_0_CC_FC，上層節點爲if_end_0_CC_FC，節點N爲land.lhs.true26_0_CC_FC。

但是我看到我的算法陷入了無限循環。要麼花費太多時間，要麼停滯不前，我不確定。順便說一下，此圖中有119個塊。這是代碼。你能看到任何可能使它陷入無限循環的問題嗎？

void CheckIfNotAlwaysInPath(bool& violation, BasicBlock* BS, 
    BasicBlock* BT, BasicBlock* BN, set<BasicBlock*> visited) 
{ 
    int i; 

    // If already visited 
    if (visited.find(BS) != visited.end()) // If already had visited 
     return; 

    visited.insert(BS); 

    if (BS == BN) 
    { 
     if (visited.find(BT) == visited.end()) 
      violation = true; 
     return; 
    } 

    if (isa<ReturnInst>(BS->getTerminator())) 
     return; 
    if (BS->getTerminator()->getNumSuccessors() == 0) 
     return; 


    for(i = 0; i < BS->getTerminator()->getNumSuccessors(); i++) 
    { 
     if (visited.find(BS->getTerminator()->getSuccessor(i)) == visited.end()) 
      CheckIfNotAlwaysInPath(violation, BS->getTerminator()->getSuccessor(i), BT, BN, visited); 
    } 
}

enter image description here 。

來源

2012-08-30 pythonic

該圖有點大，至少對我而言，我無法識別該圖中的某個東西，您是否介意縮放它，使其像素化較少？ – mmoment

您是否認爲它太大並且需要太多時間來計算每條路徑 – pythonic

第一次*截圖*失敗了「最小，完整的示例」要求！ –

檢查圖中的反饋。然後檢查代碼中的引用功能塊/狀態機。直到if.end531_0_CC_FC的圖表的上半部分應該沒問題。之後for.body塊或for.cond675.loopexit_0_cc_FC可能會出錯......或其他一些環回。

我的第一個猜測是從for.cond675.loopexit_0_cc_FC到for.body.688.lr.ph_0_CC_FC的迴環。

來源

2012-08-30 09:47:35 mmoment

但我確定，我們不會迴環。訪問集是爲此目的。你認爲我還可以迴環嗎？ – pythonic

圖中有條件反饋，對吧？ – mmoment

基本上for.cond675，for.body688是繼任者。現在因爲forbody688已經在訪問集合中（因爲我們之前遇到過），所以算法不會再訪問它。這樣，環回不會再被分析。 – pythonic

檢查節點是否在有向圖的節點路徑中

回答

相關問題