Home · Pages · Index · Overviews

Shortest Paths Module Reference

Shortest paths routines More...

 #include <path.h>

Descriptive Types

  SP_Item : void
 

Routines

SP_Item * SP_Value (double v)
SP_Item * SP_Test (boolean (*cond)(Indx_Type p, double v))
SP_Item * SP_Edge (double (*func)(float *w, Indx_Type p, Indx_Type q, double d))

SP_Item * Seed_Zone (Indx_Type seed)
SP_Item * Slice_Zone (Slice *slice C)
SP_Item * Region_Zone (Region *region C)
SP_Item * Array_Zone ()
SP_Item * Image_Zone (SP_Item *test K, SP_Item *zone K)

void Kill_SP (SP_Item *item)
SP_Item * Inc_SP (SP_Item *item)

Float_Array * Shortest_PathsG (Float_Array *w, boolean iscon2n, SP_Item *cost K,
                               SP_Item *source K, SP_Item *zone K)

Vector * Find_PathG (Float_Array *w, boolean iscon2n, SP_Item *cost K,
                      Float_Array *d, Indx_Type end)

Vector * Shortest_BetweenG (Float_Array *w, boolean iscon2n, SP_Item *cost K,
                                    SP_Item *source K, SP_Item *target K, double *score IO)

Detailed Description

One can view an array as a lattice or undirected graph, and from this view point one can then think about paths in this graph as discretely sampled curves in space. For example, for a 3D array and 2n-connectivity, every element or vertex of the array has 6 edges connecting it to adjacenet elements. If one attaches a weight or score to every element of the array, say w(p) for pixel p, then the cost of a connected path P = p0, p1, … pn in an array is the sum of the weights of the scores of the vertices, i.e., w(P) = Σi w(pi ). One can also consider the geometric distance from one vertex v to another w, d(v,w) (e.g. the distance of the edge from (0,0,0) to (1,1,1) is √3), in which case the cost of a path is the sum of its edge distances, i.e., d(P) = Σi>0 d(pi-1,pi ). For a given blending factor α, one can more generally consider the cost of a path to be b(P) = w(P) + α d(P). In the most general case, one can consider every edge (p,q) to have a non-negative weight e(p,q) in which case the cost of a path is the sum of the weights of its edges: e(P) = Σi>0 e(pi-1,pi ). It is an easy exercise to show that this model encompasses the simpler scoring functions w(P), d(P), and b(P).

The shortest path problem is to compute the shortest or lowest scoring path from one array element or vertex to another. This can be generalized in at least two ways. The first is given two regions R and S of an array, the problem becomes to find the shortest path between the two regions, which includes identifying which vertices in R and S are at the respective ends of a shortest path. The mylib library supports this variation by introducing an SP_Item micro-object which can encode a single pixel (Seed_Zone), an array Slice (Slice_Zone), a connected Region (Region_Zone), the entire array (Array_Zone), or the set of pixels within a slice, region, or the entire array, that have a particular weight w or satisfy a particular predicate (Image_Zone). Each of the routines mentioned returns an SP_Item micro-object that can only be used as an input argument to one of the two shortest paths routines. The second variation of shortest paths computes the shortest path to every vertex in a given region that begin within a specified source region. Given that the region can have almost any shape, this variation effectively allows one to compute geodesic distances.

As seen above the SP_Item micro-object is used to encode regions or 'zones'. These short-lived objects can also be used to convey (1) a double value, such as the blending factor α, (SP_Value), (2) a boolean predicate on a pixel that determines if it is in an Image_Zone (SP_Test), and (3) a double function on an edge (p,q) of distance d over weight array w that determines the cost of an edge in a path (SP_Edge). To keep conventions simple, SP_Item arguments are always killed by the recieving routine, but if one wants to use an item multiple times then one can increment its reference count with Inc_SP and then explicitly kill it with Kill_SP when appropriate.

The routine Shortest_Paths supports the computation of the shortest iscon2n-connected path from any vertex in a zone source to every other vertex in a zone zone, with respect to weight array w and the scoring scheme cost that is an SP_Item built from either an SP_Value or SP_Edge. In the case of an SP_Value, then paths are scored according to b(P) described in the first paragraph and the double value of cost is the blending factor α. In the case of an SP_Edge, then paths are scored according to e(P) described above and the function encoded by cost provides the required general edge score e(p,q). The weight array w further defines the lattice under consideration and the values that define Image_Zone arguments (if used). Specifically, for the SP_Item source, the image zone is those pixels within the slice, region, or array for which eithere (a) w has the value of the SP_Value given as test when creating the image zone, or (b) the predicate suppled by the SP_Test given as test is true for the pixel. But for the SP_Item zone, the image zone is those pixels within the slice, region, or array for which either (a) w does not have the given value (if SP_Value), or (b) the predicate of the image zone is false for the pixel in question. To enable unique values that identify pixels as being in or out of an image zone, weights within w can be negative, in which case the weight of the vertex for the purpose of computing path scores is taken as the absolute value of the given number. Shortest_Paths generates and returns an array, say d, of the same shape as w, for which d[p] for a vertex p in zone is the value of the shortest path from a vertex in source to this vertex. Given d and a particular vertex end in the zone over which it was computed, Find_Path returns a vector that lists the vertices on a shortest path from a vertex in the source zone to the vertex end.

