graph - protocolo - Encontrar todos los ciclos en gráficos no dirigidos

open graphs

Question

Necesito un algoritmo de trabajo para encontrar todos los ciclos simples en un gráfico no dirigido. Sé que el costo puede ser exponencial y el problema es NP-completo, pero voy a usarlo en un pequeño gráfico (hasta 20-30 vértices) y los ciclos son pequeños en número.

Después de una larga investigación (principalmente aquí) aún no tengo un enfoque de trabajo. Aquí hay un resumen de mi búsqueda:

Encontrar todos los ciclos en un gráfico no dirigido

Ciclos en un gráfico no dirigido -> detecta solo si hay un ciclo o no

Encontrar polígonos dentro de un Gráfico no dirigido -> descripción muy bonita, pero no hay solución

Encontrar todos los ciclos en un gráfico dirigido -> encuentra ciclos solo en gráficos dirigidos

Detecta ciclos en gráfico no dirigido usando la biblioteca de gráficos de impulso

La única respuesta que encontré, que se acerca a mi problema, es esta:

Encuentra todos los ciclos en gráfico, redux

Parece que encontrar un conjunto básico de ciclos y XOR-ing podría hacer el truco. Encontrar un conjunto básico de ciclos es fácil, pero no entiendo cómo combinarlos para obtener todos los ciclos en el gráfico ...

Answer 1

Aquí hay una versión C ++ del código python anterior:

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

Answer 2

Aquí hay una versión MATLAB muy corta de este algoritmo adaptado del código python anterior, para cualquier persona que pueda necesitarlo también.

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

Answer 3

Aquí hay una versión del nodo del código 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()

Answer 4

Aquí hay una versión vb .net del código python anterior:

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

Módulo final

Answer 5

Axel, he traducido tu código a Python. Aproximadamente 1/4 de las líneas de código y más claras para leer.

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()

Answer 6

Inspirado por @LetterRip y @Axel Kemper Aquí hay una versión más corta de 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);
    }
}

Answer 7

La siguiente es una implementación de demostración en C # (y Java, ver el final de la respuesta) basada en la primera búsqueda de profundidad.

Un bucle externo escanea todos los nodos del gráfico e inicia una búsqueda desde cada nodo. Los vecinos del nodo (de acuerdo con la lista de bordes) se agregan a la ruta del ciclo. La recursividad finaliza si no se pueden agregar más vecinos no visitados. Se encuentra un nuevo ciclo si la ruta es más larga que dos nodos y el siguiente vecino es el inicio de la ruta. Para evitar ciclos duplicados, los ciclos se normalizan girando el nodo más pequeño al inicio. Los ciclos en orden invertido también se tienen en cuenta.

Esto es solo una implementación ingenua. El periódico clásico es: Donald B. Johnson. Encontrar todos los circuitos elementales de un grafo dirigido. SIAM J. Comput., 4 (1): 77 - 84, 1975.

Una encuesta reciente de algoritmos modernos se puede encontrar 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;
        }
    }
}

Los ciclos para el gráfico de demostración:

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

El algoritmo codificado en 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;
    }

}

Answer 8

La versión de Matlab omitió algo, la función findNewCycles (ruta) debería ser:

función findNewCycles (ruta)

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

Answer 9

Para un gráfico no dirigido, el enfoque estándar es buscar una llamada base de ciclo: un conjunto de ciclos simples a partir de los cuales se puede generar mediante combinaciones de todos los demás ciclos. Estos no son necesariamente todos los ciclos simples en el gráfico. Considere por ejemplo el siguiente gráfico:

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

Aquí hay 3 ciclos simples: ABCA, BCDB y ABDCA. Sin embargo, puede tomar cada 2 de estos como base y obtener el 3d como una combinación del 2. Esto es una diferencia sustancial de los gráficos dirigidos donde uno no puede combinar ciclos tan libremente debido a la necesidad de observar la dirección del borde.

El algoritmo de referencia estándar para encontrar una base de ciclo para un gráfico no dirigido es este: construya un árbol de expansión y luego para cada borde que no sea parte del árbol, construya un ciclo desde ese borde y algunos bordes en el árbol. Tal ciclo debe existir porque de lo contrario el borde sería parte del árbol.

