text: Dismiss
  Announcing Stack Overflow Documentation
  
  We started with Q&A. Technical documentation is next, and we need your help.
  
  Whether you're a beginner or an experienced developer, you can contribute.
  
  # help in the Donalds B. Johnson's algorithm, i cannot understand the pseudo code (PART II)
  
  i cannot understand a certain part of the paper published by Donald Johnson about finding cycles (Circuits) in a graph.
  
  More specific i cannot understand what is the matrix Ak which is mentioned in the following line of the pseudo code :
  
  Ak:=adjacency structure of strong component K with least vertex in subgraph of G induced by {s,s+1,....n};
  
  to make things worse some lines after is mentins " for i in Vk do " without declaring what the Vk is...
  
  As far i have understand we have the following: 1) in general, a strong component is a sub-graph of a graph, in which for every node of this sub-graph there is a path to any node of the sub-graph (in other words you can access any node of the sub-graph from any other node of the sub-graph)
  
  2) a sub-graph induced by a list of nodes is a graph containing all these nodes plus all the edges connecting these nodes. in paper the mathematical definition is " F is a subgraph of G induced by W if W is 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 the edges in the graph, W is a set of nodes.
  
  3)in the code implementation the nodes are named by integer numbers 1 ... n.
  
  4) I suspect that the Vk is the set of nodes of the strong component K.
  
  now to the question. Lets say we have a graph G= (V,E) with V = {1,2,3,4,5,6,7,8,9} which it can be divided into 3 strong components the SC1 = {1,4,7,8} SC2= {2,3,9} SC3 = {5,6} (and their edges)
  
  Can anybody give me an example for s =1, s= 2, s= 5 what if going to be the Vk and Ak according to the code?
  
  The pseudo code is in my previous question in http://stackoverflow.com/questions/2908575/help-in-the-donalds-b-johnsons-algorithm-i-cannot-understand-the-pseudo-code
  
  thank you in advance
  
  -
  
  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.
  
  Addendum: As noted in this proposed edit and helpful answer, the algorithm specifies that `unblock()` should remove the element having the value `w`, not the element having the index `w`.
  
  ``````list.remove(Integer.valueOf(w));
  ``````
  
  Sample output:
  
  ```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. A variation that produces only unique cycles 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 http://stackoverflow.com/questions/2908575
  * @see http://stackoverflow.com/questions/2939877
  */
  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>>();
  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++) {
  }
  }
  
  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)) {
  }
  }
  }
  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;
  }
  }
  }
  }
  ``````
  -
  +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
  @Gedde: I've added a variation, citing it above; note code fix in revision 7. – trashgod Mar 10 at 17:19
  
  I had sumbitted an edit request to @trashgod's code to fix the exception thrown in `unblock()`. Essentially, the algorithm states that the element `w` (which is not an index) is to be removed from the list. The code above used `list.remove(w)`, which treats `w` as an index.
  
  My edit request was rejected! Not sure why, because I have tested the above with my modification on a network of 20,000 nodes and 70,000 edges and it doesn't crash.
  
  I have also modified Johnson's algorithm to be more adapted to undirected graphs. If anybody wants these modifications 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);
  }
  }
  }
  ``````
  -
  +1 for spotting this; I've updated my answer similarly. The edit request may have looked like an attempt to circumvent the comment threshold, but it's a good answer. – trashgod Feb 12 '13 at 10:45
  
  The following variation produces unique cycles. Based on this example, it is adapted from an answer supplied by @user1406062.
  
  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 http://stackoverflow.com/questions/2908575
  * @see http://stackoverflow.com/questions/2939877
  */
  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>>();
  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)) {
  }
  }
  n = a.size();
  blocked = new boolean[n];
  b = new ArrayList<List<Integer>>();
  for (int i = 0; i < n; i++) {
  }
  }
  
  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)) {
  }
  }
  }
  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
  ``````
  -
  
  @trashgod, your sample output contains cycle which are cyclic permutation. For example 0-1-0 and 1-0-1 are same Actually the output should contains only 5 cycle i.e. 0 1 0, 0 2 0, 0 1 2 0, 0 2 1 0, 1 2 1,
  
  Johnson paper explain what a cycle is: 'Two elementary circuits are distinct if one is not a cyclic permutation of the other. ' One can also check wolfram page: This also output 5 cycle for the same input.
explanation: The provided text is a technical discussion on the Donald B. Johnson algorithm for finding cycles in a graph. It includes a detailed explanation of the algorithm, a specific question about the meaning of certain variables in the pseudo code, and an example implementation in Java. The text also contains a follow-up answer that addresses a bug in the implementation and provides a corrected version of the code.
  
  The document contains a specific question and an answer to that question.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: Dismiss
  Announcing Stack Overflow Documentation
  
  We started with Q&A. Technical documentation is next, and we need your help.
  
  Whether you're a beginner or an experienced developer, you can contribute.
  
  # help in the Donalds B. Johnson's algorithm, i cannot understand the pseudo code (PART II)
  
  i cannot understand a certain part of the paper published by Donald Johnson about finding cycles (Circuits) in a graph.
  
  More specific i cannot understand what is the matrix Ak which is mentioned in the following line of the pseudo code :
  
  Ak:=adjacency structure of strong component K with least vertex in subgraph of G induced by {s,s+1,....n};
  
  to make things worse some lines after is mentins " for i in Vk do " without declaring what the Vk is...
  
  As far i have understand we have the following: 1) in general, a strong component is a sub-graph of a graph, in which for every node of this sub-graph there is a path to any node of the sub-graph (in other words you can access any node of the sub-graph from any other node of the sub-graph)
  
  2) a sub-graph induced by a list of nodes is a graph containing all these nodes plus all the edges connecting these nodes. in paper the mathematical definition is " F is a subgraph of G induced by W if W is 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 the edges in the graph, W is a set of nodes.
  
  3)in the code implementation the nodes are named by integer numbers 1 ... n.
  
  4) I suspect that the Vk is the set of nodes of the strong component K.
  
  now to the question. Lets say we have a graph G= (V,E) with V = {1,2,3,4,5,6,7,8,9} which it can be divided into 3 strong components the SC1 = {1,4,7,8} SC2= {2,3,9} SC3 = {5,6} (and their edges)
  
  Can anybody give me an example for s =1, s= 2, s= 5 what if going to be the Vk and Ak according to the code?
  
  The pseudo code is in my previous question in http://stackoverflow.com/questions/2908575/help-in-the-donalds-b-johnsons-algorithm-i-cannot-understand-the-pseudo-code
  
  thank you in advance
  
  -
  
  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.
  
  Addendum: As noted in this proposed edit and helpful answer, the algorithm specifies that `unblock()` should remove the element having the value `w`, not the element having the index `w`.
  
  ``````list.remove(Integer.valueOf(w));
  ``````
  
  Sample output:
  
  ```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. A variation that produces only unique cycles 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 http://stackoverflow.com/questions/2908575
  * @see http://stackoverflow.com/questions/2939877
  */
  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>>();
  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++) {
  }
  }
  
  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)) {
  }
  }
  }
  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;
  }
  }
  }
  }
  ``````
  -
  +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
  @Gedde: I've added a variation, citing it above; note code fix in revision 7. – trashgod Mar 10 at 17:19
  
  I had sumbitted an edit request to @trashgod's code to fix the exception thrown in `unblock()`. Essentially, the algorithm states that the element `w` (which is not an index) is to be removed from the list. The code above used `list.remove(w)`, which treats `w` as an index.
  
  My edit request was rejected! Not sure why, because I have tested the above with my modification on a network of 20,000 nodes and 70,000 edges and it doesn't crash.
  
  I have also modified Johnson's algorithm to be more adapted to undirected graphs. If anybody wants these modifications 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);
  }
  }
  }
  ``````
  -
  +1 for spotting this; I've updated my answer similarly. The edit request may have looked like an attempt to circumvent the comment threshold, but it's a good answer. – trashgod Feb 12 '13 at 10:45
  
  The following variation produces unique cycles. Based on this example, it is adapted from an answer supplied by @user1406062.
  
  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 http://stackoverflow.com/questions/2908575
  * @see http://stackoverflow.com/questions/2939877
  */
  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>>();
  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)) {
  }
  }
  n = a.size();
  blocked = new boolean[n];
  b = new ArrayList<List<Integer>>();
  for (int i = 0; i < n; i++) {
  }
  }
  
  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)) {
  }
  }
  }
  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
  ``````
  -
  
  @trashgod, your sample output contains cycle which are cyclic permutation. For example 0-1-0 and 1-0-1 are same Actually the output should contains only 5 cycle i.e. 0 1 0, 0 2 0, 0 1 2 0, 0 2 1 0, 1 2 1,
  
  Johnson paper explain what a cycle is: 'Two elementary circuits are distinct if one is not a cyclic permutation of the other. ' One can also check wolfram page: This also output 5 cycle for the same input.
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The provided text is a technical discussion on the Donald B. Johnson algorithm for finding cycles in a graph. It includes a detailed explanation of the algorithm, a specific question about the meaning of certain variables in the pseudo code, and an example implementation in Java. The text also contains a follow-up answer that addresses a bug in the implementation and provides a corrected version of the code.
  
  The document contains a specific question and an answer to that question.
  
  Label: question-and-answer