Help in the Donalds B. Johnson's algorithm, I cannot understand the pseudo code (PART II)?

It works! In an earlier iteration of the Johnson algorithm I had supposed that A was an adjacency matrix Instead, it appears to represent an adjacency list In that example, implemented below, the vertices {a, b, c} are numbered {0, 1, 2}, yielding the following circuits: 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 as an optimization remains import java.util. ArrayList; import java.util.

Arrays; import java.util. List; import java.util. Stack; /** * @see dutta.csc.ncsu.edu/csc791_spring07/wrap/... * @see stackoverflow.com/questions/2908575 * @see stackoverflow.com/questions/2939877 * @see en.wikipedia.org/wiki/Adjacency_matrix * @see en.wikipedia.org/wiki/Adjacency_list */ public final class CircuitFinding { final Stack stack = new Stack(); final List a; final List b; final boolean blocked; final int n; int s; public static void main(String args) { List a = new ArrayList(); a.

Add(new ArrayList(Arrays. AsList(1, 2))); a. Add(new ArrayList(Arrays.

AsList(0, 2))); a. Add(new ArrayList(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 a) { this.

A = a; n = a.size(); blocked = new booleann; be = new ArrayList(); for (int I = 0; I Remove(w); if (blockedw) { unblock(w); } } } private boolean circuit(int v) { boolean f = false; stack. Push(v); blockedv = 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 (!blockedw) { 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(v).

Add(w); } } } v = stack.pop(); return f; } public void find() { while (s.

It works! In an earlier iteration of the Johnson algorithm, I had supposed that A was an adjacency matrix. Instead, it appears to represent an adjacency list.In that example, implemented below, the vertices {a, b, c} are numbered {0, 1, 2}, yielding the following circuits: 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 as an optimization remains.

Import java.util. ArrayList; import java.util. Arrays; import java.util.

List; import java.util. Stack; /** * @see dutta.csc.ncsu.edu/csc791_spring07/wrap/... * @see stackoverflow.com/questions/2908575 * @see stackoverflow.com/questions/2939877 * @see en.wikipedia.org/wiki/Adjacency_matrix * @see http://en.wikipedia.org/wiki/Adjacency_list */ public final class CircuitFinding { final Stack stack = new Stack(); final List a; final List b; final boolean blocked; final int n; int s; public static void main(String args) { List a = new ArrayList(); a. Add(new ArrayList(Arrays.

AsList(1, 2))); a. Add(new ArrayList(Arrays. AsList(0, 2))); a.

Add(new ArrayList(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 a) { this. A = a; n = a.size(); blocked = new booleann; be = new ArrayList(); for (int I = 0; I Remove(w); if (blockedw) { unblock(w); } } } private boolean circuit(int v) { boolean f = false; stack.

Push(v); blockedv = 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 (!blockedw) { 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(v). Add(w); } } } v = stack.pop(); return f; } public void find() { while (s.

1 Wow, hope it wasn't his bachelor thesis. – stacker Jun 1 '10 at 20:14 @stacker: I hope not! Paraphrasing Knuth: "Beware of bugs in the above code; I have only tried it, not proved it correct." – trashgod Jun 2 '10 at 2:34 @trashgod Thank you for your kind and very usefull help @stacker basically is my a small part of my MSC dissertation but it's no problem as I have already wrote most of the code plus I use totally different structures.

I haven't tested your code but still there is a minor problem. The Ak refers to subgraph of strong components (in your example the network all an SCC .. but what happens if it can be divided in 2 SCC? How is going to be the Ak then?

) That stil remains the big question mark. My idea is that propably ( I have to test to it to check for the correctness) the Ak is the adjaceny list – Pitelk Jun 2 '10 at 18:26 of the subgraph containing the s, but with the edges from this SCC to all the other SCCs removed . For example let {0,1,2} be your example graph which is connected to the {3,4} with an edge from 2 -> 3 then the A0, A1,A2 will be the (already given by you) adjacency list plus the new one WITHOUT the edge from 2->3.

– Pitelk Jun 2 '10 at 18:34 All the fuss about the SCC is becuase you can divide the G to smaller one hence improve the perfomance of the algorithm ( as the algorithm has a complexity O(E*C) where C=number of cycles ..which C grows 2^n where n is the number of nodes...) Anyway, A million thanks for your all your help! – Pitelk Jun 2 '10 at 18:35.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.