algorithm - una - superponer graficas en r

¿Cómo puedo verificar si un gráfico dirigido es acíclico?

Question

¿Cómo puedo verificar si un gráfico dirigido es acíclico? ¿Y cómo se llama el algoritmo? Agradecería una referencia.

Answer 1

Aquí está mi implementación de ruby ​​del algoritmo del nodo peel off leaf .

def detect_cycles(initial_graph, number_of_iterations=-1)
    # If we keep peeling off leaf nodes, one of two things will happen
    # A) We will eventually peel off all nodes: The graph is acyclic.
    # B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic.
    graph = initial_graph
    iteration = 0
    loop do
        iteration += 1
        if number_of_iterations > 0 && iteration > number_of_iterations
            raise "prevented infinite loop"
        end

        if graph.nodes.empty?
            #puts "the graph is without cycles"
            return false
        end

        leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? }

        if leaf_nodes.empty?
            #puts "the graph contain cycles"
            return true
        end

        nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) }
        edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) }
        graph = Graph.new(nodes2, edges2)
    end
    raise "should not happen"
end

Answer 2

Aquí hay un código rápido para encontrar si un gráfico tiene ciclos:

func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool
{

    if(breadCrumb[root] == true)
    {
        return true;
    }

    if(visited[root] == true)
    {
        return false;
    }

    visited[root] = true;

    breadCrumb[root] = true;

    if(G[root] != nil)
    {
        for child : Int in G[root]!
        {
            if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb))
            {
                return true;
            }
        }
    }

    breadCrumb[root] = false;
    return false;
}


let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]];

var visited = [false,false,false,false,false,false,false,false,false];
var breadCrumb = [false,false,false,false,false,false,false,false,false];




var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb)

La idea es así: un algoritmo dfs normal con una matriz para realizar un seguimiento de los nodos visitados, y una matriz adicional que sirve como marcador para los nodos que conducen al nodo actual, de modo que siempre que ejecutemos un dfs para un nodo establecemos su elemento correspondiente en la matriz de marcadores como verdadero, de modo que cuando se encuentre un nodo ya visitado, verificamos si su elemento correspondiente en la matriz de marcadores es verdadero, si es verdadero, entonces es uno de los nodos que se lo permite a sí mismo (de ahí ciclo), y el truco es que cada vez que devuelve un dfs de un nodo, establecemos su marcador correspondiente en falso, de modo que si lo volvemos a visitar de otra ruta no nos engañemos.

Answer 3

Hacer una simple búsqueda en profundidad no es suficiente para encontrar un ciclo. Es posible visitar un nodo varias veces en un DFS sin un ciclo existente. Dependiendo de dónde empiece, es posible que no visite todo el gráfico.

Puede verificar ciclos en un componente conectado de un gráfico de la siguiente manera. Encuentra un nodo que solo tenga bordes salientes. Si no hay tal nodo, entonces hay un ciclo. Comience un DFS en ese nodo. Al atravesar cada borde, compruebe si el borde apunta a un nodo que ya está en su pila. Esto indica la existencia de un ciclo. Si no encuentra ese borde, no hay ciclos en ese componente conectado.

Como señala Rutger Prins, si su gráfico no está conectado, necesita repetir la búsqueda en cada componente conectado.

Como referencia, el algoritmo de componente fuertemente conectado de Tarjan está estrechamente relacionado. También lo ayudará a encontrar los ciclos, no solo a informar si existen.

Answer 4

Intentaría ordenar el gráfico topológicamente , y si no puede, entonces tiene ciclos.

Answer 5

La solución dada por ShuggyCoUk es incompleta porque podría no verificar todos los nodos.

def isDAG(nodes V):
    while there is an unvisited node v in V:
        bool cycleFound = dfs(v)
        if cyclefound:
            return false
    return true

Esto tiene timecomplexity O (n + m) o O (n ^ 2)

Answer 6

No debe haber ningún borde posterior al hacer DFS. Mantenga la pista de los nodos ya visitados mientras hace DFS, si encuentra un borde entre el nodo actual y el existente, entonces el gráfico tiene un ciclo.

Answer 7

Sé que este es un tema antiguo, pero para los buscadores del futuro aquí hay una implementación de C # que he creado (¡ningún reclamo de que sea más eficiente!). Esto está diseñado para usar un número entero simple para identificar cada nodo. Puedes decorar eso como desees siempre que los hashes de objetos de tu nodo sean iguales.

Para gráficos muy profundos, esto puede tener una gran sobrecarga, ya que crea un hashset en cada nodo en profundidad (se destruyen a lo ancho).

Usted ingresa el nodo desde el que desea buscar y la ruta lleva a ese nodo.

• Para un gráfico con un único nodo raíz envía ese nodo y un hashset vacío
• Para un gráfico que tenga múltiples nodos raíz, envuelva esto en un foreach sobre esos nodos y pase un nuevo hashset vacío para cada iteración.

• Al verificar ciclos debajo de cualquier nodo dado, simplemente pase ese nodo junto con un hashset vacío

  private bool FindCycle(int node, HashSet<int> path)
  {
  
      if (path.Contains(node))
          return true;
  
      var extendedPath = new HashSet<int>(path) {node};
  
      foreach (var child in GetChildren(node))
      {
          if (FindCycle(child, extendedPath))
              return true;
      }
  
      return false;
  }

Answer 8

Solución 1 : Algoritmo de Kahn para verificar el ciclo . Idea principal: mantener una cola donde el nodo con grado cero se agregará a la cola. A continuación, despegue el nodo uno por uno hasta que la cola esté vacía. Verifique si los bordes internos de cualquier nodo existen.

Solución2 : Algoritmo de Tarjan para verificar el componente fuerte conectado.

Solución 3 : DFS . Use la matriz de enteros para etiquetar el estado actual del nodo: es decir, 0 - significa que este nodo no se ha visitado anteriormente. -1 - significa que se ha visitado este nodo y se están visitando sus nodos secundarios. 1 - significa que este nodo ha sido visitado, y está hecho. Entonces, si el estado de un nodo es -1 mientras se realiza el DFS, significa que debe existir un ciclo.

Answer 9

Lema 22.11 sobre el libro Introduction to Algorithms (Segunda edición) establece que:

Un gráfico dirigido G es acíclico si y solo si una búsqueda en profundidad de G no produce bordes posteriores