ayuda en el algoritmo de Donalds B. Johnson, no puedo entender el pseudo código (PARTE II)

Question

no puedo entender una cierta parte del artículo publicado por Donald Johnson sobre encontrar ciclos (Circuitos) en un gráfico.

más específica i no pueden entender lo es la matriz Ak que se menciona en la siguiente línea de la pseudo código:

Ak: = estructura de adyacencia de fuerte componente K con menos vértice en subgrafo de G inducido por { s, s + 1, .... n};

a empeorar las cosas algunas líneas después de que se mentins "para i en Vk no" sin declarar lo que el Vk es ...

Por lo que tengo entender que tenemos la siguiente: 1) en general, una componente fuerte es un sub-gráfico de un gráfico, en el que para cada nodo de este sub-gráfico hay una ruta a cualquier nodo del sub-gráfico (en otras palabras, puede acceder a cualquier nodo del sub-gráfico desde cualquier otro nodo del sub-gráfico)

2) un sub-gráfico inducida por una lista de nodos es un gráfico que contiene todos estos nodos además de todos los bordes que conectan estos nodo s. en papel la definición matemática es "F es un subgrafo de G inducido por W si W es un subconjunto de V y F = (W, {u, y) | u, y en W y (u, y) en E)}) donde u, y son bordes, E es el conjunto de todos los bordes en el gráfico, W es un conjunto de nodos.

3) en la implementación del código, los nodos se nombran por números enteros 1 ... n.

4) I sospechoso que el Vk es el conjunto de nodos de la fuerte componente K.

ahora a la cuestión. digamos que tenemos un gráfico G = (V, E) con V = { 1,2,3,4,5,6,7,8,9} que se puede dividir en 3 componentes fuertes SC1 = {1,4,7,8} SC2 = {2,3,9} SC3 = {5,6} (y sus bordes)

¿Alguien me puede dar un ejemplo para s = 1, s = 2, s = 5 qué pasa si es Vk y Ak según el código?

El pseudo código está en mi pregunta anterior en Understanding the pseudocode in the Donald B. Johnson's algorithm

y el documento se puede encontrar en Understanding the pseudocode in the Donald B. Johnson's algorithm

gracias de antemano

Answer 1

Funciona! En un earlier iteration del Johnson algorithm, había supuesto que A era un adjacency matrix. En cambio, parece representar un adjacency list. En ese ejemplo, implementado a continuación, los vértices {a, b, c} están numerados {0, 1, 2}, produciendo los siguientes circuitos.

Adición: Como se ha señalado en este propuso edit y útil answer, el algoritmo especifica que unblock() debe quitar el elemento que tiene el valor w, no el elemento que tiene el índice de w.salida

list.remove(Integer.valueOf(w)); 

muestra:

 
0 1 0 
0 1 2 0 
0 2 0 
0 2 1 0 
1 0 1 
1 0 2 1 
1 2 0 1 
1 2 1 
2 0 1 2 
2 0 2 
2 1 0 2 
2 1 2 

Por defecto, el programa comienza con s = 0; implementando s := least vertex in V como una optimización permanece. Se muestra una variación que produce solo ciclos únicos here.

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 
import java.util.Stack; 

/** 
* @see http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf 
* @see https://stackoverflow.com/questions/2908575 
* @see https://stackoverflow.com/questions/2939877 
* @see http://en.wikipedia.org/wiki/Adjacency_matrix 
* @see http://en.wikipedia.org/wiki/Adjacency_list 
*/ 
public final class CircuitFinding { 

    final Stack<Integer> stack = new Stack<Integer>(); 
    final List<List<Integer>> a; 
    final List<List<Integer>> b; 
    final boolean[] blocked; 
    final int n; 
    int s; 

