查找图中的所有循环，redux

发布于 2024-09-01 19:51:05 字数 829 浏览 9 评论 0原文

我知道这个问题有很多答案。然而，我发现他们都没有真正说到点子上。
有些人认为循环（几乎）与强连接组件相同（s.查找有向图中的所有循环)，因此可以使用为该目标设计的算法。
有些人认为可以通过 DFS 并检查后沿来找到循环（例如有关文件依赖性的 boost 图形文档）。

我现在想就是否可以通过 DFS 检测图中的所有循环并检查后沿提出一些建议？
http://www.me.utexas.edu/~bard/ IP/Handouts/cycles.pdf（在 SO 上找到）陈述了一种基于循环基础的方法。就我个人而言，我觉得它不是很直观，所以我正在寻找不同的解决方案。

编辑：我最初的意见显然是错误的。 S.下一个回答是“白痴”。
初步意见：我的观点是，它确实可以这样工作，因为 DFS-VISIT（DFS 的伪代码）新进入尚未访问的每个节点。从这个意义上说，每个顶点都表现出一个循环的潜在开始。此外，由于 DFS 访问每条边一次，因此通向循环起点的每条边也被覆盖。因此，通过使用 DFS 和后沿检查，确实应该可以检测图中的所有周期。请注意，如果存在具有不同数量的参与者节点的循环（例如三角形、矩形等），则必须做额外的工作来区分每个循环的实际“形状”。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

無心 2024-09-08 19:51:05

我已经彻底回答了这个问题，所以检查一下：

源删除排序总是返回最大循环吗？

答案的相关部分：

对您的
图表。
您有兴趣认回
边，即在遍历中，一条边
它指向一个祖先（在
DFS 树，它是由
第一个访问节点的边
时间）的访问节点。为了
例如，如果 DFS 堆栈有节点
[A->B->C->D] 当你探索 D 时
你找到一条边 D->B，那就是背面
边缘。每个后沿定义一个周期。
更重要的是，引发的周期
by back-edges 是一组基本的
图表的循环。 “一套基本的
循环”：您可以构造所有循环
通过 UNIONing 和
基本集的异或循环。为了
例如，考虑循环
[A1->A2->A3->A1]和
[A2→B1→B2→B3→A2]。你可以联合
他们进入循环：
[A1->A2->B1->B2->B3->A2->A3->A1]。

回复收藏 0 原文

亂 2024-09-08 19:51:05

也许这可以以某种方式帮助你，我发现这个描述有向图的彩色 dfs 的站点。因此，您可以考虑将我在这里介绍的 dfs 翻译更正为 php。

我添加的是创建森林的一部分和查找所有循环的另一部分。因此，请考虑将我的代码的这两部分确定为正确是不安全的。

具有图论知识的人也许能够进行测试。 dfs 部分没有注释，因为它已经在参考站点中进行了描述。我建议你举一个不止一棵树的例子，并在纸上画出森林（需要4种颜色），以便更好地理解。

这是代码：

 <?php 

    //define the graph
    $g = Array(
    1 => Array(1,2,3,4,5),
    2 => Array(1,2,3,4,5),
    3 => Array(1,2,3,4,5),
    4 => Array(1,2,3,4,5),
    5 => Array(1,2,3,4,5)
    );

    //add needed attributes on the graph
    $G = Array();
    foreach($g as $name => $children)
    {
        $child = Array();
        foreach($children as $child_name)//attaching a v letter is not needed, just a preference
            $child['v'.$child_name] = null;

        $G['v'.$name] = 
        Array('child'=>$child, 
            'color'=>'WHITE',//is used in dfs to make visit
            'discover_time'=>null,//is used in dfs to classify edges
            'finish_time'=>null,//is used in dfs to classify edges                  
            'father'=>null,//is used to walk backward to the start of a cycle
            'back_edge'=>null//can be omited, this information can be found with in_array(info, child_array)
        );
    }   


new test($G);
class test
{
    private $G = Array();//graph
    private $C = Array();//cycles
    private $F = Array();//forest
    private $L = Array();//loops
    private $time_counter = 0;

