2
\$\begingroup\$

This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

from queue import PriorityQueue
from copy import deepcopy

class Graph:
    def __init__(self):
        self.verts = set()

    def add_vert(self, id):
        new_vert = Vertex(id)
        self.verts.add(new_vert)
        return new_vert

    def get_vert(self, id):
        for vert in self.verts:
            if vert.id == id:
                return vert
        return None

    def dfs(self, start, end):
        path_stack = []
        visited = set()
        path_stack.append([start])

        while path_stack:
            cur_path = path_stack.pop()
            last = cur_path[-1]
            visited.add(last)

            if last != end:
                path_stack = self.push_paths_in_order(path_stack, cur_path, visited)
            else:
                return cur_path
        return None

    def push_paths_in_order(self, path_stack, cur_path, visited):
        last = cur_path[-1]
        queue = PriorityQueue()

        for neighbour in last.neighbours:
            if neighbour not in visited:
                    # make queue like max heap so that we can push
                    # paths to path_stack in increasing order
                    dist_to_neighbour = last.neighbours[neighbour] * -1
                    queue.put((dist_to_neighbour, neighbour))

        while not queue.empty():
            new_path = deepcopy(cur_path)
            next_vert = queue.get(0)[1]
            new_path.append(next_vert)
            path_stack.append(new_path)
        return path_stack


class Vertex:
    def __init__(self, id):
        self.id = id
        self.neighbours = dict()

    def add_neighbour(self, to, weight):
        self.neighbours[to] = weight
\$\endgroup\$
5
  • \$\begingroup\$ The elements of a graph are usually called nodes, which are connected by edges. Vertex is something I associate with "a point" in computer graphics. Might be just me though. \$\endgroup\$ Nov 19, 2016 at 21:07
  • \$\begingroup\$ @I'lladdcommentstomorrow I see your point. Do you think Node would be a better name for Vertex? \$\endgroup\$ Nov 19, 2016 at 21:35
  • \$\begingroup\$ Vertex seems quite normal to me. \$\endgroup\$
    – kraskevich
    Nov 19, 2016 at 21:36
  • \$\begingroup\$ @cycloidistic no, not a better name, just one I have seen being used in this context more often. This was just a comment fyi. \$\endgroup\$ Nov 19, 2016 at 22:00
  • \$\begingroup\$ @I'lladdcommentstomorrow Ok. Makes sense. I think I'll use Node from now on to minimise the chance someone might be a bit confused. \$\endgroup\$ Nov 19, 2016 at 22:11

1 Answer 1

2
\$\begingroup\$
  1. The algorithm you've implemented is not a depth-first search. I'm not sure what it does exactly. It uses a priority queue for some reason (a depth-first search doesn't need a priority queue). It also stores the entire path in the stack and copies every time it discovers a new vertex, which makes it time and space inefficient (your's implementation needs O(n^2) space and time even on a sparse graph (for instance, a tree), while a correct implementation is always linear in number of vertices and edges).

  2. A standard depth-first search goes like this:

    stack = [start_vertex]
    parent = empty dict
    seen = set(start_vertex)
    while not stack.empty():
         v = stack.pop()
         for u in neighbors of v:
              if not u in seen:
                  seen.add(u)
                  stack.push(u)
                  parent[u] = v
    

    The code is much simpler and more efficient. To find the path itself, we can just iterate starting from the destination vertex and going to the current vertex's parent until we reach the start vertex. This way, it requires a linear amount of time and space.

  3. The code itself is rather obscure, in my opinion. Why do we multiply something by -1 here: last.neighbors[neighbor] * -1 (probably you do it to "reverse" the order, but it's not that clear when you read it for the first time)? The fact that neightbors[v] is actually a weight of the edge is also confusing (I would expect to see something like distance or weight in the name of the variable if it stores the length of the edge). By the way, depth-first search works with unweighted graph, so I don't see the point of storing the weights, anyway.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for the answer. I always thought that I must have been doing something odd but I wasn't sure what the alternative was. Storing the parents in a dictionary makes sense. With your code, should there be a part of it which checks whether you found the destination node and if so you would then return the path? Also, you mentioned constructing the path once you hit the destination. Would you make this another function? Where would you put it? Thanks again for the answer :) \$\endgroup\$ Nov 19, 2016 at 22:19
  • \$\begingroup\$ @cycloidistic Yes, I would make a separate function/method (in the same class as the dfs method) for reconstructing the path given the dict of parents, the destination and the source node. One can break the while loop when the destination is popped, but it's not necessary. We can keep iterating until the stack is empty and then check if the destination is in the seen set. \$\endgroup\$
    – kraskevich
    Nov 19, 2016 at 22:26
  • \$\begingroup\$ Ok makes sense. \$\endgroup\$ Nov 19, 2016 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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