Determining which objects are or are not linked to the main root object

Question

I am trying to navigate through a bunch of objects with links to other objects. I want to start with the lowest id number (the root object) and navigate through each of the objects based on connected links. Some of the object links will loop back to previous objects, so I want to make sure I look at each one only once otherwise I will get stuck in an infinite loop. I also want to be able to tell which objects cannot be accessed by navigating through the links beginning at the first link.

The tables in my database look like this:

Object Table:

+----+---------+
| id | title   |
+----+---------+
|  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 |
+----+---------+

Object_Links Table:

+----+---------+--------------+
| id |  obj_id |  obj_link_id |
+----+---------+--------------+
|  1 |       1 |           12 |
|  2 |       1 |            5 |
|  3 |       3 |            1 |
|  4 |       3 |           12 |
|  5 |       3 |            3 |
|  6 |       4 |            1 |
|  7 |       4 |            5 |
|  8 |       5 |            6 |
|  9 |       6 |            7 |
| 10 |       7 |            7 |
| 11 |       7 |            8 |
| 12 |       9 |           12 |
| 13 |       9 |            5 |
| 14 |      10 |            1 |
| 15 |      10 |            5 |
| 16 |      10 |            8 |
| 17 |      11 |            1 |
| 18 |      11 |            5 |
| 19 |      11 |           10 |
| 20 |      12 |            3 |
| 21 |      15 |           16 |
| 22 |      16 |           15 |
+----+---------+--------------+

So, from the table you can see that object 1 has links to both objects 12 and 5.

My SQL query looks like this:

select  object.id, title, obj_link_id
    from  object
    left join  object_links  ON object.id = object_links.object_id
    order by  object.id 

which gives the table:

+----+---------+--------------+
| id | title   |  obj_link_id |
+----+---------+--------------+
|  1 | Apple   |           12 |
|  1 | Apple   |            5 |
|  3 | Carrot  |            1 |
|  3 | Carrot  |           12 |
|  3 | Carrot  |            3 |
|  4 | Dill    |            1 |
|  4 | Dill    |            5 |
|  5 | Egg     |            6 |
|  6 | Fred    |            7 |
|  7 | Goat    |            7 |
|  7 | Goat    |            8 |
|  8 | Harry   |         NULL |
|  9 | Igloo   |           12 |
|  9 | Igloo   |            5 |
| 10 | Jason   |            1 |
| 10 | Jason   |            5 |
| 10 | Jason   |            8 |
| 11 | Klaus   |            1 |
| 11 | Klaus   |            5 |
| 11 | Klaus   |           10 |
| 12 | Banana  |            3 |
| 15 | Oyster1 |           16 |
| 16 | Oyster2 |           15 |
+----+---------+--------------+

In PHP I am using:

$objects = $stmt->fetchAll(PDO::FETCH_CLASS);

I wasn't sure whether there was a better way to fetch these for my purposes so am open to suggestions.

A print_r($objects) yields:

Array
(
    [0] => stdClass Object
        (
            [id] => 1
            [title] => Apple
            [obj_link_id] => 12
        )

    [1] => stdClass Object
        (
            [id] => 1
            [title] => Apple
            [obj_link_id] => 5
        )

    [2] => stdClass Object
        (
            [id] => 3
            [title] => Carrot
            [obj_link_id] => 1
        )

    [3] => stdClass Object
        (
            [id] => 3
            [title] => Carrot
            [obj_link_id] => 12
        )

    [4] => stdClass Object
        (
            [id] => 3
            [title] => Carrot
            [obj_link_id] => 3
        )

    [5] => stdClass Object
        (
            [id] => 4
            [title] => Dill
            [obj_link_id] => 1
        )

    [6] => stdClass Object
        (
            [id] => 4
            [title] => Dill
            [obj_link_id] => 5
        )

    [7] => stdClass Object
        (
            [id] => 5
            [title] => Egg
            [obj_link_id] => 6
        )

    [8] => stdClass Object
        (
            [id] => 6
            [title] => Fred
            [obj_link_id] => 7
        )

    [9] => stdClass Object
        (
            [id] => 7
            [title] => Goat
            [obj_link_id] => 7
        )

    [10] => stdClass Object
        (
            [id] => 7
            [title] => Goat
            [obj_link_id] => 8
        )

    [11] => stdClass Object
        (
            [id] => 8
            [title] => Harry
            [obj_link_id] =>
        )

    [12] => stdClass Object
        (
            [id] => 9
            [title] => Igloo
            [obj_link_id] => 12
        )

    [13] => stdClass Object
        (
            [id] => 9
            [title] => Igloo
            [obj_link_id] => 5
        )

    [14] => stdClass Object
        (
            [id] => 10
            [title] => Jason
            [obj_link_id] => 1
        )

    [15] => stdClass Object
        (
            [id] => 10
            [title] => Jason
            [obj_link_id] => 5
        )

    [16] => stdClass Object
        (
            [id] => 10
            [title] => Jason
            [obj_link_id] => 8
        )

    [17] => stdClass Object
        (
            [id] => 11
            [title] => Klaus
            [obj_link_id] => 1
        )

    [18] => stdClass Object
        (
            [id] => 11
            [title] => Klaus
            [obj_link_id] => 5
        )

    [19] => stdClass Object
        (
            [id] => 11
            [title] => Klaus
            [obj_link_id] => 10
        )

    [20] => stdClass Object
        (
            [id] => 12
            [title] => Banana
            [obj_link_id] => 3
        )

    [21] => stdClass Object
        (
            [id] => 15
            [title] => Oyster1
            [obj_link_id] => 16
        )

    [22] => stdClass Object
        (
            [id] => 16
            [title] => Oyster2
            [obj_link_id] => 15
        )

)

