API tools faq
paste
Advertisement
Guest User

GRT2

a guest
Jun 29th, 2016
60
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.84 KB | None | 0 0
raw download clone embed print report
  1. import numpy as np
  2. import timeit
  3. import matplotlib.pyplot as plt
  4. import networkx as nx
  5. import sys
  6. import math
  7.  
  8. n_color = [] # node colors
  9.  
  10. def get_edge_weight(G, i, j):
  11. return G.get_edge_data(i,j, key=0).get('c');
  12. def get_edge_name(G, i, j):
  13. return G.get_edge_data(i,j, key=0).get('n');
  14.  
  15. def init(n):
  16. # START
  17. dist = [];
  18. prev = [];
  19. proc = [];
  20. for i in range(0,n):
  21. dist.append(500000);
  22. prev.append(-1);
  23. proc.append([False]);
  24.  
  25. return [dist, prev, proc];
  26. # STOP
  27.  
  28. def get_min_distance_index(n, dist, proc):
  29. # START
  30. j = 500000;
  31. index = -1;
  32. for i in range(0,n):
  33. if proc[i] == [False]:
  34. if j > dist[i]:
  35. j = dist[i];
  36. index = i;
  37.  
  38. return index;
  39. # STOP
  40.  
  41. def update_distance(G, u, v, dist, prev):
  42. # START
  43. #x = [];
  44. #x.append(get_edge_weight(G,u,v));
  45. #print(str(x[0]));
  46. x = dist[u] + get_edge_weight(G,u,v);
  47. #print(str(x) + str(u) + str(v));
  48. #print("dist" + str(dist[v]))
  49. if x < dist[v]:
  50. #print("Distanz" + str(dist[u]));
  51. dist[v] = dist[u] + get_edge_weight(G,u,v);
  52. #print("Distanz" + str(dist[v]));
  53. prev[v] = u;
  54.  
  55. return [dist, prev];
  56. # STOP
  57.  
  58. def has_unprocessed_nodes(proc):
  59. # START
  60. for i in range(0,len(proc)):
  61. if proc[i]==[False]:
  62. return True;
  63.  
  64. return False;
  65. # STOP
  66.  
  67. def dijkstra(G, start):
  68. # START
  69. [dist, prev, proc] = init(nx.number_of_nodes(G));
  70. dist[start] = 0;
  71. #print(dist);
  72.  
  73. while has_unprocessed_nodes(proc):
  74. #print(has_unprocessed_nodes(proc));
  75. u = get_min_distance_index(nx.number_of_nodes(G),dist,proc);
  76. #print(proc)
  77. proc[u] = [True];
  78. for v in range(0,nx.number_of_nodes(G)):
  79. if(proc[v] == [True]):
  80. L = G.adjacency_list()
  81. for i in range(0,len(L[u])):
  82. [dist,prev] = update_distance(G,u,L[u][i],dist,prev);
  83.  
  84. return [prev, dist];
  85. # STOP
  86.  
  87. def bellman_ford(G, start):
  88. # START
  89. [dist, prev, proc] = init(nx.number_of_nodes(G));
  90. dist[start] = 0;
  91. #print(dist);
  92.  
  93. for i in range(0,nx.number_of_nodes(G)-1):
  94. for u in range(0,nx.number_of_nodes(G)):
  95. L = G.adjacency_list()
  96. for v in range(0,len(L[u])):
  97. [dist,prev] = update_distance(G,u,L[u][v],dist,prev);
  98.  
  99. for u in range(0,nx.number_of_nodes(G)):
  100. L = G.adjacency_list()
  101. for v in range(0,len(L[u])):
  102. if (dist[u] + get_edge_weight(G,u,L[u][v])) < dist[L[u][v]]:
  103. #print("Es existiert ein Zyklus mit negativem Gewicht")
  104. sys.exit()
  105.  
  106. return [prev, dist]
  107. # STOP
  108.  
  109. def heuristic(pos, i, j):
  110. x1 = pos[i][0]
  111. y1 = pos[i][1]
  112. x2 = pos[j][0]
  113. y2 = pos[j][1]
  114. # START
  115. abstand = math.sqrt((x1-x2)**2 + (y1-y2)**2);
  116.  
  117. return abstand
  118. # STOP
  119.  
  120. def get_lowest_f(openList, fscore):
  121. # START
  122. min = 500000;
  123. for i in range(0,len(openList)):
  124. if min > fscore[i]:
  125. min = fscore[i]
  126. index = openList[i];
  127.  
  128. return index;
  129. # STOP
  130.  
  131. def astar(G, pos, start, goal):
  132. # START
  133. prev = []
  134. gscore = []
  135. fscore = []
  136. for i in range(0,nx.number_of_nodes(G)):
  137. prev.append(-1)
  138. gscore.append(500000)
  139. fscore.append(500000)
  140.  
  141. gscore[start] = 0
  142. fscore[start] = gscore[start] + heuristic(pos,start,goal)
  143.  
  144. openList = []
  145. closedList = []
  146.  
  147. openList.append(start)
  148.  
  149. while len(openList) > 0:
  150. current = get_lowest_f(openList,fscore)
  151.  
  152. if current == goal:
  153. #for i in range(0,len(closedList)):
  154. # print(str(closedList[i]))
  155. # n_color[closedList[i]] = 'r'
  156. #for i in range(0,len(openList)):
  157. # n_color[openList[i]] = 'g'
  158. #print(closedList)
  159. #print(openList)
  160. #print(gscore)
  161. #print(fscore)
  162. return prev
  163.  
  164. #print(str(current))
  165. openList.remove(current)
  166. closedList.append(current)
  167.  
  168. L = G.adjacency_list()
  169. for i in range(0,len(L[current])):
  170. bool = True
  171. for j in range(0,len(closedList)):
  172. if closedList[j] == L[current][i]:
  173. bool = False
  174. if bool:
  175. t = gscore[current] + heuristic(pos,current,L[current][i])
  176. if t < gscore[L[current][i]]:
  177. bool2 = True
  178. for k in range(0,len(openList)):
  179. if openList[k] == L[current][i]:
  180. bool2 = False
  181. if bool2:
  182. openList.append(L[current][i])
  183. prev[L[current][i]] = current
  184. gscore[L[current][i]] = t
  185. fscore[L[current][i]] = gscore[L[current][i]] + heuristic(pos,L[current][i],goal)
  186.  
  187. #print(closedList)
  188. #print(openList)
  189. #print(gscore)
  190. #print(fscore)
  191. return prev
  192. # STOP
  193.  
  194. def get_path(G, prev, goal):
  195. # START
  196. P = [];
  197. P.append(goal);
  198. while prev[goal] != -1:
  199. P.append(prev[goal]);
  200. goal = prev[goal];
  201.  
  202. P1 = [];
  203. for i in range(0,len(P)):
  204. P1.append(P[len(P)-1-i])
  205.  
  206. return P1;
  207. # STOP
  208.  
  209. def build_graph():
  210. G = nx.MultiGraph()
  211. for i in range(0, 11):
  212. G.add_node(i)
  213. pos = { 0 : [ 4, 3] }
  214. pos.update( { 1 : [10, 1] } )
  215. pos.update( { 2 : [ 7, 5] } )
  216. pos.update( { 3 : [14, 4] } )
  217. pos.update( { 4 : [12, 6] } )
  218. pos.update( { 5 : [ 3, 8] } )
  219. pos.update( { 6 : [ 8, 9] } )
  220. pos.update( { 7 : [16, 9] } )
  221. pos.update( { 8 : [ 1,14] } )
  222. pos.update( { 9 : [ 5,13] } )
  223. pos.update( { 10 : [13,13] } )
  224. # n := nodename, c := cost
  225. G.add_edge( 0, 1, n='a', c=7 )
  226. G.add_edge( 1, 3, n='b', c=5 )
  227. G.add_edge( 0, 2, n='c', c=1 )
  228. G.add_edge( 2, 3, n='d', c=8 )
  229. G.add_edge( 2, 4, n='e', c=5 )
  230. G.add_edge( 4, 3, n='f', c=4 )
  231. G.add_edge( 3, 7, n='g', c=5 )
  232. G.add_edge(10, 7, n='h', c=5 )
  233. G.add_edge( 6,10, n='i', c=6 )
  234. G.add_edge( 5, 0, n='j', c=5 )
  235. G.add_edge( 5, 4, n='k', c=9 )
  236. G.add_edge( 5, 6, n='l', c=5 )
  237. G.add_edge( 9, 6, n='m', c=5 )
  238. G.add_edge( 5, 9, n='n', c=6 )
  239. G.add_edge( 8, 5, n='o', c=6 )
  240. G.add_edge( 8, 9, n='p', c=4 )
  241. G.add_edge( 4,10, n='q', c=7 )
  242. return [G, pos]
  243.  
  244. def build_squre_lattice_graph(N):
  245. G = nx.MultiGraph()
  246. pos = { 0 : [0,0] }
  247. for i in range(0,N):
  248. for j in range(0,N):
  249. k = i*N+j
  250. G.add_node(k)
  251. pos.update( { k : [i,j] })
  252. for i in range(0,N):
  253. for j in range(0,N):
  254. u = (i)*N+(j)
  255. v = (i+1)*N+(j)
  256. if i+1<N and j<N:
  257. label = str(u) + '0'
  258. G.add_edge( u, v, n=label, c=1 )
  259. u = (i)*N+(j)
  260. v = (i)*N+(j+1)
  261. if i<N and j+1<N:
  262. label = str(u) + '1'
  263. G.add_edge( u, v, n=label, c=1 )
  264. u = (i)*N+(j)
  265. v = (i+1)*N+(j+1)
  266. if i+1<N and j+1<N:
  267. label = str(u) + '2'
  268. G.add_edge( u, v, n=label, c=1 )
  269. u = (i+1)*N+(j)
  270. v = (i)*N+(j+1)
  271. if i+1<N and j+1<N:
  272. label = str(u) + '3'
  273. G.add_edge( u, v, n=label, c=1 )
  274. return [G, pos]
  275.  
  276.  
  277. if __name__ == '__main__':
  278.  
  279. #[G, pos] = build_graph()
  280. [G, pos] = build_squre_lattice_graph(10)
  281.  
  282. #n_color = ['w'] * nx.number_of_nodes(G) # white color
  283.  
  284. start = 0 # index of start node
  285. goal = 99 # index of end node
  286.  
  287. time1 = timeit.default_timer()
  288. [prev, dist] = dijkstra(G, start)
  289. time2 = timeit.default_timer()
  290. print(str(time2-time1))
  291. #print(prev)
  292. #print(dist)
  293.  
  294. time1 = timeit.default_timer()
  295. [prev, dist] = bellman_ford(G, start)
  296. time2 = timeit.default_timer()
  297. print(str(time2-time1))
  298. #print(prev)
  299. #print(dist)
  300.  
  301. time1 = timeit.default_timer()
  302. prev = astar(G, pos, start, goal)
  303. time2 = timeit.default_timer()
  304. print(str(time2-time1))
  305. #print(prev)
  306.  
  307. P = get_path(G, prev, goal)
  308. #print('path := ')
  309. #print(P)
  310.  
  311. #cost = dist[ goal ]
  312. #print('cost := ' + str(cost))
  313.  
  314. plt.clf()
  315. plt.title('Praktikum Graphentheorie: KWP')
  316. plt.gca().invert_yaxis()
  317. nx.draw_networkx(G, pos)
  318. nx.draw_networkx_nodes(G, pos, node_color=n_color)
  319. nx.draw_networkx_edges(G, pos)
  320. #nx.draw_networkx_edge_labels(G, pos)
  321. plt.show();
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!