5
\$\begingroup\$

I have implemented a depth first search using a stack (in a separate class). Any suggestions please on improvements for the below code:

class Stack:
    """(LIFO) queuing policy implemented using python list."""

    def __init__(self):
        self.list = []

    def push(self, item):
        """Push 'item' onto the stack."""
        self.list.append(item)

    def pop(self):
        """Pop the most recently pushed item from the stack."""
        return self.list.pop()

    def top(self):
        """Return the last element."""
        return self.list[-1]

    def is_empty(self):
        """Returns true if the stack is empty."""
        return len(self.list) == 0


def depth_first_search(graph, start):
    stack = Stack()
    stack.push(start)
    path = []

    while not stack.is_empty():
        vertex = stack.pop()
        if vertex in path:
            continue
        path.append(vertex)
        for neighbor in graph[vertex]:
            stack.push(neighbor)

    return path


def main():
    adjacency_matrix = {
        1: [2, 3],
        2: [4, 5],
        3: [5],
        4: [6],
        5: [6],
        6: [7],
        7: []
    }
    dfs_path = depth_first_search(adjacency_matrix, 1)
    print(dfs_path)


if __name__ == '__main__':
    main()
\$\endgroup\$
5
\$\begingroup\$

Lists in Python are already stacks. It would be better if you used a raw list as people are more familiar with lists then a custom Stack class.

When using a plain Python list the while loop can take advantage of lists being truthy if they have items. This allows you to do while stack: instead.

I would prefer this to be a generator function as we likely won't need the entire DFS path. path can then be a set for \$O(1)\$ lookup rather than a list with \$O(n)\$ lookup. ("if vertex in path:")

def depth_first_search(graph, start):
    stack = [start]
    visited = set()
    while stack:
        vertex = stack.pop()
        if vertex in visited:
            continue
        yield vertex
        visited.add(vertex)
        for neighbor in graph[vertex]:
            stack.append(neighbor)
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Small clarification: the reason I've used a separate Stack class is because DFS uses stack. Although python lists are essentially stacks, I though it would be better if I'm explicit about it. \$\endgroup\$
    – Saurabh
    Aug 2 '20 at 4:58
  • \$\begingroup\$ @Saurabh That is understandable. If you at all feel my explanation lacking just say and I'll amend it when possible :) \$\endgroup\$
    – Peilonrayz
    Aug 2 '20 at 5:00
  • 1
    \$\begingroup\$ thank you for a very clear & detailed explanation :) \$\endgroup\$
    – Saurabh
    Aug 2 '20 at 5:06
  • \$\begingroup\$ @Saurabh if you want to be explicit then use types. Define a new type stack as follows Stack = list. It might seem silly but it achieves the explicitness that you want ;) \$\endgroup\$ Jun 29 at 22:09
  • 1
    \$\begingroup\$ @CharlieParker FWIW Stack would not be a new type, just an 'alias'. If you do type(Stack([])) you'll see the code is still just a plain list. If you want a new type you'd have to inherit from list - class Stack(list): pass or Stack = type("Stack", (list,), {}). \$\endgroup\$
    – Peilonrayz
    Jun 29 at 22:29
1
\$\begingroup\$

Since Saurabh mentioned he wanted to be explicit:

from typing import Any 

Stack = list[Any]

def depth_first_search(graph, start) -> Iterator:
    stack : Stack = [start]
    visited = set()
    while stack:
        vertex = stack.pop()
        if vertex in visited:
            continue
        yield vertex
        visited.add(vertex)
        for neighbor in graph[vertex]:
            stack.append(neighbor)

though it might look superficial I think it is really nice to have Stack explicitly telling the user that the current list with start is a Stack. So we get double explicitness from the type definition and the initialization of your stack - with no user defined stacks.


Edit:

Comment from Peilonrayz:

if you want a new type you'd have to inherit from list - class Stack(list): pass or Stack = type("Stack", (list,), {}).

\$\endgroup\$
3
  • \$\begingroup\$ Warning: NoReturn is not what you or the OP wants - SO answer. The return type should be an Iterator. \$\endgroup\$
    – Peilonrayz
    Jun 29 at 22:34
  • \$\begingroup\$ thanks! Removed that. \$\endgroup\$ Jun 29 at 22:35
  • \$\begingroup\$ @Peilonrayz thanks for the update and comments! Have to admit you have a difficult name to remember for us Hispanic speaking peeps! Thanks again. \$\endgroup\$ Jun 30 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.