Определение того, какие объекты связаны или не связаны с основным корневым объектом

Ответ 1

Легче (IMHO) обрабатывать данные как два отдельных массива. Набор объектов и их ссылки. Кроме того, в качестве первой части я конвертирую объект, чтобы иметь идентификатор в качестве ключа, это позволяет мне использовать его напрямую, а не искать идентификатор каждый раз.

Также, чтобы сделать решение намного проще, я создал флаг в массиве объектов, когда я его посещаю, поэтому, когда я пытаюсь его снова ссылаться, я могу проверить, был ли он уже посещен.

<?php 
error_reporting ( E_ALL );
ini_set ( 'display_errors', 1 );

$objects =[[1,'apple'],
        [3, 'Carrot'],
        [4, 'Dill'],
        [5, 'Egg '],
        [6, 'Fred'],
        [7, 'Goat'],
        [8, 'Harry'],
        [9, 'Igloo'],
        [10, 'Jason'],
        [11, 'Klaus'],
        [12, 'Banana'],
        [15, 'Oyster1'],
        [16, 'Oyster2' ]];
$links =[[1,12],
        [1,5],
        [3,1],
        [3,12],
        [3,3],
        [4,1],
        [4,5],
        [5,6],
        [6,7],
        [7,7],
        [7,8],
        [8,null],
        [9,12],
        [9,5],
        [10,1],
        [10,5],
        [10,8],
        [11,1],
        [11,5],
        [11,10],
        [12,3],
        [15,16],
        [16,15 ]];

function buildTree ( $id, &$objects, $links )   {
    foreach ( $links as $testNode )    {
        if ( $testNode[0] == $id && 
                $testNode[1] != $id &&
                $testNode[1] != null &&
                !isset($objects[$testNode[1]]['visited']) )    {
            $objects[$testNode[1]]['visited'] = true;
            buildTree ( $testNode[1], $objects, $links);
        }
    }
}

// Convert array to have the ID as key
$objects = array_combine(array_column($objects, 0), $objects);
// Fetch ID of first item
reset($objects);
$startID = key($objects);
// Mark as visited
$objects[$startID]['visited'] = true;
// Process
buildTree ( $startID, $objects, $links);

$linked = [];
$notLinked = [];
foreach ( $objects as $object)  {
    if ( isset($object['visited']) )    {
        $linked[] = $object[1];
    }
    else    {
        $notLinked[] = $object[1];
    }
}
echo "Linked...".PHP_EOL;
print_r($linked);

echo "Not linked...".PHP_EOL;
print_r($notLinked);

Как вы можете видеть, ядром является рекурсивная функция buildTree. Это использует &$objects, так как это означает, что все вызовы функции будут использовать один и тот же массив. Поскольку я хочу создать все виды использования элементов, это важно.

Условие в buildTree проверяет, хочет ли он node, это не относится к тому же node (трату времени, которое вы ищете больше), а не null (не знаете, почему вы ссылаетесь на null, но снова не стоит смотреть дальше) и что node еще не был посещен. Если эти условия в порядке, он отмечает следующий node по мере посещения и переходит на следующий уровень.

Выход...

Linked...
Array
(
    [0] => apple
    [1] => Carrot
    [2] => Egg 
    [3] => Fred
    [4] => Goat
    [5] => Harry
    [6] => Banana
)
Not linked...
Array
(
    [0] => Dill
    [1] => Igloo
    [2] => Jason
    [3] => Klaus
    [4] => Oyster1
    [5] => Oyster2
)

Ответ 2

Это обход трассировки. Начиная с node (root), вы хотите пересечь график, отслеживающий каждую посещаемую node по пути. Как только обход закончился, посещенные связаны. Первый поиск по белому может быть выполнен следующим образом:

//To form a graph fetch all objects from the database (sorted by id) and 
//index them in a hash map
$objects = $stmt->fetchAll(PDO::FETCH_OBJ);
$nodes = [];
foreach ($objects as $object) {
    $nodes[$object->id] = new Node($object);
}

//fetch all connections from the database and link the objects
$links = $stmt->fetchAll(PDO::FETCH_OBJ);
foreach ($links as $link) {
    $nodes[$link->obj_id]->addLink($nodes[$link->obj_link_id]);
}

//let assume root is the first node (sorted by id), 
//traverse the graph starting from root
$root = reset($nodes);
$root->traverse();

//now if a node can be reached by the root it is marked as visited
$linked = [];
$notLinked = [];
foreach ($nodes as $node) {
    if ($node->isVisited()) {
        $linked[] = $node;
    } else {
        $notLinked[] = $node;
    }
}

И класс node:

class Node
{

    /**
     * List of neighbor nodes.
     *
     * @var Node[]
     */
    private $links = [];

    /**
     * id, title info
     *
     * @var array
     */
    private $data = [];

    /**
     * To track visited nodes.
     *
     * @var bool
     */
    private $visited = false;

    /**
     * Node constructor.
     * @param array $data
     */
    public function __construct($data)
    {
        $this->data = $data;
    }


    /**
     * Add a link to this node.
     *
     * @param Node $node
     * @return void
     */
    public function addLink(Node $node)
    {
        $this->links[] = $node;
    }

    /**
     * Traverse the graph in a Breadth-First-Search fashion marking
     * every visited node.
     * @return void
     */
    public function traverse()
    {
        //initialize queue
        $q = new SplQueue();

        //add root to queue and mark as visited
        $q->enqueue($this);
        $this->visited = true;

        while (!$q->isEmpty()) {
            /** @var Node $cur */
            $cur = $q->dequeue();

            foreach ($cur->links as $link) {

                //if link not visited already add it to queue and mark visited
                if (!$link->visited) {
                    $link->visited = true;
                    $q->enqueue($link);
                }
            }
        }
    }

