# ............................................................................
#                          G R A P H     ( U N D I R E C T E D )
# ............................................................................
#                     implemented without any separate NODE structure
# ............................................................................

# Each node is recognized by its label 0,1, ... N-1.
# The label also serves as an index in structure(s) representing the graph.
#
# Graph is represented as a list of lists (or 2D array) named 'edges'.
# The list item   edges[i], contains the list of all neighbours of node i.
# More precisely, edges[i], contains the list of labels of all neighbours
#                            of node with label i.

class Graph:
    def __init__(self, n):  # discrete graph with no edges
        self.size = n
        self.edges = [[] for i in range(n)]  # list of empty lists

    def addedge(self, inode1, inode2):
        self.edges[inode1].append(inode2)
        self.edges[inode2].append(inode1)

    def print(self):
        for i in range( self.size ):
            print(i, self.edges[i])

# ............................................................................
#                      S T A C K
# ............................................................................

class Stack:
  def __init__(self):
    self.storage = []

  def isEmpty(self):
    return len(self.storage) == 0

  def push(self, node):
    self.storage.append(node)

  def pop(self):
    return self.storage.pop()

  def top(self):
    return self.storage[-1]

# ............................................................................
#                         Q U E U E
# ............................................................................

class Queue:
    def __init__(self, sizeOfQ):
        self.size = sizeOfQ
        self.q = [None] * sizeOfQ
        self.front = 0
        self. tail = 0

    def isEmpty(self):
        return (self.tail == self.front)

    def Enqueue(self, node):
        if self.tail+1 == self.front or \
        self.tail - self.front == self.size-1:
            pass  # implement overflow fixing here
        self.q[self.tail] = node
        self.tail = (self.tail + 1) % self.size

    def Dequeue(self):
        node = self.q[self.front]
        self.front = (self.front + 1) % self.size
        return node

    def front(self):
        return self.Dequeue()

    def push(self, node):
        self.Enqueue(node)



# ............................................................................
#                      G R A P H   S E A R C H
# ............................................................................

# In this implementation, the nodes are not separate objects,
# each node is just a number, the label of the node (0,1, ..., n).

# Note, that the difference between this code and the code in graph.py
# which represents each node as a separate object,
# is very small indeed.
# However, the performance may differ on big data, too many objects
# tend to slow down the process due to memory load.

def DFS(graph):
    visited = [False] * graph.size
    stack = Stack()
    stack.push(0) # start in node 0
    visited[0] = True
    while(not stack.isEmpty()):
        node = stack.pop()
        print(node, end = " ")
        for neigh in graph.edges[node]:
            if not visited[neigh] :
                stack.push(neigh)
                visited[neigh] = True


def BFS(graph):
    visited = [False] * graph.size
    queue = Queue(200)
    queue.Enqueue(0)
    visited[0] = True
    while(not queue.isEmpty()):
        node = queue.Dequeue()
        print(node, end = " ")              # process node
        for neigh in graph.edges[node]:
            if not visited[neigh] :
                queue.Enqueue(neigh)
                visited[neigh] = True


def BFS2(graph, nodeId):
    visited = [False] * graph.size
    queue = Queue(200)
    queue.Enqueue(nodeId)
    visited[nodeId] = True
    while(not queue.isEmpty()):
        node = queue.Dequeue()
        print(node, end = " ")              # process node
        for neigh in graph.edges[node]:
            if not visited[neigh]:
                queue.Enqueue(neigh)
                visited[neigh] = True


# ____________________________________________________________________________
# ............................................................................
#                              M A I N
# ____________________________________________________________________________

g = Graph(6)
g.addedge(1, 2)
g.addedge(1, 3)
g.addedge(2, 5)
g.addedge(3, 5)
g.addedge(1, 4)
g.addedge(0, 3)

g.print()

DFS(g); print()
BFS(g); print()
BFS2(g, 4); print()