Flight Search

flights.pl

:- initialization(main).
main :-
  routes(vie, nrt, R),
  write(R), halt.

% data

flight(vie, nrt, 1000).
flight(vie, fra, 40).
flight(vie, cdg, 50).
flight(cdg, nrt, 800).
flight(fra, nrt, 800).

% algorithm

route(Dep, Arr, Route, Cost) :-
  route(Dep, Arr, Route, 0, Cost).
route(Dep, Arr, [Dep, Arr], AccCost, FinalCost) :-
  flight(Dep, Arr, Cost),
  FinalCost is AccCost + Cost.
route(Dep, Arr, [Dep|C], AccCost, FinalCost) :-
  flight(Dep, Z, Cost),
  NewCost is AccCost + Cost,
  route(Z, Arr, C, NewCost, FinalCost).

routes(Dep, Arr, Routes) :-
  setof(C-R, route(Dep, Arr, R, C), Routes).

flights.sql

with recursive route(dep, arr, acc_route, acc_price) as (
  select -- seed query
    dep,
    arr,
    dep || '-' || arr as acc,
    price
  from flights
  where dep = 'vie'

  union all

  select -- recursive query
    R.dep,
    F.arr,
    acc_route || '-' || F.arr as acc_route,
    acc_price + F.price
  from route R, flights F
  where R.arr = F.dep
)
select acc_route, acc_price -- final projection
from route
where arr = 'nrt'
order by acc_price

run.sh

#!/bin/bash

docker run --rm -i -t -v $(pwd):/source nacyot/prolog-swi:apt swipl -s  /source/flights.pl