Σάββατο, 27 Απριλίου 2019

Dijkstra's algorithm

This is a rosettacode.org task
The graph stored in a jagged array. A tuple in m2000 is an array of one dimension. We can put tuple in a tuple too, so this is a jagged array. When we store an array in an array, we store only the pointer to array (which is an object, so we can read the type if we wish).

So Edges is a pointer to the graph (which we didn't change values). The task want only to find the path from a to e, and the weight. But here we search all the paths from every vertex to every vertex (and if not possible the a "no path" label printed).

I use an inventory list only with keys, because we can delete any of them without cost (this list need unique keys). Because we have the statement Inventory in a loop, the second time the inventory must be empty (or an exception produced), but algorithm end when inventory is empty. (to clear an inventory S we have to use Clear S.

There are two lambda functions inside loop. Because we use closures, and for d and pa we get new pointer in each iteration we have to redefine the lambdas to get new closures (with new pointers). Closures in lambda are copies, and this include pointers.

Also I use some subs, which have same scope as the module where we call them. Functions and Modules are namespaces (this include the lambda functions). There is special call to place the same namespace the Call Local but here not used.

I use this pdf for information about algorithm.


Module Dijkstra`s_algorithm {
        const max_number=1.E+306
        GetArr=lambda (n, val)->{
                dim d(n)=val
                =d()
        }
        term=("",0)
        Edges=(("a", ("b",7),("c",9),("f",14)),("b",("c",10),("d",15)),("c",("d",11),("f",2)),("d",("e",6)),("e",("f", 9)),("f",term))
        Document Doc$="Graph:"+{
        }
        ShowGraph()
        Doc$="Paths"+{
        }
        Print "Paths"
        For from_here=0 to 5
                pa=GetArr(len(Edges), -1)
                d=GetArr(len(Edges), max_number)
                Inventory S=1,2,3,4,5,6
                return d, from_here:=0
                RemoveMin=Lambda S, d, max_number-> {
                        ss=each(S)
                        min=max_number
                        p=0
                        while ss
                                val=d#val(eval(S,ss^)-1)
                                if min>val then let min=val : p=ss^ 
                        end while
                        =s(p!)  ' use p as index not key
                        Delete S, eval(s,p)
                }
                Show_Distance_and_Path$=lambda$ d, pa, from_here, max_number (n) -> {
                        ret1$=chr$(from_here+asc("a"))+" to "+chr$(n+asc("a"))
                        if d#val(n) =max_number then =ret1$+ "No Path" :exit
                        let ret$="", mm=n, m=n
                        repeat
                                n=m
                                ret$+=chr$(asc("a")+n)
                                m=pa#val(n)
                        until  from_here=n 
                        =ret1$+format$("{0::-4} {1}",d#val(mm),strrev$(ret$))
                }
                while len(s)>0 
                        u=RemoveMin()
                        rem Print u, chr$(u-1+asc("a"))
                        Relaxed()
                end while
                For i=0 to len(d)-1
                        line$=Show_Distance_and_Path$(i)
                        Print line$
                        doc$=line$+{
                        }
                next
        next
        Clipboard Doc$
        End
        Sub Relaxed()
                local vertex=Edges#val(u-1), i
                local e=Len(vertex)-1, edge=(,), val
                for i=1 to e
                        edge=vertex#val(i)
                        if edge#val$(0)<>"" then
                                val=Asc(edge#val$(0))-Asc("a")
                                if d#val(val)>edge#val(1)+d#val(u-1) then  return d, val:=edge#val(1)+d#val(u-1) : Return Pa, val:=u-1
                        end if
                next 
        end sub
        Sub ShowGraph()
                Print "Graph"
                local i
                for i=1 to len(Edges)
                        show_edges(i)
                next
        end sub
        Sub show_edges(n)
                n--
                local vertex=Edges#val(n), line$
                local e=each(vertex 2 to end), v2=(,)
                While e 
                        v2=array(e)
                        line$=vertex#val$(0)+if$(v2#val$(0)<>""->"->"+v2#val$(0)+format$(" {0::-2}",v2#val(1)),"")
                        Print line$
                        Doc$=line$+{
                        }
                end while
        end sub
}
Dijkstra`s_algorithm




Graph:
a->b  7
a->c  9
a->f 14
b->c 10
b->d 15
c->d 11
c->f  2
d->e  6
e->f  9
f
Paths
a to a   0 a
a to b   7 ab
a to c   9 ac
a to d  20 acd
a to e  26 acde
a to f  11 acf
b to a     No Path
b to b   0 b
b to c  10 bc
b to d  15 bd
b to e  21 bde
b to f  12 bcf
c to a     No Path
c to b     No Path
c to c   0 c
c to d  11 cd
c to e  17 cde
c to f   2 cf
d to a     No Path
d to b     No Path
d to c     No Path
d to d   0 d
d to e   6 de
d to f  15 def
e to a     No Path
e to b     No Path
e to c     No Path
e to d     No Path
e to e   0 e
e to f   9 ef
f to a     No Path
f to b     No Path
f to c     No Path
f to d     No Path
f to e     No Path
f to f   0 f

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου