Froglingo

An Alternative to DBMS, Programming Language, Web Server, and File System

 

 

/*

            Case Study: Froglingo Implementation of Dijkastra Shortest Path Algorithm

                        Froglingo Development Association

                                    2/30/2010

 

            File Name: dijkastra.Frog

            The MS DOS command to inventory this application: frog -b dijkastra.frog

            For example in the folder FOLDER having the executable frog.exe:

                        C:\FOLDER\frog -b dijkastra.frog

 

            Description: The Dijkastra shortest path algorithm is a typical example of what

            a programming language does. Using this example, we demonstrate how Froglingo

            handles tense procedural logic while Froglingo has the EP data model as the core

            in handling business data.

*/

 

 

/*  The pseudo code of Dijkastra Shortest Path Algorithm. Froglingo Implementation follows it.

 

    function Dijkstra(Graph, source):

      for each vertex v in Graph:           // Initializations

          dist[v] := infinity               // Unknown distance function from source to v

          previous[v] := undefined          // Previous node in optimal path from source

      dist[source] := 0                     // Distance from source to source

      Q := the set of all nodes in Graph

      // All nodes in the graph are unoptimized - thus are in Q

      while Q is not empty:                 // The main loop

          u := vertex in Q with smallest dist[]

          if dist[u] = infinity:

             break                         // all remaining vertices are inaccessible from source

          if u is target

                        break

            remove u from Q

                for each neighbor v of u:         // where v has not yet been removed from Q.

              alt := dist[u] + dist_between(u, v)

              if alt < dist[v]:             // Relax (u,v,a)

                  dist[v] := alt

                  previous[v] := u

      return dist[]

*/

 

 

/* inventory all the directed links inside the stand (folder) G.

*/

create G;

cd G;

 

/*

   Given a directed link x to y, and its weight w, it is recorded as

            x y = w;

   The links involving the vertices A, B, C, D, E, F, U, Y are given below.

*/

create F;

create A B = 8;

create B A = 1;

create A D = 5;

create D B = 1;

create B D = 7;

create B C = 2;

create A E = 4;

create B F = 11;

create B Y = 3;

create Y F = 6;

create B U = 7;

 

/* Move back to the root folder (//) to construct the procedural */

cd ..;

 

/* Q here is in the correspondance to the Q in the pseudo code */

create  Q;

 

create prv;

create visited;

create loop_on_Q;

create is_u_target;

create deal_1_v;

create is_v_in_Q;

create add_v_to_Q;

create re_order;

create to_compare;

create is_smaller;

create modify_v_w;

create delete_w_v;

 

create print_rev_seq null = void;

create print_rev_seq $t = print_rev_seq (prv $t), $t;

 

 

create print_null_as_void null = void;

create print_null_as_void $x = void;

 

create rem_subordinate $Q =

            print_null_as_void (select delete $x where $x {+ $Q);

 

create dijkastra $s $t = rem_subordinate Q,

                                    rem_subordinate prv,

                                    rem_subordinate visited,

                                    (create Q 0 $s = true), 

                                    loop_on_Q (mterm pfirst (pfirst Q)) (mterm pfirst Q) $s $t ;

 

create loop_on_Q null $uw $s $t= "There is not connection between " , $s , " and ", $t;

create loop_on_Q $u $uw $s $t = is_u_target ($u == $t) $u $uw $s $t;

 

create is_u_target true $u $uw $s $t = "The shortest path has been found: ", print_rev_seq $u, "End of SHORTEST\n";

 

create continue_if_null null = void;

create continue_if_null $x = $x;

 

create is_not_visited  $v = (visited $v != true);

create is_u_target false $u $uw $s $t =

            delete_w_v $uw $u,

            (create visited $u = true),

            continue_if_null (select deal_1_v (is_not_visited (mterm $lnk)) $u $uw $lnk (mterm $lnk) where $lnk {+ $u ),

            loop_on_Q (mterm pfirst (pfirst Q)) (mterm pfirst Q) $s $t;

 

create deal_1_v false $u $uw $uv_w $v = "Intermediate result: Visited already, Ignore", $v;

 

create deal_1_v true $u $uw $uv_w $v =

            is_v_in_Q (select re_order $u $uw $v $uv_w $vw where Q $vw $v == true) $u $uw $v $uv_w;

 

create is_v_in_Q null $u $uw $v $uv_w= add_v_to_Q $u ($uw + $uv_w) $v;

 

create is_v_in_Q $some $u $uw $v $uv_w = void;

 

create add_v_to_Q $u $w $v = (create Q $w $v = true), (create prv $v = $u);

 

create re_order $u $uw $v $uv_w $vw= to_compare ($uw + $uv_w) $vw $u $v;

create to_compare $w_new $w_old $u $v = is_smaller ($w_new < $w_old) $w_new $w_old $u $v;

 

create is_smaller true $alt $old $u $v = modify_v_w $alt $old $v, update prv $v = $u;

create is_smaller false $alt $old $u $v = void;

 

create if_only_v true $w $v = delete Q $w;

create if_only_v false $w $v = delete Q $w $v;

create delete_w_v $w $v = if_only_v (pnext (Q $w $v) == null) $w $v;

 

create modify_v_w $alt $old $v = (delete_w_v $old $v), (create Q $alt $v = true);

 

 

/* Find the shortest path from A to F */

dijkastra (G A) (G F);

 

/*The answer is: The shortest path has been found: "G AG DG BG YG F"End of SHORTEST; That is A, D, B, Y, and F */