    public function __construct($G)
    {
        $this->G = $G;

        foreach($this->G as $node_name => $foo)
        {
            if($this->G[$node_name]['color'] === 'WHITE')
                $this->DFS_Visit($node_name);
        }

        $tree =array();
        foreach($this->G as $node_name => $data)
        {
            if($data['father'] === null)//new tree found
            {
                $this->F[] = $tree;//at first an empty array is inserted
                $tree = Array();
                $tree[$node_name] = $data; 
            }
            else
                $tree[$node_name] = $data;
        }
        array_shift($this->F);//remove the empty array
        $this->F[] = $tree;//add the last tree

        $this->find_all_elementary_cycles();

        file_put_contents('dump.log', count($this->L)." Loops found: \n", FILE_APPEND);
        file_put_contents('dump.log', print_r($this->L,true)."\n", FILE_APPEND);

        file_put_contents('dump.log', count($this->C)." Cycles found: \n", FILE_APPEND);
        file_put_contents('dump.log', print_r($this->C,true)."\n", FILE_APPEND);

        file_put_contents('dump.log', count($this->F)." trees found in the Forest: \n", FILE_APPEND);
        file_put_contents('dump.log', print_r($this->F,true)."\n", FILE_APPEND);
    }

    public function find_all_elementary_cycles()
    {
        /*** For each tree of the forest ***/
        foreach($this->F as $tree)
        {
            /*** Foreach node in the tree ***/
            foreach($tree as $node_name => $node)
            {
                /*** If this tree node connects to some child with backedge 
                (we hope to avoid some loops with this if) ***/
                if ( $node['back_edge'] === true )
                    /*** Then for every child ***/
                    foreach ( $node['child'] as $child_name => $edge_classification)
                        if($edge_classification === 'BACK_EDGE')
                            $this->back_edge_exploit($node_name, $child_name, $tree);               
            }
        }
    }

    private function back_edge_exploit ($back_edge_sender, $back_edge_receiver, $tree)
    {
        /*** The input of this function is a back edge, a back edge is defined as follows
        -a sender node: which stands lower in the tree and a reciever node which of course stands higher
        ***/

        /*** We want to get rid of loops, so check for a loop ***/
        if($back_edge_sender == $back_edge_receiver)
            return $this->L[] = $back_edge_sender;//we need to return cause no there is no cycle in a loop

        /*** For this backedge sender node the backedge reciever might send a direct edge to the sender ***/
        if( isset($this->G[$back_edge_receiver]['child'][$back_edge_sender]) > 0 )
            /*** This edge that the reciever sends could be a tree edge, this will happen 
            -in the case that: the backedge reciever is a father, but it can be a forward edge
            -in this case: for the forward edge to exist the backedge reciever does not have to be 
            -a father onlly: it can also be an ancestore. Whatever of both cases, we have a cycle
            ***/
            if( $this->G[$back_edge_receiver]['child'][$back_edge_sender] === 'TREE_EDGE' or 
                $this->G[$back_edge_receiver]['child'][$back_edge_sender] === 'FORWARD_EDGE')
                    $this->C[md5(serialize(Array($back_edge_receiver,$back_edge_sender)))]
                    = Array($back_edge_receiver,$back_edge_sender);


        /*** Until now we have covered, loops, cycles of the kind father->child which occur from one tree edge 
        - and one: back edge combination, and also we have covered cycles of the kind ancestore->descendant 
        -which: occur from the combination of one forward edge and one backedge (of course might happen that 
        -a father: can send to the child both forward and tree edge, all these are covered already).
        -what are left: are the cycles of the combination of more than one tree edges and one backedge ***/
        $cycle = Array();
        attach_node://loops must be handled before this, otherwise goto will loop continously
        $cycle[] =  $back_edge_sender; //enter the backedge sender
        $back_edge_sender = $tree[$back_edge_sender]['father']; //backedge sender becomes his father
        if($back_edge_sender !== $back_edge_receiver) //if backedge sender has not become backedge reciever yet
            goto attach_node;//the loop again

        $cycle[] = $back_edge_receiver;
        $cycle = array_reverse($cycle);
        $this->C[md5(serialize($cycle))] = $cycle;
    }


