Merge branch 'nick-jiang-master' · omnarayan/python-patterns@fca3d21 · GitHub

omnarayan / python-patterns Public

forked from faif/python-patterns

• Notifications You must be signed in to change notification settings
• Fork 0
• Star 0

• Code
• Pull requests
• Actions
• Projects
• Wiki
• Security and quality
• Insights

Additional navigation options

Commit fca3d21

Browse filesBrowse the repository at this point in the historyBrowse files

faif

committed

Merge branch 'nick-jiang-master'

2 parents 8300928 + 6eb5e62 commit fca3d21
Copy full SHA for fca3d21

1 file changed

+16-16Lines changed: 16 additions & 16 deletions

File tree

Expand file treeCollapse file tree

Open diff view settings

Filter options

• graph_search.py

Expand file treeCollapse file tree

Open diff view settings

Collapse file

‎graph_search.py‎

Copy file name to clipboardExpand all lines: graph_search.py

+16-16Lines changed: 16 additions & 16 deletions

Original file line number	Diff line number	Diff line change
@@ -10,10 +10,10 @@ class GraphSearch:
10	10	def __init__(self, graph):
11	11	self.graph = graph
12	12
13		- def find_path(self, start, end, path=[]):
	13	+ def find_path(self, start, end, path=None):
14	14	self.start = start
15	15	self.end = end
16		- self.path = path
	16	+ self.path = path if path else []
17	17
18	18	self.path += [self.start]
19	19	if self.start == self.end:
@@ -27,37 +27,37 @@ def find_path(self, start, end, path=[]):
27	27	return newpath
28	28	return None
29	29
30		- def find_all_path(self, start, end, path=[]):
	30	+ def find_all_path(self, start, end, path=None):
31	31	self.start = start
32	32	self.end = end
33		- self.path = path
34		- self.path += [self.start]
	33	+ _path = path if path else []
	34	+ _path += [self.start]
35	35	if self.start == self.end:
36		- return [self.path]
	36	+ return [_path]
37	37	if self.start not in self.graph:
38	38	return []
39	39	paths = []
40	40	for node in self.graph[self.start]:
41		- if node not in self.path:
42		- newpaths = self.find_all_path(node, self.end, self.path)
	41	+ if node not in _path:
	42	+ newpaths = self.find_all_path(node, self.end, _path[:])
43	43	for newpath in newpaths:
44	44	paths.append(newpath)
45	45	return paths
46	46
47		- def find_shortest_path(self, start, end, path=[]):
	47	+ def find_shortest_path(self, start, end, path=None):
48	48	self.start = start
49	49	self.end = end
50		- self.path = path
	50	+ _path = path if path else []
51	51
52		- self.path += [self.start]
	52	+ _path += [self.start]
53	53	if self.start == self.end:
54		- return self.path
	54	+ return _path
55	55	if self.start not in self.graph:
56	56	return None
57	57	shortest = None
58	58	for node in self.graph[self.start]:
59		- if node not in self.path:
60		- newpath = self.find_shortest_path(node, self.end, self.path)
	59	+ if node not in _path:
	60	+ newpath = self.find_shortest_path(node, self.end, _path[:])
61	61	if newpath:
62	62	if not shortest or len(newpath) < len(shortest):
63	63	shortest = newpath
@@ -82,5 +82,5 @@ def find_shortest_path(self, start, end, path=[]):
82	82
83	83	### OUTPUT ###
84	84	# ['A', 'B', 'C', 'D']
85		- # [['A', 'B', 'C', 'D']]
86		- # ['A', 'B', 'C', 'D']
	85	+ # [['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]
	86	+ # ['A', 'B', 'D']

0 commit comments

Comments

0 (0)