## Assignment 6 : Solution

### The program

#include <stdio.h>

#define GRAPH_SIZE 20

typedef struct {
int noOfNodes;
char *label;
int **data;

struct _node {
char label;
struct _node *next;
};
typedef struct _node node;

{
int i, j;

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);
}

{
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 )
{
int i, j;

if (n > 0) {
for (i=0; i<n; ++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;
}
}
}

void printLL ( node *head , int n )
{
int i, j;
node *curr;

for (i=0; i<n; ++i) {
printf("Label : %c. Links to :", curr->label);
while (curr->next != NULL) {
curr = curr->next;
printf(" %c ", curr->label);
}
printf("\n");
}
}

{
int i, j, n;

n = M.noOfNodes;
if (n > 0) {
for (i=0; i<n; ++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;
}
}
}

{
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) {
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 ()
{

srand((unsigned int)time(NULL));

printf("-----------------------------------------------------\n");

printf("-----------------------------------------------------\n");
}

### Output

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
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
-----------------------------------------------------
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
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
-----------------------------------------------------

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
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
-----------------------------------------------------
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
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
-----------------------------------------------------