    public static void main(String[] args) { 
     List<List<Integer>> a = new ArrayList<List<Integer>>(); 
     a.add(new ArrayList<Integer>(Arrays.asList(1, 2))); 
     a.add(new ArrayList<Integer>(Arrays.asList(0, 2))); 
     a.add(new ArrayList<Integer>(Arrays.asList(0, 1))); 
     CircuitFinding cf = new CircuitFinding(a); 
     cf.find(); 
    } 

    /** 
    * @param a adjacency structure of strong component K with 
    * least vertex in subgraph of G induced by {s, s + 1, n}; 
    */ 
    public CircuitFinding(List<List<Integer>> a) { 
     this.a = a; 
     n = a.size(); 
     blocked = new boolean[n]; 
     b = new ArrayList<List<Integer>>(); 
     for (int i = 0; i < n; i++) { 
      b.add(new ArrayList<Integer>()); 
     } 
    } 

    private void unblock(int u) { 
     blocked[u] = false; 
     List<Integer> list = b.get(u); 
     for (int w : list) { 
      //delete w from B(u); 
      list.remove(Integer.valueOf(w)); 
      if (blocked[w]) { 
       unblock(w); 
      } 
     } 
    } 

    private boolean circuit(int v) { 
     boolean f = false; 
     stack.push(v); 
     blocked[v] = true; 
     L1: 
     for (int w : a.get(v)) { 
      if (w == s) { 
       //output circuit composed of stack followed by s; 
       for (int i : stack) { 
        System.out.print(i + " "); 
       } 
       System.out.println(s); 
       f = true; 
      } else if (!blocked[w]) { 
       if (circuit(w)) { 
        f = true; 
       } 
      } 
     } 
     L2: 
     if (f) { 
      unblock(v); 
     } else { 
      for (int w : a.get(v)) { 
       //if (v∉B(w)) put v on B(w); 
       if (!b.get(w).contains(v)) { 
        b.get(w).add(v); 
       } 
      } 
     } 
     v = stack.pop(); 
     return f; 
    } 

    public void find() { 
     while (s < n) { 
      if (a != null) { 
       //s := least vertex in V; 
       L3: 
       circuit(s); 
       s++; 
      } else { 
       s = n; 
      } 
     } 
    } 
} 

Answer 2

había sumbitted una solicitud edit al código de @ trashgod para fijar la excepción lanzada en unblock(). Básicamente, el algoritmo indica que el elemento w (que es no un índice) debe eliminarse de la lista. El código anterior usó list.remove(w), que trata w como índice.

Mi pedido edit fue rechazado. No estoy seguro por qué, porque he probado lo anterior con mi modificación en una red de 20,000 nodos y 70,000 bordes y no se cuelga.

También he modificado el algoritmo de Johnson para que esté más adaptado a los gráficos no dirigidos. Si alguien quiere estas modificaciones, contácteme.

A continuación está mi código para unblock().

private void unblock(int u) { 
    blocked[u] = false; 
    List<Integer> list = b.get(u); 
    int w; 
    for (int iw=0; iw < list.size(); iw++) { 
     w = Integer.valueOf(list.get(iw)); 
     //delete w from B(u); 
     list.remove(iw); 
     if (blocked[w]) { 
      unblock(w); 
     } 
    } 
} 

Answer 3

@trashgod, su salida de muestra contiene ciclos que son permutaciones cíclicas. Por ejemplo 0-1-0 y 1-0-1 son mismo En realidad la salida debe contiene sólo 5 ciclo es decir 0 1 0, 0 2 0, 0 1 2 0, 0 2 1 0, 1 2 1,

El artículo de Johnson explica qué es un ciclo: 'Dos circuitos elementales son distintos si uno no es una permutación cíclica del otro. ' También se puede verificar la página wolfram: Esto también muestra 5 ciclos para la misma entrada.

http://demonstrations.wolfram.com/EnumeratingCyclesOfADirectedGraph/

Answer 4

la siguiente variación produce ciclos únicos. Basado en este example, está adaptado de answer suministrado por @user1406062.

