3

I have to do a recursive function in pSQL to get the following query:

  • I have a table called tb_route with from_city and to_city
  • I have another column with the distance in km between different cities.

The table is builded recursively. I have to make a recursive CTE to show the route between two cities (i.e., from 'Santiago de compostela' to 'Saint Jean Pied de Port') showing the total km of the route and the cities where it goes through.

The output has to be something like this:

output

This is what I've tried:

WITH RECURSIVE cities AS (
      SELECT *
      FROM textil.tb_route
      WHERE to_city_name = 'Santigo de Compostela'
  UNION ALL
      SELECT e.from_city, e.to_city, e.route, e.km
      FROM textil.tb_route e
  INNER JOIN cities tb_route ON tb_route.from_city_name = e.from_city
)

SELECT *
FROM cities;

And I had an error like: 

ERROR:  column e.from_city does not exist
LINE 8: ...JOIN cities tb_route ON tb_route.from_city_name = e.from_cit...

Table:

CREATE TABLE textil.tb_route
(
    from_city_name            CHARACTER VARYING(120) NOT NULL ,
    to_city_name              CHARACTER VARYING(120) NOT NULL ,
    km_distance_num           NUMERIC(5,2) NOT NULL ,
    CONSTRAINT pk_route PRIMARY KEY (from_city_name, to_city_name)
);

Data:

INSERT INTO textil.tb_route VALUES
  ('Saint Jean Pied de Port','Roncesvalles',25.7),
  ('Somport','Jaca',30.5),
  ('Roncesvalles','Zubiri',21.5),
  ('Jaca','Arrés',25),
  ('Zubiri','Pamplona/Iruña',20.4),
  ('Arrés','Ruesta',28.7),
  ('Pamplona/Iruña','Puente la Reina/Gares',24),
  ('Ruesta','Sangüesa',21.8),
  ('Puente la Reina/Gares','Estella/Lizarra',22),
  ('Sangüesa','Monreal',27.25),
  ('Estella/Lizarra','Torres del Río',29),
  ('Monreal','Puente la Reina/Gares',31.1),
  ('Torres del Río','Logroño',20),
  ('Logroño','Nájera',29.6),
  ('Nájera','Santo Domingo de la Calzada',21),
  ('Santo Domingo de la Calzada','Belorado',22.7),
  ('Belorado','Agés',27.4),
  ('Agés','Burgos',23),
  ('Burgos','Hontanas',31.1),
  ('Hontanas','Boadilla del Camino',28.5),
  ('Boadilla del Camino','Carrión de los Condes',24.6),
  ('Carrión de los Condes','Terradillos de los Templarios',26.6),
  ('Terradillos de los Templarios','El Burgo Ranero',30.6),
  ('El Burgo Ranero','León',37.1),
  ('León','San Martín del Camino',25.9),
  ('San Martín del Camino','Astorga',24.2),
  ('Astorga','Foncebadón',25.9),
  ('Foncebadón','Ponferrada',27.3),
  ('Ponferrada','Villafranca del Bierzo',24.1),
  ('Villafranca del Bierzo','O Cebreiro',28.4),
  ('O Cebreiro','Triacastela',21.1),
  ('Triacastela','Sarria',18.3),
  ('Sarria','Portomarín',22.4),
  ('Portomarín','Palas de Rei',25),
  ('Palas de Rei','Arzúa',28.8),
  ('Arzúa','Pedrouzo',19.1),
  ('Pedrouzo','Santiago de Compostela',20),
  ('Bayona','Ustaritz',14.3),
  ('Ustaritz','Urdax',21.2),
  ('Urdax','Elizondo',18.8),
  ('Elizondo','Berroeta',9.7),
  ('Berroeta','Olagüe',20.4),
  ('Olagüe','Pamplona/Iruña',25),
  ('Irún','Hernani',26.6),
  ('Hernani','Tolosa',18.9),
  ('Tolosa','Zerain',33),
  ('Zerain','Salvatierra/Agurain',28),
  ('Salvatierra/Agurain','Vitoria/Gasteiz',27.4),
  ('Vitoria/Gasteiz','La Puebla de Arganzón',18.5),
  ('La Puebla de Arganzón','Haro',31),
  ('Haro','Santo Domingo de la Calzada',20),
  ('Bayona','Irún',33.8),
  ('Tolosa','Zegama',37.9),
  ('Zegama','Salvatierra/Agurain',20.1),
  ('La Puebla de Arganzón','Miranda del Ebro',22.3),
  ('Miranda del Ebro','Pancorbo',16.7),
  ('Pancorbo','Briviesca',23.4),
  ('Briviesca','Monasterio de Rodilla',19.8),
  ('Monasterio de Rodilla','Burgos',28.5);
