Graphviz  2.41.20170921.2350
shortestpth.c
Go to the documentation of this file.
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 
21 static 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  */
35 int *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  */
100 int *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 }
array2 vis
Definition: vis.h:47
double COORD
Definition: pathutil.h:41
int directVis(Ppoint_t, int, Ppoint_t, int, vconfig_t *)
Definition: visibility.c:400
int N
Definition: vis.h:40
COORD ** array2
Definition: vis.h:29
int * shortestPath(int root, int target, int V, array2 wadj)
Definition: shortestpth.c:35
int * makePath(Ppoint_t p, int pp, COORD *pvis, Ppoint_t q, int qp, COORD *qvis, vconfig_t *conf)
Definition: shortestpth.c:100
Definition: pathgeom.h:26
Definition: vis.h:38
#define INT_MAX
Definition: arith.h:52