UNIT uGrafo;

INTERFACE
    USES uElem,uCola,uConjunto,uPila;

    TYPE

        TListaDestinos = ^TNodoD;

        TNodoD = RECORD
            sig:TListaDestinos;
            info:TElem;
        END;

        TGrafo = ^TNodoO;

        TNodoO = RECORD
            ady:TListaDestinos;
            sig:TGrafo;
            info:TElem;
        END;


        PROCEDURE CrearGrafoVacio(VAR grafo:TGrafo);

        PROCEDURE InsertarVertice(VAR grafo:TGrafo; e:TElem);

        PROCEDURE EliminarVertice(VAR grafo:TGrafo; e:TElem);

        PROCEDURE InsertarArco (VAR grafo:TGrafo; vO,vD:TElem);

        PROCEDURE EliminarArco(VAR grafo:TGrafo; vO,vD:TElem);

        FUNCTION EsGrafoVacio (grafo:TGrafo):boolean;

        PROCEDURE Pertenece (grafo:TGrafo; e:TElem; VAR b:boolean; VAR pos:TGrafo);

        FUNCTION PerteneceAdy (listaAdy:TListaDestinos; e:TElem):boolean;

        PROCEDURE BorrarListaAdy (VAR listaAdy:TListaDestinos);

        PROCEDURE MostrarAnchura (grafo:TGrafo);

        PROCEDURE BorrarGrafo (VAR grafo:TGrafo);


