# Mind you C-Kermit is a communication software, not a toy language to # solve a chess problem. # # OK, let's talk computer network communication. One famous problem in # computer network is to find an optimal path from a source to a # destination. The path can be based on distance or transmit time, or ... # Following is the implementation of the Dijkstra's shortest path algorithm # through a graph of nodes. # # Reference: Andrew Tanenbaum, Computer Network. # # Dat Thuc Nguyen 20 Dec 2003 asg node_list "#" define node_node_distance { # \%1 first node # \%2 second node # \%3 distance asg \%1 \flower(\%1) asg \%2 \flower(\%2) echo {Add node \%1 and node \%2 distance \%3} if = 0 \findex({#\%1#},\m(node_list)) { # first node exists in graph? asg node_list {\m(node_list)\%1#} } if = 0 \findex({#\%2#},\m(node_list)) { # second node exists in graph? asg node_list {\m(node_list)\%2#} } (setq d_\%1_\%2 (setq d_\%2_\%1 \%3)) } define remove_node { # \%1, \%2, ... node to be removed local parms for i 1 \v(argc)-1 1 { asg parms \m(parms) \&_[i] } disable_node \m(parms) detach_node \m(parms) } define enable_node { local parms for i 1 \v(argc)-1 1 { if = \findex({#\%1#},\m(node_list)) 0 { asg node_list {\m(node_list)\&_[i]#} } asg parms \m(parms) \&_[i] } echo enable node: \m(parms) } define disable_node { local parms for i 1 \v(argc)-1 1 { if > \findex({#\&_[i]#},\m(node_list)) 0 { asg node_list \freplace(\m(node_list),{#\&_[i]#},#) } asg parms \m(parms) \&_[i] } echo disable node: \m(parms) } define detach_node { local parms for i 1 \v(argc)-1 1 { asg parms \m(parms) \&_[i] graph_dim for j 1 ll 1 { # disconnect with other nodes if define \m(d_\&s[j]_\&_[i]) { detach_edge \&s[j] \&_[i] } } } echo detach node: \m(parms) } define detach_edge { # \%1 first node # \%2 second node (setq d_\%1_\%2) (setq d_\%2_\%1) } define graph_dim { local \&a \&b nodenum j n asg n \faaconvert(node,&a,&b) asg n \faaconvert(vertex,&a,&b) asg nodenum 0 array declare \&s[] asg ll \fsplit(\m(node_list),&s,#) for j 1 ll 1 { (++ nodenum) (setq node<\&s[j]> \m(nodenum)) (setq vertex<\m(nodenum)> '\&s[j]) } } define shortest_path { # \%1 source node # \%2 destination node echo echo {Search shortest path from \%1 to \%2} asg \%1 \flower(\%1) asg \%2 \flower(\%2) if = 0 \findex(\%1,\m(node_list)) END -999 Source node \%1 does not exist if = 0 \findex(\%2,\m(node_list)) END -999 Destination node \%2 not exist graph_dim local \&p[] \&l[] \&b[] INFINITY declare \&p[ll] # Predecessor node declare \&l[ll] # Length between two nodes declare \&b[ll] # Label markes path scanned asg INFINITY 1000000000 local i j h k d_k_i n1 n2 for j 1 ll 1 { (setq i node<\&s[j]>) (setq \\&p[i] -1) (setq \\&l[i] INFINITY) (setq \\&b[i] 0) } asg n1 \%1 asg n2 \%2 asg \%1 \m(node<\%1>) asg \%2 \m(node<\%2>) (setq k \%2) # k is the initial working node (setq \\&l[k] 0) # Destination length is zero (setq \\&b[k] 1) # Destination node permanent while ( != k \%1 ) { (setq h k) # To identify non existing path (run in cycle) for j 1 ll 1 { (setq i node<\&s[j]>) asg vk \freplace(\m(vertex<\m(k)>),',) asg vi \freplace(\m(vertex<\m(i)>),',) if not define \m(d_\m(vk)_\m(vi)) continue # Skip non existing edge asg d_k_i \m(d_\m(vk)_\m(vi)) (if ( AND d_k_i (! \&b[i]) ( < (+ \&l[k] d_k_i) \&l[i] )) (setq \\&p[i] k \\&l[i] (+ \&l[k] d_k_i)) ) } (setq k 0 smallest INFINITY) for j 1 ll 1 { (setq i node<\&s[j]>) (if ( AND (! \&b[i]) (< \&l[i] smallest)) (setq smallest \&l[i] k i) ) } if == h k END -999 * No path found between \m(n1) and \m(n2) * asg \&b[k] 1 # Set permanent node on path } echo local path dist asg path "-" asg dist 0 (setq k \%1) while true { asg path "\m(path) \m(vertex<\m(k)>) -" (setq from k) (setq k \&p[k] to k) if < k 0 break asg vk \freplace(\m(vertex<\m(from)>),',) asg vi \freplace(\m(vertex<\m(to)>),',) asg d_k_i \m(d_\m(vk)_\m(vi)) asg msg {from \m(vertex<\m(from)>) to - \m(vertex<\m(to)>), distance: \m(d_k_i)} echo \freplace(\m(msg),',) (++ dist d_k_i) } if > \m(dist) 0 { echo {Path found: \freplace(\m(path),',), total distance: \m(dist)} } else { END -999 ** No Path found between \m(vertex) and \m(vertex) ** } echo } # Make a sample graph # Node 0 connects with node 1, quality (distance, transmit time) is 110 node_node_distance 0 1 110 # Node 0 connects with node 2, quality (distance, transmit time) is 230 node_node_distance 0 2 230 # Node 0 connects with node 9, quality (distance, transmit time) is 120 node_node_distance 0 9 120 # Node 1 connects with node 3, quality (distance, transmit time) is 75 node_node_distance 1 3 75 # Node 1 connects with node 2, quality (distance, transmit time) is 50 node_node_distance 1 2 50 # Node 2 connects with node 3, quality (distance, transmit time) is 85 node_node_distance 2 3 85 # Node 3 connects with node 4, quality (distance, transmit time) is 185 node_node_distance 3 4 185 # Node 1 connects with node 4, quality (distance, transmit time) is 885 node_node_distance 1 4 885 # Node 4 connects with node 5, quality (distance, transmit time) is 325 node_node_distance 4 5 325 # Node 2 connects with node 5, quality (distance, transmit time) is 25 node_node_distance 2 5 25 # Node 5 connects with node 7, quality (distance, transmit time) is 325 node_node_distance 5 7 325 # City Paris connects with London, quality (distance, transmit time) is 600 node_node_distance Paris London 600 # City Paris connects with Athen, quality (distance, transmit time) is 2000 node_node_distance Paris Athen 2000 # City Athen connects with Macao, quality (distance, transmit time) is 2500 node_node_distance Athen Macao 2500 # Find the shortest path between node 0 and node 4: shortest_path 0 4 # Find the shortest path between Paris and Macao shortest_path Paris Macao end