Implementing Graph Algorithms (Basic Level in Python)

undirected_graph.py

import Queue

class UndirectedGraph(object):
    """
    Undirected Graph, with graph represented as an adjacency matrix
    """

    def __init__(self, vertices):
        self.adjacency_matrix = []
        for i in range(vertices):
            self.adjacency_matrix.append([0] * vertices)

    def add_edge(self, source, destination):
        """
        Adds an edge defined by vertices from source to destination
        then destination to source in matrix
        """
        self.adjacency_matrix[source][destination] = 1
        self.adjacency_matrix[destination][source] = 1

    def get_vertex(self):
        """
        Generator for returning the next vertex from the adjacency list
        """
        for v, __ in enumerate(self.adjacency_matrix):
            yield v

    def get_neighbor(self, vertex):
        """
        Generator for returning the next vertex adjacent to the given vertex
        """
        for i, flag in enumerate(self.adjacency_matrix[vertex]):
            if flag == 1:
                yield i

    def dfs_recursive(self):
        """
        Computes the parents for each vertex as determined through depth-first-search
        """
        
        parents = {}

        self.dfs_util(0, parents)

        return parents

    def dfs_util(self, vertex, parents):
        for u in self.get_neighbor(vertex):
            if u not in parents:
                parents[u] = vertex
                self.dfs_util(u, parents)

    def dfs_iterative(self):
        """
        Computes the parents for each vertex as determined through depth-first-search
        """
        
        parents = {}
        to_visit = [0]

        while to_visit:
            v = to_visit.pop()

            for neighbor in self.get_neighbor(v):
                if neighbor not in parents:
                    parents[neighbor] = v
                    to_visit.append(neighbor)

        return parents

    def bfs(self):
        """
        Computes the the parents for each vertex as determined through breadth-first search
        """
        
        parents = {}
        to_visit = Queue.Queue()
        to_visit.put(0)

        while not to_visit.empty():
            v = to_visit.get()

            for neighbor in self.get_neighbor(v):
                if neighbor not in parents:
                    parents[neighbor] = v
                    to_visit.put(neighbor)

        return parents

    def is_bipartite(self):
        """
        Returns true if graph is bipartite
        """
        
        colorings = {}
        to_visit = Queue.Queue()
        to_visit.put(0)
        colorings[0] = 0

        while not to_visit.empty():
            v = to_visit.get()

            for u in self.get_neighbor(v):
                if u not in colorings:
                    colorings[u] = 1 - colorings[v]
                    to_visit.put(u)
                elif colorings[u] == colorings[v]:
                    return False

        return True