metro.lisp

(setq net '((	A  	B 	C  	D	E	F)
		    ((A 0) 	00	2	4 	8 	0	16)
		    ((B 0)	2	00	0	3	0	0 )
		    ((C 0)	4	0	00	3	0	0 )
		    ((D 0)	8	3	3	00	5	3 )
		    ((E 0)	0	0	0	5	00	5 )
		    ((F 0)	16	0	0	3	5	00)
		)
)

(setq infinity 1000) ; Áàãîôèêñ infinity =  max (net) + 1

(defun createListOfUnxploredNodes (net start) 
"Ôóíêöèÿ ñîçäàåò ñïèñîê íåèñëåäîâàííûõ âåðøèí âèäà:((A <infinity> 0 0) (B <infinity> 0 0) .. )"
	(cond (
		(eq (car net) nil) 
		;Åñëè ïðîñìîòðåëè âñå âåðøèíû â ñåòè, òî âûõîäèì èç ðåêóðñèè
		nil
	)
	(T
		(cons
		(append
			(append
			(append
				(cons (append nil (caar net)) nil)
				(cond
				(
					(eq(caar net) start)
					(cons
						`0
						nil
					)
				)
				(T
					(cons
									infinity
										nil
									)
								)
							)
						)
						`(((0)))
					)
					`(0)
				)
				(createListOfUnxploredNodes
					(cons
						(cdar net)
						nil
					)
					start
				)
			)
		)
	)
)

(defun deleteVisitedNode(nodesList nodeToDelete)	
"Âîçâðàùàåò ñïèñîê nodesList áåç ýëåìåíòà nodeToDelete, íå ìîäèôèöèðóÿ èñõîäíûé ñïèñîê."
	(cond
		(
			(eq(caar nodesList) nodeToDelete)
				(cdr nodesList)
		)
		(T
			(cons
				(car nodesList)
				(deleteVisitedNode (cdr nodesList) nodeToDelete)
			)
		)
	)
)


(defun findConnectedNodes (net nodeToProcess listOfAllNodes avaibleNodes) 
"Ôóíêöèÿ âûâîäèò ñïèñîê ñîåäèííåíûõ ñ âåðøèíîé nodeToProcess èç net, åñëè âåðøèíà â net åñòü â avaibleNodes"
	(cond
		(
			(eq (caaadr net) nodeToProcess) 
			;Åñëè íàøëè âåðøèíó â íóæíîé ñòðîêå, òî
				(   ;Ïðîñìàðèâàåì âñå ÿ÷åéêè â íàéäåííîé ñòðîêå è åñëè âòðåòèòüñÿ ÿ÷åéêà â êîòîðîé íå 0, òî äîáàâëÿåì åå â ñïèñîê âûõîäíûõ ïðàìåòðîâ
					extendResult (exploreConnectionsOfNode (cdadr net) listOfAllNodes) 
					avaibleNodes
				)

		)
		(T	;Åñëè íå íàøëè, òî ïðîñìàòðèâàåì ñëåäóþùóþ ñòðîêó
			(findConnectedNodes (cdr net) nodeToProcess listOfAllNodes avaibleNodes)
		)
	)
)

(defun exploreConnectionsOfNode (lineToExplore listOfAllNodes) 
 "Ôóíêöèÿ ïðîñìîòðà âñåõ ÿ÷åéêè â íàéäåííîé ñòðîêå è åñëè âòðåòèòüñÿ ÿ÷åéêà â êîòîðîé íå 0, òî äîáàâëÿåì åå â ñïèñîê âûõîäíûõ ïðàìåòðîâ"
	(cond
		(
			(eq (car lineToExplore) nil) 
			;Åñëè ïðîñìîòðåëè âåñü ñïèñîê, òî âûõîäèì èç ðåêóðñèè
			nil
		)
		(T
			(cond
				(
					(> (car lineToExplore) 0)
						(cons
							(append
								(cons(car listOfAllNodes) nil)
								(cons(car lineToExplore) nil)
							)
							(exploreConnectionsOfNode (cdr lineToExplore) (cdr listOfAllNodes))
						)
				)
				(T
					(exploreConnectionsOfNode (cdr lineToExplore) (cdr listOfAllNodes))
				)
			)
		)
	)

)

(defun findListWithNodeInHead (searchingNode nodesList)
	(cond
		(
			(eq (car nodesList) nil)
				nil
		)
		(T
			(cond
				(
					(eq(caar nodesList) searchingNode)
						(car nodesList)
				)
				(T
					(findListWithNodeInHead searchingNode (cdr nodesList))
				)
			)
		)
	)
)

(defun extendResult(listOfConnectedNodes avaibleNodes) 
	"Ðàñøèðÿåò ïîëó÷åííûé ñïèñîê âåðøèí âèäà: ((A 3) (B 7)) äî âèäà: ((A 1000 ((0)) 3) (B 1000 ((0)) 7))"
	(cond												
	;Ïðè ýòîì ïðîñìàòðèâàÿ avaibleNodes, åñëè êàêîé-òî âåðøèíû òàì íåò, òî îíà íå ïîïàäåò â ðåçóëüòèðóþùèé ñïèñîê
		(
			(eq (car listOfConnectedNodes) nil) 
			;Åñëè ïðîñìîòðåëè âåñü ñïèñîê, òî âûõîäèì èç ðåêóðñèè
				nil
		)
		(T
			(cond
				(
					(eq
						(setq 
							obtainedList 
							;Íàõîäèò â ñïèñêå äîñòóïíûõ âåðøèí ñïèñîê èñêîìîé âåðøèíû
							(findListWithNodeInHead (caar listOfConnectedNodes) avaibleNodes )
						)  
						nil
					)
						(cond
							(
								(eq (car listOfConnectedNodes) nil) 
								;Åñëè ïðîñìîòðåëè âåñü ñïèñîê, òî âûõîäèì èç ðåêóðñèè
									nil
							)
							(T
								(extendResult (cdr listOfConnectedNodes) avaibleNodes)
							)
						)
				)
				(T
					(append
						(cons
							(append
								(append
									(append
										(cons
											(car obtainedList)
											nil
										)
										(cons
											(cadr obtainedList)
											nil
										)
									)
									(cons
										(caddr obtainedList)
										nil
									)
								)
								(cons
									(+
										(cadddr obtainedList)
										(cadar listOfConnectedNodes)
									)
									nil
								)
							)
							nil
						)
						(extendResult (cdr listOfConnectedNodes) avaibleNodes)
					)
				)
			)
		)
	)
)




(defun findDistanceToConnectedNodes (net connectedNodes currentNode)
	"Ôóíêöèÿ ïðîñìàòðèâàåì ñïèñîê ñîåäèííåíûõ âåðøèí è ëèáî çàìåíÿåò ðàññòîÿíèå, åñëè îíî ìåíüøå, ëèáî îñòàâëÿåò òàê êàê åñòü"
	(cond
	;Ïðè ýòîì ïðîñìàòðèâàÿ avaibleNodes, åñëè êàêîé-òî âåðøèíû òàì íåò, òî îíà íå ïîïàäåò â ðåçóëüòèðóþùèé ñïèñîê
		(
			(eq (setq processingNode (car connectedNodes)) nil) 
			;Åñëè ïðîñìîòðåëè âåñü ñïèñîê, òî âûõîäèì èç ðåêóðñèè
				nil
		)
		(T
			(cons
				(findDistanceToNode net currentNode processingNode)
				(findDistanceToConnectedNodes net (cdr connectedNodes) currentNode)
			)
		)
	)
)


(defun findDistanceToNode (net currentNode observingNode)
	(append
		(cons
			(car observingNode) ;Ïîëó÷àåì èìÿ âåðøèíû observingNode
			nil
		)
		(cons
			(+ 
			;Ñêëàäûâàåì distance observingNode ñ value currentNode è ñ âåñîì ïåðåõîäà íà observingNode è ïîìåùàåì âñå ýòî â distance observingNode
				(cadddr observingNode)
				(+
					(cadr currentNode)
					(findTransferCost net observingNode) 
					;Íàõîäèì ñêîëüêî "âåñèò" ïåðåñàäêà íà ñòàíöèè observingNode
				)
			)
			nil
		)
	)
)

(defun findTransferCost (net observingNode)
	(cond
		(
			(eq (caaadr net) (car observingNode))
				(car(cdaadr net))
		)
		(T
			(findTransferCost (cdr net) observingNode)
		)
	)
)
(defun createOuputMessage (outPut)
	(append
		(cons
			"Ñàìàÿ êîðîòêàÿ äèñòàíöèÿ:"
			nil
		)
		(append
			(cons
				(cadr outPut)
				nil
			)
			(append
				(cons
					"è ñàìûå êîðîòêèå ïóòè:"
					nil
				)
				(addGoalToListOfWays (car outPut) (caddr outPut))
			)
		)
	)
)
(defun addGoalToListOfWays (finalNode listOfWays)
	(cond
		(
			(eq (car listOfWays) nil)
			nil
		)
		(T
			(cons
				(append
					(car  listOfWays)
					(cons finalNode nil)
				)
				(addGoalToListOfWays finalNode (cdr listOfWays))
			)
		)
	)
)

(defun lookingFor (net start goal &optional listOfUnexploredNodes )
 "Îñíîâíàÿ ôóíêöèÿ ïîèñêà: ìàññèâ, íà÷àëüíàÿ òî÷êà, ôèíèøíàÿ òî÷êà, îòôîðìàòèðîâàííûé ñïèñîê ñ âåðøèíàìè òèïà <infinity>"
	(cond
		((eq start goal)(createOuputMessage outPut))
		(T (lookingFor	net
				(car
					(setq outPut (
						findNodeWithSmallestValue  
						;Ôóíêöèÿ íàõîäèò âåðøóñó ñ ìèíèìëüíûì value è âîçâðàùàåò åå â âèäå (D 10 ((B C) (A F)) X)
						;Ôóíêöèÿ replaceValueAndListOfNodesIfNeeded âåðíåò ñïèñîê âåðøèí, ñðåäè êîòîðûõ íàõîäèì âåðøèíó ñ ìèíèìàëüíûì value
						(setq listOfUnexploredNodes	
							(replaceValueAndListOfNodesIfNeeded	
							;1 àðãåìåíò - findDistanceToConnectedNodes
							;findDistanceToConnectedNodes Âåðíåò ñïèñîê âåðøèí è ðàññòîÿíèÿ äî íèõ. Äàëåå íóæíî ïðîñìîòðåòü ýòîò ñïèñîê è ñïèñîê íåèñëåäîâàííûõ âåðøèí è ãäå íàäî óñòàíîâèòü íîâîå çíà÷åíèå.
								(findDistanceToConnectedNodes
									;Ïåðâûé àðãóìåíò - èñõîäíàÿ ñõåìà, äëÿ îïðåäåëåíèÿ çàäåðæåê ïðè ïåðåñàäêàõ íà ñòàíöèÿõ
									net 
									;Âòîðîé àðãóìåíò  - ñîåäèíåííûå âåðøèíû
									(findConnectedNodes 
										;Íàõîäèì ñâÿçàííûå âåðøèíû ñ òåêóùåé
										net  
										(cond (
												(eq listOfUnexploredNodes nil)
												(car (setq currentNode 
													;Ïîëó÷èëè òåêóùóþ âåðøèíó â âèäå (A 0 (0) 0)
														(car (extendResult  
																(cons(append (cons start nil) `(0)) nil)
																(setq unexploredNodes (createListOfUnxploredNodes net start))
															)
														)
													)
												)
											)
											(T (car
													(setq currentNode 
													;Ïîëó÷èëè òåêóùóþ âåðøèíó â âèäå (A 0 (0) 0)
													(car(extendResult  (cons(append (cons start nil) `(0)) nil) listOfUnexploredNodes))
													)
											    )
											)
										)
										(car net)
										(cond 	( 
													(eq listOfUnexploredNodes nil)
													(setq listOfUnexploredNodes	
													;Ñîõðàíÿåì ïîëó÷åííûé ñïèñêî â unexloredNodes
														(deleteVisitedNode 	
														;deleteVisitedNode âåðíåò ñïèñîê íåèññëåäîâàííûõ âåðøèí áåç ìîäèôèêàöèè èñõîäíîãî
															(setq unexploredNodes (createListOfUnxploredNodes net start)) 
															(car currentNode)
														)
													)
												)
												(T 	(setq listOfUnexploredNodes	
													;Ñîõðàíÿåì ïîëó÷åííûé ñïèñêî â unexloredNodes
														(deleteVisitedNode 	listOfUnexploredNodes 
														;deleteVisitedNode âåðíåò ñïèñîê íåèññëåäîâàííûõ âåðøèí áåç ìîäèôèêàöèè èñõîäíîãî
															(car currentNode)
														)
													)
												)
										)
									) ; Ýòà ñêîáêà çàêðûâàåò findConnectedNodes 
									currentNode ;Òðåòèé - òåêóùàÿ ðàññìàòðèâàåìàÿ âåðøèíà
								) ; Ýòà ñêîáêà çàêðûâàåò findDistanceToConnectedNodes
								;2îé - ñïèñîê íåïîñåùåííûõ âåðøèí
								listOfUnexploredNodes
								;3é - ñïèñîê âåðøèí òåêóùåé âåðøèíû + èìÿ òåêóùåé âåðøèíû
								(createOutputListOfNodesForCurrentNode 	
								;Ó òåêóùåé âåðøèíû B åñòü ñïèñîê âèäà: ((A E) (C D)), ôóíêöèÿ âîçâðàùàåò ñïèñîê âèäà ((A E B) (C D B))
								;Åñëè ñïèñîê âåðøùèí ó òåêóùåé âåðøèíû èìååò âèä: ((A E)), òî ôóíêöèÿ âåðíåò ñïèñîê ((A E B))
								;Åñëè ñïèñîê âåðøèí ó òåêóùåé âåðøèíû èìååò âèä: (0), òî ôóíêöèÿ âåðíåò ((B))
									(car currentNode) ;1 àðãóìåíò èìÿ âåðøèíû
									(caddr currentNode) ;2 àðãóìåíò ñïèñîê âåðøèí
								)
							) ; Ýòà ñêîáêà çàêðûâàåò replaceValueAndListOfNodesIfNeeded
						)
					)
				)
			)
			goal
			listOfUnexploredNodes
			)
		)
	)
)

(defun findNodeWithSmallestValue (lisOfNodes &optional currentMin)
"Íàõîäèò âåðøèíó ñ íàèìåíüøèì çíà÷åíèåì"
	(cond
		(
			(eq (car lisOfNodes) nil)
				currentMin
		)
		(
			(eq currentMin nil)
				(findNodeWithSmallestValue	
					(cdr lisOfNodes)
					(setq currentMin (car lisOfNodes))
				)
		)
		(T
			(findNodeWithSmallestValue		(cdr lisOfNodes)
											(minOfTwoNodes currentMin (car lisOfNodes))
			)
		)
	)
)

(defun minOfTwoNodes (node1 node2)
"Ñðàâíèâàåò 2 âåðøèíû"
	(cond
		(
			(<
				(cadr node1)
				(cadr node2)
			)
				node1
		)
		(T
			node2
		)
	)
)

(defun createOutputListOfNodesForCurrentNode (nodeName listOfNodeForCurrentNode)
	(cond
		(
			(eq (car listOfNodeForCurrentNode) nil)
				nil
		)
		(T
			(cons
				(cond
					(
						(eq (caar listOfNodeForCurrentNode) `0)
							(cons
								nodeName
								nil
							)
					)
					(T
						(append
							(car listOfNodeForCurrentNode)
							(cons
								nodeName
								nil
							)
						)
					)
				)
				(createOutputListOfNodesForCurrentNode nodeName (cdr listOfNodeForCurrentNode))
			)
		)
	)
)

(defun getConnectedNodeByCurrentUnxploredNode (nodeToSeach listOfNodes)
	(cond
		(
			(eq (car listOfNodes) nil)
				nil
 		)
		(T
			(cond
				(
					(eq (caar listOfNodes) nodeToSeach)
						(car listOfNodes)
				)
				(T
					(getConnectedNodeByCurrentUnxploredNode nodeToSeach (cdr listOfNodes))
				)
			)
		)
	)
)

(defun replaceValueAndListOfNodesIfNeeded (listOfConnectedNode listOfUnexploredNodes listOfNodeToReplacePath)
	;Òóò èìååì íà ìåñòå listOfConnectedNode ñïèñîê âèäà: ((B 7) (D 14) ..)
	;Íàõîäèì â ñïèñêå listOfUnexploredNodes âåðøèíó ñ ïîõîæèì íàçâàíèåì, íàïðèìåð (D 1000 0 0)
	;È åñëè âòîðîé ïàðàìåòð (1000) > âòîðîãî ïàðàìåòðà 1îãî ñïèñêà (14), òî çàìåíÿåì 1000 íà 14
	;è çàìåíÿåì ñïèñîê âåðøèí îò òåêóùåé âåðøèíû
	;Ôîðìàò listOfConnectedNode ((B 4) (D 7))
	;Ôîðìàò listOfUnexploredNodes ((B 1000 (0) 0) (C 1000 (0) 0) (D 1000 (0) 0) (E 1000 (0) 0))
	(cond
		(
			(eq (car listOfUnexploredNodes) nil)
			nil
		)
		(T
			(cond
				(
					(eq(setq foundedNode 	(getConnectedNodeByCurrentUnxploredNode (caar listOfUnexploredNodes)
																					listOfConnectedNode
											)
						)
						nil ;Åñëè â ñîåäèíåííûõ âåðøèíàõ, òàêîé íåò
					)
						(cons	;òî îñòàâëÿåì òåêóùóþ íå èññëåäîâàííóþ âåðøèíó áåç èçìåíåíèÿ
							(car listOfUnexploredNodes)
							(replaceValueAndListOfNodesIfNeeded listOfConnectedNode (cdr listOfUnexploredNodes) listOfNodeToReplacePath)
						)
				)
				(T	;Ïîïàäàåì ñþäà, åñëè íàøëè â ñïèñêå listOfConnectedNode íóæíóþ âåðøèíó
					(cond	;Ñðàâíèâàåì çíà÷åíèå X èç (D X) è Y èç ((D Y 0 0))
						(
							(<	;Åñëè X < Y, òî çàìåíÿåì Y íà X è
								(cadr foundedNode)
								(cadar listOfUnexploredNodes)
							)
								(cons
									(append
										(append
											(append
												(cons
													(car foundedNode) ;Èìÿ âåðøèíû
													nil
												)
												(cons
													(cadr foundedNode) ;X
													nil
												)
											)
											(cons
												listOfNodeToReplacePath
												nil
											)

										)
										(cdddar listOfUnexploredNodes)
									)
									(replaceValueAndListOfNodesIfNeeded (cdr listOfConnectedNode)
																		(cdr listOfUnexploredNodes)
																		listOfNodeToReplacePath
									)
								)
						)
						(
							(=	;Åñëè X = Y, òî X íå èçìåíÿåì, à â ñïèñîê âåðøèí äîáàâëÿåì listOfNodeToReplacePath, êîòîðûé â ôîðìàòå
								;((A B C D) (A C E)..)
								(cadr foundedNode)
								(cadar listOfUnexploredNodes)
							)
								(cons
									(append
										(append
											(append
												(cons
													(car foundedNode) ;Èìÿ âåðøèíû
													nil
												)
												(cons
													(cadar listOfUnexploredNodes) ;X
													nil
												)
											)
											(cons
												(append
													(caddar listOfUnexploredNodes)
													listOfNodeToReplacePath

												)
												nil
											)

										)
										(cdddar listOfUnexploredNodes)
									)
									(replaceValueAndListOfNodesIfNeeded 
										(cdr listOfConnectedNode)
										(cdr listOfUnexploredNodes)
										listOfNodeToReplacePath
									)
								)
						)
						(T
							;Ïîïàäàåì ñþäà, åñëè X > Y, â ýòîì ñëó÷àå îñòàâëÿåì âñå áåç èçìåíåíèÿ
							(cons
								(append
									(append
										(append
											(cons
												(caar listOfUnexploredNodes) ;Èìÿ âåðøèíû
												nil
											)
											(cons
												(cadar listOfUnexploredNodes) ;X
												nil
											)
										)
										(cons
											(caddar listOfUnexploredNodes)
											nil
										)
									)
									(cdddar listOfUnexploredNodes)
								)
								(replaceValueAndListOfNodesIfNeeded 
									(cdr listOfConnectedNode)
									(cdr listOfUnexploredNodes)
									listOfNodeToReplacePath
								)
							)
						)
					)
				)
			)
		)
	)
)

(print (lookingFor net `A `F))