Publi

Cómo encontrar la ruta de un elemento dentro de una jerarquía en PHP

Hace poco, hablábamos de cómo generar un array que contuviera una jerarquía de elementos, vimos cómo podíamos generarlo de forma muy rápida una vez tenemos todos los elementos en una lista en la que previamente indicamos el padre de cada uno de ellos.

El problema hoy es algo distinto, tenemos esa jerarquía o árbol, y queremos encontrar la ruta hacia arriba, es decir, todos los elementos por los que tenemos que pasar para llegar hasta un elemento dado. Puede ser útil cuando estén visitando nuestra página y accedan a algún elemento interior tras el cual queremos mostrar unas migas de pan o breadcrumbs (para ello tenemos que saber todo lo que hay por encima de la categoría actual).

Como ejemplo, vamos a hacer una jerarquía con paises / comunidades autónomas / provincias / ciudades y vamos a buscar una ciudad dentro de ese array (está simplificado en el ejemplo).

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
105
106
107
108
<?php

$ex = array(
        array('id' => 1,
          'nombre' => 'España',
          'parentId' => 0),
        array('id' => 2,
          'nombre' => 'Portugal',
          'parentId' => 0),
        array('id' => 3,
          'nombre' => 'Francia',
          'parentId' => 0),
        array('id' => 4,
          'nombre' => 'Andalucía',
          'parentId' => 1),
        array('id' => 5,
          'nombre' => 'Galicia',
          'parentId' => 1),
        array('id' => 6,
          'nombre' => 'Madrid',
          'parentId' => 1),
        array('id' => 7,
          'nombre' => 'Castilla la Mancha',
          'parentId' => 1),
        array('id' => 8,
          'nombre' => 'Castilla y León',
          'parentId' => 1),
        array('id' => 9,
          'nombre' => 'Jaén',
          'parentId' => 4),
        array('id' => 10,
          'nombre' => 'Córdoba',
          'parentId' => 4),
        array('id' => 11,
          'nombre' => 'Sevilla',
          'parentId' => 4),
        array('id' => 12,
          'nombre' => 'Huelva',
          'parentId' => 4),
        array('id' => 13,
          'nombre' => 'Cádiz',
          'parentId' => 4),
        array('id' => 14,
          'nombre' => 'Málaga',
          'parentId' => 4),
        array('id' => 15,
          'nombre' => 'Granada',
          'parentId' => 4),
        array('id' => 16,
          'nombre' => 'Almería',
          'parentId' => 4),
        array('id' => 17,
          'nombre' => 'Linares',
          'parentId' => 9),
        array('id' => 18,
          'nombre' => 'Úbeda',
          'parentId' => 9),
        array('id' => 19,
          'nombre' => 'Baeza',
          'parentId' => 9),
        array('id' => 20,
          'nombre' => 'Baños de la Encina',
          'parentId' => 9),
        );

function buildTree($data, $rootId=0)
{
  $tree = array('children' => array(),
        'root' => array()
        );
  foreach ($data as $ndx=>$node)
    {
      $id = $node['id'];
      /* Puede que exista el children creado si los hijos entran antes que el padre */
      $node['children'] = (isset($tree['children'][$id]))?$tree['children'][$id]['children']:array();
      $tree['children'][$id] = $node;

      if ($node['parentId'] == $rootId)
    $tree['root'][$id] = &$tree['children'][$id];
      else
    {
      $tree['children'][$node['parentId']]['children'][$id] = &$tree['children'][$id];
    }

    }
  return $tree;
}

function findPath($tree, $childId, $reverse=true)
{
  $path = array($childId);
  $current = $childId;

  while (isset($tree['children'][$current]))
    {
      $current = $tree['children'][$current]['parentId'];
      $path[] = $current;
    }

  if (!$reverse)
    return array_reverse($path);
  else
    return $path;
}

$arbol = buildTree($ex);

print_r(findPath($arbol, 17));

Ahora buscamos el elemento con id 17 (Linares), tras ello, el script debe devolver:

Array
(
[0] => 17
[1] => 9
[2] => 4
[3] => 1
[4] => 0
)

lo cual es la ruta desde Linares hacia atrás: Linares (17), Jaén (9), Andalucía (4), España (1), root (0).

Esta función findPath() ahora mismo, funciona sólo con colecciones creadas con buildTree(), por lo que es muy importante que se respeten los nombres de los elementos (id de elemento, parentId para el id del elemento superior). De todas formas, podéis modificar estos algoritmos y os agradecería que comentaseis vuestros resultados.

Foto: Roberto Verzo (Flickr CC-by)

También podría interesarte....

There are 7 comments left Ir a comentario

  1. Pingback: Cómo encontrar la ruta de un elemento dentro de una jerarquía en PHP | PlanetaLibre /

  2. Aiden Aiden1 /
    Usando Google Chrome Google Chrome 116.0.0.0 en Windows Windows NT

    Stick to the fantastic job, That i look over couple articles or blog posts on this subject web-site together with It is my opinion that online webpage is certainly legitimate appealing and features have communities for superb material. บาคาร่า ไม่ผ่านเอเย่นต์

  3. mahmishal mishal /
    Usando Google Chrome Google Chrome 116.0.0.0 en Windows Windows NT

    It’s a superior strategies notably to help you the a newcomer to blogosphere, summary and even legitimate information… Bless you designed for writing this town. Required browse guide. USCIS Certified Translation Services

  4. Aiden Aiden1 /
    Usando Google Chrome Google Chrome 117.0.0.0 en Windows Windows NT

    When i stunned while using the research people meant to makes unique post awesome. Superb pastime! ทดลองเล่นสล็อต

  5. mahmishal mishal /
    Usando Google Chrome Google Chrome 116.0.0.0 en Windows Windows NT

    I enjoyed reading this post such an interesting info post. Thanks for providing good info. разговорный английский

  6. yitzchak kerrigan /
    Usando Google Chrome Google Chrome 117.0.0.0 en Windows Windows NT

    the nation’s certainly fabulous web log. the nation’s realy informative together with a a great decent project. i want it. คาสิโน888

  7. yitzchak kerrigan /
    Usando Google Chrome Google Chrome 117.0.0.0 en Windows Windows NT

    May very well just launched some blog page, the knowledge most people furnish on this internet site seems to have made it easier everybody vastly. Thanks a lot for the purpose of your personal instance & give good results. franchise opportunities

Leave a Reply