UNIVERSIDAD DE LOS ANDES
COORDINACION GENERAL DE ESTUDIOS INTERACTIVOS A DISTANCIA
MERIDA - VENEZUELA
Curso de Lógica y Matemática
Postgrado en Modelado y Simulación de Sistemas
MANUAL de PROLOG - BRATKO
GRAFOS EN PROLOG
Un Grafo es otra estructura de datos que es ampliamente usada en los algoritmos actuales. En esta clase describiremos una representación de grafos en PROLOG y desarrollaremos algunos programas para operaciones de grafo típicas (coloreado, búsqueda).
REPRESENTACIÓN
Un grafo es usualmente definido como un par (V,E), donde V es un conjunto de vértices y E es un conjunto de arcos o aristas (edges). Hay muchas representaciones posibles de grafos en PROLOG, mostraremos dos de ellas.
Representación A mantiene los vértices y arcos en dos listas diferentes (conjuntos):
g([Vertice, ...],[e(Vertice1,Vertice2,Valor), ...])
Notar, que ésta representación es apropiada para grafos dirigidos también como para grafos no dirigidos. En caso de grafos no dirigidos, uno puede agregar cada una de los arcos no dirigidos e(V1,V2,H) como dos arcos dirigidos e(V1,V2,H), e(V2,V1,H) o, mejor, es posible ajustar el acceso al procedimiento arco (definido abajo).
Representación B está basada en la idea de vecindad (adyacencia) y el grafo es representado como una lista de vértices y sus vecinos.
[Vertice-[Vertice2-Valor, ...], ...]
En este caso, la representación de grafos no dirigidos contiene cada uno de los arcos dos veces.
Aquí está el procedimiento para acceder a los arcos en la representación A.
arco(g(Es,Vs),V1,V2,Valor) :-
miembro(e(V1,V2,Valor),Vs).
Si el grafo es no dirigido, el procedimiento arco puede ser ajustado de la siguiente forma:
arco(g(Es,Vs),V1,V2,Valor) :-
miembro(e(V1,V2,Valor),Vs) ; miembro(e(V2,V1,Valor),Vs).
Aquí está el procedimiento arco para la representación B.
arco(Grafo,V1,V2,Valor) :-
miembro(V1-NB,Grafo),
miembro(V2-Valor,NB).
Ahora, es posible definir el procedimiento para encontrar la vecindad de un vértice usando el procedimiento arco.
vecindad(Grafo,V,NB) :-
setof(V1-E,arco(Grafo,V,V1,E),NB).
En caso de la representación B es mejor (más eficiente) definir la vecindad directamente.
vecindad(Grafo,V,NB) :- miembro(V1-NB,Grafo).
Notar, que algunos grafos no usan valores en los arcos mientras otros asignan valores también a los vértices. En esos casos, los procedimientos de arriba tienen que ser reescritos por consiguiente.
COLOREADO
La meta del coloreado de grafo es agregar un color (de la paleta limitada de colores) a cada uno de los vértices en tal forma que los vértices adyacentes (a través de los arcos) tengan asignado diferentes colores. Aún si el coloreado de grafo parece ser un problema sólo-teórico, los algoritmos para coloreado de grafo son ampliamente usados en aplicaciones prácticas (satisfacción de restricción).
En ésta clase presentaremos tres algoritmos para coloreado de grafo. Comenzaremos con el algoritmo ingenuo (naive algoritm) que implementa un método de generar y probar en una forma basta. Entonces mejoramos el algoritmo enlazando las fases de generar y probar en un procedimiento. Finalmente, implementamos un método más sofisticado llamado chequeo hacia delante (forward checking).
El siguiente programa usa el método generar y probar para colorear los vértices de un grafo. Primero, el color es asignado a cada uno de los vértices y entonces el programa prueba la validez del coloreado.
% coloreado1(+Grafo, +Colores, -Coloreado)
coloreado1(g(Vs,Es),Colores,Coloreado) :-
gener(Vs,Colores,Coloreado),
probar(Es,Coloreado).
% gener(+Vertices,+Colores,-Coloreado)
gener([],_,[]).
gener([V|Vs],Colores,[V-C|T]) :-
miembro(C,Colores), % generador de colores no determinista
gener(Vs,Colores,T).
% probar(+Arcos,+Coloreado)
probar([],_).
probar([e(V1,V2)|Es],Coloreado) :-
miembro(V1-C1,Coloreado), % encuentra el color del Vértice V1
miembro(V2-C2,Coloreado), % encuentra el color del Vértice V2
C1\=C2, % prueba la diferencia de colores
probar(Es,Coloreado).
El programa de arriba no es muy eficiente porque genera muchos coloreados erróneos los cuales son rechazados en la fase de prueba. Además, el generador omite los vértices en conflicto y genera otros coloreados independientemente del conflicto.
Está claro que podemos probar la validez del coloreado durante la generación de colores. El siguiente programa enlaza la generación y la prueba en un procedimiento. Notar, que usamos acumulador para salvar el coloreado parcial.
% coloreado2(+Grafo,+Colores,-Coloreado)
coloreado2(g(Vs,Es),Colores,Coloreado) :-
gat(Vs,Es,Colores,[],Coloreado). % generar y probar
% gat(Vertices,Arcos,Colores,ColoredVertices,FinalColoreado)
gat([],_,_,Coloreado,Coloreado).
gat([V|Vs],Es,Cs,Acc,Coloreado) :-
miembro(C,Cs), % generar el color para el vértice V
probar2(Es,V,C,Acc), % probar la validez del coloreado actual
gat(Vs,Es,Cs,[V-C|Acc],Coloreado).
% probar2(+Arcos,+Vertice,+Color,+ActColoreado)
probar2([],_,_,_).
probar2([e(V1,V2)|Es],V,C,CColoreado) :-
(V=V1 -> (miembro(V2-C2,CColoreado) -> C\=C2 ; true)
;(V=V2 -> (miembro(V1-C1,CColoreado) -> C\=C1 ; true)
;true)),
probar2(Es,V,C,CColoreado).
El programa de arriba usa backtracking para encontrar otro coloreado válido, pero no es capaz de detectar un conflicto antes de que el conflicto realmente ocurra, es decir, después de asignar el color al segundo vértice del arco en conflicto.
Es posible mejorar la conducta del algoritmo por chequeo hacia delante (forward checking) de conflictos. Primero, asignamos el conjunto de todos los colores posibles a cada uno de los vértices (prep). Entonces, escogemos un vértice y su color (del conjunto de posibles colores asignados a éste vértice) y removemos éste color de todos los vértices adyacentes (fc), es decir, removemos (alguno) de los conflictos futuros. Por lo tanto, conocemos que el color asignado no está en conflicto con los vértices ya coloreados.
Notar, que el chequeo hacia adelante agrega alguna sobrecarga adicional al algoritmo, es posible que el backtracking clásico podría ser más eficiente en algunos casos. También, la eficiencia del algoritmo con chequeo hacia adelante depende de la estrategia de escoger las variables y colores para la asignación.
% coloreado3(+Grafo,+Colores,-Coloreado)
coloreado3(g(Vs,Es),Colores,Coloreado) :-
prep(Vs,Colores,ColoredVs),
gtb(ColoredVs,Es,[],Coloreado).
% prep(+Vertices,+Colores,+SuperColoreado)
prep([],_,[]).
prep([V|Vs],Colores,[V-Colores|CVs]) :-
prep(Vs,Colores,CVs).
% gtb(+SuperColoreado,+Arcos,+PartialColoreado,-Coloreado)
gtb([],_,Coloreado,Coloreado).
gtb([V-Cs|Vs],Es,Acc,Coloreado) :-
miembro(C,Cs), % selecciona solamente un color
fc(Es,V,C,Vs,ConstrainedVs), % chequeo hacia adelante
gtb(ConstrainedVs,Es,[V-C|Acc],Coloreado).
% fc(+Arcos,+Vertice,+VerticeColor,+InputSuperColoreado,-OutputSuperColoreado)
fc([],_,_,Vs,Vs).
fc([e(V1,V2)|Es],V,C,Vs,ConstrVs) :-
(V=V1 -> constr(Vs,V2,C,NuevoVs)
;(V=V2 -> constr(Vs,V1,C,NuevoVs)
;NuevoVs=Vs)),
fc(Es,V,C,NuevoVs,ConstrVs).
% constr(+InputSuperColoreado,+Vertice,-VerticeForbiddenColor,+OutputSuperColoreado)
constr([V-Cs|Vs],V,C,[V-NuevoCs|Vs]) :-
borrar(Cs,C,NuevoCs),NuevoCs\=[].
constr([V1-Cs|Vs],V,C,[V1-Cs|NuevoVs]) :-
V\=V1,
constr(Vs,V,C,NuevoVs).
constr([],_,_,[]).
borrar([],_,[]).
borrar([X|T],X,T).
borrar([Y|T],X,[Y|NuevoT]) :-
X\=Y,
borrar(T,X,NuevoT).
Noten que borrar no falla si el elemento no está presente en la lista.
BÚSQUEDA
Otro grupo de algoritmos con relación a grafos son los de búsqueda (sobre el grafo). En ésta clase presentaremos dos algoritmos: búsqueda simple que encuentra el camino entre dos vértices y el algoritmo de Dijkstra el cual encuentra el camino de distancia mínima desde un vértice a todos los vértices.
El siguiente programa encuentra un camino desde vértice a otro vértice. El mismo programa puede ser usado para encontrar un camino en grafos dirigidos y no dirigidos dependiendo de la definición del procedimiento arco. Notar, que usamos acumulador para que contenga parte del camino y prevenir ciclos.
% camino(+Grafo,+Start,+Stop,-Camino)
camino(Grafo,Start,Stop,Camino) :-
camino1(Grafo,Start,Stop,[Start],Camino).
camino1(Grafo,Stop,Stop,Camino,Camino).
camino1(Grafo,Start,Stop,ActCamino,Camino) :-
Start\=Stop,
arco(Grafo,Start,Proximo),
non_miembro(Proximo,ActCamino),
camino1(Grafo,Proximo,Stop,[Proximo|ActCamino],Camino).
non_miembro(_,[]).
non_miembro(X,[Y|T]) :-
X\=Y,
non_miembro(X,T).
El algoritmo de Dijkstra es bien conocido por encontrar el camino mínimo en grafos con arcos (no negativos). Aquí está su implementación en PROLOG el cual encuentra la distancia mínima a todos los vértices desde un vértice dado.
% min_dist(+Grafo,+Start,-MinDist)
min_dist(Grafo,Start,MinDist) :-
dijkstra(Grafo,[],[Start-0],MinDist).
% dijkstra(+Grafo,+CerradoVertices,+AbiertoVertices,-Distancias)
dijkstra(_,MinDist,[],MinDist).
dijkstra(Grafo,Cerrado,Abierto,MinDist) :-
escoger_v(Abierto,V-D,RestAbierto),
vecindad(Grafo,V,NB), % NB es una lista de vértices adyacentes + distancia a V
diff(NB,Cerrado,NuevoNB),
merge(NuevoNB,RestAbierto,D,NuevoAbierto),
dijkstra(Grafo,[V-D|Cerrado],NuevoAbierto,MinDist).
% escoger_v(+AbiertoVertices,-VerticeToExpand,-RestAbiertoVertices)
escoger_v([H|T],MinV,Rest) :-
escoger_minv(T,H,MinV,Rest).
escoger_minv([],MinV,MinV,[]).
escoger_minv([H|T],M,MinV,[H2|Rest]) :-
H=V1-D1, M=V-D,
(D1<D -> ProximoM=H,H2=M
; ProximoM=M,H2=H),
escoger_minv(T,ProximoM,MinV,Rest).
% diff(+ListaOfVertices,+Cerrado,-ListaOfNonCerradoVertices)
diff([],_,[]).
diff([H|T],Cerrado,L) :-
H=V-D,
(miembro(V-_,Cerrado) -> L=NuevoT ; L=[H|NuevoT]),
diff(T,Cerrado,NuevoT).
% mezclar(+ListaOfVertices,+OldAbiertoVertices,-AllAbiertoVertices)
mezclar([],L,_,L).
mezclar([V1-D1|T],Abierto,D,NuevoAbierto) :-
(remover(Abierto,V1-D2,RestAbierto)
-> VD is min(D2,D+D1)
; RestAbierto=Abierto,VD is D+D1),
NuevoAbierto=[V1-VD|SubAbierto],
mezclar(T,RestAbierto,D,SubAbierto).
remover([H|T],H,T).
remover([H|T],X,[H|NT]) :-
H\=X,
remover(T,X,NT).
Compara el procedimiento remover con el procedimiento borrar (parte de coloreado). ¿Ves la diferencia?
Extiende el programa de arriba en una forma que también encuentre el camino mínimo (no sólo la distancia mínima) a todos los vértices.
Los algoritmos de grafo pueden ser usados para resolver muchos tipos de problemas.