Thread: BFS in C, how to get just the path to the goal?

  1. #1
    Registered User
    Join Date
    Sep 2019
    Posts
    1

    BFS in C, how to get just the path to the goal?

    I have a program in C that does BFS to search for a goal vertex. The problem is that it spits out all the vertices it visited and not just the path to the goal. I can't quite come up with a solution for it without causing segmentation faults.

    Suppose the input file is:

    Code:
    10
    4 8 10
    9 6 10 7 2
    1 6 2 3 7
    7 2 9 1 5
    3 6 1 5
    8 5 4
    5 3 8 7
    6 1 3 9
    2 7 1 9
    10 4 9
    The first line is the number of vertices while the other lines list out the adjacency matrix.

    Output comes out as 1--7--3--2--6--5--9--8--10 when searching for 10 when I just want to save the path 1--7--9--10. Can anyone recommend some new data structures so that I can change this path? What I have tried doesn't work.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <time.h>
    #include <unistd.h>
    
    
    
    
    #define PATH_MAX 4096
    int edges_visited;
    
    
    struct bfs {
    	struct AdjList* path;
    	struct Node* next;
    };
    //struct bfs paths[1000];
    
    
    
    
    struct AdjList {
    	int value;
    	int mark;
    	struct Node* list;
    };
    struct Node {
    	struct AdjList* vertex;
    	struct Node* next;
    };
    struct Queue {
    };
    typedef struct AdjList AdjList;
    typedef struct Node Node;
    // creates a new vertex and return pointer to it
    AdjList* new_vertex(int value, AdjList* graph[]) {
    	AdjList* vertex = (AdjList*)malloc(sizeof(AdjList));
    	vertex->value = value;
    	vertex->list = 0;
    	graph[value] = vertex;
    	return vertex;
    }
    // connect vertex a to vertex b
    // by adding b to a's list
    void do_connect(AdjList* a, AdjList* b) {
    	Node* node = (Node*)malloc(sizeof(Node));
    	node->vertex = b;
    	node->next = a->list;
    	a->list = node;
    }
    
    
    // connects a to b and b to a
    void connect(AdjList* a, AdjList* b) {
    	do_connect (a, b);
    	//do_connect (b, a);
    }
    
    
    // visit function
    int visit(AdjList* vertex, int goal) {
    	if (vertex->value == goal) {
    		printf ("%d ", vertex->value);
    		//clock_t end = clock();
    		//time_spent += (double)(end - begin) / CLOCKS_PER_SEC;
    
    
    		//printf("Time elpased is %f seconds", time_spent);
    		return 1;
    		//exit(0);
    	}
    	printf ("%d --" ,vertex->value);
    	
    	//return 0;
    }
    int do_bfs(AdjList *vertex, int* count, int goal) {
    	Node *initialQueue, *front, *rear, *p, *temp;
    
    
    	//struct bfs paths[1000];
    
    
    	///int path_i = 0;
    	//paths[path_i].path = vertex; 
    
    
    	AdjList *w;
    	// mark vertex with count
    	vertex->mark = ++(*count);
    	visit (vertex, goal);
    
    
    	// initialize queue with a vertex
    	initialQueue = (Node*)malloc(sizeof(Node));
    	initialQueue->vertex = vertex;
    	initialQueue->next = 0;
    	front = initialQueue;
    	rear  = initialQueue;
    	// while queue is not empty
    	while (front != 0) {
    		// for vertex w in V adjacent to the front vertex
    		p = front->vertex->list;
    		while (p != 0) {
    			w = p->vertex;
    			
    			// if w is marked with 0
    			if (w->mark == 0) {
    				// paths[path_i].next = w->list;
    				// path_i++;
    				Node* nextQueue;
    				// count = count + 1, mark w with count
    				edges_visited = edges_visited+1;
    				w->mark = ++(*count);
    				int is_goal = visit (w,goal);
    				if(is_goal == 1){
    					return path_i;
    				}
    				// add w to queue
    				nextQueue = (Node*)malloc(sizeof(Node));
    				nextQueue->vertex = w;
    				nextQueue->next = 0;
    				rear->next = nextQueue;
    				rear = nextQueue;
    			}
    
    
    			p = p->next;
    			//paths[path_i].path = p->vertex;
    
    
    		}
    		// remove front vertex from queue
    		temp = front;
    		front = front->next;
    		free (temp);
    	}
    }
    int bfs(AdjList *graph[], int goal, int no_vertices) {
    	int i;
    	int count = 0;
    	// set all to unvisited
    	for (i = 0; i < no_vertices; i ++) {
    		graph[i]->mark = 0;
    	}
    	// do bfs for each vertex
    	i = do_bfs (graph[1], &count, goal);
    	return i;
    }
    int main(int argc, char *argv[]) {
    
    
    	 char c[1000];
         FILE *fptr;
         int is_bfs = 0;
         int is_dfs = 0;
         int is_extended = 0;
         int goal_vertex;
         char *graph_file;
    
    
         for(int i = 0; i< argc; i++){
         	if (strcmp("-dfs", argv[i]) == 0) {
    			is_dfs = 1;	
    		}	
    		if (strcmp("-bfs", argv[i]) == 0) {
    			is_bfs = 1;	
    		}
    		if (strcmp("-dest", argv[i]) == 0) {
    			goal_vertex = atoi(argv[i+1]);
    		}
    		if (strcmp("-e", argv[i]) == 0) {
    			is_extended = 1;
    		}
         }
    
    
         graph_file = argv[argc-1];
         //printf("\n Graph file name is: %s", graph_file);
         
         //printf("\n file path name is: %s", file_string);
         
         if ((fptr = fopen(graph_file, "r")) == NULL)
         {
            printf("Error! opening file");
            // Program exits if file pointer returns NULL.
            exit(1);         
         }
         fscanf(fptr, "%[^\n]",c);
       	 //printf("\n %s",c);
    
    
       	 int no_vertices = atoi(c);
         no_vertices = no_vertices+1;
    
    
         AdjList *graph[no_vertices];
         for(int i = 0; i<=no_vertices; i++){
         	new_vertex(i, graph);
         }
    
    
         const size_t line_size = 300;
         char* line = malloc(line_size);
    
    
         for(int i = 0; i<no_vertices; i++){
       		//fscanf(fptr,"%[^\n]",c);
       		//printf("\n %s", c);
    
    
       		fgets(line, line_size, fptr);
       		//printf(line);
       		char* token = strtok(line, " ");
       		int start_vertex = atoi(token);
       		while (token){
       			//printf("token: %s\n", token);
       			token = strtok(NULL,  " ");
       			if(token != NULL){
       				int dest_vertex = atoi(token);
       			    connect(graph[start_vertex], graph[dest_vertex]);
       			}
       		}
         }
         //printGraph(graph, no_vertices);
    	double time_spent = 0.0;
    	clock_t start,end;
    
    
    	if (is_dfs == 1){
    		// do depth first search
    		printf ("path: ");
    		
    		start = clock();
    		dfs (graph, goal_vertex, no_vertices);
    		end = clock();
    	}
    	int path_i = 0;
    	if (is_bfs == 1) {
    		// do breadth first search
    		printf ("\n\n");
    		start = clock();
    
    
    		printf ("path: ");
    		path_i = bfs (graph, goal_vertex, no_vertices);
    		end = clock();
    
    
    	}
    	time_spent = ((double) (end-start))/CLOCKS_PER_SEC;
    	double time_spent_ms = time_spent * 1000000;
    	printf("\nEdges: %d", edges_visited);
    	printf("\nExecution time: %f ms \n", time_spent_ms);
    
    
    	// printf("\n%d", path_i);
    	// printf("\n%d",paths[0].path->value);
    
    
    	fflush( stdout );
    }



    Any suggestions?

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,429
    > Output comes out as 1--7--3--2--6--5--9--8--10 when searching for 10 when I just want to save the path 1--7--9--10.
    ...
    > printf ("%d --" ,vertex->value);
    I can recommend that you run the code in the debugger, put a breakpoint on this line and run the code.
    When you get to vertex->value == 3, then you stop and have a really good think about
    a) how you got to this point.
    b) how to prevent getting to this point.

    Oh, and you need to put back the return 0; in the visit() function as well.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. What steps should I take to accomplish my goal in networking?
    By HelpfulPerson in forum Networking/Device Communication
    Replies: 4
    Last Post: 09-10-2013, 08:13 PM
  2. Goal: ReactOS programmer, Tactic: Unknown?
    By Witch in forum C Programming
    Replies: 4
    Last Post: 05-29-2011, 01:02 PM
  3. goal is to write a telephone directory
    By cowgiljl in forum C++ Programming
    Replies: 1
    Last Post: 12-07-2003, 03:21 AM
  4. Whats ur Professional Goal?
    By Liam Battle in forum A Brief History of Cprogramming.com
    Replies: 62
    Last Post: 05-11-2002, 06:14 PM

Tags for this Thread