The code example below illustrates the use of the routines and in particular the use of SP_Items. A shortest path is sought from the points (2,3) and (3,2) to all other points (x,y) in the 10x10 array w that are between diagonals -3 to 3, inclusive, where the weight of a path is the number of vertices in it. The pixels (2,3) and (3,2) are encoded as the sources by setting their values to -1 and then passing Shortest_Paths the SP_Item Image_Zone(SP_Value(-1.),Slice_Zone(s)) where s is the smallest possible slice that contains both points. The computation is restricted to the desired band of diagonals by the region r which is communicated to Shortest_Paths via the SP_Item Region_Zone(r). The blending factor α is set to 0. so the score of paths is just the sum of the vertex weights, all of which are 1, implying that the score of a path is the number of vertices in it. Note that upon completion all objects of all types have been killed, noting especially, that the SP_Items are killed by the routines they are passed to, and as a result, the Slice s and Region r are killed by the items that consumed their references.

 boolean REGFUN(Indx_Type p, void *arg)
 { if (p%10 - p/10 >= -3 && p%10 - p/10 <= 3) }

 { Array  *d;
   Vector *p;
   float  *f;
   int     i;

   Array *w = Make_Array_With_Shape(PLAIN_KIND,FLOAT32_TYPE,Coord("10,10"));
   float *f = AFLOAT32(w);

   Slice   *s = Make_Slice(a,Coord2(2,2),Coord2(3,3));
   Region  *r = Record_Region(a,0,0,2,1,NULL,REGFUN);
   SP_Item *a = SP_Value(0.);

   for (i = 0; i < a->size; i++)
     f[i] = 1.;
   f[23] = f[32] = -1.;

   printf("Array:");
   Print_Array(a,stdout,4,"%2.0f");

   d = Shortest_Paths(w,1,Inc_SP(a),Image_Zone(SP_Value(-1.),Slice_Zone(s)),Region_Zone(r));

   printf("\nLengths:");
   Print_Array(w,stdout,4,"%2.0f");

   p = Find_Path(w,1,a,d,67);

   printf("\nPath:");
   Print_Array(p,stdout,4,"%2lld");

   Kill_Array(p);
   Kill_Array(d);
   Kill_Array(w);
 }

The output of the example is shown below, where the first array is the value of w on input, the second array is the set of distances d returned by Shortest_Paths, and lastly, the the shortest path from one of the two source vertices to pixel (6,7) is computed by Find_Path and then output. Note that in the distance array, pixels adjacent to the diagonal band but not in it are set to -1., and all values not set by the algorithm have been replaced with a question mark.

 Array:
     Array [0,9] x [0,9]

     {  1,  1,  1,  1,  1,  1,  1,  1,  1,  1
        1,  1,  1,  1,  1,  1,  1,  1,  1,  1
        1,  1,  1, -1,  1,  1,  1,  1,  1,  1
        1,  1, -1,  1,  1,  1,  1,  1,  1,  1
        1,  1,  1,  1,  1,  1,  1,  1,  1,  1
        1,  1,  1,  1,  1,  1,  1,  1,  1,  1
        1,  1,  1,  1,  1,  1,  1,  1,  1,  1
        1,  1,  1,  1,  1,  1,  1,  1,  1,  1
        1,  1,  1,  1,  1,  1,  1,  1,  1,  1
        1,  1,  1,  1,  1,  1,  1,  1,  1,  1
     }

 Lengths:
     Array [0,9] x [0,9]

     {  6,  5,  4,  3, -1,  ?,  ?,  ?,  ?,  ?
        5,  4,  3,  2,  3, -1,  ?,  ?,  ?,  ?
        4,  3,  2,  1,  2,  3, -1,  ?,  ?,  ?
        3,  2,  1,  2,  3,  4,  5, -1,  ?,  ?
       -1,  3,  2,  3,  4,  5,  6,  7, -1,  ?
        ?, -1,  3,  4,  5,  6,  7,  8,  9, -1
        ?,  ?, -1,  5,  6,  7,  8,  9, 10, 11
        ?,  ?,  ?, -1,  7,  8,  9, 10, 11, 12
        ?,  ?,  ?,  ?, -1,  9, 10, 11, 12, 13
        ?,  ?,  ?,  ?,  ?, -1, 11, 12, 13, 14
     }

 Path:
     Array [0,8]

     { 32, 42, 52, 53, 63, 64, 65, 66, 67 }

The second form of the computation, embodied by Shortest_Between, finds a shortest path between zone source and zone target of score score or less, and if it finds one then it returns a newly-generated vector that lists the vertices in a shortest path between them, and NULL if it does not find such a path. This version is optimized to take time porportional to the number of vertices that are at distance score/2 or less from a vertex in one of the two zones. The variable score is modified to be the cost of the path (if one is found) just before returning. The algorithm is expected to be quite fast if you request the shortest path between two nearby vertices in an array.


