-
Notifications
You must be signed in to change notification settings - Fork 0
/
bfs.janus
222 lines (201 loc) · 6.87 KB
/
bfs.janus
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
/*
* getlist gets the contents of a single list in the adjacency list.
*
* Parameters:
* int G[] A list of adjacency list elements
* int nodes[] A list of pointers to the start of each individual list
* int i The list that should get extracted (numbered)
* int res[] A list to store the returned elements in
*
* Postcondition:
* A copy of a the items in a list in the adjacency list.
*/
procedure getlist(int G[], int nodes[], int i, int res[])
// end contains a pointer to the end of the wanted list
local int end = 0
if i = (size(nodes) - 1) then
// If we try to get the last list we stop at the end of the element list
end += size(G)
else
// Or else, we stop where the next list starts
end += nodes[i + 1][0]
fi i = (size(nodes) - 1)
// All elements of the wanted list are loaded into res
local int r = nodes[i][0]
from r = nodes[i][0] do
res[r - nodes[i][0]] += G[r]
r += 1
until r = end
delocal int r = end
// end is delocated
if i = (size(nodes) - 1) then
end -= size(G)
else
end -= nodes[i + 1][0]
fi i = (size(nodes) - 1)
delocal int end = 0
/*
* enqueue adds an item to a queue.
*
* Parameters:
* int queue[] Queue to add item to.
* int tailpointer Pointer to the last item in the queue
* int item Item to add to the queue.
*
* Postcondition:
* A queue with the item added to the tail and an empty item (0).
*
* Errors:
* Item added to the queue is empty (0).
* Queue is full.
*/
procedure enqueue(int queue[], int tailpointer, int item)
// Error checks (input)
if item = 0 then
error("Item added to queue is empty (0).")
fi item = 0
if queue[tailpointer] != 0 then
error("Queue is full. Cannot enqueue item.")
fi queue[tailpointer] != 0
// Adds the item to the queue spot and empties the item
local int tmp = item
queue[tailpointer] += tmp
item -= tmp
delocal int tmp = queue[tailpointer]
// Goes to next queue spot
if tailpointer + 1 != size(queue) then
tailpointer += 1
else
tailpointer -= size(queue) - 1
fi tailpointer != 0
/*
* dequeue removes an item to a queue.
*
* Parameters:
* int queue[] Queue to add item to.
* int headpointer Pointer to the first item in the queue
* int placeholder Empty item placeholder.
*
* Postcondition:
* A queue with the first item removed and the dequeued item.
*
* Errors:
* Placeholder item not empty (0).
* Queue is empty.
*/
procedure dequeue(int queue[], int headpointer, int placeholder)
// Error checks (input)
if placeholder != 0 then
error("Placeholder not empty (0).")
fi placeholder != 0
if queue[headpointer] = 0 then
error("Queue is empty. Tried to remove item from empty queue.")
fi queue[headpointer] = 0
// Loads the queue item into the placeholder and empties the queue spot
local int tmp = queue[headpointer]
placeholder += tmp
queue[headpointer] -= tmp
delocal int tmp = placeholder
// Goes to next queue spot
if headpointer + 1 != size(queue) then
headpointer += 1
else
headpointer -= size(queue) - 1
fi headpointer != 0
/*
* BFS searches a graph from a single source node creating a breadth-first tree.
*
* Parameters:
* int G[] A list of adjacency list elements
* int nodes[] A list of pointers to the start of each individual list
* int s The source node
* int headpointer A pointer to the head of a queue
* int order[] An array with the order taken in the BFS
*/
procedure BFS(int G[], int nodes[], int s, int headpointer, int order[])
// FIFO queue
local int queue[size(G)] = {0}, int tailpointer = headpointer
// Storage for dequeued node and adjacent nodes, loopcounter
local int store = 0, int adjstore = 0, int i = 0
local int adj[size(G)] = {0} // Stores the current adjacent nodes
// We mark the current node as the source node and enqueue it
nodes[s-1][1] -= 1
store += s
call enqueue(queue, tailpointer, store)
from headpointer = 0 do
if queue[headpointer] != 0 then
// We dequeue a node and gets its adjacency list
call dequeue(queue, headpointer, store)
call getlist(G, nodes, store-1, adj)
order[headpointer] += store
// We check the list and enqueue all unvisited nodes
from i = 0 do
if adj[i] = 0 then
skip
else
if nodes[adj[i]-1][1] = 0 then
adjstore += adj[i]
nodes[adj[i]-1][1] += store
call enqueue(queue, tailpointer, adjstore)
fi nodes[adj[i]-1][1] = store
fi adj[i] = 0
i += 1
until i = size(adj)
i -= size(adj)
// Remove the content from adj and store
uncall getlist(G, nodes, store-1, adj)
store -= order[headpointer]
fi queue[headpointer] != 1
until headpointer = tailpointer
// Delocal local variables
delocal int adj[size(G)] = {0}
delocal int store = 0, int adjstore = 0, int i = 0
delocal int queue[size(G)] = {0}, int tailpointer = headpointer
/*
* printpath prints a path from the source of a breadth-first tree to a node
* if such a path exists
*
* Parameters:
* int G[] A list of adjacency list elements
* int v The destination node
*/
procedure printpath(int G[], int v)
local int u = G[v-1][1]
if G[v-1][1] = 0 then
printf("No path exists from the source of G to node %d", v)
else
if G[v-1][1] != -1 then
call printpath(G, u)
fi G[v-1][1] != -1
printf("%d", v)
fi G[v-1][1] = 0
delocal int u = G[v-1][1]
/*
* Main procedure. Creates an adjacency list and runs BFS, then printpath on it.
*/
procedure main()
// Adjacency list, list of adjacent nodes
int G[] = {2, 4, 1, 5, 4, 1, 3, 5, 2, 4, 7, 4}
// Adjacency list, node information.
// Each node has a pointer to their first element
// Each node stores its parent
int nodes[7][2] = {{0, 0},
{2, 0},
{4, 0},
{5, 0},
{8, 0},
{10, 0},
{11, 0}}
int headpointer = 0
int order[size(nodes)-1] = {0}
int s = 1
int v = 3
call BFS(G, nodes, s, headpointer, order)
print("A shortest path from source 1 to node 3:")
call printpath(nodes, v)
v += 2
print("A shortest path from source 1 to node 5:")
call printpath(nodes, v)
v += 2
print("A shortest path from source 1 to node 7:")
call printpath(nodes, v)