API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jan 27th, 2020
86
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.95 KB | None | 0 0
raw download clone embed print report
  1. const data = {
  2. "algorithmData":{
  3. "0":{
  4. "left":{
  5. "0_0_0_1":{
  6. "parkingSpaceID":"0_0_0_1",
  7. "isValid":true,
  8. "parkingSpaceNumber":1
  9. },
  10. "0_0_0_2":{
  11. "parkingSpaceID":"0_0_0_2",
  12. "isValid":true,
  13. "parkingSpaceNumber":2
  14. },
  15. "0_0_0_3-invalid_OQzhP":{
  16. "parkingSpaceID":"0_0_0_3-invalid_OQzhP",
  17. "isValid":false,
  18. "parkingSpaceNumber":3
  19. },
  20. "0_0_0_4-invalid_25qO6":{
  21. "parkingSpaceID":"0_0_0_4-invalid_25qO6",
  22. "isValid":false,
  23. "parkingSpaceNumber":4
  24. },
  25. "0_0_0_5-invalid_NJ2Aw":{
  26. "parkingSpaceID":"0_0_0_5-invalid_NJ2Aw",
  27. "isValid":false,
  28. "parkingSpaceNumber":5
  29. },
  30. "0_0_0_6-invalid_Qlh6u":{
  31. "parkingSpaceID":"0_0_0_6-invalid_Qlh6u",
  32. "isValid":false,
  33. "parkingSpaceNumber":6
  34. },
  35. "0_0_0_7-invalid_xZDL4":{
  36. "parkingSpaceID":"0_0_0_7-invalid_xZDL4",
  37. "isValid":false,
  38. "parkingSpaceNumber":7
  39. },
  40. "0_0_0_8-invalid_msNUp":{
  41. "parkingSpaceID":"0_0_0_8-invalid_msNUp",
  42. "isValid":false,
  43. "parkingSpaceNumber":8
  44. }
  45. },
  46. "right":{
  47. "0_1_0_1":{
  48. "parkingSpaceID":"0_1_0_1",
  49. "isValid":true,
  50. "parkingSpaceNumber":1
  51. },
  52. "0_1_0_2":{
  53. "parkingSpaceID":"0_1_0_2",
  54. "isValid":true,
  55. "parkingSpaceNumber":2
  56. },
  57. "0_1_0_3-invalid_9qApW":{
  58. "parkingSpaceID":"0_1_0_3-invalid_9qApW",
  59. "isValid":false,
  60. "parkingSpaceNumber":3
  61. },
  62. "0_1_0_4":{
  63. "parkingSpaceID":"0_1_0_4",
  64. "isValid":true,
  65. "parkingSpaceNumber":4
  66. },
  67. "0_1_0_5":{
  68. "parkingSpaceID":"0_1_0_5",
  69. "isValid":true,
  70. "parkingSpaceNumber":5
  71. },
  72. "0_1_0_6":{
  73. "parkingSpaceID":"0_1_0_6",
  74. "isValid":true,
  75. "parkingSpaceNumber":6
  76. },
  77. "0_1_0_7-invalid_zQN3G":{
  78. "parkingSpaceID":"0_1_0_7-invalid_zQN3G",
  79. "isValid":false,
  80. "parkingSpaceNumber":7
  81. },
  82. "0_1_0_8":{
  83. "parkingSpaceID":"0_1_0_8",
  84. "isValid":true,
  85. "parkingSpaceNumber":8
  86. }
  87. }
  88. },
  89. "1":{
  90. "left":{
  91. "1_0_0_1":{
  92. "parkingSpaceID":"1_0_0_1",
  93. "isValid":true,
  94. "parkingSpaceNumber":1
  95. },
  96. "1_0_0_2":{
  97. "parkingSpaceID":"1_0_0_2",
  98. "isValid":true,
  99. "parkingSpaceNumber":2
  100. },
  101. "1_0_0_3-invalid_RxtPW":{
  102. "parkingSpaceID":"1_0_0_3-invalid_RxtPW",
  103. "isValid":false,
  104. "parkingSpaceNumber":3
  105. },
  106. "1_0_0_4":{
  107. "parkingSpaceID":"1_0_0_4",
  108. "isValid":true,
  109. "parkingSpaceNumber":4
  110. },
  111. "1_0_0_5":{
  112. "parkingSpaceID":"1_0_0_5",
  113. "isValid":true,
  114. "parkingSpaceNumber":5
  115. },
  116. "1_0_0_6":{
  117. "parkingSpaceID":"1_0_0_6",
  118. "isValid":true,
  119. "parkingSpaceNumber":6
  120. },
  121. "1_0_0_7-invalid_FK3hF":{
  122. "parkingSpaceID":"1_0_0_7-invalid_FK3hF",
  123. "isValid":false,
  124. "parkingSpaceNumber":7
  125. },
  126. "1_0_0_8":{
  127. "parkingSpaceID":"1_0_0_8",
  128. "isValid":true,
  129. "parkingSpaceNumber":8
  130. }
  131. }
  132. }
  133. }
  134. }
  135.  
  136. const graph = {
  137. ingang: {'0': 0, 'B': 2},
  138. //Eerste verdieping
  139. '0': {AW1: 0},
  140. AW1: {AP1: 5, AP2: 5, AW2: 0},
  141. AW2: {AP3: 4, AP4: 4, AW3: 0},
  142. AW3: {AP5: 3, AP6: 3, AW4: 0},
  143. AW4: {AP7: 2, AP8: 2, AW5: 0},
  144. AW5: {AP9: 1, AP10: 1},
  145. AP1: {uitgang: 0},
  146. AP2: {uitgang: 0},
  147. AP3: {uitgang: 0},
  148. AP4: {uitgang: 0},
  149. AP5: {uitgang: 0},
  150. AP6: {uitgang: 0},
  151. AP7: {uitgang: Infinity},
  152. AP8: {uitgang: Infinity},
  153. AP9: {uitgang: Infinity},
  154. AP10: {uitgang: Infinity},
  155. //Tweede verdieping
  156. 'B': {BW1: 0},
  157. BW1: {BP1: 5, BW2: 0},
  158. BW2: {BP2: 4, BW3: 0},
  159. BW3: {BP3: 3, BW4: 0},
  160. BW4: {BP4: 2, BW5: 0},
  161. BW5: {BP5: 1},
  162. BP1: {uitgang: 1},
  163. BP2: {uitgang: 1},
  164. BP3: {uitgang: 1},
  165. BP4: {uitgang: 1},
  166. BP5: {uitgang: 1},
  167. uitgang: {},
  168. };
  169.  
  170. const tempGraph = {
  171. 'ingang': {},
  172. 'uitgang': {}
  173. }
  174.  
  175. const makeGraph = (data) => {
  176. const parkingSpots = data.algorithmData
  177. let connectionNodeI = 0
  178. let floorNodeI = 0
  179.  
  180. //Loop through all the floors
  181. for(const floor in parkingSpots) {
  182. //For each floor add the floor to the start node
  183. tempGraph.ingang[floor] = floorNodeI
  184. //Get the keys for the left right places
  185. const LR = Object.keys(parkingSpots[floor])
  186. //Loop through all the spots and added them to the node graph
  187. let countSpots = 0
  188. //Count how many spots there are for each floor
  189. if(LR.length > 1) {
  190. LR.forEach(function (spot, index) {
  191. countSpots += Object.keys(parkingSpots[floor][spot]).length / 2
  192. })
  193. } else {
  194. LR.forEach(function (spot, index) {
  195. countSpots += Object.keys(parkingSpots[floor][spot]).length
  196. })
  197. }
  198.  
  199. //Add the connection nodes to the graph
  200. for (const spotList in parkingSpots[floor]){
  201. console.log(spotList)
  202. for (var i = 1; i <= countSpots; i++){
  203. if (!((floor + '_' + 'C' + i) in tempGraph)) {
  204. if (i >= countSpots/2) {
  205. tempGraph[floor + '_' + 'C' + i] = {}
  206. } else if (i === 1) {
  207. tempGraph[floor + '_' + 'C' + i] = {}
  208. tempGraph[floor + '_' + 'C' + i][floor + '_' + 'C' + (i+1)] = 0
  209. tempGraph[floor] = {}
  210. tempGraph[floor][floor + '_' + 'C' + i] = 0
  211. } else {
  212. tempGraph[floor + '_' + 'C' + i] = {}
  213. tempGraph[floor + '_' + 'C' + i][floor + '_' + 'C' + (i+1)] = 0
  214. }
  215. } else {
  216. continue;
  217. }
  218.  
  219. }
  220. let iSpot = 1
  221. for (const spotKey in parkingSpots[floor][spotList]) {
  222. let spot = parkingSpots[floor][spotList][spotKey];
  223.  
  224. if (spot['isValid']) {
  225. tempGraph[floor + '_' + 'C' + iSpot][spot['parkingSpaceID']] = 0
  226. tempGraph[spot['parkingSpaceID']] = {'uitgang': 0}
  227. } else {
  228. tempGraph[floor + '_' + 'C' + iSpot][spot['parkingSpaceID']] = Infinity
  229. tempGraph[spot['parkingSpaceID']] = {'uitgang': Infinity}
  230.  
  231. }
  232. iSpot++;
  233. }
  234. }
  235.  
  236.  
  237. floorNodeI++;
  238. }
  239.  
  240. console.log('TEMP', tempGraph)
  241. }
  242.  
  243. makeGraph(data)
  244.  
  245. const findLowestCostNode = (costs, processed) => {
  246. const knownNodes = Object.keys(costs);
  247.  
  248. return knownNodes.reduce((lowest, node) => {
  249. if (lowest === null && !processed.includes(node)) {
  250. lowest = node;
  251. }
  252. if (costs[node] < costs[lowest] && !processed.includes(node)) {
  253. lowest = node;
  254. }
  255. return lowest;
  256. }, null)
  257. };
  258.  
  259. // function that returns the minimum cost and path to reach Finish
  260. const dijkstra = (graph) => {
  261.  
  262. // de kosten van de childnodes van de parent node (bij het begin dus ingang)
  263. const trackedCosts = Object.assign({uitgang: Infinity}, graph.ingang);
  264. console.log(trackedCosts)
  265.  
  266. // Hier worden de naam van de parent node van de child nodes opgeslagen
  267. const trackedParents = {uitgang: null};
  268. for (let child in graph.ingang) {
  269. trackedParents[child] = 'ingang';
  270. }
  271.  
  272. //De lijst van de langsgelopen nodes
  273. const processedNodes = [];
  274.  
  275. //Vind de laagste kostende node
  276. let node = findLowestCostNode(trackedCosts, processedNodes);
  277.  
  278. while (node) {
  279. //Hoeveel het kost om naar die node te gaan
  280. let costToReachNode = trackedCosts[node];
  281. //De children van de node die nu wordt behandeld
  282. let childrenOfNode = graph[node];
  283.  
  284. for (let child in childrenOfNode) {
  285. //Hoeveel het cost van de parent node naar de child node te gaan
  286. let costFromNodetoChild = childrenOfNode[child];
  287. //De totale kosten om deze route te volgen
  288. let costToChild = costToReachNode + costFromNodetoChild;
  289. //Checken of de node al in de lijst van langsgelopen nodes zit of dat de kosten van de loop hoger is dan de kost naar de child
  290. if (!trackedCosts[child] || trackedCosts[child] > costToChild) {
  291. //Voeg node toe aan aan de kosten van de langsgelopen nodes
  292. trackedCosts[child] = costToChild;
  293. //Voeg parent van de node toe aan de trackedParents lijst
  294. trackedParents[child] = node;
  295. }
  296. }
  297. //Voeg node toe aan langsgelopen nodes
  298. processedNodes.push(node);
  299. //Ga naar volgende node in de lijst
  300. node = findLowestCostNode(trackedCosts, processedNodes);
  301. }
  302. //Hierin komen de nodes voor het meest optimale pad
  303. let optimalPath = ['uitgang'];
  304. //Pak de node waarbij de child uitgang is
  305. let parent = trackedParents.uitgang;
  306. //Loop door trackedParents tot dat er geen parent node meer is
  307. while (parent) {
  308. optimalPath.push(parent);
  309. parent = trackedParents[parent];
  310. }
  311. //Draai de lijst om en haal uitgang weg
  312. optimalPath.reverse().pop(-1);
  313. //Return de optimale pad
  314. return optimalPath;
  315. };
  316. // makeGraph(data)
  317.  
  318. console.log(dijkstra(tempGraph));
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!