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 | /****************************************** |
16 | |
17 | Breadth First Search |
18 | Computes single-source distances for |
19 | unweighted graphs |
20 | |
21 | ******************************************/ |
22 | |
23 | #include "bfs.h" |
24 | #include <stdlib.h> |
25 | /* #include <math.h> */ |
26 | |
27 | void bfs(int vertex, vtx_data * graph, int n, DistType * dist, Queue * Q) |
28 | /* compute vector 'dist' of distances of all nodes from 'vertex' */ |
29 | { |
30 | int i; |
31 | int closestVertex, neighbor; |
32 | DistType closestDist = INT_MAX; |
33 | |
34 | /* initial distances with edge weights: */ |
35 | for (i = 0; i < n; i++) |
36 | dist[i] = -1; |
37 | dist[vertex] = 0; |
38 | |
39 | initQueue(Q, vertex); |
40 | |
41 | if (graph[0].ewgts == NULL) { |
42 | while (deQueue(Q, &closestVertex)) { |
43 | closestDist = dist[closestVertex]; |
44 | for (i = 1; i < graph[closestVertex].nedges; i++) { |
45 | neighbor = graph[closestVertex].edges[i]; |
46 | if (dist[neighbor] < -0.5) { /* first time to reach neighbor */ |
47 | dist[neighbor] = closestDist + 1; |
48 | enQueue(Q, neighbor); |
49 | } |
50 | } |
51 | } |
52 | } else { |
53 | while (deQueue(Q, &closestVertex)) { |
54 | closestDist = dist[closestVertex]; |
55 | for (i = 1; i < graph[closestVertex].nedges; i++) { |
56 | neighbor = graph[closestVertex].edges[i]; |
57 | if (dist[neighbor] < -0.5) { /* first time to reach neighbor */ |
58 | dist[neighbor] = |
59 | closestDist + |
60 | (DistType) graph[closestVertex].ewgts[i]; |
61 | enQueue(Q, neighbor); |
62 | } |
63 | } |
64 | } |
65 | } |
66 | |
67 | /* For dealing with disconnected graphs: */ |
68 | for (i = 0; i < n; i++) |
69 | if (dist[i] < -0.5) /* 'i' is not connected to 'vertex' */ |
70 | dist[i] = closestDist + 10; |
71 | } |
72 | |
73 | int |
74 | bfs_bounded(int vertex, vtx_data * graph, int n, DistType * dist, |
75 | Queue * Q, int bound, int *visited_nodes) |
76 | /* compute vector 'dist' of distances of all nodes from 'vertex' */ |
77 | /* ignore nodes whose distance to 'vertex' is more than bound */ |
78 | { |
79 | /* we assume here, that all distances are initialized with -1 !!!! */ |
80 | |
81 | int i; |
82 | int num_visit; |
83 | int closestVertex, neighbor; |
84 | DistType closestDist; |
85 | /* initialize distances with edge weights: */ |
86 | /* for (i=0; i<n; i++) */ |
87 | /* dist[i]=-1; */ |
88 | |
89 | dist[vertex] = 0; |
90 | |
91 | initQueue(Q, vertex); |
92 | |
93 | num_visit = 0; |
94 | while (deQueue(Q, &closestVertex)) { |
95 | closestDist = dist[closestVertex]; |
96 | if (closestDist > bound) { |
97 | dist[closestVertex] = -1; |
98 | break; |
99 | } else { |
100 | visited_nodes[num_visit++] = closestVertex; |
101 | } |
102 | for (i = 1; i < graph[closestVertex].nedges; i++) { |
103 | neighbor = graph[closestVertex].edges[i]; |
104 | if (dist[neighbor] < -0.5) { /* first time to reach neighbor */ |
105 | dist[neighbor] = closestDist + 1; |
106 | enQueue(Q, neighbor); |
107 | } |
108 | } |
109 | } |
110 | |
111 | /* set distances of all nodes in Queue to -1 */ |
112 | /* for next run */ |
113 | while (deQueue(Q, &closestVertex)) { |
114 | dist[closestVertex] = -1; |
115 | } |
116 | dist[vertex] = -1; |
117 | return num_visit; |
118 | } |
119 | |
120 | #ifndef __cplusplus |
121 | |
122 | void mkQueue(Queue * qp, int size) |
123 | { |
124 | qp->data = N_GNEW(size, int); |
125 | qp->queueSize = size; |
126 | qp->start = qp->end = 0; |
127 | } |
128 | |
129 | Queue *newQueue(int size) |
130 | { |
131 | Queue *qp = GNEW(Queue); |
132 | mkQueue(qp, size); |
133 | return qp; |
134 | } |
135 | |
136 | void freeQueue(Queue * qp) |
137 | { |
138 | free(qp->data); |
139 | } |
140 | |
141 | void delQueue(Queue * qp) |
142 | { |
143 | free(qp->data); |
144 | free(qp); |
145 | } |
146 | |
147 | void initQueue(Queue * qp, int startVertex) |
148 | { |
149 | qp->data[0] = startVertex; |
150 | qp->start = 0; |
151 | qp->end = 1; |
152 | } |
153 | |
154 | boolean deQueue(Queue * qp, int *vertex) |
155 | { |
156 | if (qp->start >= qp->end) |
157 | return FALSE; /* underflow */ |
158 | *vertex = qp->data[qp->start++]; |
159 | return TRUE; |
160 | } |
161 | |
162 | boolean enQueue(Queue * qp, int vertex) |
163 | { |
164 | if (qp->end >= qp->queueSize) |
165 | return FALSE; /* overflow */ |
166 | qp->data[qp->end++] = vertex; |
167 | return TRUE; |
168 | } |
169 | |
170 | #endif |
171 | |