Please note, that the number in the brackets is just the array index, not the object id number, so don't let the index throw you off.

I am trying to find a way to determine which are the linked and which are the unlinked objects. Based on the above scenario the objects should be separated as follows:

**Linked:**

    Apple
    Banana
    Carrot
    Egg
    Fred
    Goat
    Harry

**Not Linked:**

    Dill
    Igloo
    Jason
    Klaus
    Oyster1
    Oyster2

My main question:

How can I create a loop in PHP to loop through a structure like this especially when each object can have multiple links? Ultimately I would like to produce two collections of objects, one containing the linked objects and one containing the unlinked objects. A sample collection might look like this:

stdClass Object
(
  [LinkedElements] => stdClass Object
    (
      [1] => stdClass Object
        (
          [id] => 1
          [name] => Apple
          [link] => Array
            (
              [0] => 14
              [1] => 5
            )

        )

      [14] => stdClass Object
        (
          [id] => 14
          [name] => Banana
          [link] => Array
            (
              [0] => 3
            )

        )

      [3] => stdClass Object
        (
          [id] => 3
          [name] => Carrot
          [link] => Array
            (
              [0] => 1
              [1] => 14
              [2] => 3
            )

        )

      [5] => stdClass Object
        (
          [id] => 5
          [name] => Egg
          [link] => Array
            (
              [0] => 6
            )

        )

      [6] => stdClass Object
        (
          [id] => 6
          [name] => Fred
          [link] => Array
            (
              [0] => 7
            )

        )

      [7] => stdClass Object
        (
          [id] => 7
          [name] => Goat
          [link] => Array
            (
              [0] => 7
              [1] => 8
            )

        )

      [8] => stdClass Object
        (
          [id] => 8
          [name] => Harry
        )

    )

  [UnLinkedElements] => stdClass Object
    (
      [4] => stdClass Object
        (
          [id] => 4
          [name] => Dill
          [link] => Array
            (
              [0] => 1
              [1] => 5
            )

        )

      [9] => stdClass Object
        (
          [id] => 9
          [name] => Igloo
          [link] => Array
            (
              [0] => 14
              [1] => 5
            )

        )

      [10] => stdClass Object
        (
          [id] => 10
          [name] => Jason
          [link] => Array
            (
              [0] => 1
              [1] => 5
              [2] => 8
            )

        )

      [11] => stdClass Object
        (
          [id] => 11
          [name] => Klaus
          [link] => Array
            (
              [0] => 1
              [1] => 5
              [2] => 10
            )

        )

      [15] => stdClass Object
        (
          [id] => 15
          [name] => Oyster1
          [link] => Array
            (
              [0] => 16
            )

        )

      [16] => stdClass Object
        (
          [id] => 16
          [name] => Oyster2
          [link] => Array
            (
              [0] => 15
            )

        )

    )

)

Please note:

• Navigation is done from object to link, not the other way around.
• It is okay to have an object point to itself (as object 7 does).
• The above sample structure (underneath my main question) is a suggestion only and I am open to other suggestions.
• Disclaimer: This question is based on another question I previously asked. In my original question I manually created the test objects, but I was not able to pull them out of my database in this fashion.

Answer 1

It's easier (IMHO) to deal with the data as two separate arrays. A set of objects and their links. Also, as the first part I convert the object to have the ID as the key, this allows me to use it directly rather than having to search for the ID each time.

Also to make the solution a lot simpler, I've created a flag in the object array as I visit it, so that when I try and reference it again, I can check if it's already been visited.

<?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);

As you can see, the core is the recursive buildTree function. This uses &$objects as this means that all calls to the function will use the same array. As I want to build up all the uses of the items, this is important.

The condition in buildTree, checks to see if it's the node we want, it's not referring to the same node (waste of time looking any more), not null (not sure why you link to null, but again not worth looking any further) and that the node hasn't already been visited. If these conditions are OK, it marks the next node as visited and goes down into the next level.

The output is...

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
)