#include <iostream>
#include <stdio.h>
#include <conio.h>

struct vertice {
char insertar;
   struct vertice *sig;
   struct arista *aris;
};

struct arista {
struct vertice *destino;
   struct arista *sig;
};

typedef struct vertice *Nodo;
typedef struct arista *Ar;

void crear_nodo(Nodo &grafo)
{
    Nodo Noden=new struct vertice;

    cin>>Noden->insertar;
    Noden->sig=NULL;
    Noden->aris=NULL;

    if(grafo==NULL)
    {
        grafo = Noden;
        return;
    }
    else
    {
        Nodo aux=grafo;

        if(Noden->insertar==aux->insertar)
      cout<<"\nNODO EXISTENTE :(";

        while(aux->sig!=NULL)
        {
            if(Noden->insertar==aux->insertar)
            cout<<"\nNODO EXISTENTE :(";
            aux = aux->sig;
        }
        aux->sig = Noden;

        return;
    }

}

void add_arista(Nodo &aux, Nodo &aux2, Ar &nuevo)
{
    Ar i;

    if(aux->aris==NULL)
    {   aux->aris=nuevo;
        nuevo->destino=aux2;
        cout<<"\nARISTA CREADA :).";
    }
    else
    {   i=aux->aris;
      if(i->destino->insertar==aux2->insertar)
        {
        cout<<"\n\nARISTA YA EXISTENTE :(";
            return;
        }
        while(i->sig!=NULL)
        {
            if(i->destino->insertar==aux2->insertar)
            {
            cout<<"\n\nARISTA YA EXISTENTE";
               return;
            }
    i=i->sig;
        }
        nuevo->destino=aux2;
        i->sig=nuevo;
        cout<<"\nARISTA CREADA";
    }

}

void insert_arista(Nodo grafo)
{
char ini, fin;
    Ar Noden=new struct arista;
    Nodo aux, aux2;

    cout<<"\t\t\tEnlace creado con exito!\n";

    if(grafo==NULL)
     {
         cout<<"SIN ELEMENTOS QUE EVALUAR";
         return;
     }
    Noden->sig=NULL;
    cout<<"INGRESE PUNTO INICIO: ";
    cin>>ini;
    cout<<"INGRESE PUNTO FINAL: ";
    cin>>fin;
    aux=grafo;
    aux2=grafo;
    while(aux2!=NULL)
    {
        if(aux2->insertar==fin)
        {
            break;
        }

        aux2=aux2->sig;
    }
    if(aux2==NULL)
    {
        cout<<"\nEL NODO "<<fin<<" NO EXISTE\n";
      return;
    }

    while(aux!=NULL)
    {
        if(aux->insertar==ini)
        {
            add_arista(aux, aux2, Noden);
            return;
        }

        aux = aux->sig;
    }
    cout<<"\n RUTA CREADA SIN EXITO\n"<<endl;
    cout<<"\nEL NODO "<<ini<<" NO EXISTE\n";
    return;
}

void imprimirgrafo(Nodo grafo)
{
    if(grafo==NULL)
    {
      cout<<"LO SENTIMOS, NO SE CREO NINGUN GRAFO";
    return;
    }

Nodo aux;
    Ar ar;
    aux=grafo;
    cout<<"\t\t\tMOSTRANDO matriz DE ADYACENCIA \n\n";

    while(aux!=NULL)
    {   cout<<" "<<aux->insertar<<" : ";
        if(aux->aris!=NULL)
        {
            ar=aux->aris;
            while(ar!=NULL)
            {
            cout<<ar->destino->insertar;
            if(ar->sig!=NULL)
                cout<<",**** ";
                ar=ar->sig;
             }

        }
        aux=aux->sig;
        cout<<endl;
    }
}


void deleted(char var, Nodo grafo)
{
Nodo aux;
    Ar ar, ant, fijo;
    aux=grafo;

    while(aux!=NULL)
    {
        if(aux->aris!=NULL)
        {
            fijo=aux->aris;
            ar=aux->aris;
            ant=aux->aris;
            while(ar!=NULL)
            {
            if(ar->destino->insertar==var)
                {
                   if(fijo==ar)
                   {
                    aux->aris=fijo->sig;
                     delete(fijo);
                     break;
                   }
                   else
                    {
                      ant->sig=ar->sig;
                        delete(ar);
                        break;
                     }
                }
                ant=ar;
                ar=ar->sig;
             }

        }
        aux=aux->sig;
        cout<<endl;
    }
}


void aristas_null(Nodo &aux)
{
    Ar i,j;

    i=aux->aris;
    while(i->sig!=NULL)
    {
        j=i;
        i=i->sig;
        delete(j);
    }
}