    private function DFS_Visit($node_name)
    { 
        $this->G[$node_name]['color'] = 'GRAY';
        $this->G[$node_name]['discover_time'] = $this->time_counter++;

        foreach($this->G[$node_name]['child'] as $child_name => $foo)
        {               
                if($this->G[$child_name]['color'] === 'BLACK') {#child black 

                    if( $this->G[$node_name]['discover_time'] < 
                    $this->G[$child_name]['discover_time'] ){#time of father smaller
                        $this->G[$node_name]['child'][$child_name] = 'FORWARD_EDGE';
                    }
                    else{#time of child smaller
                        $this->G[$node_name]['child'][$child_name] = 'CROSS_EDGE';
                    }
                }
                elseif($this->G[$child_name]['color'] === 'WHITE'){#child white
                    $this->G[$node_name]['child'][$child_name] = 'TREE_EDGE';
                    $this->G[$child_name]['father'] = $node_name;#father in the tree
                    $this->DFS_Visit($child_name);
                }#child discovered but not explored (and father discovered)
                elseif($this->G[$child_name]['color'] === 'GRAY'){#child gray
                    $this->G[$node_name]['child'][$child_name] = 'BACK_EDGE';
                    $this->G[$node_name]['back_edge'] = true;
                }
        }//for  
        $this->G[$node_name]['color'] = 'BLACK';//fully explored
        $this->G[$node_name]['finish_time'] = $this->time_counter++;
    }

}

?>

这是输出：

编辑 1：
back_edge_exploit 方法可以被此版本取代：

![private function back_edge_exploit ($back_edge_sender, $back_edge_receiver, $tree)
{
    /*** The input of this function is a back edge, a back edge is defined as follows
    -a sender node: which stands lower in the tree and a reciever node which of course stands higher
    ***/

    /*** We want to get rid of loops, so check for a loop ***/
    if($back_edge_sender == $back_edge_receiver)
        return $this->L\[\] = $back_edge_sender;//we need to return cause no there is no cycle in a loop

    $cycle = Array();//There is always a cycle which is a combination of tree edges and on backedge 
    $edges_count = 0; //If the cycle has more than 2 nodes we need to check for forward edge
    $backward_runner = $back_edge_sender;//this walks backward up to the start of cycle

    attach_node://loops must be handled before this, otherwise goto will loop continously
    $edges_count++;
    $cycle\[\] =    $backward_runner; //enter the backedge sender
    $backward_runner = $tree\[$backward_runner\]\['father'\]; //backedge sender becomes his father
    if($backward_runner !== $back_edge_receiver) //if backedge sender has not become backedge reciever yet
        goto attach_node;//the loop again
    else
        $cycle\[\] = $backward_runner;

    if($edges_count>1 and $this->G\[$back_edge_receiver\]\['child'\]\[$back_edge_sender\] === 'FORWARD_EDGE' )
        $this->C\[\] = Array($back_edge_receiver,$back_edge_sender);

    $this->C\[\] = array_reverse($cycle); //store the tree edge->back_edge cycle 
}][2]

编辑 2：
我不得不说，我发现 back_edge_exploit 是不够的，它只能找到由树边和一个后边构成的循环。

**** 编辑 3：****
虽然这个解决方案被发现是不完整的，但它有一些有用的信息，甚至它本身的不足也是一条信息，所以我认为保留它可能是有用的。但我编辑答案的主要原因是我找到了另一个解决方案，我将在下面介绍。

但在此之前，关于 dfs 方法的另一个注意事项是，通过遍历所有交叉、前向、树、后边缘的任何有效组合，可能会发生循环。因此，根据 dfs 信息找到实际周期并不简单（需要额外的代码），请考虑
这个例子：

在此处输入图像描述

只要涉及到新的解决方案，它就在 1970 年的旧论文中进行了描述，由James C. Tiernan（检查此链接）作为一种有效的算法查找有向图中的所有基本循环。还有一个无需转到的现代实现在这里查看< /a>

