FilesExpand file tree

 master

/

bfs.c

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

73 lines (61 loc) · 2.2 KB

 master

/

bfs.c

Copy path

Top

File metadata and controls

• Code
• Blame

73 lines (61 loc) · 2.2 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/*

* Copyright 2018-2020 Redis Labs Ltd. and Contributors

*

* This file is available under the Redis Labs Source Available License Agreement

*/

#include "./bfs.h"

#include "../util/arr.h"

#include "../graph/entities/qg_edge.h"

#include <stddef.h>

#include "rax.h"

// Returns a set of nodes reached at given level from S.

QGNode **BFS(QGNode *s, int *level) {

void *seen; // Has node been visited?

int current_level = 0; // Tracks BFS level.

rax *visited = raxNew(); // Dictionary of visited nodes.

QGNode **next = array_new(QGNode *, 0); // Nodes to explore next.

QGNode **current = array_new(QGNode *, 1); // Nodes currently explored.

current = array_append(current, s);

// As long as we've yet to reach required level and there are nodes to process.

while(current_level < *level && array_len(current)) {

// As long as there are nodes in the frontier.

for(int i = 0; i < array_len(current); i++) {

QGNode *n = current[i];

// Have we already processed n?

seen = raxFind(visited, (unsigned char *)n->alias, strlen(n->alias));

if(seen != raxNotFound) continue;

// Expand node N by visiting all of its neighbors

for(int j = 0; j < array_len(n->outgoing_edges); j++) {

QGEdge *e = n->outgoing_edges[j];

seen = raxFind(visited, (unsigned char *)e->dest->alias, strlen(e->dest->alias));

if(seen == raxNotFound) {

next = array_append(next, e->dest);

}

}

for(int j = 0; j < array_len(n->incoming_edges); j++) {

QGEdge *e = n->incoming_edges[j];

seen = raxFind(visited, (unsigned char *)e->src->alias, strlen(e->src->alias));

if(seen == raxNotFound) {

next = array_append(next, e->src);

}

}

// Mark n as visited.

raxInsert(visited, (unsigned char *)n->alias, strlen(n->alias), NULL, NULL);

}

/* No way to progress and we're interested in the lowest level leafs

* do not clear current queue. */

if(array_len(next) == 0 && *level == BFS_LOWEST_LEVEL) {

*level = current_level;

break;

}

// Queue consumed, swap queues.

array_clear(current);

QGNode **tmp = current;

current = next;

next = tmp;

current_level++;

}

raxFree(visited);

array_free(next);

return current;

}