from __future__ import absolute_import
from __future__ import print_function
from __future__ import division

from ds_stack import Stack


# def dfs(adjacency_dict, start_vertex):
#     """Depth First Search algorith."""
#     ls_stack = Stack()
#     ls_stack.push([start_vertex])
#     visited_set = set([start_vertex])

#     while ls_stack.size() > 0:
#         path_ls = ls_stack.pop()
#         # Take the lastest vertex as the new starting one.
#         vertex = path_ls[-1]
#         print('path_ls: {}'.format(path_ls))
#         print('vertex: {}'.format(vertex))
#         yield vertex, path_ls
#         for vertex in adjacency_dict[vertex] - set([start_vertex]):
#             visited_set.add(vertex)
#             ls_stack.push([vertex])
#             dfs(adjacency_dict, vertex)

def dfs_recur(adjacency_dict, start_vertex, end_vertex, path_ls=None):
    if path_ls is None:
        path_ls = [start_vertex]
    else:
        path_ls.append(start_vertex)
    print('path_ls: {}'.format(path_ls))

    if start_vertex == end_vertex:
        return path_ls

    for vertex in adjacency_dict[start_vertex]:
        if vertex not in path_ls:
            path_ls = dfs_recur(adjacency_dict, vertex, end_vertex, path_ls=path_ls)

    return path_ls


def main():
    # Small word ladder graph.
    adjacency_dict = {
        'fool': {'cool', 'pool', 'foil', 'foul'},
        'foul': {'fool', 'foil'},
        'foil': {'fool', 'foul', 'fail'},
        'cool': {'fool', 'cool'},
        'fail': {'foil', 'fall'},
        'fall': {'fail', 'pall'},
        'pool': {'fool', 'cool', 'poll'},
        'poll': {'pool', 'pall', 'pole'},
        'pall': {'fall', 'pale', 'poll'},
        'pole': {'poll', 'pope', 'pale'},
        'pope': {'pole'},
        'pale': {'pall', 'pole', 'sale', 'page'},
        'sale': {'pale', 'sage'},
        'page': {'pale', 'sage'},
        'sage': {'sale', 'page'} 
    }
    
    start_vertex = 'fool'
    end_vertex = 'sage'
    path_ls = dfs_recur(adjacency_dict, start_vertex, end_vertex, path_ls=None)
    print('path_ls: {}'.format(path_ls))
    # traverse_dfs(adjacency_dict, start_vertex, end_vertex)


if __name__ == '__main__':
    main()

@@ -789,16 +789,17 @@
 ertex)%0A%0A
+%0A
 def dfs_
@@ -829,36 +829,24 @@
 tart_vertex,
- end_vertex,
  path_ls=Non
@@ -999,67 +999,8 @@
 ))%0A%0A
-    if start_vertex == end_vertex:%0A        return path_ls%0A%0A
     
@@ -1128,36 +1128,24 @@
 ict, vertex,
- end_vertex,
  path_ls=pat
@@ -1172,16 +1172,321 @@
 th_ls%0A%0A%0A
+def traverse_dfs_recur(adjacency_dict, start_vertex, end_vertex):%0A    path_ls = dfs_recur(adjacency_dict, start_vertex, path_ls=None)%0A%0A    end_vertex_cand = path_ls%5B-1%5D%0A    while end_vertex_cand != end_vertex:%0A        path_ls.pop()%0A        end_vertex_cand = path_ls%5B-1%5D%0A%0A    print(' -%3E '.join(path_ls))%0A%0A%0A
 def main
@@ -2177,24 +2177,26 @@
 = 'sage'%0A   
+ #
  path_ls = d
@@ -2237,20 +2237,8 @@
 tex,
- end_vertex,
  pat
@@ -2247,24 +2247,26 @@
 ls=None)%0A   
+ #
  print('path
@@ -2294,18 +2294,16 @@
 ls))%0A   
- #
  travers
@@ -2307,16 +2307,22 @@
 erse_dfs
+_recur
 (adjacen
@@ -2357,17 +2357,16 @@
 ertex)%0A%0A
-%0A
 if __nam

Complete dfs_recur() & traverse_dfs_recur()