Поиск всех циклов в неориентированных графах

Ответ 1

Для неориентированного графа стандартный подход состоит в том, чтобы искать так называемую базу циклов: набор простых циклов, из которых можно генерировать с помощью комбинаций все другие циклы. Это не обязательно все простые циклы в графе. Рассмотрим, например, следующий график:

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

Здесь есть три простых цикла: 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.

Базовый алгоритм может быть усовершенствован различными способами. Насколько мне известно, лучшее уточнение принадлежит Патону (К. Патон, Алгоритм нахождения фундаментального набора циклов для неориентированного линейного графа, Comm. ACM 12 (1969), с. 514-518.). Реализация с открытым исходным кодом на Java доступна здесь: http://code.google.com/p/niographs/.

Я должен был упомянуть, как вы комбинируете простые циклы из базы циклов, чтобы сформировать новые простые циклы. Вы начинаете с перечисления в любом (но исправленном ниже) порядке всех ребер графа. Затем вы представляете циклы последовательностями нулей и единиц, помещая единицы в позиции ребер, которые принадлежат циклу, и нули в позиции ребер, которые не являются частью цикла. Затем вы делаете битовое исключающее ИЛИ (XOR) последовательностей. Причина, по которой вы делаете XOR, заключается в том, что вы хотите исключить ребра, которые принадлежат обоим циклам, и, таким образом, сделать комбинированный цикл непростым. Вам также необходимо проверить, что 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). Теперь мы можем, например, XOR A-B-C-A с B-D-C-B, и результат будет (1, 1, 0, 1, 1), который является точно A-B-D-C-A. Или мы можем XOR A-B-C-A и A-B-D-C-A с результатом (0, 0, 1, 1, 1). Что именно B-D-C-B.

С учетом базы циклов вы можете обнаружить все простые циклы, изучив все возможные комбинации из 2 или более различных базовых циклов. Более подробно процедура описана здесь: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf на стр. 14.

Для полноты картины я бы заметил, что кажется возможным (и неэффективным) использовать алгоритмы для нахождения всех простых циклов ориентированного графа. Каждое ребро неориентированного графа можно заменить двумя направленными ребрами, идущими в противоположных направлениях. Тогда алгоритмы для ориентированных графов должны работать. Будет 1 "ложный" цикл из 2 узлов для каждого ребра неориентированного графа, который необходимо игнорировать, и будет версия по часовой стрелке и против часовой стрелки каждого простого цикла неориентированного графа. Реализация с открытым исходным кодом в Java алгоритмов для нахождения всех циклов в ориентированном графе может быть найдена по ссылке, которую я уже цитировал.

Ответ 2

Ниже приведена демонстрационная реализация на С# (и Java, см. конец ответа) на основе первого поиска глубины.

Внешний цикл проверяет все узлы графика и запускает поиск из каждого node. Node соседние (по списку ребер) добавляются к циклу цикла. Рекурсия завершается, если не может быть добавлено больше не посещаемых соседей. Новый цикл найден, если путь длиннее двух узлов, а следующий сосед - это начало пути. Чтобы избежать повторяющихся циклов, циклы нормализуются поворотом наименьшего Node до начала. Учитываются также циклы в обратном порядке.

Это просто наивная реализация. Классическая статья: Дональд Б. Джонсон. Поиск всех элементарных схем ориентированного графа. SIAM J. Comput., 4 (1): 77-84, 1975.

Недавний обзор современных алгоритмов можно найти здесь

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;
    }

}

Ответ 3

Аксель, я перевел твой код на 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()

Ответ 4

Здесь просто очень хромая версия 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

Ответ 5

Ниже приведена версия кода Python на С++:

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) );
    }
}

Ответ 6

Вдохновленный @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);
    }
}

Ответ 7

Ниже приведена версия vb.net кода python выше:

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

Конечный модуль

Ответ 8

Кажется, что вышеописанный алгоритм имеет некоторые проблемы. Версия С# не может найти несколько циклов. Мой график:

  {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 не найден. Я также попробовал версию на С++, он возвращает очень большое (десятки миллионов) количество циклов, что, по-видимому, неверно. Вероятно, он не соответствует циклам.

Извините, у меня немного хруст, и я еще не исследовал его. Я написал свою собственную версию на основе поста Николая Огнянова (большое спасибо за ваш пост). Для графика выше моя версия возвращает 8833 цикла, и я пытаюсь проверить, что это правильно. Версия С# возвращает 8397 циклов.

Ответ 9

Вот версия узла кода 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()

Ответ 10

Версия Matlab пропустила что-то, функция findNewCycles (path) должна быть:

функция findNewCycles (путь)

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