IMPLEMENTATION

        PROCEDURE CrearGrafoVacio(VAR grafo:TGrafo);
            BEGIN
                grafo := NIL;
            END;{CrearGrafoVacio}

        PROCEDURE InsertarVertice(VAR grafo:TGrafo; e:TElem);
            VAR
                buleano:boolean;
                pos,aux:TGrafo;
            BEGIN
                CrearGrafoVacio(pos);
                Pertenece(grafo,e,buleano,pos);

                IF buleano=FALSE THEN
                    BEGIN
                        new(aux);
                        Asignar(aux^.info , e);
                        aux^.sig := grafo;
                        aux^.ady := NIL;
                        grafo := aux;
                    END;{IF}

            END;{InsertarVertice}

        PROCEDURE EliminarVertice(VAR grafo:TGrafo; e:TElem);
            VAR
                aux,act,ant,pos:TGrafo;
                b:boolean;
            BEGIN
                ant := NIL;
                act := grafo;

                b := FALSE;

                pos := NIL;


                Pertenece(grafo, e, b,pos);


                WHILE act<>NIL DO
                    BEGIN
                        EliminarArco(grafo, act^.info, e);

                        IF act<>NIL THEN
                            IF Iguales(act^.info , e) THEN
                                BEGIN
                                    BorrarListaAdy(act^.ady);
                                    IF ant=NIL THEN
                                        BEGIN
                                            aux := grafo;
                                            grafo := grafo^.sig;
                                            dispose(aux);

                                            act := grafo;
                                        END{IF}
                                    ELSE
                                        BEGIN
                                            ant^.sig := act^.sig;
                                            dispose(act);

                                            act := ant^.sig;

                                        END{ELSE}
                                END {IF}

                            ELSE
                                BEGIN
                                    ant := act;
                                    act := act^.sig;
                                END;{ELSE}

                    END;{WHILE}

            END;{EliminarVertice}

        PROCEDURE InsertarArco (VAR grafo:TGrafo; vO,vD:TElem);
            VAR
                b1,b2:boolean;
                pos1,pos2:TGrafo;
                aux:TListaDestinos;
            BEGIN

                b1 := FALSE;
                b2 := FALSE;

                pos1 := NIL;
                pos2 := NIL;

                Pertenece(grafo,vO,b1,pos1);
                Pertenece(grafo,vD,b2,pos2);

                IF b1 AND b2 THEN
                    IF NOT( PerteneceAdy(pos1^.ady , vD) ) THEN
                        BEGIN
                            new(aux);
                            Asignar(aux^.info , vD);
                            aux^.sig := pos1^.ady;
                            pos1^.ady := aux;
                        END;{IF}
            END;{InsertarArco}

        PROCEDURE EliminarArco(VAR grafo:TGrafo; vO,vD:TElem);
            VAR
                b:boolean;
                pos:TGrafo;
                ant,act,aux : TListaDestinos;
            BEGIN
                pos := NIL;
                b := FALSE;

                Pertenece(grafo,vO,b,pos);

                IF b THEN
                    BEGIN
                        ant := NIL;
                        act := pos^.ady;

                        WHILE (act<>NIL) AND NOT(Iguales(act^.info , vD)) DO
                            BEGIN
                                ant := act;
                                act := act^.sig;
                            END;{WHILE}

                        IF act<>NIL THEN
                            IF ant=NIL THEN
                                BEGIN
                                    aux := pos^.ady;
                                    pos^.ady := pos^.ady^.sig;
                                    dispose(aux);

                                END{IF}
                            ELSE
                                BEGIN
                                    ant^.sig := act^.sig;
                                    dispose(act);
                                END;{ELSE}

                    END;{IF}


            END;{EliminarArco}

        FUNCTION EsGrafoVacio (grafo:TGrafo):boolean;
            BEGIN
                EsGrafoVacio := (grafo = NIL);
            END;{EsGrafoVacio}

        PROCEDURE Pertenece (grafo:TGrafo; e:TElem; VAR b:boolean; VAR pos:TGrafo);
            BEGIN
                WHILE (grafo<>NIL) AND (b=FALSE) DO
                    BEGIN
                        b := Iguales(grafo^.info , e);
                        grafo := grafo^.sig;
                    END;{WHILE}

                pos := grafo;

            END;{Pertenece}

        FUNCTION PerteneceAdy (listaAdy:TListaDestinos; e:TElem):boolean;
            VAR
                check:boolean;
            BEGIN
                check := FALSE;

                WHILE (listaAdy<>NIL) AND (check=FALSE) DO
                    BEGIN
                        check := Iguales(listaAdy^.info , e);
                        listaAdy := listaAdy^.sig;
                    END;{WHILE}

                PerteneceAdy := check;

            END;{Pertenece}

        PROCEDURE BorrarListaAdy (VAR listaAdy:TListaDestinos);
            VAR
                aux:TListaDestinos;
            BEGIN
                WHILE listaAdy<>NIL DO
                    BEGIN
                        aux := listaAdy;
                        listaAdy := listaAdy^.sig;
                        dispose(aux);
                    END;{WHILE}

            END;{BorrarListaAdy}

        PROCEDURE MostrarAnchura (grafo:TGrafo);
            VAR
                conjR,conjV,conjD:TConjunto;
                cola:TCola;
                aux,pos:TGrafo;
                e:TElem;
                aux2:TListaDestinos;
                b:boolean;
            BEGIN
                IF grafo<>NIL THEN
                    BEGIN
                        CrearConjuntoVacio(conjR);
                        CrearConjuntoVacio(conjV);
                        CrearConjuntoVacio(conjD);
                        CrearGrafoVacio(pos);

                        CrearColaVacia(cola);
                        aux := grafo;

                        WHILE aux<>NIL DO
                            BEGIN
                                Poner(conjV , aux^.info);
                                aux := aux^.sig;
                            END;{WHILE}


                        Asignar(e , grafo^.info);
                        Mostrar(e);
                        Poner(conjR , e);

                        aux2 := grafo^.ady;

                        WHILE aux2<>NIL DO
                            BEGIN
                                InsertarCola(cola , aux2^.info);
                                aux2 := aux2^.sig;
                            END;{WHILE}

                        WHILE NOT(EsColaVacia(cola)) DO
                            BEGIN
                                Cabecera(cola , e);
                                Mostrar(e);
                                Poner(conjR , e);

                                pos := NIL;

                                Pertenece(grafo,e,b,pos);

                                WHILE (pos^.ady<>NIL) DO
                                    BEGIN
                                        IF NOT(uConjunto.Pertenece(conjR , pos^.ady^.info)) THEN
                                            InsertarCola(cola , pos^.ady^.info);
                                        pos^.ady := pos^.ady^.sig;

                                    END;{WHILE}

                                uCola.Eliminar(cola);

                            END;{WHILE}

                        Diferencia(conjV , conjR , conjD);

                        WHILE NOT(EsConjuntoVacio(conjD)) DO
                            BEGIN
                                Asignar(e , conjD^.info);

                                Mostrar(e);

                                Poner(conjR , e);

                                pos := NIL;

                                b := FALSE;

                                Pertenece(grafo,e,b,pos);

                                WHILE pos^.ady<>NIL DO
                                    BEGIN
                                        IF NOT(uConjunto.Pertenece(conjR , pos^.ady^.info)) THEN
                                            InsertarCola(cola , pos^.ady^.info);

                                        pos^.ady := pos^.ady^.sig;
                                    END;{WHILE}

                                WHILE NOT(EsColaVacia(cola)) DO
                                    BEGIN
                                        Cabecera(cola , e);
                                        Mostrar(e);
                                        Poner(conjR,e);

                                        pos := NIL;

                                        b := FALSE;

                                        Pertenece(grafo,e,b,pos);

                                        WHILE pos^.ady<>NIL DO
                                            BEGIN
                                                IF NOT(uConjunto.Pertenece(conjR,pos^.ady^.info)) THEN
                                                    InsertarCola(cola , pos^.ady^.info);
                                                pos^.ady := pos^.ady^.sig;

                                            END;{WHILE}

                                        uCola.Eliminar(cola);


                                    END;{WHILE}

                                EliminarConjunto(conjD);
                                Diferencia(conjV, conjR , conjD);
                            END;{WHILE}


                    END;{IF}

            END;{MostrarAnchura}


        PROCEDURE BorrarGrafo (VAR grafo:TGrafo);
            VAR
                aux:TGrafo;

            BEGIN
                WHILE (grafo<>NIL) DO
                    BEGIN
                        aux := grafo;
                        grafo := grafo^.sig;
                        dispose(aux);
                    END;

            END;




END.