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#ifdef __cplusplus
15extern "C" {
16#endif
17
18#ifndef _BFS_H_
19#define _BFS_H_
20
21#include "defs.h"
22
23#ifdef __cplusplus
24 class Queue {
25 private:
26 int *data;
27 int queueSize;
28 int end;
29 int start;
30 public:
31 Queue(int size) {
32 data = new int[size];
33 queueSize = size;
34 start = 0;
35 end = 0;
36 } ~Queue() {
37 delete[]data;
38 } void initQueue(int startVertex) {
39 data[0] = startVertex;
40 start = 0;
41 end = 1;
42 }
43
44 bool dequeue(int &vertex) {
45
46 if (start >= end)
47 return false; /* underflow */
48
49 vertex = data[start++];
50 return true;
51
52 }
53
54 bool enqueue(int vertex) {
55 if (end >= queueSize)
56 return false; /* overflow */
57 data[end++] = vertex;
58 return true;
59 }
60 };
61
62
63 void bfs(int vertex, vtx_data * graph, int n, DistType * dist,
64 Queue & Q);
65 void bfs_bounded(int vertex, vtx_data * graph, int n, DistType * dist,
66 Queue & Q, int bound, int *visited_nodes,
67 int &num_visited_nodes);
68#else
69 typedef struct {
70 int *data;
71 int queueSize;
72 int end;
73 int start;
74 } Queue;
75
76 extern void mkQueue(Queue *, int);
77 extern void freeQueue(Queue *);
78 extern void initQueue(Queue *, int startVertex);
79 extern boolean deQueue(Queue *, int *);
80 extern boolean enQueue(Queue *, int);
81
82 extern void bfs(int, vtx_data *, int, DistType *, Queue *);
83 extern int bfs_bounded(int, vtx_data *, int, DistType *, Queue *, int,
84 int *);
85#endif
86
87#endif
88
89#ifdef __cplusplus
90}
91#endif
92