from collections import deque

import random as rand

import math as math

# the dfault weight is 1 if not assigend but all the implementation is weighted

class DirectedGraph:

# enter True or False for this constructor

def __init__(self):

self.graph = {}

# adding vertices and edges

# note that self loops are not supported in undirected simpl graphs but it is in multigraphs

def add_pair(self, u, v, w = 1):

if self.graph.get(u):

if self.graph[u].count([w,v]) == 0:

self.graph[u].append([w, v])

else:

self.graph[u] = [[w, v]]

if not self.graph.get(v):

self.graph[v] = []

def remove_pair(self, u, v):

if self.graph.get(u):

for _ in self.graph[u]:

if _[1] == v:

self.graph[u].remove(_)

# if no destination is meant the defaut value is -1

def dfs(self, s = -2, d = -1):

if s == d:

return []

stack = []

visited = []

if s == -2:

s = list(self.graph.keys())[0]

stack.append(s)

visited.append(s)

ss = s

while True:

# check if there is any non isolated nodes

if len(self.graph[s]) != 0:

ss = s

for __ in self.graph[s]:

if visited.count(__[1]) < 1:

if __[1] == d:

visited.append(d)

return visited

else:

stack.append(__[1])

visited.append(__[1])

ss =__[1]

break

# check if all the children are visited

if s == ss :

stack.pop()

if len(stack) != 0:

s = stack[len(stack) - 1]

else:

s = ss

# check if se have reached the starting point

if len(stack) == 0:

return visited

# c is the count of nodes you want and if you leave it or pass -1 to the funtion the count

# will be random from 10 to 10000

def fill_graph_randomly(self, c = -1):

if c == -1:

c = (math.floor(rand.random() * 10000)) + 10

for _ in range(c):

# every vertex has max 100 edges

e = math.floor(rand.random() * 102) + 1

for __ in range(e):

n = math.floor(rand.random() * (c)) + 1

if n == _:

continue

self.add_pair(_, n, 1)

def bfs(self, s = -2):

d = deque()

visited = []

if s == -2:

s = list(self.graph.keys())[0]

d.append(s)

visited.append(s)

while d:

s = d.popleft()

if len(self.graph[s]) != 0:

for __ in self.graph[s]:

if visited.count(__[1]) < 1:

d.append(__[1])

visited.append(__[1])

return visited