Assignment 6 : Solution
The program
#include <stdio.h>
#define GRAPH_SIZE 20
typedef struct {
int noOfNodes;
char *label;
int **data;
} adjMat;
struct _node {
char label;
struct _node *next;
};
typedef struct _node node;
adjMat newAdjMat ( int n )
{
int i, j;
adjMat M;
if (n <= 0) {
M.noOfNodes = 0;
M.label = NULL;
M.data = NULL;
} else {
M.noOfNodes = n;
M.label = (char *)malloc(n*sizeof(char));
M.data = (int **)malloc(n*sizeof(int *));
for (i=0; i<n; ++i) {
M.label[i] = i + 'A';
M.data[i] = (int *)malloc(n*sizeof(int));
M.data[i][i] = 0;
for (j=0; j<n; ++j) if (j!=i) M.data[i][j] = rand() & 1;
}
}
return(M);
}
void printAdjMat ( adjMat M )
{
int i, j;
printf(" ");
for (i=0; i<M.noOfNodes; ++i) printf(" %c ",M.label[i]);
printf("\n");
for (i=0; i<M.noOfNodes; ++i) {
printf(" %c ",M.label[i]);
for (j=0; j<M.noOfNodes; ++j) printf("%2d ",M.data[i][j]);
printf("\n");
}
}
node *newLL ( int n )
{
node *head = NULL, *curr;
int i, j;
if (n > 0) {
head = (node *)malloc(n*sizeof(node));
for (i=0; i<n; ++i) {
curr = head + i;
curr->label = i + 'a';
for (j=0; j<n; ++j) if ((i!=j)&&(rand()&1)) {
curr->next = (node *)malloc(sizeof(node));
curr = curr->next;
curr->label = j + 'a';
}
curr->next = NULL;
}
}
return(head);
}
void printLL ( node *head , int n )
{
int i, j;
node *curr;
for (i=0; i<n; ++i) {
curr = head + i;
printf("Label : %c. Links to :", curr->label);
while (curr->next != NULL) {
curr = curr->next;
printf(" %c ", curr->label);
}
printf("\n");
}
}
node *adjMatToLL ( adjMat M )
{
node *head = NULL, *curr;
int i, j, n;
n = M.noOfNodes;
if (n > 0) {
head = (node *)malloc(n*sizeof(node));
for (i=0; i<n; ++i) {
curr = head + i;
curr->label = M.label[i];
for (j=0; j<n; ++j) if (M.data[i][j]) {
curr->next = (node *)malloc(sizeof(node));
curr = curr->next;
curr->label = M.label[j];
}
curr->next = NULL;
}
}
return(head);
}
adjMat LLToAdjMat ( node *head , int n )
{
adjMat M;
int i, j, done;
node *curr;
if (n > 0) {
M.noOfNodes = n;
M.label = (char *)malloc(n*sizeof(char));
M.data = (int **)malloc(n*sizeof(int *));
for (i=0; i<n; ++i) M.label[i] = head[i].label;
for (i=0; i<n; ++i) {
curr = head + i;
M.data[i] = (int *)calloc(n,sizeof(int));
while (curr->next != NULL) {
curr = curr->next;
j = done = 0;
while ((j<n)&&(!done)) {
if (curr->label == M.label[j]) {
M.data[i][j] = 1;
done = 1;
} else ++j;
}
if (!done) fprintf(stderr,"Unknown label %c...\n",curr->label);
}
}
} else {
M.noOfNodes = 0;
M.label = NULL;
M.data = NULL;
}
return(M);
}
int main ()
{
adjMat M;
node *head;
srand((unsigned int)time(NULL));
M = newAdjMat(GRAPH_SIZE);
printf("Generating random adjacency matrix :\n");
printAdjMat(M);
head = adjMatToLL(M);
printf("The corresponding linked list :\n");
printLL(head,GRAPH_SIZE);
printf("-----------------------------------------------------\n");
head = newLL(GRAPH_SIZE);
printf("Generating random linked list :\n");
printLL(head,GRAPH_SIZE);
M = LLToAdjMat(head,GRAPH_SIZE);
printf("The corresponding adjacency matrix :\n");
printAdjMat(M);
printf("-----------------------------------------------------\n");
}
Output
Generating random adjacency matrix :
A B C D E F G H I J K L M N O P Q R S T
A 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 1 0 1 0 1
B 0 0 0 1 0 1 1 1 0 1 0 0 0 0 0 0 1 1 0 0
C 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1
D 1 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1 0 1 0
E 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 0
F 1 0 1 1 1 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0
G 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0
H 1 1 0 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0
I 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
J 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 1 1 0 0
K 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0
L 1 1 0 0 1 0 0 1 1 1 1 0 1 0 1 0 1 1 0 1
M 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 0 1 1 0 1
N 1 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 0 1 0 0
O 1 0 1 1 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0
P 0 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0
Q 0 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0
R 1 1 0 1 0 0 1 1 1 1 0 0 1 0 1 1 0 0 1 1
S 0 1 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 0
T 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 0 1 1 0
The corresponding linked list :
Label : A. Links to : H I J M O P R T
Label : B. Links to : D F G H J Q R
Label : C. Links to : B G H I J R S T
Label : D. Links to : A B C E F J K M N Q S
Label : E. Links to : F I K M O P R S
Label : F. Links to : A C D E H I J M O P S
Label : G. Links to : A B C D F H I J M N
Label : H. Links to : A B G I K O P Q
Label : I. Links to : A E F T
Label : J. Links to : H I L N O Q R
Label : K. Links to : A D G M P S
Label : L. Links to : A B E H I J K M O Q R T
Label : M. Links to : A B C D F G I J K Q R T
Label : N. Links to : A E H I J M O P R
Label : O. Links to : A C D G I J K N
Label : P. Links to : B F G H I L O Q S
Label : Q. Links to : C D F J M N P R S
Label : R. Links to : A B D G H I J M O P S T
Label : S. Links to : B E F J K O P Q R
Label : T. Links to : B C D E F G K L P R S
-----------------------------------------------------
Generating random linked list :
Label : a. Links to : e g i k l m n r s
Label : b. Links to : a c e f h i j k n p q r t
Label : c. Links to : e f g h l o q
Label : d. Links to : a e g i k l m n p q r s
Label : e. Links to : a b c d f g i l n o
Label : f. Links to : a c d g h i o p q t
Label : g. Links to : a c d e i l m q s
Label : h. Links to : a b g i j n p r s t
Label : i. Links to : a c e f h l p s t
Label : j. Links to : b c e f h i n q r s
Label : k. Links to : a h j l n p q r t
Label : l. Links to : c d g j s
Label : m. Links to : b c d e g h i k l n o s t
Label : n. Links to : b e h j l m r s t
Label : o. Links to : c e g j k r s t
Label : p. Links to : b d f g h i m o q
Label : q. Links to : d g h l n o p
Label : r. Links to : a b c d e g h i j k l m n o s t
Label : s. Links to : a c d e h i k m n o r
Label : t. Links to : a c e f h i l m
The corresponding adjacency matrix :
a b c d e f g h i j k l m n o p q r s t
a 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 0 1 1 0
b 1 0 1 0 1 1 0 1 1 1 1 0 0 1 0 1 1 1 0 1
c 0 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0 1 0 0 0
d 1 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 0
e 1 1 1 1 0 1 1 0 1 0 0 1 0 1 1 0 0 0 0 0
f 1 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1
g 1 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0
h 1 1 0 0 0 0 1 0 1 1 0 0 0 1 0 1 0 1 1 1
i 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1
j 0 1 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 1 1 0
k 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1
l 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0
m 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 0 0 0 1 1
n 0 1 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 1 1
o 0 0 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 1
p 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 0 0 0
q 0 0 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 0 0 0
r 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1
s 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0
t 1 0 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0
-----------------------------------------------------
Generating random adjacency matrix :
A B C D E F G H I J K L M N O P Q R S T
A 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0 0 1 1 1
B 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 1
C 0 0 0 0 0 1 0 1 0 0 1 1 1 1 1 0 0 1 1 0
D 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0
E 0 1 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 1 1
F 0 1 0 0 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1
G 1 1 1 1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 1
H 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 1 1 1 0 0
I 1 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0
J 0 0 1 0 1 1 0 0 0 0 1 1 1 0 1 1 0 1 1 0
K 0 1 0 1 1 1 1 0 0 1 0 0 0 1 0 1 1 1 0 1
L 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 1 0 1
M 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0
N 1 0 1 1 0 1 1 1 1 0 0 1 1 0 1 1 0 0 1 1
O 1 0 1 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 0
P 1 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0
Q 1 1 0 0 0 0 1 1 1 0 1 1 1 1 1 0 0 1 0 0
R 1 1 1 0 1 1 1 0 0 1 0 0 0 1 1 0 1 0 1 1
S 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0 0
T 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0
The corresponding linked list :
Label : A. Links to : C D E F G I M O R S T
Label : B. Links to : F G I J P Q R T
Label : C. Links to : F H K L M N O R S
Label : D. Links to : B F K M P S
Label : E. Links to : B C D F H I O S T
Label : F. Links to : B H J K L M N O T
Label : G. Links to : A B C D E F H K L M P T
Label : H. Links to : B F G K M O P Q R
Label : I. Links to : A E H L N Q
Label : J. Links to : C E F K L M O P R S
Label : K. Links to : B D E F G J N P Q R T
Label : L. Links to : B D H J N O P R T
Label : M. Links to : A B D E F G H I K P Q S
Label : N. Links to : A C D F G H I L M O P S T
Label : O. Links to : A C D G H I K L M N P Q R
Label : P. Links to : A B D F I K N O Q R S
Label : Q. Links to : A B G H I K L M N O R
Label : R. Links to : A B C E F G J N O Q S T
Label : S. Links to : A C E F G I J N O P
Label : T. Links to : C F G H I J Q R
-----------------------------------------------------
Generating random linked list :
Label : a. Links to : b d e g i l m n o q t
Label : b. Links to : a c l n o p q s t
Label : c. Links to : a b e g i l m p s
Label : d. Links to : e h j k l q r s
Label : e. Links to : d f h i m p r s t
Label : f. Links to : a e i k l n o s
Label : g. Links to : a b k l m p r t
Label : h. Links to : d k l o r s t
Label : i. Links to : a b d e f g j p s
Label : j. Links to : a b c g k l m o q s
Label : k. Links to : d e f g i l m n p q s t
Label : l. Links to : a b e g h j p q r
Label : m. Links to : a b f g h i j q r
Label : n. Links to : e i l m o r s t
Label : o. Links to : a d f g k n t
Label : p. Links to : b c e g h j l n q r s t
Label : q. Links to : b c d e j l m r s t
Label : r. Links to : b e g h j l m n
Label : s. Links to : b c d f g h i n o r
Label : t. Links to : a b c d h j k m q r s
The corresponding adjacency matrix :
a b c d e f g h i j k l m n o p q r s t
a 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 0 1 0 0 1
b 1 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1
c 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0
d 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0
e 0 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 1
f 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 0 0 1 0
g 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1
h 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1
i 1 1 0 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 1 0
j 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0
k 0 0 0 1 1 1 1 0 1 0 0 1 1 1 0 1 1 0 1 1
l 1 1 0 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 0 0
m 1 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0
n 0 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 0 1 1 1
o 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 1
p 0 1 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 1
q 0 1 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 1 1 1
r 0 1 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 0 0 0
s 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 0 0 1 0 0
t 1 1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0
-----------------------------------------------------