Программа построения графа путем замены вершин в исходном графе на ребра

6. Текст программы

Файл библиотеки «volkov_f.cpp»

typedef struct name_r {char reb[n][3];int N;};

typedef struct vershin {char ver[n];int N;};

typedef struct table_inc {int znach[n][n]; int N;};

void include (FILE *f,table_inc *T,vershin *name)  // Функция ввода

{

int i=0,j=0,k=0;

while (((*name).ver[k]=fgetc(f))!='\n') k++;

while (i!=k)

{

while (j!=k)

{

if (fgetc(f)=='1') (*T).znach[i][j]=1; else (*T).znach[i][j]=0;

j++;

}

fgetc(f);

j=0;

i++;

}

(*name).N=(*T).N=k;

}

// Функция перевода ребер в вершины (графа G в граф G')

void rebra (name_r *Name,table_inc T,vershin *name)

{

int i=0,j=1,l=0;

while (i!=(*name).N-1)

{

while (j!=(*name).N)

{

if (T.znach[i][j]==1)

{

(*Name).reb[l][0]=(*name).ver[i];

(*Name).reb[l][1]=(*name).ver[j];

l++;

}

j++;

}

i++;

j=i+1;

}

(*Name).N=l;

}

// Функция инцидентности ребер

table_inc rebra_inc (name_r Name)

{

table_inc R;

int i=0,j=1;

while (i!=Name.N-1)

{

while (j!=Name.N)

{

if (Name.reb[i][0]==Name.reb[j][0])

{R.znach[i][j]=1;

R.znach[j][i]=1;}

else

if (Name.reb[i][1]==Name.reb[j][1])

{R.znach[i][j]=1;

R.znach[j][i]=1;}

else

if (Name.reb[i][0]==Name.reb[j][1])

{R.znach[i][j]=1;

R.znach[j][i]=1;}

else

if (Name.reb[i][1]==Name.reb[j][0])

{R.znach[i][j]=1;

R.znach[j][i]=1;}

else {R.znach[i][j]=0;

R.znach[j][i]=0;}

j++;

}

i++;

j=i+1;

}

i=0;

while (i!=Name.N)

{

R.znach[i][i]=0;

i++;

}

R.N=Name.N;

return R;

}

void print_table (table_inc T,vershin name)

{

int i=0,j=0;

printf (" ");

while (i!=name.N)

{printf (" %c",name.ver[i]);

i++;

}

i=0;

while (i!=name.N)

{

printf ("\n%c",name.ver[i]);

while (j!=name.N)

{

printf (" %d",T.znach[i][j]);

j++;

}

i++;

j=0;

}

}

void print_table_R (table_inc R,name_r Name)

{

int i=0,j=0;

printf ("\n ");

while (i!=Name.N)

{printf ("  %c%c",Name.reb[i][0],Name.reb[i][1]);

i++;

}

i=0;

while (i!=Name.N)

{

printf ("\n%c%c",Name.reb[i][0],Name.reb[i][1]);

while (j!=Name.N)

{

printf ("  %d ",R.znach[i][j]);

j++;

}

i++;

j=0;

}

}

//Функция поиска

int search_reb (name_r Name,char isk[2])

{

int i=0;

while (i!=Name.N)

{

if (Name.reb[i][0]==isk[0])

{if (Name.reb[i][1]==isk[1]) return i;}

else

if (Name.reb[i][0]==isk[1])

if (Name.reb[i][1]==isk[0]) return i;

i++;

}

return -1;

}

//Функция удаления ребра из таблицы инцидентности

name_r delete_reb (table_inc *R,name_r *Name,int k)

{

int i=k,j=0,l=0;

name_r A;

while (j!=(*R).N)

{

if ((*R).znach[i][j]==1)

{

A.reb[l][0]=(*Name).reb[j][0];

A.reb[l][1]=(*Name).reb[j][1];

l++;

}

j++;

}

A.N=l;

j=k;

while (j!=(*R).N-1)

{

(*Name).reb[j][0]=(*Name).reb[j+1][0];

(*Name).reb[j][1]=(*Name).reb[j+1][1];

j++;

}

(*Name).N--;

j=0;

while (i!=(*R).N-1)

{

while (j!=(*R).N)

{

(*R).znach[i][j]=(*R).znach[i+1][j];

j++;

}

i++;

j=0;

}

j=k; i=0;

while (i!=(*R).N-1)

{

while (j!=(*R).N-1)

{

(*R).znach[i][j]=(*R).znach[i][j+1];

j++;

}

i++;

j=k;

}

(*R).N--;

return A;

}

//

name_r otv (table_inc R,name_r Name,char isk[2])

{

name_r o,otvet;

int i,j=0,k=0;

otvet.N=0;

i=search_reb (Name,isk);

if (i<0) printf ("\aТакой вершины не существует \n");

else

{

o=delete_reb (&R,&Name,i);

while (j!=o.N)

{

i=search_reb (Name,o.reb[j]);

while (k!=R.N)

{

if (R.znach[i][k]==1)

{

if (search_reb(otvet,Name.reb[k])<0)

{

otvet.reb[otvet.N][0]=Name.reb[k][0];

otvet.reb[otvet.N][1]=Name.reb[k][1];

otvet.N++;

}

}

k++;

}

k=0;

j++;

}

}

return otvet;

}

//Функция печатающая ответ

void print_reb (name_r Name)

{

int i=0;

while (i!=Name.N)

{

printf (" %c%c",Name.reb[i][0],Name.reb[i][1]);

i++;

}

}

Текст основной программы

#include <stdio.h>

#include <conio.h>

#define n 10

#include "volkov_f.cpp"

void main ()

{

FILE *f;

table_inc T,R;

vershin name;