- Filling Into Insert Your Code Here In Addconnection Method Include Stdio H Include Stdlib H Include String 1 (45.15 KiB) Viewed 29 times
/* Structure represents a Graph with an array of adjacencylists.Size of the array will be number of vertices.*/typedef struct Graph{ int numberOfVertices; struct node** adjLists;}Graph;
/*A function to create a newnode*/node* createNode(char* name){ node *newNode = (node *)malloc(sizeof(node)); strcpy(newNode->name, name); newNode->next = NULL; return newNode; }
/*A function to create a graph with an array of adjacency listswhich is= numberof vertices*/Graph* createGraph(int vertices){ int i; Graph* graph=(Graph*)malloc(sizeof(Graph)); Graph *graph = (Graph *)malloc(sizeof(Graph)); graph->numberOfVertices = vertices; graph->adjLists = (struct node **)malloc(vertices* sizeof(struct node *)); int i; for (i = 0; i < vertices; i++) graph->adjLists = NULL; // makeadjacent lists equal to zero return graph; }
/* function to count Number of listspresent in the graph*/int numberoflistspresent(Graph* graph){ int i, j = 0; for (i = 0; i < graph->numberOfVertices; i++) { if (graph->adjLists != NULL) // keeping trackof how many lists are already present j++; } return j;}/*searching the persons who are already there in the list*/int search(char* name, Graph* graph){ int i; for (i = 0; i < numberoflistspresent(graph); i++) { if (strcmp(graph->adjLists->name, name) ==0) // search for the person in the adjacent listsand if the person is found // return the index of the adjlist return i; } return -1;}/*adds an edge to an undirected graph*/void addConnection(Graph* graph, char* person, char* friend){ int p = search(person, graph);//search for the personin the graph int n=numberoflistspresent(graph); //number ifpersons already there in the graph //insert your code here}/*function to print the adjacency list representation of agraph*/void printGraph(Graph* graph){ int i; for (i = 0;i<graph->numberOfVertices;i++) { //print the current vertex and all itsneighbors struct node* temp = graph->adjLists; printf("\n%s---",graph->adjLists->name); while((temp->next)!=NULL) { printf("%s-", temp->next->name); temp = temp->next; } printf("NULL\n"); }}
/* CONVERSION TO MATRIX*/int getIndex(Graph* graph, char* name){ int N = graph->numberOfVertices; int i,j=0; for (i = 0; i<N&&strcmp(name,graph->adjLists->name)!=0 ;i++) { j++; } return j;}
void matrixForm(Graph* graph, int emptyMatrix[50][50],intN){ int i,j; for (i = 0; i<N;i++){ struct node* temp =graph->adjLists->next; while (temp!=0) { j = getIndex(graph, temp->name); emptyMatrix[j] = 1; temp = temp->next; } }}void graphDestroy(Graph *graph){ int i; for(i=0; i<graph->numberOfVertices;i++){ node *temp=graph->adjLists; while(temp!=NULL){ p=temp; temp=temp->next; free(p); } } free(graph->adjLists); free(graph); }
void printMatrix(int matrix[50][50], Graph* graph){ int row,col,nodes=graph->numberOfVertices; printf("\nAdjacent matrix:\n"); printf(" "); for (col = 0; col < nodes; col++) { printf("%6s ",graph->adjLists[col]->name); } printf("\n"); for (col = 0; col < nodes; col++) { printf("-------------"); } printf("\n"); for (row = 0; row < nodes; row++) { printf("%7s| ",graph->adjLists[row]->name); for (col = 0; col < nodes; col++) { printf(" %2d ",matrix[row][col]); } printf("\n"); }
}
int main(){ int Num=7; //construct a graph Graph* graph = createGraph(Num); addConnection(graph, "personA", "personB"); addConnection(graph, "personA", "personG"); addConnection(graph, "personA", "personE"); addConnection(graph, "personB", "personA"); addConnection(graph, "personB", "personE"); addConnection(graph, "personB", "personC"); addConnection(graph, "personB", "personG"); addConnection(graph, "personC", "personB"); addConnection(graph, "personC", "personD"); addConnection(graph, "personC", "personE"); addConnection(graph, "personD", "personC"); addConnection(graph, "personD", "personE"); addConnection(graph, "personD", "personF"); addConnection(graph, "personE", "personA"); addConnection(graph, "personE", "personB"); addConnection(graph, "personE", "personC"); addConnection(graph, "personE", "personD"); addConnection(graph, "personE", "personF"); addConnection(graph, "personE", "personG"); addConnection(graph, "personF", "personE"); addConnection(graph, "personF", "personG"); addConnection(graph, "personF", "personD"); addConnection(graph, "personG", "personB"); addConnection(graph, "personG", "personA"); addConnection(graph, "personG", "personE"); addConnection(graph, "personG", "personF"); //function to print the adjacency list representationof a graph printGraph(graph); /*Initialising adjacency matrix with valuesNULL*/ int N = graph->numberOfVertices, i,j; int adj_matrix[50][50]; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { adj_matrix[j] =0; } } matrixForm(graph, adj_matrix, N); printMatrix(adj_matrix, graph); graphDestroy(graph); return 0;}
personA---personB-personG-personE-NULL personB---personA-personE-personC-personG-NULL personC---personB-personD-personE-NULL personD---personC-person E-personF-NULL personE---personA-personB-personC-personD-personF-personG-NULL personF---person E-personG-personD-NULL personG---personB-personA-personE-personF-NULL Adjacent matrix: personA person personC personD personE personF personG personA 0 personB| 1 personC 0 personD 0 1 persone | personF 0 personG 1 1 0 1 0 1 нор 0 1 0 OTO 1 0 1 1 0 0 0 0 1 0 1 1 0 1 तततततत 1 1 1 0 1 1 0 0 0 1 1 0 TO 1 LLDELLO 1 1 0 0 1 1 0