void deleted_nod(Nodo &grafo)
{
char var;
    Nodo aux, ant;
    aux=grafo;
    ant=grafo;

    cout<<"\t\t\t DESHACER NODO\n\n";

    if(grafo==NULL)
    {
         cout<<"\nLO SENTIMOS, NO SE HA CREADO NINGUN GRAFO\n";
         return;
    }
    cout<<"QUE NODO DESEA ELIMINAR : ";
    cin>>var;

    deleted(var, grafo);

    while(aux!=NULL)
    {
        if(aux->insertar==var)
        {
            if(aux->aris!=NULL)
                aristas_null(aux);

            if(aux==grafo)
            {
                grafo=grafo->sig;
                delete(aux);
                cout<<"NODO ELIMINADO CON EXITO";
                return;
            }
            else
            {
                ant->sig=aux->sig;
                delete(aux);
                cout<<"NODO ELIMINADO CON EXITO";
                return;
            }
        }

        ant=aux;
        aux=aux->sig;
    }

    cout<<"\n\nEL NODO NUNCA EXISTIO \n";
    return;

}


void arista_quitar(Nodo &grafo)
{
char ini, fin;
    Nodo aux, aux2;
    Ar i, j;

    cout<<"\t\t\t DESTRUIR ENLACE \n\n";

    if(grafo==NULL)
    {
         cout<<"\nGRAFO VACIO :(\n";
         return;
    }

    cout<<"NODO DE INICIO: ";
    cin>>ini;
    cout<<"NODO A FIN: ";
    cin>>fin;

    aux=grafo;
    aux2=grafo;
    while(aux2!=NULL)
    {
        if(aux2->insertar==fin)
        {
            break;
        }
        else
        aux2=aux2->sig;
    }

    while(aux!=NULL)
    {
        if(aux->insertar==ini)
        {
            i=aux->aris;
            if(i==NULL)
            cout<<"\n\nNO EXISTIO NUNCA ENLACE \n\n";

            while(i!=NULL)
            {
                if(i->destino==aux2)
                {
                    if(i==aux->aris)
                        aux->aris=aux->aris->sig;
                    else
                        j->sig=i->sig;
                    delete(i);
                    cout<<"\n\nARISTA ELIMINADA CON EXITO\n\n";
                    return;
                }
            j=i;
            i=i->sig;
            }
        }
        aux = aux->sig;
    }
}

void mostrAr(Nodo grafo)
{
    Nodo aux;
    Ar ar;
    char var;

    cout<<"\t\tIMPRIMIR ARISTAS DE NODO \n";
    cout<<"\n\nNODO A BUSCAR: ";
    cin>>var;
    aux=grafo;
    while(aux!=NULL)
    {
        if(aux->insertar==var)
        {
            if(aux->aris==NULL)
            {   cout<<"NO EXISTEN ARISTAS";
                return;
             }
            else
            {
                cout<<aux->insertar<<" :";
                ar=aux->aris;

                while(ar!=NULL)
                {
                    cout<<ar->destino->insertar;
                    if(ar->sig!=NULL)
                    cout<<", ";
                    ar=ar->sig;
                }
                cout<<endl;
                return;
            }
        }
        else
        aux=aux->sig;
    }

    cout<<"\n\nEL NODO NUNCA EXISTIO\n\n";
}

main()
{
   int opc, lim, i;
   Nodo grafo=NULL;

do{
   clrscr();
cout<<"\t\t\t\t GRAFO NO DIRIGIDO\n\n";
cout<<"1) INGRESAR NODO\n"
    "2) INGRESAR ARISTA\n"
         "3) ELIMINAR NODO\n"
         "4) ELIMINAR ARISTA\n"
         "5) BUSCAR NODO\n"
         "6) LISTA DE ADYACENCIA\n"
         "7) SALIR\n"
         "\n\nTU OPCION ES: ";
   cin>>opc;

   switch(opc)
   {
    case 1:
         clrscr();
         cout<<"\t\t\tHAZ ELEGIDO INGRESAR NODOS\n\n";
         cout<<"NUMERO DE NODOS A INGRESAR: ";
         cin>>lim;

         for(i=0; i<lim; i++)
         {
            cout<<(i+1)<<") ";
      crear_nodo(grafo);
         }

      break;
      case 2:
      clrscr();
      insert_arista(grafo);
      break;
      case 3:
      clrscr();
      deleted_nod(grafo);
      break;
      case 4:
      clrscr();
      arista_quitar(grafo);
      break;
      case 5:
      clrscr();
      mostrAr(grafo);
         getch();
      break;
      case 6:
      clrscr();
      imprimirgrafo(grafo);
         getch();
      break;
      case 7:
      return 0;

      default:
         clrscr();
      cout<<"OPCION NO VALIDA :(";
         getch();
      }
  }while (opc!=7);
  getch();
}