home *** CD-ROM | disk | FTP | other *** search
/ Columbia Kermit / kermit.zip / ckscripts / shortest_path < prev    next >
Lisp/Scheme  |  2020-01-01  |  7KB  |  239 lines
  1. # Mind you C-Kermit is a communication software, not a toy language to
  2. # solve a chess problem.
  3. #
  4. # OK, let's talk computer network communication. One famous problem in
  5. # computer network is to find an optimal path from a source to a
  6. # destination. The path can be based on distance or transmit time, or ...
  7. # Following is the implementation of the Dijkstra's shortest path algorithm
  8. # through a graph of nodes.
  9. #
  10. # Reference: Andrew Tanenbaum, Computer Network.
  11. #
  12. # Dat Thuc Nguyen 20 Dec 2003
  13.  
  14. asg node_list "#"
  15.  
  16. define node_node_distance {
  17.     # \%1 first node
  18.     # \%2 second node
  19.     # \%3 distance
  20.     asg \%1 \flower(\%1)
  21.     asg \%2 \flower(\%2)
  22.     echo {Add node \%1 and node \%2 distance \%3}
  23.     if = 0 \findex({#\%1#},\m(node_list)) {    # first node exists in graph?
  24.     asg node_list {\m(node_list)\%1#}
  25.     }
  26.     if = 0 \findex({#\%2#},\m(node_list)) {    # second node exists in graph?
  27.     asg node_list {\m(node_list)\%2#}
  28.     }
  29.     (setq d_\%1_\%2 (setq d_\%2_\%1 \%3))
  30. }
  31.  
  32. define remove_node {
  33.     # \%1, \%2, ... node to be removed
  34.     local parms
  35.     for i 1 \v(argc)-1 1 {
  36.     asg parms \m(parms) \&_[i]
  37.     }
  38.     disable_node \m(parms)
  39.     detach_node \m(parms)
  40. }
  41.  
  42. define enable_node {
  43.     local parms
  44.     for i 1 \v(argc)-1 1 {
  45.     if = \findex({#\%1#},\m(node_list)) 0 {
  46.         asg node_list {\m(node_list)\&_[i]#}
  47.     }
  48.     asg parms \m(parms) \&_[i]
  49.     }
  50.     echo enable node: \m(parms)
  51. }
  52.  
  53. define disable_node {
  54.     local parms
  55.     for i 1 \v(argc)-1 1 {
  56.     if > \findex({#\&_[i]#},\m(node_list)) 0 {
  57.         asg node_list \freplace(\m(node_list),{#\&_[i]#},#)
  58.     }
  59.     asg parms \m(parms) \&_[i]
  60.     }
  61.     echo disable node: \m(parms)
  62. }
  63.  
  64. define detach_node {
  65.     local parms
  66.     for i 1 \v(argc)-1 1 {
  67.         asg parms \m(parms) \&_[i]
  68.         graph_dim
  69.         for j 1 ll 1 {            # disconnect with other nodes
  70.         if define \m(d_\&s[j]_\&_[i]) {
  71.         detach_edge \&s[j] \&_[i]
  72.         }
  73.     }
  74.     }
  75.     echo detach node: \m(parms)
  76. }
  77.  
  78. define detach_edge {
  79.     # \%1 first node
  80.     # \%2 second node
  81.     (setq d_\%1_\%2)
  82.     (setq d_\%2_\%1)
  83. }
  84.  
  85. define graph_dim {
  86.     local \&a \&b nodenum j n
  87.     asg n \faaconvert(node,&a,&b)
  88.     asg n \faaconvert(vertex,&a,&b)
  89.     asg nodenum 0
  90.     array declare \&s[]
  91.     asg ll \fsplit(\m(node_list),&s,#)
  92.     for j 1 ll 1 {
  93.     (++ nodenum)
  94.     (setq node<\&s[j]> \m(nodenum))
  95.     (setq vertex<\m(nodenum)> '\&s[j])
  96.     }
  97. }
  98.  
  99. define shortest_path {
  100.     # \%1 source node
  101.     # \%2 destination node
  102.  
  103.     echo
  104.     echo {Search shortest path from \%1 to \%2}
  105.  
  106.     asg \%1 \flower(\%1)
  107.     asg \%2 \flower(\%2)
  108.  
  109.     if = 0 \findex(\%1,\m(node_list)) END -999 Source node \%1 does not exist
  110.     if = 0 \findex(\%2,\m(node_list)) END -999 Destination node \%2 not exist
  111.  
  112.     graph_dim
  113.  
  114.     local \&p[] \&l[] \&b[] INFINITY
  115.  
  116.     declare \&p[ll]                     # Predecessor node
  117.     declare \&l[ll]                     # Length between two nodes
  118.     declare \&b[ll]                     # Label markes path scanned
  119.     asg INFINITY 1000000000
  120.  
  121.     local i j h k d_k_i n1 n2
  122.  
  123.     for j 1 ll 1 {
  124.     (setq i node<\&s[j]>)
  125.         (setq \\&p[i] -1)
  126.         (setq \\&l[i] INFINITY)
  127.         (setq \\&b[i] 0)
  128.     }
  129.     asg n1 \%1
  130.     asg n2 \%2
  131.  
  132.     asg \%1 \m(node<\%1>)
  133.     asg \%2 \m(node<\%2>)
  134.  
  135.     (setq k \%2)                        # k is the initial working node
  136.     (setq \\&l[k] 0)                    # Destination length is zero
  137.     (setq \\&b[k] 1)                    # Destination node permanent
  138.     while ( != k \%1 ) {
  139.     (setq h k)              # To identify non existing path (run in cycle)
  140.         for j 1 ll 1 {
  141.         (setq i node<\&s[j]>)
  142.         asg vk \freplace(\m(vertex<\m(k)>),',)
  143.         asg vi \freplace(\m(vertex<\m(i)>),',)
  144.         if not define \m(d_\m(vk)_\m(vi)) continue # Skip non existing edge
  145.         asg d_k_i \m(d_\m(vk)_\m(vi))
  146.             (if ( AND d_k_i (! \&b[i]) ( < (+ \&l[k] d_k_i) \&l[i] ))
  147.               (setq \\&p[i] k \\&l[i] (+ \&l[k] d_k_i))
  148.              )
  149.         }
  150.         (setq k 0 smallest INFINITY)
  151.         for j 1 ll 1 {
  152.         (setq i node<\&s[j]>)
  153.             (if ( AND (! \&b[i]) (< \&l[i] smallest))
  154.               (setq smallest \&l[i] k i)
  155.              )
  156.         }
  157.     if == h k END -999 * No path found between \m(n1) and \m(n2) *
  158.         asg \&b[k] 1                    # Set permanent node on path
  159.     }
  160.     echo
  161.  
  162.     local path dist
  163.     asg path "-"
  164.     asg dist 0
  165.  
  166.     (setq k \%1)
  167.     while true {
  168.         asg path "\m(path) \m(vertex<\m(k)>) -"
  169.         (setq from k)
  170.         (setq k \&p[k] to k)
  171.         if < k 0 break
  172.         asg vk \freplace(\m(vertex<\m(from)>),',)
  173.     asg vi \freplace(\m(vertex<\m(to)>),',)
  174.     asg d_k_i \m(d_\m(vk)_\m(vi))
  175.     asg msg {from \m(vertex<\m(from)>) to -
  176. \m(vertex<\m(to)>), distance: \m(d_k_i)}
  177.     echo \freplace(\m(msg),',)
  178.         (++ dist d_k_i)
  179.     }
  180.     if > \m(dist) 0 {
  181.         echo {Path found: \freplace(\m(path),',), total distance: \m(dist)}
  182.     } else {
  183.         END -999 ** No Path found between \m(vertex<n1>) and \m(vertex<n2>) **
  184.     }
  185.     echo
  186. }
  187.  
  188. # Make a sample graph
  189.  
  190. # Node 0 connects with node 1, quality (distance, transmit time) is 110
  191. node_node_distance 0 1 110
  192.  
  193. # Node 0 connects with node 2, quality (distance, transmit time) is 230
  194. node_node_distance 0 2 230
  195.  
  196. # Node 0 connects with node 9, quality (distance, transmit time) is 120
  197. node_node_distance 0 9 120
  198.  
  199. # Node 1 connects with node 3, quality (distance, transmit time) is  75
  200. node_node_distance 1 3  75
  201.  
  202. # Node 1 connects with node 2, quality (distance, transmit time) is  50
  203. node_node_distance 1 2  50
  204.  
  205. # Node 2 connects with node 3, quality (distance, transmit time) is  85
  206. node_node_distance 2 3  85
  207.  
  208. # Node 3 connects with node 4, quality (distance, transmit time) is 185
  209. node_node_distance 3 4 185
  210.  
  211. # Node 1 connects with node 4, quality (distance, transmit time) is 885
  212. node_node_distance 1 4 885
  213.  
  214. # Node 4 connects with node 5, quality (distance, transmit time) is 325
  215. node_node_distance 4 5 325
  216.  
  217. # Node 2 connects with node 5, quality (distance, transmit time) is  25
  218. node_node_distance 2 5 25
  219.  
  220. # Node 5 connects with node 7, quality (distance, transmit time) is 325
  221. node_node_distance 5 7 325
  222.  
  223. # City Paris connects with London, quality (distance, transmit time) is 600
  224. node_node_distance Paris London 600
  225.  
  226. # City Paris connects with Athen, quality (distance, transmit time) is 2000
  227. node_node_distance Paris Athen 2000
  228.  
  229. # City Athen connects with Macao, quality (distance, transmit time) is 2500
  230. node_node_distance Athen Macao 2500
  231.  
  232. # Find the shortest path between node 0 and node 4:
  233. shortest_path 0 4
  234.  
  235. # Find the shortest path between Paris and Macao
  236. shortest_path Paris Macao
  237.  
  238. end
  239.