C programming:Graph First, complete computeAdjacencyMatrix and computeReachabili
ID: 666685 • Letter: C
Question
C programming:Graph
First, complete computeAdjacencyMatrix and computeReachabilityMatrix in graph.c. These two functions will allow you to examine the results from your searches once you have constructed them. computeAdjacencyMatrix must be done in O(V^2 +VE) time.
Both of these functions are constructing VxV binary matrices where mat[i][j] = 1 represents the existence of an edge (or path in the case of the reachability matrix) between vertex i and vertex j, and 0 otherwise.
Next, complete the implementation of DFS and BFS. Instead of computing reachability from one node to all, we are computing reachability from one source to one destination node. This algorithms is essentially the same as one to all reachability, except you halt the search once the destination is found. In completing the searches, you will have a chance to utilize some of the ADTs we have covered in this class (stack, queue).
Note that a recursive DFS is provided, which will allow you to check your answers.
Files you need:
//ListDeque.h
//ListDeque.c
#include "ListDeque.h"
/* Create a link for a value.
Use this function in your add operations to make it easier to allocate links
param: val the value to store in the newy created link
pre: none
post: a link is allocated on the heap, storing the argument value
ret: the newly allocated link
*/
DLink* _createLink(TYPE val)
{
DLink* lnk = (DLink*) malloc(sizeof(DLink));
assert(lnk != 0);
lnk->value = val;
return lnk;
}
/* ************************************************************************
Basic Operations
************************************************************************ */
/* Initializes a deque.
param: d pointer to the deque
pre: d is not null
post: size, head, and tail are initialized
*/
void initListDeque(ListDeque* d)
{
/*FIXME you will write this function */
d->head = malloc(sizeof(struct DLink));
d->tail = malloc(sizeof(struct DLink));
d->size = 0;
d->head = 0;
d->tail = 0;
}
/* De-allocate all links of the deque.
Write this function in terms of a remove function, such as removeBack.
param: d pointer to the deque
pre: d is not null
post: All links are de-allocated
*/
void freeListDeque(ListDeque* d)
{
/*FIXME you will write this function */
DLink *position = d->head;
while(position != 0)
position = removeLinkListDeque(d,position);
d->size = 0;
}
/* Check whether the deque is empty.
param: d pointer to the deque
pre: d is not null
ret: 1 if the deque is empty. Otherwise, 0.
*/
int isEmptyListDeque(ListDeque *d) {
/*FIXME you will write this function */
if(d->size == 0)
return 1;
else
return 0;
}
/* Get the value stored in the link at the front of the deque
param: d pointer to the deque
pre: d is not null
pre: d is not empty
post: none
ret: value of the front of the deque
*/
TYPE frontListDeque (ListDeque *d)
{
assert(!isEmptyListDeque(d));
return d->head->value;
}
/* Get the value stored in the link at the back of the deque
param: d pointer to the deque
pre: d is not null
pre: d is not empty
post: none
ret: value of the back of the deque
*/
TYPE backListDeque(ListDeque *d)
{
/*FIXME you will write this function */
TYPE var;
var = d->tail->value;
return var;
}
/* Adds a link AFTER another link.
Write your other add functions in terms of addAfter and addBefore when possible.
param: d pointer to the deque
param: addAfter pointer to the existing link in the deque
param: newLnk pointer to the new link to add after the existing link
pre: d is not null
pre: newLnk has been properly initialized
pre: addAfter is in the deque if it is not a NULL pointer
post: newLnk is added into the deque AFTER the existing link
*/
void addLinkAfterListDeque(ListDeque* d, DLink* addAfter, DLink* newLnk)
{
/*FIXME you will write this function */
ListDeque *t=d;
while(t->head!=addAfter)
t->head=t->head->next;
if(t->head==addAfter)
t->head->next=newLnk;
newLnk->prev=t->head;
}
/* Adds a link BEFORE another link.
Write your other add functions in terms of addAfter and addBefore when possible.
param: d pointer to the deque
param: addBefore pointer to the existing link in the deque
param: newLnk pointer to the new link to add before the existing link
pre: d is not null
pre: newLnk has been properly initialized
pre: addBefore is in the deque if it is not a NULL pointer
post: newLnk is added into the deque BEFORE the existing link
*/
void addLinkBeforeListDeque(ListDeque* d, DLink* addBefore, DLink* newLnk)
{
/*FIXME you will write this function */
addBefore->prev->next = newLnk;
newLnk->prev = addBefore->prev;
newLnk->next = addBefore;
addBefore->prev = newLnk;
d->size++;
}
/* Remove a link from the deque.
Write our other remove functions in terms of this function when possible.
Be careful not to use a pointer that you have already freed when returning.
param: d pointer to the deque
param: lnk pointer to the link to be removed
pre: d is not null
pre: d is not empty
pre: lnk is in the deque
post: lnk is removed from the deque
ret: The pointer which follows lnk
*/
DLink* removeLinkListDeque(ListDeque *d, DLink *lnk)
{
/*FIXME you will write this function */
if(lnk==d->head){
removeFrontListDeque(d);
return d->head;
}
else if(lnk==d->tail){
removeBackListDeque(d);
return d->tail;
}
else{
DLink *temp = lnk->next;
temp->prev = lnk->prev;
lnk->prev->next = temp;
d->size--;
return temp;
}
return 0;
}
/* ************************************************************************
Deque Interface
************************************************************************ */
/* Adds a link to the back of the deque.
Write this function in terms of addLinkAfter() when possible.
param: d pointer to the deque
param: val value for the link to be added
pre: d is not null
post: a link storing val is added to the back of the deque
*/
void addBackListDeque (ListDeque *d, TYPE val)
{
/*FIXME you will write this function */
/*struct DLink *hehehe= malloc(sizeof(DLink));
hehehe->value = val;
addLinkBeforeListDeque(d,d->tail,hehehe);*/
DLink *newLnk=_createLink(val);
if(isEmptyListDeque(d)==1){
d->head = newLnk;
d->tail = newLnk;
newLnk->next = 0;
newLnk->prev = 0;
}
else {
d->tail->next = newLnk;
newLnk->prev = d->tail;
d->tail = newLnk;
newLnk->next = 0;
}
d->size++;
}
/* Adds a link to the front of the deque.
Write this function in terms of addLinkBefore when possible.
param: d pointer to the deque
param: val value for the link to be added
pre: d is not null
post: a link storing val is added to the front of the deque
*/
void addFrontListDeque(ListDeque *d, TYPE val)
{
/*FIXME you will write this function */
DLink *newLnk=_createLink(val);
if(isEmptyListDeque(d)==1){
d->head = newLnk;
d->tail = newLnk;
newLnk->next = 0;
newLnk->prev = 0;
}
else {
d->head->prev = newLnk;
newLnk->next = d->head;
d->head = newLnk;
newLnk->prev = 0;
}
d->size++;
}
/* Remove the front of the deque.
Write this function in terms of removeLinkListDeque().
param: d pointer to the deque
pre: d is not null
pre: d is not empty
post: the front is removed from the deque
*/
void removeFrontListDeque (ListDeque *d)
{
/*FIXME you will write this function */
if(d->size==1){
d->head = 0;
d->tail = 0;
}
else {
d->head = d->head->next;
d->head->prev = 0;
}
d->size--;
}
/* Remove the back of the deque.
Write this function in terms of removeLinkListDeque().
param: d pointer to the deque
pre: d is not null and q is not empty
post: the back is removed from the deque
*/
void removeBackListDeque(ListDeque *d)
{
/*FIXME you will write this function */
if(d->size==1){
d->head = 0;
d->tail = 0;
}
else {
d->tail = d->tail->prev;
d->tail->next = 0;
}
d->size--;
}
/* ************************************************************************
Bag Interface
************************************************************************ */
/* Returns whether or not the given value is stored in the deque
param: d pointer to the deque
param: val value that we are looking for in the deque
ret: 1 if val is contained in d, 0 otherwise
*/
int containsListDeque(ListDeque* d, TYPE val)
{
/*FIXME you will write this function */
DLink *position = d->head;
while(position != NULL)
{
if(position->value==val)
return 1;
else
position = position->next;
}
return 0;
return 0;
}
/* Removes the first occurrence of the given value from the list.
param: d pointer to the deque
param: val value that we are looking for in the deque
post: first occurrence of val is removed from the list
*/
void removeListDeque(ListDeque* q, TYPE val)
{
/*FIXME you will write this function */
/*ListDeque *t=q;
while(t->head->value!=val)
t->head=t->head->next;
if(t->head->value==val)
{
t->head->next->prev=t->head->next;
t->head->prev=t->head->next;
free(t);
}*/
DLink *position = q->head;
while(position != NULL)
{
if(position->value==val)
position = removeLinkListDeque(q,position);
else
position = position->next;
}
}
/* Reverse the deque. Note that careful swapping of the pointers inside each link
(next and prev) will cause a reverse, provided head and tail are updated properly.
param: d pointer to the deque
pre: d is not null
post: the deque is reversed
*/
void reverseListDeque(ListDeque *q)
{
/*FIXME you will write this function */
DLink *position = q->head;
DLink *temp1, *temp2;
temp1 = q->head;
temp2 = q->tail;
q->head = temp2;
q->tail = temp1;
while(position != NULL)
{
temp1 = position->next;
temp2 = position->prev;
position->next = temp2;
position->prev = temp1;
position = temp1;
}
}
/* Print the links in the deque from front to back
param: d pointer to the deque
pre: d is not null
post: the links in the deque are printed from front to back
*/
void printListDeque(ListDeque *q)
{
DLink* lnk;
lnk = q->head;
printf("Size = %d [ ", q->size);
while(lnk != NULL)
{
printf("%c ", lnk->value);
lnk = lnk->next;
}
printf("] ");
}
//type.h
//graph.h
//graph.c
//main.c
Explanation / Answer
cirListDeque.c
cirListDeque.h
graph.c
graph.h
type.h
main.c
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.