improvement for Tarjan algorithm

[scozv]

From Algo.js of Google Code on August 09, 2013 14:41:41

What steps will reproduce the problem?

1. some input data may pass Tarjan
2. some may not
3. see revision 7d99353f8542

What is the expected output? What do you see instead? Tarjan should work as Kosaraju Please use labels and text to provide additional information. how to use stack simulate recursion correctly?

Original issue: http://code.google.com/p/algo-js/issues/detail?id=14

[scozv]

From Algo.js of Google Code on October 16, 2013 09:44:25

still failed in following input in revision da291acd9cd7

8
1 2
2 3
3 1
3 4
5 4
6 4
8 6
6 7
7 8

Answer: 3,3,1,1,0, Failed in T

14
1 9
1 7
2 6
3 6
4 1
4 6
14 2
6 3
7 9
9 4
3 1

Answer: 6,1,1,0,0, Failed in T

11
1 4
4 3
3 1
4 6
6 7
6 10
10 11
11 10
7 6
2 5
5 2
5 7
5 8
8 9
7 11

Answer: 3,2,2,2,1 the 6th value is also a 1, 7th is 0, Failed in T

// http://algs4.cs.princeton.edu/42directed/mediumDG.txt 
info = line.split(' ')
    .filter(function(x){return x.length;})
    .map(function(x){
        return (+(x.replace(/^\s\s*/, '').replace(/\s\s*$/, '')));
    });
    gh.__pushEdge__(info[0]+1, info[1]+1);

Failed in T

Status: Started

[scozv]

From Algo.js of Google Code on October 17, 2013 02:50:04

improved on revision 87edee29c8f4 to pass test above except mediumDG.txt and following test:

12
1 2
2 3
2 4
2 5
3 6
4 5
4 7
5 2
5 6
5 7
6 3
6 8
7 8
7 10
8 7
9 7
10 9
10 11
11 12
12 10

[scozv]

From Algo.js of Google Code on October 18, 2013 02:20:20

proudly fixed in revision 4542b937d827 , and verified to pass the test of a graph containing over 870000 vertex.

Status: Fixed