02-Logic-Programming/02-grafos.pl at main · USACH-ParadigmasProgramacion-GM/02-Logic-Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
% Un grafo de nodos lo podemos representar de la siguiente forma
% a se conecta con b
%conecta(a, b).
% a se conecta con c
%conecta(a, c).
%conecta(b, c).
%conecta(c, f).
%conecta(d, e).

% Bi direccional

%edge(a, b).
%edge(a, c).
%edge(b, c).
%edge(c, f).
%edge(d, e).
%connected(A, B) :- edge(A, B); edge(B, A).

%
%
% Grafo con pesos

% Tipo de problemas: GRAFOS
% Los grafos tambien son llamados DAG. Grafico dirigido
% Prolog graph
% Prolog DAG

% Grafo unidireccional.
%  a -1- b -2- e
%   \         /
%   3        3
%    \       /
%     c -2- d -2- f
%            \
%            3
%             \
%              g
%

% nodo(a,b,1).
% nodo(Inicio, Destino, Costo).
% conecta(Inicio, Destino, Costo).

% Pregunta a: Representar el grafo con hechos.
conecta(a, b, 1).
conecta(b, e, 2).
conecta(a, c, 3).
conecta(c, d, 2).
conecta(e, d, 3).
conecta(d, f, 2).
conecta(d, g, 3).

% Consulta: ¿Hay camino directo entre 2 nodos/puntos/ciudades/etc?
existeCaminoDirecto(Inicio, Destino) :-
	conecta(Inicio, Destino, _).

% existeCaminoDirecto(a,b). true
% existeCaminoDirecto(a,c). true
% existeCaminoDirecto(a,d). false
% existeCaminoDirecto(b,d). false

% Consulta: ¿Existe un camino entre un punto/nodo ORIGEN y un punto/nodo DESTINO?
% ExisteUnCamino?
% existeUnCamino(a, d, Camino).

existeUnCamino(Inicio, Destino) :-
	conecta(Inicio, Destino, _).

existeUnCamino(Inicio, Destino) :-
	conecta(Inicio, Intermedio, _),
	existeUnCamino(Inicio, Intermedio),
    existeUnCamino(Intermedio, Destino).

% Consulta: ¿Cual es el costo de ir desde punto/nodo ORIGEN hacia un punto/nodo DESTINO?

%costoTotalDeOrigenADestino(a, d, CostoTotal).

%costoTotalDeOrigenADestino(Origen, Destino, CostoTotal).
costoTotalDeOrigenADestino(Origen, Origen, 0) :- !.
costoTotalDeOrigenADestino(Origen, Destino, CostoTotal):-
	conecta(Origen, Intermedio, Costo1),
	costoTotalDeOrigenADestino(Intermedio, Destino, Costo2),
	CostoTotal is Costo1 + Costo2.


% Obtener todos los caminos entre punto inicio y punto final, junto con el costo total de este
% encontrarUnCamino entre un Punto Inicio y Punto final, sumando los costos
%encontrarUnCamino(Inicio, Destino, CostoTotal, CaminoEncontrado, []).
%https://www.swi-prolog.org/pldoc/man?predicate=%5C%2B/1

% Predicado
%encontrarUnCamino(Inicio, Destino, CostoTotal, CaminoEncontrado, Vistos).

% Ejemplo
%encontrarUnCamino(a, d, CostoTotal, CaminoEncontrado, []).

encontrarUnCamino(Inicio, Destino, CostoTotal, [Inicio,Destino], _) :-
    conecta(Inicio, Destino, CostoTotal).

encontrarUnCamino(Inicio, Destino, CostoTotal, [Inicio|SiguientesPuntos], Vistos) :-
	\+ member(Inicio, Vistos),
	conecta(Inicio, Opcion, Costo1),
	encontrarUnCamino(Opcion, Destino, Costo2, SiguientesPuntos, [Inicio|Vistos]),
	CostoTotal is Costo1 + Costo2.