Composition Between Relational Structures
A Little Bit about 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 Executions
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