dfs.c

/*
DFS(G,v)   ( v is the vertex where the search starts )
         Stack S := {};   ( start with an empty stack )
         for each vertex u, set visited[u] := false;
         push S, v;
         while (S is not empty) do
            u := pop S;
            if (not visited[u]) then
               visited[u] := true;
               for each unvisited neighbour w of u
                  push S, w;
            end if
         end while
      END DFS()
*/
#include "dfs.h"

void stack_enqueue(struct node *n, struct list_head *stack)
{
	if (list_empty(stack))
		INIT_LIST_HEAD(stack);
	list_add(&n->list, stack);
}

struct node *stack_dequeue(struct list_head *stack)
{
	struct node *n;

	n = list_first_entry(stack, struct node, list);
	list_del(&n->list);

	return n;
}

void add_visited(struct node *n, struct list_head *visited)
{
	if (list_empty(visited))
		INIT_LIST_HEAD(visited);
	list_add(&n->list, visited);
}

bool is_visited(char *path, struct list_head *visited)
{
	struct node *tmp;

	list_for_each_entry(tmp, visited, list) {
		if (strncmp(tmp->path, path, 1024) == 0)
			return true;
	}

	return false;
}

void clear_list(struct list_head *visited)
{
	struct node *n, *tmp;

	list_for_each_entry_safe(n, tmp, visited, list) {
		free(n->path);
		list_del(&n->list);
		free(n);
	}
}

void print_list_dfs(struct list_head *collection_of_nodes_and_stuff)
{
	struct node *n;

	if (list_empty(collection_of_nodes_and_stuff))
		return;

	list_for_each_entry(n, collection_of_nodes_and_stuff, list) {
		printf("path: %s\n", n->path);
	}
}