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 "config.h"
16
17#include <limits.h>
18#include "memory.h"
19#include "sgraph.h"
20#include "fPQ.h"
21
22#if 0
23/* Max. number of maze segments around a node */
24static int MaxNodeBoundary = 100;
25
26typedef struct {
27 int left, right, up, down;
28} irect;
29
30/* nodes in the search graph correspond to line segments in the
31 * grid formed by n_hlines horizontal lines and n_vlines vertical lines.
32 * The vertical segments are enumerated first, top to bottom, left to right.
33 * Then the horizontal segments left to right, top to bottom. For example,
34 * with an array of 4 vertical and 3 horizontal lines, we have
35 *
36 * |--14--|--15--|--16--|
37 * 1 3 5 7
38 * |--11--|--12--|--13--|
39 * 0 2 4 6
40 * |-- 8--|-- 9--|--10--|
41 */
42static irect
43get_indices(orthograph* OG,int i, int j)
44{
45 irect r;
46 int hl = OG->n_hlines-1;
47 int vl = OG->n_vlines-1;
48 r.left = i*hl + j;
49 r.right = r.left + hl;
50 r.down = (vl+1)*hl + j*vl + i;
51 r.up = r.down + vl;
52 return r;
53}
54
55static irect
56find_boundary(orthograph* G, int n)
57{
58 rect R = G->Nodes[n];
59 irect r;
60 int i;
61
62 for (i = 0; i < G->n_vlines; i++) {
63 if (R.left == G->v_lines[i]) {
64 r.left = i;
65 break;
66 }
67 }
68 for (; i < G->n_vlines; i++) {
69 if (R.right == G->v_lines[i]) {
70 r.right = i;
71 break;
72 }
73 }
74 for (i = 0; i < G->n_hlines; i++) {
75 if (R.down == G->h_lines[i]) {
76 r.down = i;
77 break;
78 }
79 }
80 for (; i < G->n_hlines; i++) {
81 if (R.up == G->h_lines[i]) {
82 r.up = i;
83 break;
84 }
85 }
86 return r;
87}
88#endif
89
90void
91gsave (sgraph* G)
92{
93 int i;
94 G->save_nnodes = G->nnodes;
95 G->save_nedges = G->nedges;
96 for (i = 0; i < G->nnodes; i++)
97 G->nodes[i].save_n_adj = G->nodes[i].n_adj;
98}
99
100void
101reset(sgraph* G)
102{
103 int i;
104 G->nnodes = G->save_nnodes;
105 G->nedges = G->save_nedges;
106 for (i = 0; i < G->nnodes; i++)
107 G->nodes[i].n_adj = G->nodes[i].save_n_adj;
108 for (; i < G->nnodes+2; i++)
109 G->nodes[i].n_adj = 0;
110}
111
112void
113initSEdges (sgraph* g, int maxdeg)
114{
115 int i;
116 int* adj = N_NEW (6*g->nnodes + 2*maxdeg, int);
117 g->edges = N_NEW (3*g->nnodes + maxdeg, sedge);
118 for (i = 0; i < g->nnodes; i++) {
119 g->nodes[i].adj_edge_list = adj;
120 adj += 6;
121 }
122 for (; i < g->nnodes+2; i++) {
123 g->nodes[i].adj_edge_list = adj;
124 adj += maxdeg;
125 }
126}
127
128sgraph*
129createSGraph (int nnodes)
130{
131 sgraph* g = NEW(sgraph);
132
133 /* create the nodes vector in the search graph */
134 g->nnodes = 0;
135 g->nodes = N_NEW(nnodes, snode);
136 return g;
137}
138
139snode*
140createSNode (sgraph* g)
141{
142 snode* np = g->nodes+g->nnodes;
143 np->index = g->nnodes;
144 g->nnodes++;
145 return np;
146}
147
148static void
149addEdgeToNode (snode* np, sedge* e, int idx)
150{
151 np->adj_edge_list[np->n_adj] = idx;
152 np->n_adj++;
153}
154
155sedge*
156createSEdge (sgraph* g, snode* v1, snode* v2, double wt)
157{
158 sedge* e;
159 int idx = g->nedges++;
160
161 e = g->edges + idx;
162 e->v1 = v1->index;
163 e->v2 = v2->index;
164 e->weight = wt;
165 e->cnt = 0;
166
167 addEdgeToNode (v1, e, idx);
168 addEdgeToNode (v2, e, idx);
169
170 return e;
171}
172
173void
174freeSGraph (sgraph* g)
175{
176 free (g->nodes[0].adj_edge_list);
177 free (g->nodes);
178 free (g->edges);
179 free (g);
180}
181
182#include "fPQ.h"
183
184/* shortest path:
185 * Constructs the path of least weight between from and to.
186 *
187 * Assumes graph, node and edge type, and that nodes
188 * have associated values N_VAL, N_IDX, and N_DAD, the first two
189 * being ints, the last being a node*. Edges have a E_WT function
190 * to specify the edge length or weight.
191 *
192 * Assumes there are functions:
193 * agnnodes: graph -> int number of nodes in the graph
194 * agfstnode, agnxtnode : iterators over the nodes in the graph
195 * agfstedge, agnxtedge : iterators over the edges attached to a node
196 * adjacentNode : given an edge e and an endpoint n of e, returns the
197 * other endpoint.
198 *
199 * The path is given by
200 * to, N_DAD(to), N_DAD(N_DAD(to)), ..., from
201 */
202
203#define UNSEEN INT_MIN
204
205static snode*
206adjacentNode(sgraph* g, sedge* e, snode* n)
207{
208 if (e->v1==n->index)
209 return (&(g->nodes[e->v2]));
210 else
211 return (&(g->nodes[e->v1]));
212}
213
214int
215shortPath (sgraph* g, snode* from, snode* to)
216{
217 snode* n;
218 sedge* e;
219 snode* adjn;
220 int d;
221 int x, y;
222
223 for (x = 0; x<g->nnodes; x++) {
224 snode* temp;
225 temp = &(g->nodes[x]);
226 N_VAL(temp) = UNSEEN;
227 }
228
229 PQinit();
230 if (PQ_insert (from)) return 1;
231 N_DAD(from) = NULL;
232 N_VAL(from) = 0;
233
234 while ((n = PQremove())) {
235#ifdef DEBUG
236 fprintf (stderr, "process %d\n", n->index);
237#endif
238 N_VAL(n) *= -1;
239 if (n == to) break;
240 for (y=0; y<n->n_adj; y++) {
241 e = &(g->edges[n->adj_edge_list[y]]);
242 adjn = adjacentNode(g, e, n);
243 if (N_VAL(adjn) < 0) {
244 d = -(N_VAL(n) + E_WT(e));
245 if (N_VAL(adjn) == UNSEEN) {
246#ifdef DEBUG
247 fprintf (stderr, "new %d (%d)\n", adjn->index, -d);
248#endif
249 N_VAL(adjn) = d;
250 if (PQ_insert(adjn)) return 1;
251 N_DAD(adjn) = n;
252 N_EDGE(adjn) = e;
253 }
254 else {
255 if (N_VAL(adjn) < d) {
256#ifdef DEBUG
257 fprintf (stderr, "adjust %d (%d)\n", adjn->index, -d);
258#endif
259 PQupdate(adjn, d);
260 N_DAD(adjn) = n;
261 N_EDGE(adjn) = e;
262 }
263 }
264 }
265 }
266 }
267
268 /* PQfree(); */
269 return 0;
270}
271
272