1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14
15#include "vis.h"
16
17#ifdef DMALLOC
18#include "dmalloc.h"
19#endif
20
21static COORD unseen = (double) INT_MAX;
22
23/* shortestPath:
24 * Given a VxV weighted adjacency matrix, compute the shortest
25 * path vector from root to target. The returned vector (dad) encodes the
26 * shorted path from target to the root. That path is given by
27 * i, dad[i], dad[dad[i]], ..., root
28 * We have dad[root] = -1.
29 *
30 * Based on Dijkstra's algorithm (Sedgewick, 2nd. ed., p. 466).
31 *
32 * This implementation only uses the lower left triangle of the
33 * adjacency matrix, i.e., the values a[i][j] where i >= j.
34 */
35int *shortestPath(int root, int target, int V, array2 wadj)
36{
37 int *dad;
38 COORD *vl;
39 COORD *val;
40 int min;
41 int k, t;
42
43 /* allocate arrays */
44 dad = (int *) malloc(V * sizeof(int));
45 vl = (COORD *) malloc((V + 1) * sizeof(COORD)); /* One extra for sentinel */
46 val = vl + 1;
47
48 /* initialize arrays */
49 for (k = 0; k < V; k++) {
50 dad[k] = -1;
51 val[k] = -unseen;
52 }
53 val[-1] = -(unseen + (COORD) 1); /* Set sentinel */
54 min = root;
55
56 /* use (min >= 0) to fill entire tree */
57 while (min != target) {
58 k = min;
59 val[k] *= -1;
60 min = -1;
61 if (val[k] == unseen)
62 val[k] = 0;
63
64 for (t = 0; t < V; t++) {
65 if (val[t] < 0) {
66 COORD newpri;
67 COORD wkt;
68
69 /* Use lower triangle */
70 if (k >= t)
71 wkt = wadj[k][t];
72 else
73 wkt = wadj[t][k];
74
75 newpri = -(val[k] + wkt);
76 if ((wkt != 0) && (val[t] < newpri)) {
77 val[t] = newpri;
78 dad[t] = k;
79 }
80 if (val[t] > val[min])
81 min = t;
82 }
83 }
84 }
85
86 free(vl);
87 return dad;
88}
89
90/* makePath:
91 * Given two points p and q in two polygons pp and qp of a vconfig_t conf,
92 * and the visibility vectors of p and q relative to conf,
93 * compute the shortest path from p to q.
94 * If dad is the returned array and V is the number of polygon vertices in
95 * conf, then the path is V(==q), dad[V], dad[dad[V]], ..., V+1(==p).
96 * NB: This is the only path that is guaranteed to be valid.
97 * We have dad[V+1] = -1.
98 *
99 */
100int *makePath(Ppoint_t p, int pp, COORD * pvis,
101 Ppoint_t q, int qp, COORD * qvis, vconfig_t * conf)
102{
103 int V = conf->N;
104
105 if (directVis(p, pp, q, qp, conf)) {
106 int *dad = (int *) malloc(sizeof(int) * (V + 2));
107 dad[V] = V + 1;
108 dad[V + 1] = -1;
109 return dad;
110 } else {
111 array2 wadj = conf->vis;
112 wadj[V] = qvis;
113 wadj[V + 1] = pvis;
114 return (shortestPath(V + 1, V, V + 2, wadj));
115 }
116}
117