Algorithms

Mark Churchill wrote:

how to calculate shortest path between houses

Pseudocode for Longest Path
	Nodes of graph have integer names

Node Extensible( sequence s )
  Boolean found, Node endpoint
	p = EndOfPath(s)
        Set Inpath(x) = true for any x in s
	//LastUsed remembers last vertex used to extend s
	y = LastUsed(p)+1
        // now find first vertex which is :
        // not in use in s
        // adjacent to p
        // >= y
	found = false, q = y
        While q <= number of vertices And Not found
            found = Not InPath(q) And IsEdge(p, i)
            If Not found Then q = q + 1
        End While
        If Not found Then
            Extensible = -1
        Else
            Extensible = q
        End If

Sequence Truncate( sequence s )
        'Reset Lastused for EndofPath of s and remove EndofPath
         p = EndOfPath(s)
	 // p will be removed so reset Lastused
         Lastused(p) = 0
         If s.length = 1 then
		// choose new start vertex
		Truncate = s+1 // s is integer name for old start
        Else
                Truncate = all but last node of s
        End If

Sequence Extend( sequence s )
	 p = EndOfPath(s)
         q = Extensible(s)
            If q = -1 Then
                If s.Length > s*.Length Then s* = s
                // backtrack
                Extend = Truncate( s )
            Else
                Lastused(p) = q
                Extend = s + q
            End If
        End If

73Zeppelin wrote:

// now find first vertex which is :
// not in use in s
// adjacent to p
// >= y

73Zeppelin wrote:

If s.Length > s*.Length Then s* = s

zenerguy32 wrote:

If I'm reading that correctly it will only use nodes which have not already been used in the current path. However, it shouldn't matter how many times any particular node is used but rather how many times each "road" between nodes is used.

In my example, "0-1-5-4-3-2-0-9-8-7-6-1" was a valid path. Node '0' is used twice, but each "road" leading to each of its three neighbors is used only once (0-1,2-0,0-9). Am I understanding your pseudocode correctly?

zenerguy32 wrote:

73Zeppelin wrote:
If s.Length > s*.Length Then s* = s


do? Thanks!

m-khansari wrote:

hi

I want to implement data versioning in a application...
I need a Delta algorithm component.
where can I find it?

thanks.

shaibee wrote:

have a double value describing rotation angle for a text box object. I need to convert it to quaternion. I have searched the web, and all I get is converters that conver Euler angle to Quaternion.

I would appreciate any formulae or algorithm.
And this double value is the only information I have for rotation.

73Zeppelin wrote:

rotation is given by a unit vector (ax, ay, az) and the angle theta is in radians

/ write_item(X) by T

write_item(X)
{
     while(true)
     {
          if( write_TS(X) > TS(T) || read_TS(X) > TS(T) )  // <--THIS LINE
          {
                abort(T); // break or return
          }
          else if( write_TS(X) < TS(T) )
          {
               wait until the transaction T', which TS(T) > TS(T'), has
               either committed or aborted; // write_TS(X) == TS(T')
                  continue;   
          }
          else
          {
                write_item(X);
                write_TS(X) = TS(T);
                break; // or return                
          }
     }
} 

// rmax(X): the max timestamp of a transaction that read that item.
// wmax(X): the max timestamp of a transaction that wrote the item.

// read X:

if t >= wmax(X)
    rmax(X) <- max(t, rmax(X))
    wait for a committed value of X
    perform read
else 
    abort

// write X:

if t >= rmax(X) and t >= wmax(X)
    wmax(X) <- t
    wait until X value is a committed value and
        pending reads are done
    perform write
else
    if t < rmax(X)
    abort
else
    do nothing