代码之家 › 专栏 › 技术社区 › Pierre de LESPINAY

排序实体依赖项

algorithm php

1

Pierre de LESPINAY · 技术社区 · 6 年前

我有一些相互关联的实体。

Answer
  - AnswerGroup
AnswerGroup
Condition
  - Question
Notion
Question
  - AnswerGroup
  - Theme
  - Notion
Theme

PHP表示:

$entities = [
    ['name' => 'Answer', 'relations' => ['AnswerGroup']],
    ['name' => 'AnswerGroup', 'relations' => []],
    ['name' => 'Condition', 'relations' => ['Question']],
    ['name' => 'Notion', 'relations' => []],
    ['name' => 'Question', 'relations' => ['Theme', 'AnswerGroup', 'Notion']],
    ['name' => 'Theme', 'relations' => []],
];

我需要对它们进行排序,以使依赖关系排在第一位。我期待的结果是:

array:6 [
  0 => "AnswerGroup"
  1 => "Answer"
  2 => "Notion"
  3 => "Theme"
  4 => "Question"
  5 => "Condition"
]

我天真地以为我可以简单地使用 usort 像那样

usort($entities, function ($entityA, $entityB) {
    if (in_array($entityB, $entityA['relations'])) {
        return 1;
    }
    if (in_array($entityA, $entityB['relations'])) {
        return -1;
    }
    return 0;
});

但是:

dump(array_column($entities ,'name'));

给予

array:6 [
  0 => "Answer"
  1 => "AnswerGroup"
  2 => "Condition"
  3 => "Notion"
  4 => "Question"
  5 => "Theme"
]

如何订购我的实体?

1 回复 | 直到 6 年前

1

2

Nick SamSmith1986 6 年前

这是做你想做的事情的一种方式。它使用递归函数列出每个实体的所有依赖项(关系)。在处理之前,对每个实体的关系列表进行排序,以便按字母顺序获得每个级别关系的结果。终于 array_unique 用于删除重复条目(例如 AnswerGroup 是两者的关系 Answer 和 Question )

function list_dependents($entity, $entities) {
    $sorted = array();
    sort($entity['relations']);
    foreach ($entity['relations'] as $r) {
        $sorted = array_merge($sorted, list_dependents($entities[array_search($r, array_column($entities, 'name'))], $entities));
    }
    $sorted = array_merge($sorted, array($entity['name']));
    return $sorted;
}
$sorted = array();
foreach ($entities as $entity) {
    $sorted = array_merge($sorted, list_dependents($entity, $entities));
}
$sorted = array_values(array_unique($sorted));
print_r($sorted);

输出:

Array (
    [0] => AnswerGroup
    [1] => Answer
    [2] => Notion
    [3] => Theme
    [4] => Question
    [5] => Condition 
)

Demo on 3v4l.org