Directed Graph with Python

graph.py

from collections import defaultdict, deque, Counter

class Vertex:
    def __init__(self, name):
        self.name = name
        self.adjacent = []

    def addEdge(self, vertex):
        self.adjacent.append(vertex)

class Graph:
    def __init__(self):
        self.vertexes = []

    def addVertex(self, vertex):
        self.vertexes.append(vertex)

    def path_BFS(self, start, end):
        visited = set()
        visited.add(start)
        queue = deque()
        queue.append((start, [start.name]))
        while queue:
            vertex, path = queue.popleft()
            for neighbour in vertex.adjacent:
                if neighbour not in visited:
                    if neighbour == end:
                        return path + [neighbour.name]
                    queue.append((neighbour, path + [neighbour.name]))
                    visited.add(neighbour)

    def has_path_DFS(self, start, end):
        def has_path_DFS_helper(start, end):
            visited.add(start)
            if start == end:
                return True
            for neighbour in start.adjacent:
                if neighbour not in visited:
                    if has_path_DFS_helper(neighbour, end):
                        return True
            return False

        visited = set()
        return has_path_DFS_helper(start, end)

    def isCyclic(self):
        def isCyclicUtil(v):
            visited.add(v)
            currRec.add(v)
            for neighbour in v.adjacent:
                if not neighbour in visited:
                    if isCyclicUtil(neighbour):
                        return True
                elif neighbour in currRec:
                    return True
            currRec.remove(v)
            return False

        visited = set()
        currRec = set()
        for vertex in self.vertexes:
            if vertex not in visited:
                if isCyclicUtil(vertex):
                    return True
        return False

    def toplogical_sort(self):
        def inbound_count():
            c = Counter()
            for vertex in self.vertexes:
                c[vertex] = 0
            for vertex in self.vertexes:
                for neighbour in vertex.adjacent:
                    c[neighbour] += 1
            return c

        def add_non_dependent():
            add = []
            for key, value in inbound_counter.items():
                if value == 0:
                    add.append(key)
            for vertex in add:
                del inbound_counter[vertex]
            process_next.extend(add)

        order = []
        process_next = deque()
        inbound_counter = inbound_count()
        add_non_dependent()
        while process_next:
            vertex = process_next.popleft()
            for neighbour in vertex.adjacent:
                inbound_counter[neighbour] -= 1
            order.append(vertex.name)
            add_non_dependent()
        return order if len(order) == len(self.vertexes) else 'Cycle!'

    def toplogical_sort_alternative(self):
        def toplogical_sort_util(v):
            visited.add(v)
            for neighbour in v.adjacent:
                if neighbour not in visited:
                    toplogical_sort_util(neighbour)
            stack.append(v.name)

        if self.isCyclic():
            return False
        visited = set()
        stack = []
        for vertex in self.vertexes:
            if vertex not in visited:
                toplogical_sort_util(vertex)
        return stack[::-1]

    def has_path_BFS_bidirectional(self, start, end):
        def BFS_once(queue, visited):
            vertex = queue.popleft()
            for neighbour in vertex.adjacent:
                if neighbour not in visited:
                    queue.append(neighbour)
                    visited.add(neighbour)

        visited_1 = set()
        visited_2 = set()
        visited_1.add(start)
        visited_2.add(end)
        queue_1 = deque()
        queue_2 = deque()
        queue_1.append(start)
        queue_2.append(end)
        while queue_1 and queue_2:
            BFS_once(queue_1, visited_1)
            BFS_once(queue_2, visited_2)
            if visited_1 & visited_2:
                return True
        return False