Descriptive Types Documentation

SP_Item: void

A very short-lived object that encodes either a sub-region of an array, or a value, pixel predicate, or edge function for use in a shortest path computation. Its' sole purpose is to commmunicate inputs of different types to the shortest path routines.


Routine Documentation

SP_Item * SP_Value (double v)

The returned item encodes a double value. This item can be used as either the argument test to Image_Zone or as the argument cost to one of the shortest path routines.

SP_Item * SP_Test (boolean (*cond)(Indx_Type p, double v))

The returned item encodes a pointer to a boolean function that takes a pixel p and its weight v as input. This item can only be used as the argument test to Image_Zone.

SP_Item * SP_Edge (double (*func)(float *w, Indx_Type p, Indx_Type q, double d))

The returned item encodes a pointer to a double function that returns the weight of the edge from pixel p to pixel q, where for convenience d is the Euclidean distance between the two pixels and w is the floating point vector of pixel weights for the shortest path computation in question. This item can only be used as the argument cost to one of the shortest path routines.

SP_Item * Seed_Zone (Indx_Type seed)

The returned item encodes the region consisting of the single pixel seed.

SP_Item * Slice_Zone (Slice *slice C)

The returned item encodes the region covered by the Slice slice.

SP_Item * Region_Zone (Region *region C)

The returned item encodes the region covered by the Region region.

SP_Item * Array_Zone ()

The returned item encodes the region covered by the entire array. The array in question will be the weight array w passed to one of the shortest path routines.

SP_Item * Image_Zone (SP_Item *test K, SP_Item *zone K)

The argument zone can be a Slice_Zone, Region_Zone, or Array_Zone and the argument test can be an SP_Value or an SP_Test. The returned zone encodes the subset of pixels in the region encoded by zone for which the pixels (a) have the weight value of test in the case test is an SP_Value, or (b) satisfy the predicate encoded by test in the case test is an SP_Test. When the zone is used to represent a start or stopping set for paths, the pixels are those that have the test value or predicate. However, when the zone is representing the area within which shortest paths will be computed, then the pixels are those that do not have the test value or do not satisfy the test predicate. In the case of a value, it can be negative in order to make it unique, in which case the absolute value of pixels with this value are used in computing shortest paths.

void Kill_SP (SP_Item *item)

Explicitly kills item p and its reference to a Slice or Region if it consumed one.

SP_Item * Inc_SP (SP_Item *item)

Increment the reference count of item p so that it does not get killed when passed to a routine that can take it as an argument.

Float_Array * Shortest_PathsG (Float_Array *w, boolean iscon2n, SP_Item *cost K,
                               SP_Item *source K, SP_Item *zone K)

For the graph defined and weighted by w with respect to iscon2n connectivity, compute the length of a shortest path from a vertex in source to each vertex in zone, where the paths are scored according to item cost and are constrained to lie within zone. If cost is an SP_Value, the paths are scored according to b(P) described in the first paragraph on scoring and the double value of cost is the blending factor α. if cost is an an SP_Edge, then paths are scored according to e(P) described and the function encoded by cost provides the required general edge score e(p,q). Values in w may be negative in order to facilitate the identification of pixels in an Image_Zone, but the absolute value of w is used to compute the cost of paths. An array, say d, with the same shape as w is generated and returned, where the positive distances to each vertex in zone have been computed. Only the vertices in zone are guaranteed to have a correct value as the routine is implemented so as to take time proportional to the size of zone, and not the size of w. However, to assist tracing shortest paths using d, vertices that are not in zone but adjacent to vertices in zone, have been set to -1. (an impossible value as all distances must be positive).

Vector * Find_PathG (Float_Array *w, boolean iscon2n, SP_Item *cost K,
                      Float_Array *d, Indx_Type end)

Assuming d was computed from w, iscon2n, and cost with Shortest_Paths, return a vector containing the sequence of array indices on a shortest path from a source vertex to the vertex or array element end.

Vector * Shortest_BetweenG (Float_Array *w, boolean iscon2n, SP_Item *cost K,
                                    SP_Item *source K, SP_Item *target K, double *score IO)

For the graph defined and non-negatively weighted by w with respect to iscon2n connectivity, find a shortest path between a vertex in source and a vertex in target, where the paths are weighted according to item cost which must be an SP_Value or an SP_Edge. If cost is an SP_Value, the paths are scored according to b(P) described in the first paragraph on scoring and the double value of cost is the blending factor α. if cost is an an SP_Edge, then paths are scored according to e(P) described and the function encoded by cost provides the required general edge score e(p,q). Values in w may be negative in order to facilitate the identification of pixels in an Image_Zone, but the absolute value of w is used to compute the cost of paths.

A path of score at most *score is sought and if none is found then NULL is returned. Otherwise, a vector listing the vertices along the shortest path found is generated and returned, and the score of the path is placed in the double value pointed at by score. This algorithm is optimized to take time porportional to the number of vertices that are at distance score/2 or less from a vertex in one of the two zones. Thus the algorithm is expected to be quite fast if you request the shortest path between two nearby vertices in an array.