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.
The content structure of the provided text passage is a discussion and explanation of a specific part of Donald B. Johnson's algorithm for finding cycles in a graph. The passage includes a detailed explanation of the algorithm's components and a request for an example to clarify the meaning of certain variables and structures.
no_question

the passage does not contain a direct mathematical question that requires a numerical answer or a calculation. instead, it is a request for an explanation and an example to better understand the algorithm.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
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.
user
The content structure of the provided text passage is a discussion and explanation of a specific part of Donald B. Johnson's algorithm for finding cycles in a graph. The passage includes a detailed explanation of the algorithm's components and a request for an example to clarify the meaning of certain variables and structures.

TYPE: NO_QUESTION

The passage does not contain a direct mathematical question that requires a numerical answer or a calculation. Instead, it is a request for an explanation and an example to better understand the algorithm.