grafos enprolog

Programación Lógica

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
PROLOGy 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érticesy 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 listasdiferentes
(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 degrafos 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 (definidoabajo).

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 estecaso, la representación de grafos no dirigidos contiene cada uno de los arcos dos
veces.

Procedimiento para acceder a los arcos en la representación A.
arco(g(Es,Vs),V1,V2,Valor):miembro(e(V1,V2,Valor),Vs).

Docente: Ing. Arturo Díaz Pulido

Programación Lógica

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).

Procedimiento arco para la representación B.
arco(Grafo,V1,V2,Valor) :miembro(V1-NB,Grafo),
miembro(V2-Valor,NB).

Ahora, es posible definirel 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...