Graphviz  2.41.20170921.2350
bfs.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 /******************************************
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
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
Definition: legal.c:33
Queue * newQueue(int size)
Definition: bfs.c:129
void bfs(int vertex, vtx_data *graph, int n, DistType *dist, Queue *Q)
Definition: bfs.c:27
void freeQueue(Queue *qp)
Definition: bfs.c:136
boolean enQueue(Queue *qp, int vertex)
Definition: bfs.c:162
int queueSize
Definition: bfs.h:71
Definition: bfs.h:69
int bfs_bounded(int vertex, vtx_data *graph, int n, DistType *dist, Queue *Q, int bound, int *visited_nodes)
Definition: bfs.c:74
int nedges
Definition: sparsegraph.h:80
void initQueue(Queue *qp, int startVertex)
Definition: bfs.c:147
int * data
Definition: bfs.h:70
int * edges
Definition: sparsegraph.h:81
void mkQueue(Queue *qp, int size)
Definition: bfs.c:122
Agraph_t * graph(char *name)
Definition: gv.cpp:38
int DistType
Definition: sparsegraph.h:92
#define NULL
Definition: logic.h:39
int start
Definition: bfs.h:73
#define GNEW(t)
Definition: memory.h:37
int end
Definition: bfs.h:72
void delQueue(Queue *qp)
Definition: bfs.c:141
double dist(Site *s, Site *t)
Definition: site.c:41
boolean deQueue(Queue *qp, int *vertex)
Definition: bfs.c:154
#define N_GNEW(n, t)
Definition: agxbuf.c:20
#define FALSE
Definition: cgraph.h:35
#define INT_MAX
Definition: arith.h:52
#define TRUE
Definition: cgraph.h:38