Skip to content

Commit 6549ce0

Browse files
sinanazemsinanazem
committed
add graph
1 parent f6d3c80 commit 6549ce0

File tree

1 file changed

+250
-0
lines changed

1 file changed

+250
-0
lines changed

‎data-structure/graph/graph.ipynb‎

Lines changed: 250 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,250 @@
1+
{
2+
"cells": [
3+
{
4+
"cell_type": "code",
5+
"execution_count": 116,
6+
"metadata": {},
7+
"outputs": [],
8+
"source": [
9+
"class Graph:\n",
10+
" def __init__(self, edge) -> None:\n",
11+
" self.edge = edge\n",
12+
" self.adj_dict = dict()\n",
13+
" self.create_adj_dict()\n",
14+
" \n",
15+
" \n",
16+
" def create_adj_dict(self):\n",
17+
" for start, dist in self.edge:\n",
18+
" if start in self.adj_dict:\n",
19+
" self.adj_dict[start].append(dist)\n",
20+
" else:\n",
21+
" self.adj_dict[start] = [dist]\n",
22+
" \n",
23+
" def get_path(self, start, dist, path=[]):\n",
24+
" path = path + [start]\n",
25+
" if start == dist:\n",
26+
" return [path]\n",
27+
" \n",
28+
" if start not in self.adj_dict:\n",
29+
" return []\n",
30+
" \n",
31+
" paths = []\n",
32+
" for vertex in self.adj_dict[start]:\n",
33+
" if vertex not in path:\n",
34+
" new_paths = self.get_path(vertex, dist, path)\n",
35+
" for p in new_paths:\n",
36+
" paths.append(p)\n",
37+
" return paths\n",
38+
" \n",
39+
" def shortest_path(self, start, dist, path=[]):\n",
40+
" a = self.get_path(start, dist, path)\n",
41+
" a2 = [(index, len(list_)) for index, list_ in enumerate(a)]\n",
42+
" index = sorted(a2, key=lambda x: x[1])[0][0]\n",
43+
" \n",
44+
" return a[index]\n",
45+
" \n",
46+
" \n",
47+
" def shortest_path_2(self, start, dist, path=[]):\n",
48+
" path = path + [start]\n",
49+
" if start == dist:\n",
50+
" return path\n",
51+
" \n",
52+
" if start not in self.adj_dict:\n",
53+
" return None\n",
54+
" \n",
55+
" short_path = None\n",
56+
" \n",
57+
" for vertex in self.adj_dict[start]:\n",
58+
" if vertex not in path:\n",
59+
" n_sp = self.shortest_path(vertex, dist, path)\n",
60+
" if n_sp:\n",
61+
" if short_path is None or len(n_sp) < len(short_path):\n",
62+
" short_path = n_sp\n",
63+
" return short_path"
64+
]
65+
},
66+
{
67+
"cell_type": "code",
68+
"execution_count": 117,
69+
"metadata": {},
70+
"outputs": [],
71+
"source": [
72+
"\n",
73+
"routes = [\n",
74+
" (\"Kerman\", \"Yazd\"),\n",
75+
" (\"Kerman\", \"Esfahan\"),\n",
76+
" (\"Esfahan\", \"Mashhad\"),\n",
77+
" (\"Yazd\", \"Mashhad\"),\n",
78+
" (\"Yazd\", \"Esfahan\"),\n",
79+
" (\"Mashhad\", \"Tehran\"),\n",
80+
"]"
81+
]
82+
},
83+
{
84+
"cell_type": "code",
85+
"execution_count": 118,
86+
"metadata": {},
87+
"outputs": [],
88+
"source": [
89+
"obj = Graph(routes)"
90+
]
91+
},
92+
{
93+
"cell_type": "code",
94+
"execution_count": 119,
95+
"metadata": {},
96+
"outputs": [
97+
{
98+
"data": {
99+
"text/plain": [
100+
"{'Kerman': ['Yazd', 'Esfahan'],\n",
101+
" 'Esfahan': ['Mashhad'],\n",
102+
" 'Yazd': ['Mashhad', 'Esfahan'],\n",
103+
" 'Mashhad': ['Tehran']}"
104+
]
105+
},
106+
"execution_count": 119,
107+
"metadata": {},
108+
"output_type": "execute_result"
109+
}
110+
],
111+
"source": [
112+
"obj.adj_dict"
113+
]
114+
},
115+
{
116+
"cell_type": "code",
117+
"execution_count": 120,
118+
"metadata": {},
119+
"outputs": [
120+
{
121+
"data": {
122+
"text/plain": [
123+
"[['Kerman']]"
124+
]
125+
},
126+
"execution_count": 120,
127+
"metadata": {},
128+
"output_type": "execute_result"
129+
}
130+
],
131+
"source": [
132+
"obj.get_path(\"Kerman\", \"Kerman\")"
133+
]
134+
},
135+
{
136+
"cell_type": "code",
137+
"execution_count": 121,
138+
"metadata": {},
139+
"outputs": [
140+
{
141+
"data": {
142+
"text/plain": [
143+
"[]"
144+
]
145+
},
146+
"execution_count": 121,
147+
"metadata": {},
148+
"output_type": "execute_result"
149+
}
150+
],
151+
"source": [
152+
"obj.get_path(\"Shiraz\", \"Kerman\")"
153+
]
154+
},
155+
{
156+
"cell_type": "code",
157+
"execution_count": 123,
158+
"metadata": {},
159+
"outputs": [
160+
{
161+
"data": {
162+
"text/plain": [
163+
"[['Kerman', 'Yazd', 'Mashhad', 'Tehran'],\n",
164+
" ['Kerman', 'Yazd', 'Esfahan', 'Mashhad', 'Tehran'],\n",
165+
" ['Kerman', 'Esfahan', 'Mashhad', 'Tehran']]"
166+
]
167+
},
168+
"execution_count": 123,
169+
"metadata": {},
170+
"output_type": "execute_result"
171+
}
172+
],
173+
"source": [
174+
"\n",
175+
"obj.get_path(\"Kerman\", \"Tehran\")"
176+
]
177+
},
178+
{
179+
"cell_type": "code",
180+
"execution_count": 124,
181+
"metadata": {},
182+
"outputs": [
183+
{
184+
"name": "stdout",
185+
"output_type": "stream",
186+
"text": [
187+
"4 µs ± 52.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n"
188+
]
189+
}
190+
],
191+
"source": [
192+
"%%timeit\n",
193+
"obj.shortest_path(\"Kerman\", \"Tehran\")"
194+
]
195+
},
196+
{
197+
"cell_type": "code",
198+
"execution_count": 125,
199+
"metadata": {},
200+
"outputs": [
201+
{
202+
"name": "stdout",
203+
"output_type": "stream",
204+
"text": [
205+
"4.42 µs ± 55 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n"
206+
]
207+
}
208+
],
209+
"source": [
210+
"%%timeit\n",
211+
"obj.shortest_path_2(\"Kerman\", \"Tehran\")"
212+
]
213+
},
214+
{
215+
"cell_type": "code",
216+
"execution_count": null,
217+
"metadata": {},
218+
"outputs": [],
219+
"source": []
220+
},
221+
{
222+
"cell_type": "code",
223+
"execution_count": null,
224+
"metadata": {},
225+
"outputs": [],
226+
"source": []
227+
}
228+
],
229+
"metadata": {
230+
"kernelspec": {
231+
"display_name": "ml_env",
232+
"language": "python",
233+
"name": "python3"
234+
},
235+
"language_info": {
236+
"codemirror_mode": {
237+
"name": "ipython",
238+
"version": 3
239+
},
240+
"file_extension": ".py",
241+
"mimetype": "text/x-python",
242+
"name": "python",
243+
"nbconvert_exporter": "python",
244+
"pygments_lexer": "ipython3",
245+
"version": "3.9.18"
246+
}
247+
},
248+
"nbformat": 4,
249+
"nbformat_minor": 2
250+
}

0 commit comments

Comments
 (0)