我的基本循环算法（这就是名字）的实现是用 php 实现的，并且尽可能接近原始算法。我已经检查过了并且有效。这是关于有向图的，如果你声明你的图，以便有一个有向循环 v1->v2->v3 和另一个有向循环 v2->v3->v1 那么两个循环都会被发现，这是合乎逻辑的，因为它适用于有向图。

至于无向图，作者建议使用其他算法，这些算法比修改算法提供更好的解决方案，但是可以通过修改图定义并添加对长度为 2 的循环（被视为无向边）的额外检查来完成。特别是，三个节点的无向循环将在定义中定义两次，每个方向一次，如下所示：v1->v2->v3 和 v3->v2->v1。然后算法将找到它两次，每个方向一次，然后修改 EC3_Circuit_Confirmation 上的单行可以删除多余的一行。

节点是按顺序定义的，可以更改常量first和邻接表，使第一个节点从零或一开始计数。

这是 Tiernan 的 EC 算法的 php 代码：

<?php 

    define(first,1);    //Define how to start counting, from 0 or 1 
    //nodes are considered to be sequential 
    $G[first] = Array(2); $G[] = Array(1,3); $G[] = Array(4); $G[] = Array(1); 


    $N=key(array_slice($G, -1, 1, TRUE));//last key of g
    $H=Array(Array());
    $P = Array();
    $P[first] = first;
    $k = first;
    $C = Array();//cycles
    $L = Array();//loops

########################## ALGORITHM START #############################

    #[Path Extension]
    EC2_Path_Extension:  
    //scan adjacency list
        foreach($G[$P[$k]] as $j => $adj_node)
            //if there is an adjacent node bigger than P[1] and this nodes does not belong in P
            if( ($adj_node > $P[first]) and (in_array($adj_node, $P))===false and 
            (count($H[$P[$k]])>0 and in_array($adj_node, $H[$P[$k]]))===false)
            {
                $k++;
                $P[$k] = $G[$P[$k-1]][$j];  
                goto EC2_Path_Extension;    
            }

    #[EC3 Circuit Confirmation]  
    EC3_Circuit_Confirmation: 
    if(!in_array($P[first], $G[$P[$k]]))
        goto EC4_Vertex_Closure;
    //otherwise
    if (count($P)===1)
        $L[] = current($P);
    else
        $C[] = implode($P);


    #[EC4 Vertex Closure]
    EC4_Vertex_Closure:
    if($k===first)
        goto EC5_Advance_Initial_Vertex;

    $H[$P[$k]] = Array(); 
    $H[$P[$k-1]][] = $P[$k];
    unset($P[$k]);
    $k--;
    goto EC2_Path_Extension;


    #[EC5 Advance Initial Vertex]
    EC5_Advance_Initial_Vertex:
    if($P[first] === $N)
        goto EC6_Terminate;

    $P[first]++; 
    $k=first;
    //Reset H 
    $H=Array(Array()); 
    goto EC2_Path_Extension;

    EC6_Terminate:
########################### ALGORITHM END ##################################

    echo "\n\n".count($L)."$count loops found: ".implode(", ",$L)."\n\n";
    echo count($C)." cycles found!\n".implode("\n",$C)."\n";

    /*** Original graph found in the paper ***/ 
    //$G[first] = Array(2); $G[] = Array(2,3,4);
    //$G[] = Array(5); $G[] = Array(3); $G[] = Array(1);


    ?>

Maybe this can help you somehow, I found this site where a colored dfs for directed graph is described. So you can consider correct the dfs translation to php I present here.

What I added is a part to create a forest and an other part to find all cycles. So please consider that it is not safe to take these two parts of my code as correct for sure.

One with knowledge on graph theory might be able to test for sure. There are no comments in the dfs part because it is described already in the reference site. I suggest that you take an example with more than one tree and draw the forest (need 4 colors) in a paper to better understand.

