In [73]:

    

import sys


    

In [76]:

    

class Vertex:
    def __init__(self, name):
        self.name = name
        self.color = None
        self.distance = sys.maxsize
        self.parent = None
    def __str__(self):
        return self.name
    def __eq__(self, other):
        return self.name == other.name
    def __hash__(self):
        return hash(self.name)


    

In [39]:

    

class Edge:
    def __init__(self, source, destination):
        self.source = source
        self.destination = destination
    def getSource(self):
        return self.source
    def getDestination(self):
        return self.destination
    def __str__(self):
        return str(self.source) + "->" + str(self.destination)


    

In [69]:

    

class Digraph:
    def __init__(self):
        self.vertices = set([])
        self.edges = {}
    def addVertex(self, vertex):
        if vertex.name in self.vertices:
            raise ValueError('Duplicate Vertex')
        else:
            self.vertices.add(vertex)
            self.edges[vertex] = []
    def addEdge(self, edge):
        source = edge.getSource()
        destination = edge.getDestination()
        if not (source in self.vertices and destination in self.vertices):
            raise ValueError('Vertex not in graph')
        self.edges[source].append(destination)
    def childrenOf(self, vertex):
        return self.edges[vertex]
    def hasVertex(self, vertex):
        return vertex in self.vertices
    def __str__(self):
        res = ''
        for k in self.edges:
            for d in self.edges[k]:
                res = res + str(k) + '->' + str(d) + '\n'
        return res[:-1]


    

In [45]:

    

def createBasicDigraph():
    vertices = []
    for name in range(10):
        vertices.append(Vertex(str(name)))
    g = Digraph()
    for n in vertices:
        g.addVertex(n)
    g.addEdge(Edge(vertices[0],vertices[1]))
    g.addEdge(Edge(vertices[1],vertices[2]))
    g.addEdge(Edge(vertices[2],vertices[3]))
    g.addEdge(Edge(vertices[3],vertices[4]))
    g.addEdge(Edge(vertices[3],vertices[5]))
    g.addEdge(Edge(vertices[0],vertices[2]))
    g.addEdge(Edge(vertices[1],vertices[1]))
    g.addEdge(Edge(vertices[1],vertices[0]))
    g.addEdge(Edge(vertices[4],vertices[0]))
    return g

def testDigraph():
    g = createBasicDigraph()
    print('The graph:')
    print(g)

testDigraph()


    

    




The graph:
0->1
0->2
1->2
1->1
1->0
2->3
3->4
3->5
4->0

In [60]:

    

class Node:
    def __init__(self, data = None, previous = None, next = None):
        self.data = data
        self.previous = previous
        self.next = next
    def __str__(self):
        return str(self.data)


    

In [33]:

    

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0
        
    def enqueue(self, data):
        node = Node(data)
        if not self.isEmpty():
            self.tail.next = node
            node.previous = self.tail
            self.tail = node
        else:
            self.head = self.tail = node
        self.length += 1
    
    def dequeue(self):
        if self.isEmpty():
            return None
        else:
            self.length -= 1
            data = self.head.data
            self.head = self.head.next
            if not self.head:
                self.tail = None
            return data

    def isEmpty(self):
        return self.length == 0
    
    def size(self):
        return self.length
        
    def __str__(self):
        current = self.head
        result = ''
        while current:
            result += str(current.data)
            current = current.next
            if current:
                result += ' -> '
        return result


    

In [35]:

    

def testQueue():
    q = Queue()
    for x in range(-10,11):
        q.enqueue(x)

    print(str(q))

    result = q.dequeue()
    while result is not None:
        print(result, end = " ")
        result = q.dequeue()


    

In [36]:

    

testQueue()


    

    




-10 -> -9 -> -8 -> -7 -> -6 -> -5 -> -4 -> -3 -> -2 -> -1 -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 

In [102]:

    

