Skip to content

Sourcery refactored master branch #1

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
sourcery-ai wants to merge 1 commit into
base: master
Choose a base branch
from
Open

Sourcery refactored master branch #1

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
130 changes: 54 additions & 76 deletions Graphs/Directed and Undirected (Weighted) Graph.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -35,12 +35,10 @@ def remove_pair(self, u, v):
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)
stack = [s]
visited = [s]
ss = s

while True:
Expand All @@ -59,15 +57,15 @@ def dfs(self, s = -2, d = -1):
break

# check if all the children are visited
if s == ss :
if s == ss:
stack.pop()
if len(stack) != 0:
s = stack[len(stack) - 1]
if stack:
s = stack[-1]
else:
s = ss

# check if se have reached the starting point
if len(stack) == 0:
if not stack:
return visited

# c is the count of nodes you want and if you leave it or pass -1 to the funtion the count
Expand All @@ -86,11 +84,10 @@ def fill_graph_randomly(self, c = -1):

def bfs(self, s = -2):
d = deque()
visited = []
if s == -2:
s = list(self.graph.keys())[0]
d.append(s)
visited.append(s)
visited = [s]
while d:
s = d.popleft()
if len(self.graph[s]) != 0:
Expand All @@ -111,12 +108,10 @@ def out_degree(self, u):
return len(self.graph[u])

def topological_sort(self, s = -2):
stack = []
visited = []
if s == -2:
s = list(self.graph.keys())[0]
stack.append(s)
visited.append(s)
stack = [s]
visited = [s]
ss = s
sorted_nodes = []

Expand All @@ -132,23 +127,21 @@ def topological_sort(self, s = -2):
break

# check if all the children are visited
if s == ss :
if s == ss:
sorted_nodes.append(stack.pop())
if len(stack) != 0:
s = stack[len(stack) - 1]
if stack:
s = stack[-1]
else:
s = ss

# check if se have reached the starting point
if len(stack) == 0:
if not stack:
return sorted_nodes

def cycle_nodes(self):
stack = []
visited = []
s = list(self.graph.keys())[0]
stack.append(s)
visited.append(s)
stack = [s]
visited = [s]
parent = -2
indirect_parents = []
ss = s
Expand All @@ -161,7 +154,7 @@ def cycle_nodes(self):
for __ in self.graph[s]:
if visited.count(__[1]) > 0 and __[1] != parent and indirect_parents.count(__[1]) > 0 and not on_the_way_back:
l = len(stack) - 1
while True and l >= 0:
while l >= 0:
if stack[l] == __[1]:
anticipating_nodes.add(__[1])
break
Expand All @@ -175,27 +168,25 @@ def cycle_nodes(self):
break

# check if all the children are visited
if s == ss :
if s == ss:
stack.pop()
on_the_way_back = True
if len(stack) != 0:
s = stack[len(stack) - 1]
if stack:
s = stack[-1]
else:
on_the_way_back = False
indirect_parents.append(parent)
parent = s
s = ss

# check if se have reached the starting point
if len(stack) == 0:
if not stack:
return list(anticipating_nodes)

def has_cycle(self):
stack = []
visited = []
s = list(self.graph.keys())[0]
stack.append(s)
visited.append(s)
stack = [s]
visited = [s]
parent = -2
indirect_parents = []
ss = s
Expand All @@ -208,34 +199,31 @@ def has_cycle(self):
for __ in self.graph[s]:
if visited.count(__[1]) > 0 and __[1] != parent and indirect_parents.count(__[1]) > 0 and not on_the_way_back:
l = len(stack) - 1
while True and l >= 0:
if stack[l] == __[1]:
anticipating_nodes.add(__[1])
break
else:
while l >= 0:
if stack[l] != __[1]:
return True
anticipating_nodes.add(stack[l])
l -= 1
anticipating_nodes.add(__[1])
break
if visited.count(__[1]) < 1:
stack.append(__[1])
visited.append(__[1])
ss =__[1]
break

# check if all the children are visited
if s == ss :
if s == ss:
stack.pop()
on_the_way_back = True
if len(stack) != 0:
s = stack[len(stack) - 1]
if stack:
s = stack[-1]
else:
on_the_way_back = False
indirect_parents.append(parent)
parent = s
s = ss

# check if se have reached the starting point
if len(stack) == 0:
if not stack:
return False

def dfs_time(self, s = -2, e = -1):
Expand Down Expand Up @@ -291,12 +279,10 @@ def remove_pair(self, u, v):
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)
stack = [s]
visited = [s]
ss = s

while True:
Expand All @@ -315,15 +301,15 @@ def dfs(self, s = -2, d = -1):
break

# check if all the children are visited
if s == ss :
if s == ss:
stack.pop()
if len(stack) != 0:
s = stack[len(stack) - 1]
if stack:
s = stack[-1]
else:
s = ss

# check if se have reached the starting point
if len(stack) == 0:
if not stack:
return visited