This is the code:

 <?php 

    //define the graph
    $g = Array(
    1 => Array(1,2,3,4,5),
    2 => Array(1,2,3,4,5),
    3 => Array(1,2,3,4,5),
    4 => Array(1,2,3,4,5),
    5 => Array(1,2,3,4,5)
    );

    //add needed attributes on the graph
    $G = Array();
    foreach($g as $name => $children)
    {
        $child = Array();
        foreach($children as $child_name)//attaching a v letter is not needed, just a preference
            $child['v'.$child_name] = null;

        $G['v'.$name] = 
        Array('child'=>$child, 
            'color'=>'WHITE',//is used in dfs to make visit
            'discover_time'=>null,//is used in dfs to classify edges
            'finish_time'=>null,//is used in dfs to classify edges                  
            'father'=>null,//is used to walk backward to the start of a cycle
            'back_edge'=>null//can be omited, this information can be found with in_array(info, child_array)
        );
    }   


new test($G);
class test
{
    private $G = Array();//graph
    private $C = Array();//cycles
    private $F = Array();//forest
    private $L = Array();//loops
    private $time_counter = 0;

    public function __construct($G)
    {
        $this->G = $G;

        foreach($this->G as $node_name => $foo)
        {
            if($this->G[$node_name]['color'] === 'WHITE')
                $this->DFS_Visit($node_name);
        }

        $tree =array();
        foreach($this->G as $node_name => $data)
        {
            if($data['father'] === null)//new tree found
            {
                $this->F[] = $tree;//at first an empty array is inserted
                $tree = Array();
                $tree[$node_name] = $data; 
            }
            else
                $tree[$node_name] = $data;
        }
        array_shift($this->F);//remove the empty array
        $this->F[] = $tree;//add the last tree

        $this->find_all_elementary_cycles();

        file_put_contents('dump.log', count($this->L)." Loops found: \n", FILE_APPEND);
        file_put_contents('dump.log', print_r($this->L,true)."\n", FILE_APPEND);

        file_put_contents('dump.log', count($this->C)." Cycles found: \n", FILE_APPEND);
        file_put_contents('dump.log', print_r($this->C,true)."\n", FILE_APPEND);

        file_put_contents('dump.log', count($this->F)." trees found in the Forest: \n", FILE_APPEND);
        file_put_contents('dump.log', print_r($this->F,true)."\n", FILE_APPEND);
    }

    public function find_all_elementary_cycles()
    {
        /*** For each tree of the forest ***/
        foreach($this->F as $tree)
        {
            /*** Foreach node in the tree ***/
            foreach($tree as $node_name => $node)
            {
                /*** If this tree node connects to some child with backedge 
                (we hope to avoid some loops with this if) ***/
                if ( $node['back_edge'] === true )
                    /*** Then for every child ***/
                    foreach ( $node['child'] as $child_name => $edge_classification)
                        if($edge_classification === 'BACK_EDGE')
                            $this->back_edge_exploit($node_name, $child_name, $tree);               
            }
        }
    }

    private function back_edge_exploit ($back_edge_sender, $back_edge_receiver, $tree)
    {
        /*** The input of this function is a back edge, a back edge is defined as follows
        -a sender node: which stands lower in the tree and a reciever node which of course stands higher
        ***/

        /*** We want to get rid of loops, so check for a loop ***/
        if($back_edge_sender == $back_edge_receiver)
            return $this->L[] = $back_edge_sender;//we need to return cause no there is no cycle in a loop

        /*** For this backedge sender node the backedge reciever might send a direct edge to the sender ***/
        if( isset($this->G[$back_edge_receiver]['child'][$back_edge_sender]) > 0 )
            /*** This edge that the reciever sends could be a tree edge, this will happen 
            -in the case that: the backedge reciever is a father, but it can be a forward edge
            -in this case: for the forward edge to exist the backedge reciever does not have to be 
            -a father onlly: it can also be an ancestore. Whatever of both cases, we have a cycle
            ***/
            if( $this->G[$back_edge_receiver]['child'][$back_edge_sender] === 'TREE_EDGE' or 
                $this->G[$back_edge_receiver]['child'][$back_edge_sender] === 'FORWARD_EDGE')
                    $this->C[md5(serialize(Array($back_edge_receiver,$back_edge_sender)))]
                    = Array($back_edge_receiver,$back_edge_sender);


        /*** Until now we have covered, loops, cycles of the kind father->child which occur from one tree edge 
        - and one: back edge combination, and also we have covered cycles of the kind ancestore->descendant 
        -which: occur from the combination of one forward edge and one backedge (of course might happen that 
        -a father: can send to the child both forward and tree edge, all these are covered already).
        -what are left: are the cycles of the combination of more than one tree edges and one backedge ***/
        $cycle = Array();
        attach_node://loops must be handled before this, otherwise goto will loop continously
        $cycle[] =  $back_edge_sender; //enter the backedge sender
        $back_edge_sender = $tree[$back_edge_sender]['father']; //backedge sender becomes his father
        if($back_edge_sender !== $back_edge_receiver) //if backedge sender has not become backedge reciever yet
            goto attach_node;//the loop again

        $cycle[] = $back_edge_receiver;
        $cycle = array_reverse($cycle);
        $this->C[md5(serialize($cycle))] = $cycle;
    }


