keon / algorithms / 370

76%

push

travis-ci

Zhengli0817 patch 1 - update topsort.py (#295)

* Update bst.py

* Update topsort.py

The original algo is wrong because it is using BFS, it should use DFS instead.

A counter-example is provided below:

depGraph = {
    "a" : [ "b" ],
    "b" : [ "c" ],
    "c" :  [ 'e'],
    'e' : [ 'g' ],
    "d" : [ ],
    "f" : ["e" , "d"],
    "g" : [ ]
}

given = [ "b", "c", "a", "d", "e", "f", "g" ]

The output of ret_dep_graph() is: ['e', 'g', 'c', 'b', 'a', 'd', 'f']

Clearly, 'g' has to be done before 'e'.

* Update topsort.py

* Update topsort.py

The original algo in topsort.py is wrong because it is using BFS, it should use DFS instead.

A counter-example is provided below:

depGraph = {
"a" : [ "b" ],
"b" : [ "c" ],
"c" : [ 'e'],
'e' : [ 'g' ],
"d" : [ ],
"f" : ["e" , "d"],
"g" : [ ]
}

given = [ "b", "c", "a", "d", "e", "f", "g" ]

The output of ret_dep_graph() is: ['e', 'g', 'c', 'b', 'a', 'd', 'f']

Clearly, 'g' has to be done before 'e'.

* Update topsort.py

* Create __init__.py

* Update __init__.py

* Update __init__.py

* Create test_topsort.py

* Update topsort.py

* Update test_topsort.py

* Update __init__.py

* Update and rename topsort.py to top_sort.py

* Update top_sort.py

* Update __init__.py

* Update test_topsort.py

64 of 64 new or added lines in 2 files covered. (100.0%)

2836 of 3094 relevant lines covered (91.66%)

0.92 hits per line