检查节点是否在有向图的节点路径中

我有一个有向图。我想知道节点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

检查节点是否在有向图的节点路径中

回答

相关问题