SKELETON CODE IS PROVIDED ALONG WITH C AND H FILES.

#include

#include

#include

#include

#include "node.h"

#include "stack_functions.h"

#define NUM_VERTICES 10

/** This function takes a pointer to the

adjacency matrix of a Graph and the

size of this matrix as arguments and

prints the matrix

*/

void print_graph(int * graph, int size);

/** This function takes a pointer to the

adjacency matrix of a Graph, the size

of this matrix, the source and dest

node numbers along with the weight or

cost of the edge and fills the adjacency

matrix accordingly.

*/

void add_edge(int * graph, int size, int src, int dst, int cost);

/** This function takes a pointer to the adjacency matrix of

a graph, the size of this matrix, source and destination

vertex numbers as inputs and prints out the path from the

source vertex to the destination vertex. It also prints

the total cost of this path.

*/

void find_path_dfs(int * graph, int size, int src, int dst);

int main()

{

int my_graph[NUM_VERTICES][NUM_VERTICES]; /// An adjacency matrix representation of graph

memset(my_graph,-1,NUM_VERTICES * NUM_VERTICES * sizeof(int)); /// Initiallize with -1 representing infinte cost.

for(int i=0; i

add_edge(&my_graph[0][0], NUM_VERTICES, i, i, 0); /// All the vertices have a cost of 0 for visiting themselves add_edge(&my_graph[0][0], NUM_VERTICES, 0, 3, 13);

add_edge(&my_graph[0][0], NUM_VERTICES, 1, 4, 14);

add_edge(&my_graph[0][0], NUM_VERTICES, 0, 3, 13);

add_edge(&my_graph[0][0], NUM_VERTICES, 1, 4, 14);

add_edge(&my_graph[0][0], NUM_VERTICES, 1, 5, 6);

add_edge(&my_graph[0][0], NUM_VERTICES, 2, 3, 9);

add_edge(&my_graph[0][0], NUM_VERTICES, 2, 9, 10);

add_edge(&my_graph[0][0], NUM_VERTICES, 3, 0, 13);

add_edge(&my_graph[0][0], NUM_VERTICES, 3, 8, 9);

add_edge(&my_graph[0][0], NUM_VERTICES, 4, 1, 14);

add_edge(&my_graph[0][0], NUM_VERTICES, 4, 6, 8);

add_edge(&my_graph[0][0], NUM_VERTICES, 5, 1, 6);

add_edge(&my_graph[0][0], NUM_VERTICES, 5, 2, 7);

add_edge(&my_graph[0][0], NUM_VERTICES, 5, 6, 12);

add_edge(&my_graph[0][0], NUM_VERTICES, 6, 4, 8);

add_edge(&my_graph[0][0], NUM_VERTICES, 6, 7, 15);

add_edge(&my_graph[0][0], NUM_VERTICES, 7, 6, 15);

add_edge(&my_graph[0][0], NUM_VERTICES, 8, 5, 11);

add_edge(&my_graph[0][0], NUM_VERTICES, 9, 8, 23);

/* Task 1: Complete the rest of the Adjacency Matrix according to Figure 8 */

print_graph(&my_graph[0][0], NUM_VERTICES);

find_path_dfs(&my_graph[0][0], NUM_VERTICES, 4, 8);

//find_path_dfs(&my_graph[0][0], NUM_VERTICES, 9, 2);

getchar();

return 0;

}

void add_edge(int * graph, int size, int src, int dst, int cost)

{

*(graph+(src*size+dst)) = cost; /// Look carefully how the indices are calculated. You will need it for 2nd task.

}

void print_graph(int * graph, int size)

{

//char vertices[size];

for(int i=0; i

{

printf("\t%d", i);

}

printf(" ");

for(int x=0; x

{

printf("%d\t", x);

for(int y=0; y

printf("%d\t", *(graph+(x*size+y)));

printf(" "); }

}

void find_path_dfs(int * graph, int size, int src, int dst)

{

int visited[10] = {0}; /// To keep track of all the visited nodes

/**** We make a stack for holding the visited vertices *******/

struct node * top = NULL; /// This is the top of the stack

/** The DFS will work as follows:

1. Visit src vertex. Set 'current_visiting' to src.

2. Explore this vertex.

If it is the destination vertex, stop.

Otherwise visit its first unvisited neighbour (add to stack the current vertex)

If no unvisited neighbour vertex remains, go back (pop from stack)

3. Repeat 2*/

int crnt_visiting = src;

int crnt_exploring = src;

int path_cost = 0;

bool PATH_FOUND = false;

while(!PATH_FOUND)

{

visited[crnt_visiting] = 1; /// Now we have visited this node

struct element temp;

if(crnt_visiting == dst) /// If the vertex is found

{

printf(" Path found: ");

printf(" Cost: %d ", path_cost);

while(!isStackEmpty(&top)) /// Empty the stack so all the allocated memory is freed.

{

printf("Pop ");

pop(&top);

}

PATH_FOUND = true;

continue;

}

else /// Explore this vertex

{

/** Complete this function. You are free to make any changes to this function.

But make sure that path cost is correctly found.

*/

}

}

}

STACK C FUNCTION

#include

#include

#include

#include "node.h"

#include "stack_functions.h"

struct element pop(struct node ** top)

{

struct element temp = (*top)->data; /// I copy the data at the top node into a temporary variable

struct node * ptr_temp = (*top)->next;

free(*top);

*top = ptr_temp;

return(temp);

}

void push(struct node ** top, struct element new_data)

{

struct node * new_node = (struct node *) malloc(sizeof(struct node));

new_node->data = new_data; /// I can assign one struct to another if the type is the same

new_node->next = * top;

* top = new_node; }

bool isStackEmpty(struct node ** top)

{

return(*top == NULL);

}

STACK H FUNTION

struct element pop(struct node ** top);

void push(struct node ** top, struct element new_data);

bool isStackEmpty(struct node ** top);

NODE H

struct element

{

int vertex_num;

int cost_to_visit;

};

struct node

{

struct element data;

struct node * next;

};

10 9 N 23 9 13 0 1 3 3 7 6 8 00 14 11 5 4 /12 7 00 8 6 15 Figure 8: A Weighted Directed Graph with 10 Vertices Task 2: For this part you will have to complete the function 'find_path_dfs ( )'which finds the cost of going from the source vertex (src) to destination vertex (dst) using Depth First Search (DFS) algorithm. You will use a stack for implementing DFS algorithm. 10 9 N 23 9 13 0 1 3 3 7 6 8 00 14 11 5 4 /12 7 00 8 6 15 Figure 8: A Weighted Directed Graph with 10 Vertices Task 2: For this part you will have to complete the function 'find_path_dfs ( )'which finds the cost of going from the source vertex (src) to destination vertex (dst) using Depth First Search (DFS) algorithm. You will use a stack for implementing DFS algorithm