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
27void 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
73int
74bfs_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
122void 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
129Queue *newQueue(int size)
130{
131 Queue *qp = GNEW(Queue);
132 mkQueue(qp, size);
133 return qp;
134}
135
136void freeQueue(Queue * qp)
137{
138 free(qp->data);
139}
140
141void delQueue(Queue * qp)
142{
143 free(qp->data);
144 free(qp);
145}
146
147void initQueue(Queue * qp, int startVertex)
148{
149 qp->data[0] = startVertex;
150 qp->start = 0;
151 qp->end = 1;
152}
153
154boolean 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
162boolean 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