# c is the count of nodes you want and if you leave it or pass -1 to the funtion the count
Expand All @@ -342,11 +328,10 @@ def fill_graph_randomly(self, c = -1):

def bfs(self, s = -2):
d = deque()
visited = []
if s == -2:
s = list(self.graph.keys())[0]
d.append(s)
visited.append(s)
visited = [s]
while d:
s = d.popleft()
if len(self.graph[s]) != 0:
Expand All @@ -359,11 +344,9 @@ def degree(self, u):
return len(self.graph[u])

def cycle_nodes(self):
stack = []
visited = []
s = list(self.graph.keys())[0]
stack.append(s)
visited.append(s)
stack = [s]
visited = [s]
parent = -2
indirect_parents = []
ss = s
Expand All @@ -376,7 +359,7 @@ def cycle_nodes(self):
for __ in self.graph[s]:
if visited.count(__[1]) > 0 and __[1] != parent and indirect_parents.count(__[1]) > 0 and not on_the_way_back:
l = len(stack) - 1
while True and l >= 0:
while l >= 0:
if stack[l] == __[1]:
anticipating_nodes.add(__[1])
break
Expand All @@ -390,27 +373,25 @@ def cycle_nodes(self):
break

# check if all the children are visited
if s == ss :
if s == ss:
stack.pop()
on_the_way_back = True
if len(stack) != 0:
s = stack[len(stack) - 1]
if stack:
s = stack[-1]
else:
on_the_way_back = False
indirect_parents.append(parent)
parent = s
s = ss

# check if se have reached the starting point
if len(stack) == 0:
if not stack:
return list(anticipating_nodes)

def has_cycle(self):
stack = []
visited = []
s = list(self.graph.keys())[0]
stack.append(s)
visited.append(s)
stack = [s]
visited = [s]
parent = -2
indirect_parents = []
ss = s
Expand All @@ -423,34 +404,31 @@ def has_cycle(self):
for __ in self.graph[s]:
if visited.count(__[1]) > 0 and __[1] != parent and indirect_parents.count(__[1]) > 0 and not on_the_way_back:
l = len(stack) - 1
while True and l >= 0:
if stack[l] == __[1]:
anticipating_nodes.add(__[1])
break
else:
while l >= 0:
if stack[l] != __[1]:
return True
anticipating_nodes.add(stack[l])
l -= 1
anticipating_nodes.add(__[1])
break
if visited.count(__[1]) < 1:
stack.append(__[1])
visited.append(__[1])
ss =__[1]
break

# check if all the children are visited
if s == ss :
if s == ss:
stack.pop()
on_the_way_back = True
if len(stack) != 0:
s = stack[len(stack) - 1]
if stack:
s = stack[-1]
else:
on_the_way_back = False
indirect_parents.append(parent)
parent = s
s = ss

# check if se have reached the starting point
if len(stack) == 0:
if not stack:
return False
def all_nodes(self):
return list(self.graph)
Expand Down
23 changes: 10 additions & 13 deletions Graphs/a_star.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -18,7 +18,7 @@
cost = 1

#the cost map which pushes the path closer to the goal
heuristic = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
heuristic = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
for i in range(len(grid)):
for j in range(len(grid[0])):
heuristic[i][j] = abs(i - goal[0]) + abs(j - goal[1])
Expand All @@ -36,9 +36,9 @@
#function to search the path
def search(grid,init,goal,cost,heuristic):

closed = [[0 for col in range(len(grid[0]))] for row in range(len(grid))]# the referrence grid
closed = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
closed[init[0]][init[1]] = 1
action = [[0 for col in range(len(grid[0]))] for row in range(len(grid))]#the action grid
action = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]

x = init[0]
y = init[1]
Expand All @@ -50,7 +50,7 @@ def search(grid,init,goal,cost,heuristic):
resign = False # flag set if we can't find expand

while not found and not resign:
if len(cell) == 0:
if not cell:
resign = True
return "FAIL"
else:
Expand All @@ -62,7 +62,7 @@ def search(grid,init,goal,cost,heuristic):
g = next[1]
f = next[0]


if x == goal[0] and y == goal[1]:
found = True
else:
Expand All @@ -76,24 +76,21 @@ def search(grid,init,goal,cost,heuristic):
cell.append([f2, g2, x2, y2])
closed[x2][y2] = 1
action[x2][y2] = i
invpath = []
x = goal[0]
y = goal[1]
invpath.append([x, y])#we get the reverse path from here
invpath = [[x, y]]
while x != init[0] or y != init[1]:
x2 = x - delta[action[x][y]][0]
y2 = y - delta[action[x][y]][1]
x = x2
y = y2
invpath.append([x, y])

path = []
for i in range(len(invpath)):
path.append(invpath[len(invpath) - 1 - i])
path = [invpath[len(invpath) - 1 - i] for i in range(len(invpath))]
print("ACTION MAP")
for i in range(len(action)):
print(action[i])
for item in action:
print(item)

return path

a = search(grid,init,goal,cost,heuristic)
Expand Down
Loading