PHPでフラットな配列を木構造に変換した際に経路を残したい

Question

実現したいこと

PHPでフラットな配列を木構造に変換した際に経路を残したいです。
配列から木構造に変換はできたのですがキーのlistとして残す部分の処理が分かりません。

該当のソースコード

// 変換前
[
    'id' => 1,
    'parent_id' => null
],
[
    'id' => 2,
    'parent_id' => 1
],
[
    'id' => 3,
    'parent_id' => 1
],
[
    'id' => 4,
    'parent_id' => 3
],
[
    'id' => 5,
    'parent_id' => null
],
[
    'id' => 6,
    'parent_id' => 5
],
[
    'id' => 7,
    'parent_id' => 6
];

// 変換後(木構造)
[
    'list' => '1',
    'id' => 1,
    'parent_id' => null,
    'children' => [
        [
            'list' => '1, 2',
            'id' => 2,
            'parent_id' => 1
        ],
        [
            'list' => '1, 3',
            'id' => 3,
            'parent_id' => 1,
            'children' => [
                'list' => '1, 3, 4',
                'id' => 4,
                'parent_id' => 3
            ]
        ],
    ],
    [
        'id' => 5,
        'parent_id' => null,
        'children' => [
            [
                'list' => '5, 6',
                'id' => 6,
                'parent_id' => 5
            ],
            [
                'list' => '5, 7',
                'id' => 7,
                'parent_id' => 6
            ]
        ]
    ],
];

試したこと

・親をみて足していく
・マップを作って参照する
他にもいろいろ試してはみましたがそもそものフラットな配列から木構造の変換の時点でもう少し何か手を加えないといけないのかもわからずはまっていますのでよろしければお助け下さい。

Answer 1

別解のため回答を分けます。
MySQLで入れ子モデルテスト

(1)サンプルテーブル作成

create table  tree (
id int not null unique,
parent_id int,
level int not null default 0,
l int not null default 0,
r int not null default 0);

insert into tree(id,parent_id) values
(1600,NULL),(1700,1600),(1750,1600),(1800,1700),(1820,1700),(1850,1700),(1900,1800);

• level=何階層目かを計算していれる
• l=左の値(計算で求める)
• r=右の値(計算で求める)

(2)procedureの作成

drop procedure if exists SET_LR;
delimiter //
create procedure SET_LR()
begin 
declare a int default 0;
declare done int default 0;
declare cur cursor FOR 
select id from tree where level=0 order by parent_id asc,id desc;
declare continue handler for sqlstate '02000' set done = 1;
update tree set level=0,l=0,r=0;
update tree set level=1,l=(select @a:=@a+1 from (select @a:=0) AS sub),r=@a:=@a+1
where parent_id is null
order by id;
open cur;
repeat
fetch cur into a;
if not done then
set @id=a;
set @sql='update tree as a1,tree as a2,tree as a3 set a1.l=a2.l+1,a1.r=a2.l+2,a1.level=a2.level+1,a2.r=a2.r+2,a3.r=a3.r+2 where a1.parent_id=a2.id and a2.l<a3.r and a1.id=?';
prepare stmt from @sql;
execute stmt using @id;
set @sql='update tree as a1,tree as a2,tree as a3 set a3.l=a3.l+2 where a1.parent_id=a2.id and a2.l<a3.l and a3.id!=a1.id and a1.id=?';
prepare stmt from @sql;
execute stmt using @id;
end if;
until done end repeat;
close cur;
end
//
delimiter ;

(3)procedureの実行
※実際にはデータを追加・更新・削除するたびに実行する

call SET_LR();

テスト

(1)単純なデータ

select * from tree;

id	parent_id	level	l	r
1600	NULL	1	1	14
1700	1600	2	2	11
1750	1600	2	12	13
1800	1700	3	3	6
1820	1700	3	7	8
1850	1700	3	9	10
1900	1800	4	4	5

(2)階層表示

select CONCAT( REPEAT( "__", LEVEL -1 ) , id ) AS id
from tree
order by l;

id
1600
__1700
____1800
______1900
____1820
____1850
__1750

(3)経路表示

select  t2.id,group_concat(t1.id order by t1.parent_id asc) as route
from tree as t1
inner join tree as t2
on t2.l between t1.l and t1.r
group by t2.id;

id	route
1600	1600
1700	1600,1700
1750	1600,1750
1800	1600,1700,1800
1820	1600,1700,1820
1850	1600,1700,1850
1900	1600,1700,1800,1900

Answer 2

なんとなく条件が曖昧ですが

$a=[
  "1700" => [
    "to_id" => 1700,
    "from_id" => 1600,
    ],
  "1800" => [
    "to_id" => 1800,
    "from_id" => 1700,
    ],
  "1900" => [
    "to_id" => 1900,
    "from_id" => 1800,
    ],
  ];

foreach($a as $key=>&$vals){
  $vals["list"]=(isset($a[$from=$vals["from_id"]])?$a[$from]["list"]:$vals["from_id"]).",".$vals["to_id"];
}
print_r($a);

ただしPHPの配列はキーが必ずしも若い順(命題でいう経路順)で格納されているわけではないので、
キーの順番が変わった場合に正しく経路が抜き出せません。
予めfrom_idでソートをしてから処理をする必要があるかもしれません

Comments

[POPO]

申し訳ありません。記載ミスをしていました。
木構造にしたデータに対して経路を保存したいと言う趣旨の質問でした。

[yambejp]

ちょっと曖昧な部分が多すぎるのでもう少しだけサンプル数（どういうデータからどういう木構造をつくりたいか）を増やせませんか？（たとえば分岐しないのかとか）

[yambejp]

ちなみにこの手の処理はDBを利用し、
親情報だけをもつ「隣接リスト」から「入れ子集合モデル」にプロシージャで変換して管理するとわかりやすくなります。

[POPO]

サンプル変更させて頂きました。
変換前から変換後のデータに変更したいです。

入れ子集合モデルは勉強したことないので調べてみます。