    private function DFS_Visit($node_name)
    { 
        $this->G[$node_name]['color'] = 'GRAY';
        $this->G[$node_name]['discover_time'] = $this->time_counter++;

        foreach($this->G[$node_name]['child'] as $child_name => $foo)
        {               
                if($this->G[$child_name]['color'] === 'BLACK') {#child black 

                    if( $this->G[$node_name]['discover_time'] < 
                    $this->G[$child_name]['discover_time'] ){#time of father smaller
                        $this->G[$node_name]['child'][$child_name] = 'FORWARD_EDGE';
                    }
                    else{#time of child smaller
                        $this->G[$node_name]['child'][$child_name] = 'CROSS_EDGE';
                    }
                }
                elseif($this->G[$child_name]['color'] === 'WHITE'){#child white
                    $this->G[$node_name]['child'][$child_name] = 'TREE_EDGE';
                    $this->G[$child_name]['father'] = $node_name;#father in the tree
                    $this->DFS_Visit($child_name);
                }#child discovered but not explored (and father discovered)
                elseif($this->G[$child_name]['color'] === 'GRAY'){#child gray
                    $this->G[$node_name]['child'][$child_name] = 'BACK_EDGE';
                    $this->G[$node_name]['back_edge'] = true;
                }
        }//for  
        $this->G[$node_name]['color'] = 'BLACK';//fully explored
        $this->G[$node_name]['finish_time'] = $this->time_counter++;
    }

}

?>

And this is the output:

EDIT 1 :
The back_edge_exploit method could be erplaced by this version:

![private function back_edge_exploit ($back_edge_sender, $back_edge_receiver, $tree)
{
    /*** The input of this function is a back edge, a back edge is defined as follows
    -a sender node: which stands lower in the tree and a reciever node which of course stands higher
    ***/

    /*** We want to get rid of loops, so check for a loop ***/
    if($back_edge_sender == $back_edge_receiver)
        return $this->L\[\] = $back_edge_sender;//we need to return cause no there is no cycle in a loop

    $cycle = Array();//There is always a cycle which is a combination of tree edges and on backedge 
    $edges_count = 0; //If the cycle has more than 2 nodes we need to check for forward edge
    $backward_runner = $back_edge_sender;//this walks backward up to the start of cycle

    attach_node://loops must be handled before this, otherwise goto will loop continously
    $edges_count++;
    $cycle\[\] =    $backward_runner; //enter the backedge sender
    $backward_runner = $tree\[$backward_runner\]\['father'\]; //backedge sender becomes his father
    if($backward_runner !== $back_edge_receiver) //if backedge sender has not become backedge reciever yet
        goto attach_node;//the loop again
    else
        $cycle\[\] = $backward_runner;

    if($edges_count>1 and $this->G\[$back_edge_receiver\]\['child'\]\[$back_edge_sender\] === 'FORWARD_EDGE' )
        $this->C\[\] = Array($back_edge_receiver,$back_edge_sender);

    $this->C\[\] = array_reverse($cycle); //store the tree edge->back_edge cycle 
}][2]

EDIT 2:
I have to say that I have found that back_edge_exploit is insufficient it will only find cycles that are made with tree edges and one back edge.