```
Improve this question

2 Answers 2

Reset to default
1

Here I leave the solution I've get finally:

with recursive caminos(from_city_name, to_city_name, path, total_distance, terminar, ultima_ciudad) as (
    -- Consulta base
    select  to_city_name
            ,'Saint Jean Pied de Port' -- Cambiar Destino 
            ,concat(to_city_name, concat(' -> ', from_city_name)) 
            ,cast(km_distance_num as numeric(8,2))
            ,0 --No terminar
            ,from_city_name
    from    textil.tb_route 
    where   to_city_name = 'Santiago de Compostela' -- Cambiar Origen 
    union all
    -- Consulta recursiva
    select  caminos.from_city_name
            ,caminos.to_city_name
            ,concat(caminos.path, concat( ' -> ', tr.from_city_name))
            ,cast(caminos.total_distance + tr.km_distance_num as numeric(8,2))
            ,case when tr.from_city_name = caminos.to_city_name then 1 else 0 end
            ,tr.from_city_name  
    from    caminos inner join textil.tb_route tr on tr.to_city_name = caminos.ultima_ciudad and caminos.terminar != 1  
)
select from_city_name, to_city_name, path, total_distance 
from caminos 
where 1 = 1
and from_city_name = 'Santiago de Compostela' --Cambiar Origen 
and ultima_ciudad = 'Saint Jean Pied de Port' -- Cambiar Destino
;
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

I understand your question as a graph-walking problem. As described in your questions, edges are directed (meaning that you can travel from from_city_name to to_city_name, but not the other way around).

Here is an approach using a recursive CTE. The idea is to start from a given city, and then follow all possible routes, while keeping track of the overall travel path in an arry. The recursion stops either when a circle is detected, or when the target city is reached. Then, the outer query filters on the successful paths (there may be none, one or several).

with recursive cte as (
    select 
        from_city_name, 
        to_city_name, 
        km_distance_num, 
        array[from_city_name::text, to_city_name::text] path
    from tb_route
    where from_city_name = 'Saint Jean Pied de Port'
    union all
    select 
        r.from_city_name, 
        r.to_city_name, 
        c.km_distance_num + r.km_distance_num,
        c.path || r.to_city_name::text
    from tb_route r
    inner join cte c on c.to_city_name = r.from_city_name
    where 
        not r.to_city_name = any(c.path) 
        and c.from_city_name <> 'Santiago de Compostela'
)
select 
    path[1] from_city_name, 
    to_city_name, 
    km_distance_num, 
    array_to_string(path, ' > ') path
from cte
where to_city_name = 'Santiago de Compostela';

Demo on DB Fiddle:

from_city_name          | to_city_name           | km_distance_num | path                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 
:---------------------- | :--------------------- | --------------: | :------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Saint Jean Pied de Port | Santiago de Compostela |           775.3 | Saint Jean Pied de Port > Roncesvalles > Zubiri > Pamplona/Iruña > Puente la Reina/Gares > Estella/Lizarra > Torres del Río > Logroño > Nájera > Santo Domingo de la Calzada > Belorado > Agés > Burgos > Hontanas > Boadilla del Camino > Carrión de los Condes > Terradillos de los Templarios > El Burgo Ranero > León > San Martín del Camino > Astorga > Foncebadón > Ponferrada > Villafranca del Bierzo > O Cebreiro > Triacastela > Sarria > Portomarín > Palas de Rei > Arzúa > Pedrouzo > Santiago de Compostela
Improve this answer

3 Comments

Hello! I've runned the code and I have this error at pgadmin 4: ERROR: recursive query "cte" column 3 has type numeric(5,2) in non-recursive term but type numeric overall LINE 18: km_distance_num, ^ HINT: Cast the output of the non-recursive term to the correct type. SQL state: 42804 Character: 715
@Stephi: you need some additional casting... I would recommend using numeric instead of numeric(n, m), as shown in my db fiddle. Note: as the asker of the question, you are free to accept whichever answer you like (including yours) - however let me pinpoint that your query is basically mine, with just a few minor changes (and you removed the code that protects against cycles, which is not necessarily a good idea). I think you should accept my answer instead!
Ok!! Thank you!!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.