Graph Theory

bellman-ford.py

class GraphBellmanFord(Graph):
    def bellman_ford(self, src: str):
        dist = {}
        for _, u in self.V.items():
            dist[u] = float('Inf')
        src = self.V[src]
        dist[src] = 0

        edges = []
        for e in self.E.values():
            edges += e

        for _ in range(len(self.V)):
            for e in edges:
                # relax edges
                if dist[e.src] != float('Inf') and dist[e.src] + e.weight < dist[e.dest]:
                    dist[e.dest] = dist[e.src] + e.weight

        for e in edges:
            if dist[e.src] != float('Inf') and dist[e.src] + e.weight < dist[e.dest]:
                return False

        return dist

if __name__ == '__main__':
    graph = Graph()
    graph.edge('s', 't', 6)
    graph.edge('s', 'y', 7)
    graph.edge('t', 'x', 5)
    graph.edge('t', 'y', 8)
    graph.edge('t', 'z', -4)
    graph.edge('y', 'x', -3)
    graph.edge('y', 'z', 9)
    graph.edge('x', 't', -2)
    graph.edge('z', 'x', 7)
    graph.edge('z', 's', 2)

    for k, v in graph.bellman_ford('s').items():
        print(k.name, v)

dijkstra.py

class GraphDijkstra(Graph):
    def min_distance(self, dist, shortest):
        min_dist = float('Inf')
        min_vtx = None
        for u in self.V.values():
            if dist[u] < min_dist and shortest[u] is False:
                min_dist = dist[u]
                min_vtx = u

        return min_vtx

    def dijkstra(self, src: str):
        dist = {}
        shortest = {}  # shortest path tree set
        for _, u in self.V.items():
            dist[u] = float('Inf')
            shortest[u] = False
        src = self.V[src]
        dist[src] = 0

        for _ in range(len(self.V)):
            u = self.min_distance(dist, shortest)
            shortest[u] = True

            for e in self.E[u]:
                if shortest[e.dest] is False and dist[e.src] + e.weight < dist[e.dest]:
                    dist[e.dest] = dist[e.src] + e.weight

        return dist



if __name__ == '__main__':
    graph = Graph()
    graph.edge('s', 't', 10)
    graph.edge('s', 'y', 5)
    graph.edge('t', 'x', 1)
    graph.edge('t', 'y', 2)
    graph.edge('y', 't', 3)
    graph.edge('y', 'x', 9)
    graph.edge('y', 'z', 2)
    graph.edge('x', 'z', 4)
    graph.edge('z', 'x', 6)
    graph.edge('z', 's', 7)

    for k, v in graph.dijkstra('s').items():
        print(k.name, v)

directed-graph.py

from queue import Queue

WHITE = 'NOTVISITED'
GRAY = 'DISCOVERED'
BLACK = 'VISITED'


class Vertex:
    def __init__(self, name):
        self.name = name
        self.color = ''


class Edge:
    def __init__(self, src: Vertex, dest: Vertex, w: int):
        self.src = src
        self.dest = dest
        self.weight = w


class Graph:
    """Directed Graph"""
    V = {}  # name -> Vertex
    E = {}  # Vertex -> [Edge]

    def vertex(self, u: str):
        self.V[u] = self.V.get(u, Vertex(u))
        return self.V[u]

    def edge(self, u: str, v: str, weight: int):
        vtx_u, vtx_v = self.vertex(u), self.vertex(v)
        e = Edge(vtx_u, vtx_v, weight)
        self.E[vtx_u] = self.E.get(vtx_u, []) + [e]

    def adj(self, u: Vertex):
        adj_list = []
        for e in self.E[u]:
            adj_list.append(e.dest)
        return adj_list

    def DFS(self):
        for _, u in self.V.items():
            u.color = WHITE

        for _, u in self.V.items():
            if u.color == WHITE:
                self.visit(u)

    def visit(self, u):
        u.color = GRAY
        for v in self.adj(u):
            if v.color == WHITE:
                self.visit(v)
        u.color = BLACK

    def BFS(self, src: str):
        for _, u in self.V.items():
            if u.name != src:
                u.color = WHITE

        vtx_src = self.V[src]
        vtx_src.color = GRAY
        q = Queue()
        q.put(vtx_src)
        while not q.empty():
            u = q.get()
            for v in self.adj(u):
                if v.color == WHITE:
                    v.color = GRAY
                    q.put(v)
            u.color = BLACK


if __name__ == '__main__':
    graph = Graph()
    graph.edge('u', 'v', 0)
    graph.edge('u', 'x', 0)
    graph.edge('v', 'y', 0)
    graph.edge('x', 'v', 0)
    graph.edge('y', 'x', 0)
    graph.edge('w', 'y', 0)
    graph.edge('w', 'z', 0)
    graph.edge('z', 'z', 0)

    graph.DFS()
    graph.BFS('u')