    /**
     * Checks if node has been visited.
     *
     * @return bool
     */
    public function isVisited()
    {
        return $this->visited;
    }

}

Ответ 3

Скажем, что "корень" obj_id 1.

Вот несколько алгоритм грубой силы, но он использует преимущества SQL-операций "set".

Insert into table1 the root (1)
Loop
    Create table2 with all nodes linked to any node in table1
    Exit if number of rows in table2 = num rows in table1
    table1 := table2

Ближе к SQL:

# Initialize:
CREATE TABLE table1 (
    obj_id ...
    PRIMARY KEY(obj_id)
)
    SELECT 1;   # assuming root is 1

start of loop:
CREATE TABLE table2 (
    obj_id ...
    PRIMARY KEY(obj_id)
)
    SELECT DISTINCT obj_link_id
        FROM table1
        JOIN object_links USING(obj_id);

SELECT @fini := ( SELECT COUNT(*) FROM table1 ) = 
                ( SELECT COUNT(*) FROM table2 )   # will give true/false
DROP TABLE table1;
RENAME TABLE table2 TO table1;
loop if @fini=0

Выходные данные - это все "подключенные" идентификаторы. Если вам нужны несвязные:

SELECT obj_id
    FROM object_links
    LEFT JOIN table1 USING(obj_id)
    WHERE table1.obj_id IS NULL;   # that is, missing from table1

Ответ 4

Вот довольно короткий способ получить все связанные идентификаторы:

$pdo = new PDO('mysql:host=localhost;dbname=test_obj_link', 'testread', 'testread');

$links = $pdo
    ->query('select obj_id, obj_link_id from object_links')
    ->fetchAll(PDO::FETCH_GROUP|PDO::FETCH_COLUMN);

function getLinks($objId, $links,  $indirectNodes = []) {
    $directNodes = isset($links[$objId]) ? $links[$objId] : [];
    foreach($directNodes as $linkedNode) {
        if (!in_array($linkedNode, $indirectNodes)) {
            $indirectNodes[] = $linkedNode;
            $indirectNodes = array_unique(array_merge(
                $indirectNodes,
                getLinks($linkedNode, $links, $indirectNodes)
            ));
        }
    }
    return $indirectNodes;
}

$linkedObjectIds = getLinks(1, $links);

fetchAll(PDO::FETCH_GROUP|PDO::FETCH_COLUMN) вернет структурированный массив со ссылками на объект, индексированный объектными идентификаторами, который выглядит так:

$links = [
    1  => ['5', '12'],
    3  => ['1', '3', '12'],
    4  => ['1', '5'],
    5  => ['6'],
    6  => ['7'],
    7  => ['7', '8'],
    9  => ['5', '12'],
    10 => ['1', '5', '8'],
    11 => ['1', '5', '10'],
    12 => ['3'],
    15 => ['16'],
    16 => ['15'],
];

Функция getLinks будет "ходить" в массиве $links рекурсивно и объединить все дочерние массивы, найденные в пути. Поскольку PHP, похоже, не использует функцию array_union - array_unique(array_merge(..)).

Результат:

$linkedObjectIds = array (
  0 => '5',
  1 => '6',
  2 => '7',
  3 => '8',
  4 => '12',
  10 => '3',
  11 => '1',
)

Обратите внимание, что индексы здесь не имеют значения.

Чтобы получить соответствующие объекты, вы можете сделать следующее:

$objects = $pdo
    ->query('select id, title from object')
    ->fetchAll(PDO::FETCH_KEY_PAIR);
$linkedObjects = array_intersect_key($objects, array_flip($linkedObjectIds));
$notLinkedObjects = array_diff_key($objects, $linkedObjects);

Переменные будут содержать:

$objects = array (
  1 => 'Apple',
  3 => 'Carrot',
  4 => 'Dill',
  5 => 'Egg',
  6 => 'Fred',
  7 => 'Goat',
  8 => 'Harry',
  9 => 'Igloo',
  10 => 'Jason',
  11 => 'Klaus',
  12 => 'Banana',
  15 => 'Oyster1',
  16 => 'Oyster2',
);
$linkedObjects = array (
  1 => 'Apple',
  3 => 'Carrot',
  5 => 'Egg',
  6 => 'Fred',
  7 => 'Goat',
  8 => 'Harry',
  12 => 'Banana',
);
$notLinkedObjects = array (
  4 => 'Dill',
  9 => 'Igloo',
  10 => 'Jason',
  11 => 'Klaus',
  15 => 'Oyster1',
  16 => 'Oyster2',
);

Демо: http://rextester.com/ZQQGE35352

Обратите внимание, что in_array() и array_unique(), вероятно, медленны, поскольку они должны искать значения, которые не сортируются. Это может привести к проблемам с производительностью некоторых наборов данных. Предполагая, что PHP может быстрее искать ключи, мы можем использовать array_key_exists() вместо in_array() и оператора массива + (объединение по ключам) вместо array_unique(array_merge()). И код будет даже немного короче:

function getLinks($objId, $links,  $indirectNodes = []) {
    $directNodes = isset($links[$objId]) ? $links[$objId] : [];
    foreach($directNodes as $linkedNode) {
        if (!array_key_exists($linkedNode, $indirectNodes)) {
            $indirectNodes[$linkedNode] = 0;
            $indirectNodes = $indirectNodes + getLinks($linkedNode, $links, $indirectNodes);
        }
    }
    return $indirectNodes;
}

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

$linkedObjectIds = array_keys(getLinks(1, $links));

Демо: http://rextester.com/GHO7179