|
What is Composition?
P: Composition Relation  if  then (a P c) = a ( ) c. if  then we can say P is a composition of A and B. We can solve Composition Relation in two methods. 1. Doing processes on  and structures. 2. Multiplying two matrices like  and . Complexity: 1. Method  <  <  : 1'rst method's complexity 2. Method  . The Algorithm 
C Source Code
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define mat 30
int k;
int Table_Comp(short P[][mat], short R[][mat], short S[][mat], int n)
{
int i, j, ii, jj;
for(i=0;i<n;i++)
{
ii = R[0][i];
jj = R[1][i];
j = 0;
while( (jj != S[0][j]) && (j < n) )
j++;
if ( jj == S[0][j] )
{
k++;
P[0][k] = ii;
P[1][k] = S[1][j];
}
}
return 0;
}
int Convert(short Mr[][mat],
short Ms[][mat],
short R[][mat],
short S[][mat],
int n)
{
int i;
for(i=0;i<n;i++)
Mr[ R[0][i] ][ R[1][i] ] = 1;
for(i=0;i<n;i++)
Ms[ S[0][i] ][ S[1][i] ] = 1;
return 0;
}
int Matris_Comp(short Mp[][mat], short Mr[][mat], short Ms[][mat], int n)
{
int i, j, t, z;
for(i=0;i<n;i++)
{
for(t=0;t<n;t++)
{
z = 0;
for(j=0;j<n;j++)
{
z += Mr[i][j] * Ms[j][t];
}
if(z > 0)
z = 1;
else
z = 0;
Mp[i][t] = z;
}
}
return 0;
}
int main(int argc, char* argv[])
{
int i, j, n;
short Mr[mat][mat]={0}, Ms[mat][mat]={0}, Mp[mat][mat]={0},
P[2][mat]={0}, R[2][mat]={0}, S[2][mat]={0};
printf("R and S 's size: ");scanf("%d", &n);
for(i=0;i<n;i++)
{
printf("R[0][%d]: ", i+1);scanf("%d",&R[0][i]);
printf("R[1][%d]: ", i+1);scanf("%d",&R[1][i]);
}
for(i=0;i<n;i++)
{
printf("S[0][%d]: ", i+1);scanf("%d",&S[0][i]);
printf("S[1][%d]: ", i+1);scanf("%d",&S[1][i]);
}
for(i=0;i<n;i++)
{
R[0][i]--;
R[1][i]--;
S[0][i]--;
S[1][i]--;
}
k = -1;
Table_Comp(P, R, S, n);
for(i=0;i<n;i++)
{
printf("(%d, %d),", P[0][i]+1, P[1][i]+1);
}
Convert(Mr, Ms, R, S, n);
Matris_Comp(Mp, Mr, Ms, n);
printf("\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d ", Mp[i][j] );
}
printf("\n");
}
return 0;
}
Sample Execution Result
R and S 's size: 5 R[0][1]: 1 R[1][1]: 1 R[0][2]: 1 R[1][2]: 2 R[0][3]: 1 R[1][3]: 3 R[0][4]: 2 R[1][4]: 4 R[0][5]: 3 R[1][5]: 2 S[0][1]: 1 S[1][1]: 4 S[0][2]: 1 S[1][2]: 3 S[0][3]: 2 S[1][3]: 3 S[0][4]: 3 S[1][4]: 1 S[0][5]: 4 S[1][5]: 1 Result using 1'rst method P = {(1, 4),(1, 3),(1, 1),(2, 1),(3, 3)} Result using 2'nd method 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0
|
Studies 
