首页 文章

查找无向图中的所有循环

提问于
浏览
48

我需要一个工作算法来查找无向图中的所有简单循环 . 我知道成本可能是指数级的,问题是NP完全的,但我将在一个小图(最多20-30个顶点)中使用它,并且循环数量很少 .

经过长时间的研究(主要是在这里),我仍然没有工作方法 . 以下是我的搜索摘要:

Finding all cycles in an undirected graph

Cycles in an Undirected Graph - >仅检测是否存在循环

Finding polygons within an undirected Graph - >非常好的描述,但没有解决方案

Finding all cycles in a directed graph - >仅在有向图中查找周期

Detect cycles in undirected graph using boost graph library

我发现的唯一一个解决我问题的答案是:

Find all cycles in graph, redux

似乎找到一组基本循环并对它们进行异或可以做到这一点 . 找到一组基本循环很容易,但我不明白如何组合它们以获得图中的所有循环...

10 回答

  • 36

    对于无向图,标准方法是寻找所谓的循环基:一组简单循环,人们可以通过组合生成所有其他循环 . 这些不一定是图中的所有简单循环 . 考虑以下图表:

    A 
      /   \
    B ----- C
      \   /
        D
    

    这里有3个简单的循环:A-B-C-A,B-C-D-B和A-B-D-C-A . 然而,您可以将这两个中的每一个作为基础,并将第三个作为2的组合获得 . 这与有向图形的实质差异在于,由于需要观察边缘方向,因此无法组合如此自由的周期 .

    用于查找无向图的循环基础的标准基线算法是:构建生成树,然后对于不属于树的每个边构建从该边创建循环和树上的一些边 . 必须存在这样的循环,否则边缘将是树的一部分 .

    例如,上面示例图的一个可能的生成树是这样的:

    A 
      /   \
    B      C
      \ 
        D
    

    不在树中的2个边是B-C和C-D . 相应的简单循环是A-B-C-A和A-B-D-C-A .

    您还可以构建以下生成树:

    A 
      /   
    B ----- C
      \   
        D
    

    对于这个生成树,简单的循环是A-B-C-A和B-C-D-B .

    可以以不同方式细化基线算法 . 据我所知,最佳细化属于Paton(K.Paton,一种用于寻找无向线性图的基本循环集的算法,Comm.ACM 12(1969),pp.514-518 . ) . 这里有一个Java开源实现:http://code.google.com/p/niographs/ .

    我应该提到如何将循环基础中的简单循环组合成新的简单循环 . 您首先列出图表的所有边缘(但在此后修复) . 然后通过将0和1的序列放置在属于循环的边缘位置和在不属于循环的边缘位置的零的位置来表示循环 . 然后,您对序列进行按位异或(XOR) . 您执行XOR的原因是您要排除属于两个循环的边,从而使组合循环不简单 . 您还需要通过检查序列的按位AND不是全零来检查2个循环是否有一些共同边 . 否则,XOR的结果将是2个不相交的循环而不是新的简单循环 .

    以下是上面示例图的示例:

    我们首先列出边缘:((AB),(AC),(BC),(BD),(CD)) . 然后,简单循环A-B-C-A,B-D-C-B和A-B-D-C-A表示为(1,1,1,0,0),(0,0,1,1,1)和(1,1,0,1,1) . 现在我们可以例如使用B-D-C-B的XOR A-B-C-A,结果是(1,1,0,1,1),它恰好是A-B-D-C-A . 或者我们可以异或A-B-C-A和A-B-D-C-A,结果为(0,0,1,1,1) . 这正是B-D-C-B .

    给定循环基础,您可以通过检查2个或更多不同基本循环的所有可能组合来发现所有简单循环 . 此处详细介绍了该过程:第14页的http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .

    为了完整起见,我会注意到使用算法来查找有向图的所有简单循环似乎是可能的(并且效率低下) . 无向图的每个边都可以被相反方向的2个有向边代替 . 然后有向图的算法应该有效 . 对于无向图的每个边缘将存在1个“假”2节点循环,其将被忽略,并且将存在无向图的每个简单循环的顺时针和逆时针版本 . 用于在有向图中查找所有周期的算法的Java开源实现可以在我已经引用的链接中找到 .

  • 0

    以下是基于深度优先搜索的C#(和Java,请参见答案结尾)的演示实现 .

    外部循环扫描图形的所有节点,并从每个节点开始搜索 . 节点邻居(根据边缘列表)被添加到循环路径中 . 如果不能添加更多未访问的邻居,则递归结束 . 如果路径长于两个节点并且下一个邻居是路径的开始,则找到新的循环 . 避免重复循环,通过将最小节点旋转到开始来对循环进行归一化 . 反向排序的周期也被考虑在内 .

    这只是一个天真的实现 . 经典论文是:Donald B. Johnson . 找到有向图的所有基本电路 . SIAM J. Comput . ,4(1):77-84,1975 .

    可以找到最近对现代算法的调查here

    using System;
    using System.Collections.Generic;
    
    namespace akCyclesInUndirectedGraphs
    {
        class Program
        {
            //  Graph modelled as list of edges
            static int[,] graph =
                {
                    {1, 2}, {1, 3}, {1, 4}, {2, 3},
                    {3, 4}, {2, 6}, {4, 6}, {7, 8},
                    {8, 9}, {9, 7}
                };
    
            static List<int[]> cycles = new List<int[]>();
    
            static void Main(string[] args)
            {
                for (int i = 0; i < graph.GetLength(0); i++)
                    for (int j = 0; j < graph.GetLength(1); j++)
                    {
                        findNewCycles(new int[] {graph[i, j]});
                    }
    
                foreach (int[] cy in cycles)
                {
                    string s = "" + cy[0];
    
                    for (int i = 1; i < cy.Length; i++)
                        s += "," + cy[i];
    
                    Console.WriteLine(s);
                }
            }
    
            static void findNewCycles(int[] path)
            {
                    int n = path[0];
                    int x;
                    int[] sub = new int[path.Length + 1];
    
                    for (int i = 0; i < graph.GetLength(0); i++)
                        for (int y = 0; y <= 1; y++)
                            if (graph[i, y] == n)
                            //  edge referes to our current node
                            {
                                x = graph[i, (y + 1) % 2];
                                if (!visited(x, path))
                                //  neighbor node not on path yet
                                {
                                    sub[0] = x;
                                    Array.Copy(path, 0, sub, 1, path.Length);
                                    //  explore extended path
                                    findNewCycles(sub);
                                }
                                else if ((path.Length > 2) && (x == path[path.Length - 1]))
                                //  cycle found
                                {
                                    int[] p = normalize(path);
                                    int[] inv = invert(p);
                                    if (isNew(p) && isNew(inv))
                                        cycles.Add(p);
                                }
                            }
            }
    
            static bool equals(int[] a, int[] b)
            {
                bool ret = (a[0] == b[0]) && (a.Length == b.Length);
    
                for (int i = 1; ret && (i < a.Length); i++)
                    if (a[i] != b[i])
                    {
                        ret = false;
                    }
    
                return ret;
            }
    
            static int[] invert(int[] path)
            {
                int[] p = new int[path.Length];
    
                for (int i = 0; i < path.Length; i++)
                    p[i] = path[path.Length - 1 - i];
    
                return normalize(p);
            }
    
            //  rotate cycle path such that it begins with the smallest node
            static int[] normalize(int[] path)
            {
                int[] p = new int[path.Length];
                int x = smallest(path);
                int n;
    
                Array.Copy(path, 0, p, 0, path.Length);
    
                while (p[0] != x)
                {
                    n = p[0];
                    Array.Copy(p, 1, p, 0, p.Length - 1);
                    p[p.Length - 1] = n;
                }
    
                return p;
            }
    
            static bool isNew(int[] path)
            {
                bool ret = true;
    
                foreach(int[] p in cycles)
                    if (equals(p, path))
                    {
                        ret = false;
                        break;
                    }
    
                return ret;
            }
    
            static int smallest(int[] path)
            {
                int min = path[0];
    
                foreach (int p in path)
                    if (p < min)
                        min = p;
    
                return min;
            }
    
            static bool visited(int n, int[] path)
            {
                bool ret = false;
    
                foreach (int p in path)
                    if (p == n)
                    {
                        ret = true;
                        break;
                    }
    
                return ret;
            }
        }
    }
    

    演示图的周期:

    1,3,2
    1,4,3,2
    1,4,6,2
    1,3,4,6,2
    1,4,6,2,3
    1,4,3
    2,6,4,3
    7,9,8
    

    用Java编码的算法:

    import java.util.ArrayList;
    import java.util.List;
    
    public class GraphCycleFinder {
    
        //  Graph modeled as list of edges
        static int[][] graph =
            {
                {1, 2}, {1, 3}, {1, 4}, {2, 3},
                {3, 4}, {2, 6}, {4, 6}, {7, 8},
                {8, 9}, {9, 7}
            };
    
        static List<int[]> cycles = new ArrayList<int[]>();
    
        /**
         * @param args
         */
        public static void main(String[] args) {
    
            for (int i = 0; i < graph.length; i++)
                for (int j = 0; j < graph[i].length; j++)
                {
                    findNewCycles(new int[] {graph[i][j]});
                }
    
            for (int[] cy : cycles)
            {
                String s = "" + cy[0];
    
                for (int i = 1; i < cy.length; i++)
                {
                    s += "," + cy[i];
                }
    
                o(s);
            }
    
        }
    
        static void findNewCycles(int[] path)
        {
                int n = path[0];
                int x;
                int[] sub = new int[path.length + 1];
    
                for (int i = 0; i < graph.length; i++)
                    for (int y = 0; y <= 1; y++)
                        if (graph[i][y] == n)
                        //  edge refers to our current node
                        {
                            x = graph[i][(y + 1) % 2];
                            if (!visited(x, path))
                            //  neighbor node not on path yet
                            {
                                sub[0] = x;
                                System.arraycopy(path, 0, sub, 1, path.length);
                                //  explore extended path
                                findNewCycles(sub);
                            }
                            else if ((path.length > 2) && (x == path[path.length - 1]))
                            //  cycle found
                            {
                                int[] p = normalize(path);
                                int[] inv = invert(p);
                                if (isNew(p) && isNew(inv))
                                {
                                    cycles.add(p);
                                }
                            }
                        }
        }
    
        //  check of both arrays have same lengths and contents
        static Boolean equals(int[] a, int[] b)
        {
            Boolean ret = (a[0] == b[0]) && (a.length == b.length);
    
            for (int i = 1; ret && (i < a.length); i++)
            {
                if (a[i] != b[i])
                {
                    ret = false;
                }
            }
    
            return ret;
        }
    
        //  create a path array with reversed order
        static int[] invert(int[] path)
        {
            int[] p = new int[path.length];
    
            for (int i = 0; i < path.length; i++)
            {
                p[i] = path[path.length - 1 - i];
            }
    
            return normalize(p);
        }
    
        //  rotate cycle path such that it begins with the smallest node
        static int[] normalize(int[] path)
        {
            int[] p = new int[path.length];
            int x = smallest(path);
            int n;
    
            System.arraycopy(path, 0, p, 0, path.length);
    
            while (p[0] != x)
            {
                n = p[0];
                System.arraycopy(p, 1, p, 0, p.length - 1);
                p[p.length - 1] = n;
            }
    
            return p;
        }
    
        //  compare path against known cycles
        //  return true, iff path is not a known cycle
        static Boolean isNew(int[] path)
        {
            Boolean ret = true;
    
            for(int[] p : cycles)
            {
                if (equals(p, path))
                {
                    ret = false;
                    break;
                }
            }
    
            return ret;
        }
    
        static void o(String s)
        {
            System.out.println(s);
        }
    
        //  return the int of the array which is the smallest
        static int smallest(int[] path)
        {
            int min = path[0];
    
            for (int p : path)
            {
                if (p < min)
                {
                    min = p;
                }
            }
    
            return min;
        }
    
        //  check if vertex n is contained in path
        static Boolean visited(int n, int[] path)
        {
            Boolean ret = false;
    
            for (int p : path)
            {
                if (p == n)
                {
                    ret = true;
                    break;
                }
            }
    
            return ret;
        }
    
    }
    
  • 29

    Axel,我已经将你的代码翻译成了python . 大约1/4的代码行和更清晰的阅读 .

    graph = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [2, 6], [4, 6], [8, 7], [8, 9], [9, 7]]
    cycles = []
    
    def main():
        global graph
        global cycles
        for edge in graph:
            for node in edge:
                findNewCycles([node])
        for cy in cycles:
            path = [str(node) for node in cy]
            s = ",".join(path)
            print(s)
    
    def findNewCycles(path):
        start_node = path[0]
        next_node= None
        sub = []
    
        #visit each edge and each node of each edge
        for edge in graph:
            node1, node2 = edge
            if start_node in edge:
                    if node1 == start_node:
                        next_node = node2
                    else:
                        next_node = node1
            if not visited(next_node, path):
                    # neighbor node not on path yet
                    sub = [next_node]
                    sub.extend(path)
                    # explore extended path
                    findNewCycles(sub);
            elif len(path) > 2  and next_node == path[-1]:
                    # cycle found
                    p = rotate_to_smallest(path);
                    inv = invert(p)
                    if isNew(p) and isNew(inv):
                        cycles.append(p)
    
    def invert(path):
        return rotate_to_smallest(path[::-1])
    
    #  rotate cycle path such that it begins with the smallest node
    def rotate_to_smallest(path):
        n = path.index(min(path))
        return path[n:]+path[:n]
    
    def isNew(path):
        return not path in cycles
    
    def visited(node, path):
        return node in path
    
    main()
    
  • 28

    这里只是一个非常蹩脚的MATLAB版本,该算法改编自上面的python代码,适用于任何可能需要它的人 .

    function cycleList = searchCycles(edgeMap)
    
        tic
        global graph cycles numCycles;
        graph = edgeMap;
        numCycles = 0;
        cycles = {};
        for i = 1:size(graph,1)
            for j = 1:2
                findNewCycles(graph(i,j))
            end
        end
        % print out all found cycles
        for i = 1:size(cycles,2)
            cycles{i}
        end
        % return the result
        cycleList = cycles;
        toc
    
    function findNewCycles(path)
    
        global graph cycles numCycles;
        startNode = path(1);
        nextNode = nan;
        sub = [];
    
        % visit each edge and each node of each edge
        for i = 1:size(graph,1)
            node1 = graph(i,1);
            node2 = graph(i,2);
            if node1 == startNode
                nextNode = node2;
            elseif node2 == startNode
                nextNode = node1;
            end
            if ~(visited(nextNode, path))
                % neighbor node not on path yet
                sub = nextNode;
                sub = [sub path];
                % explore extended path
                findNewCycles(sub);
            elseif size(path,2) > 2 && nextNode == path(end)
                % cycle found
                p = rotate_to_smallest(path);
                inv = invert(p);
                if isNew(p) && isNew(inv)
                    numCycles = numCycles + 1;
                    cycles{numCycles} = p;
                end
            end
        end
    
    function inv = invert(path)
        inv = rotate_to_smallest(path(end:-1:1));
    
    % rotate cycle path such that it begins with the smallest node
    function new_path = rotate_to_smallest(path)
        [~,n] = min(path);
        new_path = [path(n:end), path(1:n-1)];
    
    function result = isNew(path)
        global cycles
        result = 1;
        for i = 1:size(cycles,2)
            if size(path,2) == size(cycles{i},2) && all(path == cycles{i})
                result = 0;
                break;
            end
        end
    
    function result = visited(node,path)
        result = 0;
        if isnan(node) && any(isnan(path))
            result = 1;
            return
        end
        for i = 1:size(path,2)
            if node == path(i)
                result = 1;
                break
            end
        end
    
  • 0

    灵感来自@LetterRip和@Axel Kemper这是Java的缩写版本:

    public static int[][] graph =
            {
                    {1, 2}, {2, 3}, {3, 4}, {2, 4},
                    {3, 5}
            };
    public static Set<List<Integer>> cycles = new HashSet<>();
    
    static void findNewCycles(ArrayList<Integer> path) {
        int start = path.get(0);
        int next = -1;
        for (int[] edge : graph) {
            if (start == edge[0] || start == edge[1]) {
                next = (start == edge[0]) ? edge[1] : edge[0];
                if (!path.contains(next)) {
                    ArrayList<Integer> newPath = new ArrayList<>();
                    newPath.add(next);
                    newPath.addAll((path));
                    findNewCycles(newPath);
                } else if (path.size() > 2 && next == path.get(path.size() - 1)) {
                    List<Integer> normalized = new ArrayList<>(path);
                    Collections.sort(normalized);
                    cycles.add(normalized);
                }
            }
        }
    }
    
    public static void detectCycle() {
        for (int i = 0; i < graph.length; i++)
            for (int j = 0; j < graph[i].length; j++) {
                ArrayList<Integer> path = new ArrayList<>();
                path.add(graph[i][j]);
                findNewCycles(path);
            }
        for (List<Integer> c : cycles) {
            System.out.println(c);
        }
    }
    
  • 3

    这是上面的python代码的C版本:

    std::vector< std::vector<vertex_t> > Graph::findAllCycles()
    {
        std::vector< std::vector<vertex_t> > cycles;
    
        std::function<void(std::vector<vertex_t>)> findNewCycles = [&]( std::vector<vertex_t> sub_path )
        {
            auto visisted = []( vertex_t v, const std::vector<vertex_t> & path ){
                return std::find(path.begin(),path.end(),v) != path.end();
            };
    
            auto rotate_to_smallest = []( std::vector<vertex_t> path ){
                std::rotate(path.begin(), std::min_element(path.begin(), path.end()), path.end());
                return path;
            };
    
            auto invert = [&]( std::vector<vertex_t> path ){
                std::reverse(path.begin(),path.end());
                return rotate_to_smallest(path);
            };
    
            auto isNew = [&cycles]( const std::vector<vertex_t> & path ){
                return std::find(cycles.begin(), cycles.end(), path) == cycles.end();
            };
    
            vertex_t start_node = sub_path[0];
            vertex_t next_node;
    
            // visit each edge and each node of each edge
            for(auto edge : edges)
            {
                if( edge.has(start_node) )
                {
                    vertex_t node1 = edge.v1, node2 = edge.v2;
    
                    if(node1 == start_node)
                        next_node = node2;
                    else
                        next_node = node1;
    
                    if( !visisted(next_node, sub_path) )
                    {
                        // neighbor node not on path yet
                        std::vector<vertex_t> sub;
                        sub.push_back(next_node);
                        sub.insert(sub.end(), sub_path.begin(), sub_path.end());
                        findNewCycles( sub );
                    } 
                    else if( sub_path.size() > 2 && next_node == sub_path.back() )
                    {
                        // cycle found
                        auto p = rotate_to_smallest(sub_path);
                        auto inv = invert(p);
    
                        if( isNew(p) && isNew(inv) )
                            cycles.push_back( p );
                    }
                }
            }
        };
    
        for(auto edge : edges)
        {
            findNewCycles( std::vector<vertex_t>(1,edge.v1) );
            findNewCycles( std::vector<vertex_t>(1,edge.v2) );
        }
    }
    
  • 3

    这是上面python代码的vb .net版本:

    Module Module1
    '  Graph modelled as list of edges
    Public graph As Integer(,) = {{{1, 2}, {1, 3}, {1, 4}, {2, 3},
            {3, 4}, {2, 6}, {4, 6}, {7, 8},
            {8, 9}, {9, 7}}
    
    Public cycles As New List(Of Integer())()
    Sub Main()
        For i As Integer = 0 To graph.GetLength(0) - 1
            For j As Integer = 0 To graph.GetLength(1) - 1
                findNewCycles(New Integer() {graph(i, j)})
            Next
        Next
    
        For Each cy As Integer() In cycles
            Dim s As String
            s = cy(0)
            For i As Integer = 1 To cy.Length - 1
                s = s & "," & cy(i)
            Next
    
            Console.WriteLine(s)
            Debug.Print(s)
        Next
    
    End Sub
    Private Sub findNewCycles(path As Integer())
        Dim n As Integer = path(0)
        Dim x As Integer
        Dim [sub] As Integer() = New Integer(path.Length) {}
    
        For i As Integer = 0 To graph.GetLength(0) - 1
            For y As Integer = 0 To 1
                If graph(i, y) = n Then
                    '  edge referes to our current node
                    x = graph(i, (y + 1) Mod 2)
                    If Not visited(x, path) Then
                        '  neighbor node not on path yet
                        [sub](0) = x
                        Array.Copy(path, 0, [sub], 1, path.Length)
                        '  explore extended path
                        findNewCycles([sub])
                    ElseIf (path.Length > 2) AndAlso (x = path(path.Length - 1)) Then
                        '  cycle found
                        Dim p As Integer() = normalize(path)
                        Dim inv As Integer() = invert(p)
                        If isNew(p) AndAlso isNew(inv) Then
                            cycles.Add(p)
                        End If
                    End If
                End If
            Next
        Next
    End Sub
    
    Private Function equals(a As Integer(), b As Integer()) As Boolean
        Dim ret As Boolean = (a(0) = b(0)) AndAlso (a.Length = b.Length)
    
        Dim i As Integer = 1
        While ret AndAlso (i < a.Length)
            If a(i) <> b(i) Then
                ret = False
            End If
            i += 1
        End While
    
        Return ret
    End Function
    
    Private Function invert(path As Integer()) As Integer()
        Dim p As Integer() = New Integer(path.Length - 1) {}
    
        For i As Integer = 0 To path.Length - 1
            p(i) = path(path.Length - 1 - i)
        Next
    
        Return normalize(p)
    End Function
    
    '  rotate cycle path such that it begins with the smallest node
    Private Function normalize(path As Integer()) As Integer()
        Dim p As Integer() = New Integer(path.Length - 1) {}
        Dim x As Integer = smallest(path)
        Dim n As Integer
    
        Array.Copy(path, 0, p, 0, path.Length)
    
        While p(0) <> x
            n = p(0)
            Array.Copy(p, 1, p, 0, p.Length - 1)
            p(p.Length - 1) = n
        End While
    
        Return p
    End Function
    
    Private Function isNew(path As Integer()) As Boolean
        Dim ret As Boolean = True
    
        For Each p As Integer() In cycles
            If equals(p, path) Then
                ret = False
                Exit For
            End If
        Next
    
        Return ret
    End Function
    
    Private Function smallest(path As Integer()) As Integer
        Dim min As Integer = path(0)
    
        For Each p As Integer In path
            If p < min Then
                min = p
            End If
        Next
    
        Return min
    End Function
    
    Private Function visited(n As Integer, path As Integer()) As Boolean
        Dim ret As Boolean = False
    
        For Each p As Integer In path
            If p = n Then
                ret = True
                Exit For
            End If
        Next
    
        Return ret
    End Function
    

    结束模块

  • -1

    上面的循环查找器似乎有一些问题 . C#版本找不到一些周期 . 我的图是:

    {2,8},{4,8},{5,8},{1,9},{3,9},{4,9},{5,9},{6,9},{1,10},
      {4,10},{5,10},{6,10},{7,10},{1,11},{4,11},{6,11},{7,11},
      {1,12},{2,12},{3,12},{5,12},{6,12},{2,13},{3,13},{4,13},
      {6,13},{7,13},{2,14},{5,14},{7,14}
    

    例如,找不到循环: 1-9-3-12-5-10 . 我也尝试了C版本,它返回非常大(数千万)个循环次数,这显然是错误的 . 它可能无法匹配周期 .

    对不起,我有点紧张,我没有进一步调查 . 我根据Nikolay Ognyanov的帖子写了我自己的版本(非常感谢您的帖子) . 对于上图,我的版本返回8833个周期,我正在尝试验证它是否正确 . C#版本返回8397个周期 .

  • 1

    这是python代码的节点版本 .

    const graph = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [2, 6], [4, 6], [8, 7], [8, 9], [9, 7]]
    let cycles = []
    
    function main() {
      for (const edge of graph) {
        for (const node of edge) {
          findNewCycles([node])
        }
      }
      for (cy of cycles) {
        console.log(cy.join(','))
      }
    }
    
    function findNewCycles(path) {
      const start_node = path[0]
      let next_node = null
      let sub = []
    
      // visit each edge and each node of each edge
      for (const edge of graph) {
        const [node1, node2] = edge
        if (edge.includes(start_node)) {
          next_node = node1 === start_node ? node2 : node1
        }
        if (notVisited(next_node, path)) {
          // eighbor node not on path yet
          sub = [next_node].concat(path)
          // explore extended path
          findNewCycles(sub)
        } else if (path.length > 2 && next_node === path[path.length - 1]) {
          // cycle found
          const p = rotateToSmallest(path)
          const inv = invert(p)
          if (isNew(p) && isNew(inv)) {
            cycles.push(p)
          }
        }
      }
    }
    
    function invert(path) {
      return rotateToSmallest([...path].reverse())
    }
    
    // rotate cycle path such that it begins with the smallest node
    function rotateToSmallest(path) {
      const n = path.indexOf(Math.min(...path))
      return path.slice(n).concat(path.slice(0, n))
    }
    
    function isNew(path) {
      const p = JSON.stringify(path)
      for (const cycle of cycles) {
        if (p === JSON.stringify(cycle)) {
          return false
        }
      }
      return true
    }
    
    function notVisited(node, path) {
      const n = JSON.stringify(node)
      for (const p of path) {
        if (n === JSON.stringify(p)) {
          return false
        }
      }
      return true
    }
    
    main()
    
  • 2

    Matlab版本遗漏了一些东西,函数findNewCycles(path)应该是:

    function findNewCycles(path)

    global graph cycles numCycles;
    startNode = path(1);
    nextNode = nan;
    sub = [];
    
    % visit each edge and each node of each edge
    for i = 1:size(graph,1)
        node1 = graph(i,1);
        node2 = graph(i,2);
        if (node1 == startNode) || (node2==startNode) %% this if is required
            if node1 == startNode
                nextNode = node2;
            elseif node2 == startNode
                nextNode = node1;
            end
            if ~(visited(nextNode, path))
                % neighbor node not on path yet
                sub = nextNode;
                sub = [sub path];
                % explore extended path
                findNewCycles(sub);
            elseif size(path,2) > 2 && nextNode == path(end)
                % cycle found
                p = rotate_to_smallest(path);
                inv = invert(p);
                if isNew(p) && isNew(inv)
                    numCycles = numCycles + 1;
                    cycles{numCycles} = p;
                end
            end
        end
    end
    

相关问题