Graphviz  2.35.20130930.0449
bfs.h
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 #ifdef __cplusplus
15 extern "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