Para el gráfico de muestra de arriba, un árbol de expansión es, por ejemplo, este:

    A 
  /   /
B      C
  / 
    D

Los 2 bordes que no están en el árbol son BC y CD. Y los ciclos simples correspondientes son ABCA y ABDCA.

También puedes construir el siguiente árbol de expansión:

    A 
  /   
B ----- C
  /   
    D

Y luego los ciclos simples que obtienes son ABCA y BCDB.

El algoritmo de línea de base se puede refinar de diferentes maneras. Que yo sepa, el mejor refinamiento pertenece a Paton (K. Paton, un algoritmo para encontrar un conjunto fundamental de ciclos para un gráfico lineal no dirigido, Comm. ACM 12 (1969), pp. 514-518). Una implementación de código abierto en Java está disponible aquí: http://code.google.com/p/niographs/ .

Debería haber mencionado cómo combinas ciclos simples de la base del ciclo para formar nuevos ciclos simples. Comience enumerando en cualquier orden (pero fijo en el más allá) todos los bordes del gráfico. Luego, representa los ciclos por secuencias de ceros y unos colocando los que están en las posiciones de los bordes que pertenecen al ciclo y los ceros en las posiciones de los bordes que no son parte del ciclo. A continuación, realiza O exclusivo en modo bit (XOR) de las secuencias. La razón por la que hace XOR es que quiere excluir los bordes que pertenecen a ambos ciclos y así hacer que el ciclo combinado no sea simple. También debe comprobar que los 2 ciclos tienen ALGUNOS bordes comunes comprobando que el AND bit a bit de las secuencias no es todo ceros. De lo contrario, el resultado de XOR será de 2 ciclos disjuntos en lugar de un nuevo ciclo simple.

Aquí hay un ejemplo para el gráfico de muestra anterior:

Comenzamos enumerando los bordes: ((AB), (AC), (BC), (BD), (CD)). Luego, los ciclos simples ABCA, BDCB y ABDCA se representan como (1, 1, 1, 0, 0), (0, 0, 1, 1, 1) y (1, 1, 0, 1, 1). Ahora podemos, por ejemplo, XOR ABCA con BDCB y el resultado es (1, 1, 0, 1, 1) que es exactamente ABDCA. O podemos XOR ABCA y ABDCA con el resultado de (0, 0, 1, 1, 1). Que es exactamente BDCB.

Dada una base de ciclo, puede descubrir todos los ciclos simples al examinar todas las combinaciones posibles de 2 o más ciclos básicos distintos. El procedimiento se describe con más detalle aquí: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf en la página 14.

En aras de la exhaustividad, notaría que parece posible (e ineficiente) usar algoritmos para encontrar todos los ciclos simples de un gráfico dirigido. Cada borde del gráfico no dirigido puede reemplazarse por 2 bordes dirigidos que van en direcciones opuestas. Entonces los algoritmos para gráficos dirigidos deberían funcionar. Habrá 1 ciclo "falso" de 2 nodos para cada borde del gráfico no dirigido que deberá ignorarse y habrá una versión en sentido horario y una antihoraria de cada ciclo simple del gráfico no dirigido. La implementación de código abierto en Java de algoritmos para encontrar todos los ciclos en un gráfico dirigido se puede encontrar en el enlace que ya cité.

Answer 10

Parece que el buscador de ciclos anterior tiene algunos problemas. La versión de C # no puede encontrar algunos ciclos. Mi gráfica es:

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

Por ejemplo, el ciclo: 1-9-3-12-5-10 no se encuentra. Probé la versión C ++ también, devuelve un gran número (decenas de millones) de ciclos que aparentemente es incorrecto. Probablemente, no coincide con los ciclos.

Lo siento, estoy un poco arruinado y no he investigado más. Escribí mi propia versión basada en la publicación de Nikolay Ognyanov (muchas gracias por su publicación). Para el gráfico anterior, mi versión devuelve 8833 ciclos y estoy intentando verificar que sea correcta. La versión C # devuelve 8397 ciclos.