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

pseudocodigo mientras ejemplos

Question

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

Más específico no puedo entender cuál es la matriz Ak que se menciona en la siguiente línea del pseudo código:

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

para empeorar las cosas, algunas líneas después mentins "para mí en Vk do" sin declarar lo que es el Vk ...

Hasta donde he entendido, tenemos lo siguiente: 1) en general, un componente fuerte es un sub-gráfico de un gráfico, en el cual 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 inducido por una lista de nodos es un gráfico que contiene todos estos nodos más todos los bordes que conectan estos nodos. 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 del 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) Sospecho que el Vk es el conjunto de nodos del componente fuerte K.

ahora a la pregunta. 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, el SC1 = {1, 4,7,8} SC2 = {2,3,9} SC3 = {5,6} (y sus bordes)

¿Alguien puede darme un ejemplo para s = 1, s = 2, s = 5? ¿Y si va a ser el Vk y el Ak según el código?

El pseudo código está en mi pregunta anterior en Understanding the pseudocode en el algoritmo de Donald B. Johnson

y el artículo se puede encontrar en Understanding the pseudocode en el algoritmo de Donald B. Johnson

gracias de antemano

Answer 1

@trashgod, su salida de muestra contiene un ciclo que es una permutación cíclica. Por ejemplo, 0-1-0 y 1-0-1 son los mismos. En realidad, la salida debe contener solo 5 ciclos, 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. ''Uno también puede verificar la página wolfram: Esto también muestra 5 ciclos para la misma entrada.

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

Answer 2

He enviado una solicitud de edición al código de @ trashgod para corregir la excepción lanzada en unblock() . Esencialmente, el algoritmo establece que el elemento w (que no es un índice) debe eliminarse de la lista. El código anterior usa list.remove(w) , que trata w como un índice.

¡Mi solicitud de edición fue rechazada! 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 modifiqué 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

La siguiente variación produce ciclos únicos. En base a este ejemplo , se adapta de una respuesta proporcionada 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://.com/questions/2908575
 * @see https://.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, para 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

Answer 4

¡Funciona! En una iteración anterior del algoritmo de Johnson , había supuesto que A era una matriz de adyacencia . En cambio, parece representar una lista de adyacencia . 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 señala en esta edición propuesta y respuesta útil, el algoritmo especifica que unblock() debería eliminar el elemento que tiene el valor w , no el elemento que tiene el índice w .

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

Muestra de salida:

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 ya que queda una optimización. Aquí se muestra una variación que produce solo ciclos únicos.

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://.com/questions/2908575
 * @see https://.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;
            }
        }
    }
}