#include <stdlib.h>
#include <stdio.h>

typedef struct{
       int nmax;
       int nv;
       int *v_ver;
       int **m_rel;
}Graf_mr;

typedef struct nodo
{
        struct nodo *sig;
        int d;
}*pila;
int iniGraf(Graf_mr *g, int nv);
int insVertice(Graf_mr *g, int ver);
int insRelacion(Graf_mr *g, int vf, int vd);
void printGrafo(Graf_mr *g);
int supVer(Graf_mr *g, int vf);
int buscaCamino(Graf_mr *g, int vf, int vd);
/////////
int push(pila *p, int d);
int pop(pila *p, int *d);
int creanodo(pila *p, int d);



int main()
{
    int nv, ver, vf, vd;
    char res;
    Graf_mr g;
    printf("Teclea numero de vertices\n");
    scanf("%d",nv);
    iniGraf(&g,nv);

    do{
                   printf("presiona v para insertar vertice\n");
                   printf("presiona r para insertar relacion\n");
                   printf("presiona p para imprimir grafo\n");
                   printf("presiona e para eliminar grafo\n");
                   printf("presiona b para buscar camino\n");
                   getchar();
                   res=getchar();
                   switch(res)
                   {
                              case 'v':
                                   printf("\nteclea el vertice\n");
                                   scanf("%d",ver);
                                   insVertice(&g, ver);
                                   break;
                              case 'r':
                                   printf("\nteclea el vertice fuente\n");
                                   scanf("%d",vf);
                                   printf("\nteclea el vertice destino\n");
                                   scanf("%d",vd);
                                   insRelacion(&g, vf,vd);
                                   break;
                              case 'p':
                                   printGrafo(&g);
                                   break;
                              case 'e':
                                   printf("\nteclea el vertice a eliminar\n");
                                   scanf("%d",ver);
                                   supVer(&g, ver);
                                   break;
                              case 'b':
                                   printf("\nteclea el vertice fuente\n");
                                   scanf("%d",vf);
                                   printf("\nteclea el vertice destino\n");
                                   scanf("%d",vd);
                                   buscaCamino(&g,vf,vd);
                                   break;


                   }



    }while(res!='s');


    system("pause");
    return 0;
}

int iniGraf(Graf_mr *g, int nv)
{
    int b=0, i;
    if(g->v_ver=(int*)malloc(sizeof(int)*nv))

    {
                if(g->m_rel=(int**)malloc(sizeof(int*)*nv))
                {
                     b=1;
                      for(i=0; i<nv; i++)
                      {
                               if(!(*(g->m_rel+i)=((int*)malloc(sizeof(int)*nv))))
                               {
                                     while(i>=0)
                                           free(*(g->m_rel+i));
                                     free(g->m_rel);
                                     free(g->v_ver);
                                     b=0;

                               }
                      }
                      if(b)
                      {
                             g->nmax=nv;
                             g->nv=0;
                      }
                }
                else
                   free(g->v_ver);

    }
    return(b);
}

int insVertice(Graf_mr *g, int ver)
{
    int b=0,i;
    if(g->nv<g->nmax)
    {
                    *(g->v_ver+g->nv)=ver;
                    for(i=0;i<=g->nv;i++)
                    {
                                         *(*(g->m_rel+g->nv)+i)=0;
                                         *(*(g->m_rel+i)+g->nv)=0;
                    }
                    g->nv++;
                    b=1;
    }
    return b;
}

int insRelacion(Graf_mr *g, int vf, int vd)
{
    int b=0, r, c;
    for(r=0;r<g->nv&&*(g->v_ver+r)!=vf;r++);
    if(r<g->nv)
    {
               for(c=0;c<g->nv&&*(g->v_ver+c)!=vd;c++);
               if(c<g->nv)
               {
                          *(*(g->m_rel+r)+c)=1;
                          b=1;
               }
    }
    return b;
}

void printGrafo(Graf_mr *g)
{
     int r,c;
     for(r=0;r<g->nv;r++)
     {
                         printf("\n%d = ",*(g->v_ver+r));
                         for(c=0;c<g->nv;c++)
                         {
                                             if(*(g->v_ver+c))
                                                printf("\t%d ",*(g->v_ver+c));
                         }
     }
}

/*int VerFuente(Graf_mr g, )
{
    int r,c, cont=0;
    for(r=0; i<g.nv;r++);
    if()
    {}
}*/

int supVer(Graf_mr *g, int vf)
{
    int b=0,r,c,i,j;
    for(r=0;r<g->nv&&*(g->v_ver+r)!=vf;r++);
    if(r<g->nv)
    {
        for(i=r; i<g->nv-1;i++)
             *(g->v_ver+i)=*(g->v_ver+1+i);

        for(i=r; i<g->nv-1;i++)
            for(j=r; j<g->nv-1;j++)
                *(*(g->m_rel+i)+j)=*(*(g->m_rel+1+i)+j);
                g->nv--;
                b=1;
    }
    return b;


}

int buscaCamino(Graf_mr *g, int vf, int vd)
{
    int b=0,r,i;
    pila p=NULL;
    for(r=0;r<g->nv&&*(g->v_ver+r)!=vf;r++);
    if(r<g->nv)
    {

               push(&p, r);
               while(pop(&p,&r)&&!b)
                    if(*(g->v_ver+r)==vd)
                       b=1;
                    else
                       if(*(g->v_ver+r)>0);
                       {
                           *(g->v_ver+r)=-1;
                           for(i=0;i<g->nv;i++)
                           if(*(*(g->m_rel+r)+i))
                                push(&p,i);

                       }
                    for(i=0;i<g->nv;i++)
                         *(g->v_ver+i)=abs(*(g->v_ver+i));
                    while(pop(&p,&i));
       }
       return b;
}
/////////////////////////////
int push(pila *p, int d)
{
    int b;
    pila nu;
    if(!(*p))
       if(creanodo(&nu,d))
       {
                          *p=nu;
                          b=1;
       }
       else
         b=0;
    else
      b=push(&(*p)->sig, d);

    return b;

}
int pop(pila *p, int *d)
{
    int b;
    if(!*p)
      b=0;
    else
      if((*p)->sig==NULL)
      {
                         free(*p);
                        *p=NULL;
                         b=1;
      }
      else
        b=pop(&(*p)->sig, d);

      return b;

}
int creanodo(pila *p, int d)
{
        int b=0;
        if((*p=(pila)malloc(sizeof(struct nodo))))
            {
                b=1;
                (*p)->sig=NULL;
                (*p)->d=d;
            }
        return (b);
}