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
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.
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.
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.
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.