**** Edit 3: ****
Although this solutions is found to be incomplete, it has some useful information, even the insufficiency it self is a piece of information, so I think it might be useful to keep it. But the main reason I have edited my answer is that I have found an other solution which I am going to present below.

But before that an other notice could be made about the dfs aproach, there are cycles that could occur by walking any valid combination all cross,forward,tree,back edge. So finding the actual cycles relying on the dfs information is not trivial (requires extra code), consider
this example:

enter image description here

As long as the new solution is concerned it is described in an old paper of 1970, by James C. Tiernan (Check this link) as an efficient algorithm for finding all elementary cycles in a directed graph. Also there is a modern implementation of this without goto See it here

My implementation of Elementary Cycle Algorithm (that's the name) is in php and is as close to the original as possible . I have already checked it and it works. It is about directed graphs, if you declare you graph so that there is a directed cycle v1->v2->v3 and an other one v2->v3->v1 then both cycles will be found which is logical since it works on directed graphs.

As for undirected graphs the author suggests other algorithms which make a better solution than modifying the algorithms, however it can be done by modifying the graph definition and by adding an extra check for cycles of length 2 which are considered as undirected edges. In particular an undirected cycle of three nodes would be defined twice in the definition, once per orientation, like this: v1->v2->v3 and v3->v2->v1. Then the algorithm will find it twice, once per orientation, then a modification of a single line on EC3_Circuit_Confirmation can cut the extra one.

The nodes are defined sequentially, one can change the constant first and the adjacency list to make the first node count from zero or one.

This is the php code for the EC Algorithm of Tiernan :

<?php 

    define(first,1);    //Define how to start counting, from 0 or 1 
    //nodes are considered to be sequential 
    $G[first] = Array(2); $G[] = Array(1,3); $G[] = Array(4); $G[] = Array(1); 


    $N=key(array_slice($G, -1, 1, TRUE));//last key of g
    $H=Array(Array());
    $P = Array();
    $P[first] = first;
    $k = first;
    $C = Array();//cycles
    $L = Array();//loops

########################## ALGORITHM START #############################

    #[Path Extension]
    EC2_Path_Extension:  
    //scan adjacency list
        foreach($G[$P[$k]] as $j => $adj_node)
            //if there is an adjacent node bigger than P[1] and this nodes does not belong in P
            if( ($adj_node > $P[first]) and (in_array($adj_node, $P))===false and 
            (count($H[$P[$k]])>0 and in_array($adj_node, $H[$P[$k]]))===false)
            {
                $k++;
                $P[$k] = $G[$P[$k-1]][$j];  
                goto EC2_Path_Extension;    
            }

    #[EC3 Circuit Confirmation]  
    EC3_Circuit_Confirmation: 
    if(!in_array($P[first], $G[$P[$k]]))
        goto EC4_Vertex_Closure;
    //otherwise
    if (count($P)===1)
        $L[] = current($P);
    else
        $C[] = implode($P);


    #[EC4 Vertex Closure]
    EC4_Vertex_Closure:
    if($k===first)
        goto EC5_Advance_Initial_Vertex;

    $H[$P[$k]] = Array(); 
    $H[$P[$k-1]][] = $P[$k];
    unset($P[$k]);
    $k--;
    goto EC2_Path_Extension;


    #[EC5 Advance Initial Vertex]
    EC5_Advance_Initial_Vertex:
    if($P[first] === $N)
        goto EC6_Terminate;

    $P[first]++; 
    $k=first;
    //Reset H 
    $H=Array(Array()); 
    goto EC2_Path_Extension;

    EC6_Terminate:
########################### ALGORITHM END ##################################

    echo "\n\n".count($L)."$count loops found: ".implode(", ",$L)."\n\n";
    echo count($C)." cycles found!\n".implode("\n",$C)."\n";

    /*** Original graph found in the paper ***/ 
    //$G[first] = Array(2); $G[] = Array(2,3,4);
    //$G[] = Array(5); $G[] = Array(3); $G[] = Array(1);


    ?>

回复收藏 0 原文