Código:

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Map; 
import java.util.Stack; 

/** 
* @see https://en.wikipedia.org/wiki/Johnson%27s_algorithm 
* @see https://stackoverflow.com/questions/2908575 
* @see https://stackoverflow.com/questions/2939877 
* @see http://en.wikipedia.org/wiki/Adjacency_matrix 
* @see http://en.wikipedia.org/wiki/Adjacency_list 
*/ 
public final class CircuitFinding { 

    final Stack<Integer> stack = new Stack<Integer>(); 
    final Map<Integer, List<Integer>> a; 
    final List<List<Integer>> b; 
    final boolean[] blocked; 
    final int n; 
    Integer s; 

    public static void main(String[] args) { 
     List<List<Integer>> a = new ArrayList<List<Integer>>(); 
     a.add(new ArrayList<Integer>(Arrays.asList(1, 2))); 
     a.add(new ArrayList<Integer>(Arrays.asList(0, 2))); 
     a.add(new ArrayList<Integer>(Arrays.asList(0, 1))); 
     CircuitFinding cf = new CircuitFinding(a); 
     cf.find(); 
    } 

    /** 
    * @param a adjacency structure of strong component K with least vertex in 
    * subgraph of G induced by {s, s + 1, n}; 
    */ 
    public CircuitFinding(List<List<Integer>> A) { 
     this.a = new HashMap<Integer, List<Integer>>(A.size()); 
     for (int i = 0; i < A.size(); i++) { 
      this.a.put(i, new ArrayList<Integer>()); 
      for (int j : A.get(i)) { 
       this.a.get(i).add(j); 
      } 
     } 
     n = a.size(); 
     blocked = new boolean[n]; 
     b = new ArrayList<List<Integer>>(); 
     for (int i = 0; i < n; i++) { 
      b.add(new ArrayList<Integer>()); 
     } 
    } 

    private void unblock(int u) { 
     blocked[u] = false; 
     List<Integer> list = b.get(u); 
     for (int w : list) { 
      //delete w from B(u); 
      list.remove(Integer.valueOf(w)); 
      if (blocked[w]) { 
       unblock(w); 
      } 
     } 
    } 

    private boolean circuit(int v) { 
     boolean f = false; 
     stack.push(v); 
     blocked[v] = true; 
     L1: 
     for (int w : a.get(v)) { 
      if (w == s) { 
       //output circuit composed of stack followed by s; 
       for (int i : stack) { 
        System.out.print(i + " "); 
       } 
       System.out.println(s); 
       f = true; 
      } else if (!blocked[w]) { 
       if (circuit(w)) { 
        f = true; 
       } 
      } 
     } 
     L2: 
     if (f) { 
      unblock(v); 
     } else { 
      for (int w : a.get(v)) { 
       //if (v∉B(w)) put v on B(w); 
       if (!b.get(w).contains(v)) { 
        b.get(w).add(v); 
       } 
      } 
     } 
     v = stack.pop(); 
     return f; 
    } 

    public void find() { 
     s = 0; 
     while (s < n) { 
      if (!a.isEmpty()) { 
       //s := least vertex in V; 
       L3: 
       for (int i : a.keySet()) { 
        b.get(i).clear(); 
        blocked[i] = false; 
       } 
       circuit(s); 
       a.remove(s); 
       for (Integer j : a.keySet()) { 
        if (a.get(j).contains(s)) { 
         a.get(j).remove(s); 
        } 
       } 
       s++; 
      } else { 
       s = n; 
      } 
     } 
    } 
} 

Salida:

0 1 0 
0 1 2 0 
0 2 0 
0 2 1 0 
1 2 1 

Todos los ciclos, como referencia:

0 1 0 
0 1 2 0 
0 2 0 
0 2 1 0 
1 0 1 
1 0 2 1 
1 2 0 1 
1 2 1 
2 0 1 2 
2 0 2 
2 1 0 2 
2 1 2