Help in the Donalds B. Johnson algorithm, I can not understand the pseudo-code (PART II)

Question

I can not understand a certain part of the article published by Donald Johnson on the search for cycles (schemes) on the chart.

More specifically, I cannot understand what the matrix Ak is, which is mentioned in the next line of pseudocode:

Ak: = the adjacency structure of the strong component K with the smallest vertex in the subgraph G, induced by {s, s + 1, ... n};

to aggravate some lines after the “cops” for me in Vk do, without declaring what Vk is ...

As I understand it, we have the following: 1) in the general case, the strong component is a subgraph of the graph, in which for each node of this subgraph there is a path to any node of the subgraph (in other words, you can access any node of the subgraph from any other node of the subgraph)

2) the subgraph induced by the list of nodes is a graph containing all these nodes and all the edges connecting these nodes. the mathematical definition in the document is: “F is the subgraph G induced by W if W is the subset of V and F = (W, {u, y) | u, y in W and (u, y) in E)}) where u, y are edges, E is the set of all edges in the graph, W is the set of nodes.

3) in the code implementation, nodes are called integers 1 ... n.

4) I suspect that Vk is the set of nodes of the strong component K.

now to the question. Suppose that we have a graph G = (V, E) with V = {1,2,3,4,5,6,7,8,9}, which can be divided into 3 strong components: SC1 = {1, 4,7,8} SC2 = {2,3,9} SC3 = {5,6} (and their edges)

Can someone give me an example for s = 1, s = 2, s = 5, what if you are going to be Vk and Ak according to the code?

Pseudocode in my previous question Understanding Pseudocode in Donald B. Johnson's Algorithm

and the document can be found in Understanding Pseudocode in Donald B. Johnson's Algorithm

early

Answer 1

It works! In the previous iteration Johnson's algorithm I suggested that A was an adjacency matrix . Instead, it is an adjacency list . In this example, implemented below, the vertices {a, b, c} are numbered {0, 1, 2}, which gives the following schemes.

Appendix: As noted in the proposed edit and useful, the algorithm indicates that unblock() should remove an element that has the value w , and not an element with the index w .

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

Output Example:

  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

By default, the program starts with s = 0 ; implementing s := least vertex in V since optimization remains. An option that produces only unique loops is shown 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

I sent an edit request to @trashgod code to fix the exception sent to unblock() . In fact, the algorithm states that the w element (which is not an index) should be removed from the list. The above code uses list.remove(w) , which treats w as an index.

My edit request was rejected! I don’t know why, because I tested above with my modification in a network of 20,000 nodes and 70,000 edges and did not work.

I also modified Johnson's algorithm to adapt more to undirected graphs. If anyone wants these changes, please contact me.

Below is my code for 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, your sample output contains a loop, which is a cyclic permutation. For example, 0-1-0 and 1-0-1 are the same. In fact, the output should contain only 5 cycles, i.e. 0 1 0, 0 2 0, 0 1 2 0, 0 2 1 0, 1 2 1,

Johnson's report explains what a cycle is: “Two elementary circuits are different if one of them is not a cyclic permutation of the other.” You can also check the tungsten page: it also outputs 5 cycles for the same input.

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

Answer 4

The following variation gives unique loops. Based on this example , it is adapted from the answer provided by @ user1406062 .

the code:

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

Output:

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

All cycles, for reference:

 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