def bfs(graph, source):
    for vertex in graph.vertices:
        if vertex != source:
            vertex.color = "white"
            vertex.distance = sys.maxsize
            vertex.parent = None
        else:
            source = vertex
            vertex.color = "gray"
            vertex.distance = 0
            vertex.parent = None
    q = Queue()
    q.enqueue(source)
    while not q.isEmpty():
        u = q.dequeue()
        for vertex in graph.edges[u]:
            if vertex.color == "white":
                vertex.color = "gray"
                vertex.distance = u.distance + 1
                vertex.parent = u
                q.enqueue(vertex)
        u.color = "black"
#    print(q)


    

In [103]:

    

def testBfs(start):
    graph = createBasicDigraph()
    bfs(graph, Vertex(start))
    for vertex in graph.vertices:
        print(vertex.name, vertex.color, vertex.distance, vertex.parent)
        
testDigraph()
for n in range(10):
    print(n)
    testBfs(str(n))
    print()


    

    




The graph:
0->1
0->2
1->2
1->1
1->0
2->3
3->4
3->5
4->0
0
6 white 9223372036854775807 None
3 black 2 2
0 black 0 None
5 black 3 3
8 white 9223372036854775807 None
2 black 1 0
7 white 9223372036854775807 None
4 black 3 3
9 white 9223372036854775807 None
1 black 1 0

1
6 white 9223372036854775807 None
3 black 2 2
0 black 1 1
5 black 3 3
8 white 9223372036854775807 None
2 black 1 1
7 white 9223372036854775807 None
4 black 3 3
9 white 9223372036854775807 None
1 black 0 None

2
6 white 9223372036854775807 None
3 black 1 2
0 black 3 4
5 black 2 3
8 white 9223372036854775807 None
2 black 0 None
7 white 9223372036854775807 None
4 black 2 3
9 white 9223372036854775807 None
1 black 4 0

3
6 white 9223372036854775807 None
3 black 0 None
0 black 2 4
5 black 1 3
8 white 9223372036854775807 None
2 black 3 0
7 white 9223372036854775807 None
4 black 1 3
9 white 9223372036854775807 None
1 black 3 0

4
6 white 9223372036854775807 None
3 black 3 2
0 black 1 4
5 black 4 3
8 white 9223372036854775807 None
2 black 2 0
7 white 9223372036854775807 None
4 black 0 None
9 white 9223372036854775807 None
1 black 2 0

5
6 white 9223372036854775807 None
3 white 9223372036854775807 None
0 white 9223372036854775807 None
5 black 0 None
8 white 9223372036854775807 None
2 white 9223372036854775807 None
7 white 9223372036854775807 None
4 white 9223372036854775807 None
9 white 9223372036854775807 None
1 white 9223372036854775807 None

6
6 black 0 None
3 white 9223372036854775807 None
0 white 9223372036854775807 None
5 white 9223372036854775807 None
8 white 9223372036854775807 None
2 white 9223372036854775807 None
7 white 9223372036854775807 None
4 white 9223372036854775807 None
9 white 9223372036854775807 None
1 white 9223372036854775807 None

7
6 white 9223372036854775807 None
3 white 9223372036854775807 None
0 white 9223372036854775807 None
5 white 9223372036854775807 None
8 white 9223372036854775807 None
2 white 9223372036854775807 None
7 black 0 None
4 white 9223372036854775807 None
9 white 9223372036854775807 None
1 white 9223372036854775807 None

8
6 white 9223372036854775807 None
3 white 9223372036854775807 None
0 white 9223372036854775807 None
5 white 9223372036854775807 None
8 black 0 None
2 white 9223372036854775807 None
7 white 9223372036854775807 None
4 white 9223372036854775807 None
9 white 9223372036854775807 None
1 white 9223372036854775807 None

9
6 white 9223372036854775807 None
3 white 9223372036854775807 None
0 white 9223372036854775807 None
5 white 9223372036854775807 None
8 white 9223372036854775807 None
2 white 9223372036854775807 None
7 white 9223372036854775807 None
4 white 9223372036854775807 None
9 black 0 None
1 white 9223372036854775807 None

In [ ]: