# 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<n1>) and \m(vertex<n2>) **
    }
    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