рекурсивная функция php для генеалогического дерева - PullRequest
Новая
       41

рекурсивная функция php для генеалогического дерева

0 голосов
/ 30 октября 2018

У меня в базе данных есть люди по отношению к родителям, и мне нужно создать рекурсивную функцию, которая возвращает массив с генеалогическим деревом. Пример базы данных: 

NUMBER;NAME;FATHER;MOTHER
001;Name1;002;005
002;Name2;007;018
003;Name3;018;025
005;Name5;006;019
023;Name23;019;045
018;Name18;062;097
007;Name7;;-
...

Я подготовил две функции - одну для человека и вторую рекурсивную для поиска предков.

Мне нужен этот результат: 

$out[0][0] // first person
$out[1][0] // mother of first person
$out[1][1] // father of first person
$out[2][0] // grandmother of first person (mother side)
$out[2][1] // grandfather of first person (mother side)
$out[2][2] // grandmother of first person (father side)
$out[2][3] // grandmother of first person (father side)
...

следующее поколение имеет 8 предметов, следующие 16 предметов, ... Максимум - 6 поколений назад.

Я подготовил две функции - одну для человека и вторую рекурсивную для построения дерева. Во второй функции 

define("MAX_GEN",5);

function detail($number) {
    $d = mysql_query("select * from table where number = '$number'");
    if(mysql_num_rows($d) == 0) {
        $p[name] = "N/A";
        $p[number] = "N/A";
        $p[m_number] = "N/A";
        $p[f_number] = "N/A";
    }
    else $p = mysql_fetch_assoc($d);
    return $p;
}

function gen($number, $generation = 0, $out) {

    if ($generation >= MAX_GEN) {
        return false;
    }

    $record = detail($number);

    if ($generation == 0) $out[0][] = $record; // first man

    $generation++; // next generation

    if (!$out[$generation] && ($generation != MAX_GEN)) $out[$generation] = array();

    $x_mother = gen($record[m_number], $generation ); // continue with mother
    $x_father = gen($record[f_number], $generation ); // continue with father

    if ($out[$generation]) {
        $out[$generation][] = $x_mother;
        $out[$generation][] = $x_father;
    }
    return $out;
}

Но во второй функции есть проблема - я не знаю, как передать массив с результатами следующему и следующему поколению. Он по-прежнему возвращает один элемент или (после нескольких попыток) возвращает массив, который я хочу, но со вставленными массивами между поколениями, и результат не может быть использован. Кто-нибудь может мне помочь, пожалуйста?

Пример результата, который я получу здесь: http://www.foxterrier.cz/_TM_importy/example.php

Ответы [ 3 ]

0 голосов
/ 30 октября 2018

Я предпочитаю использовать итерацию для создания $ out array

вместо gen function

увеличивается число итераций 1 -> 2 -> 4 -> 8

= 2 ^ ($ generation-1) 

$parent=$generation-1;
      for($j=0;$j<pow(2,$parent);$j++){

полный код 

define("MAX_GEN",5);

function detail($number) {
    $d = mysql_query("select * from table where number = '$number'");
    if(mysql_num_rows($d) == 0) {
        $p[name] = "N/A";
        $p[number] = "N/A";
        $p[m_number] = "N/A";
        $p[f_number] = "N/A";
    }
    else $p = mysql_fetch_assoc($d);
    return $p;
}

$main_person_number=001;//number in database
$generation = 0;
$out[0][] =detail($number);// main person
$generation++; // next generation

for($i=1;$i<$MAX_GEN;$i++){
  $parent=$generation-1;
  for($j=0;$j<pow(2,$parent);$j++){
      $record = detail($out[$parent][$j]['number']);
  $out[$generation][] =$record[m_number];
  $out[$generation][] =$record[m_number];
    }
   $generation++;   
}
0 голосов
/ 30 октября 2018

Обновленное решение essam eg - теперь полностью работает:
- удалил char $ перед MAX_GET первым в цикле
- убрана генерация $ в цикле (достаточно $ i)
- добавить детализацию вызова в ( $ out [$ i] [] = $ record [m_number]; -> $ out [$ i] [] = detail ($ record [m_number]); )
- изменить добавление отца в массив (мать была дважды, а отец отсутствовал) 

define("MAX_GEN",5);

function detail($number) {
    $d = mysql_query("select * from table where number = '$number'");
    if(mysql_num_rows($d) == 0) {
        $p[name] = "N/A";
        $p[number] = "N/A";
        $p[m_number] = "N/A";
        $p[f_number] = "N/A";
    }
    else $p = mysql_fetch_assoc($d);
    return $p;
}

$main_person_number=001;//number in database
$out[0][] =detail($number);// main person


for($i=1;$i<MAX_GEN;$i++){
  $parent=$i-1;
  for($j=0;$j<pow(2,$parent);$j++){
      $record = detail($out[$parent][$j]['number']);
  $out[$i][] = detail($record[m_number]);
  $out[$i][] = detail($record[f_number]);
    }
}
0 голосов
/ 30 октября 2018

В основном это комментарий, но он немного длинный.

Вы очень ограничены как вашим дизайном базы данных, так и вашим желаемым форматом вывода. Даже без учета стоимости / сложности графической базы данных существует множество способов представления иерархических данных в реляционной базе данных .

Ваш выходной формат перечисляет каждое поколение, но не поддерживает связь между матерью и отцом, и не поддается планированию вбок или вперед - только назад.

Ваша реализация требует, чтобы вы выполняли 2 ^ N (где N - количество поколений) запросов, каждый раз делая циклический переход от кода PHP обратно к СУБД. Производительность будет отстой.

Как минимум, вы должны рассмотреть разрешение поколения за раз: 

  $ref=mysql_real_escape_string(session_id());
  mysql_query(
    "INSERT INTO results (generation, number, ref) VALUES (0, $start_number, '$ref')"
  );

  for ($x=1; $x<=max_gens; $x++) {
    mysql_query(
  "INSERT INTO results (generation, number, ref)
  SELECT $x, father, '$ref'
  FROM yourtable yt JOIN results rs ON yt.number=results.number 
  WHERE rs.generation=$x-1
  UNION 
  SELECT $x, mother, '$ref'
  FROM yourtable yt JOIN results rs ON yt.number=results.number 
  WHERE rs.generation=$x-1"
     );
  }

(но с дополнительной проверкой ошибок - и не забудьте очистить данные позже)

...