Menu
I am trying to navigate through a bunch of objects with links to other objects. I want to start with id of 1 and navigate through each of the objects. Some of the objects 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. I don't think the order of navigation matters.
Here is a sample dataset I might encounter (my actual data will be coming from a database):
<?php
$obj_array = [] ;
$obj = new stdClass;
$obj->id = 1;
$obj->name = "Apple";
$obj->link = array(14, 5);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 3;
$obj->name = "Carrot";
$obj->link = array(1, 14, 3);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 4;
$obj->name = "Dill";
$obj->link = array(1, 5);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 5;
$obj->name = "Egg";
$obj->link = array(6);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 6;
$obj->name = "Fred";
$obj->link = array(7);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 7;
$obj->name = "Goat";
$obj->link = array(7, 8);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 8;
$obj->name = "Harry";
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 9;
$obj->name = "Igloo";
$obj->link = array(14, 5);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 10;
$obj->name = "Jason";
$obj->link = array(1, 5, 8);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 11;
$obj->name = "Klaus";
$obj->link = array(1, 5, 10);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 14;
$obj->name = "Banana";
$obj->link = array(3);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 15;
$obj->name = "Oyster1";
$obj->link = array(16);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 16;
$obj->name = "Oyster2";
$obj->link = array(15);
$obj_array[] = $obj;
I would expect to see something like this (order doesn't matter):
Processed:
Apple
Banana
Carrot
Egg
Fred
Goat
Harry
Not Linked:
Dill
Igloo
Jason
Klaus
Oyster1
Oyster2
How can I create a loop to loop through a structure like this especially when each object can have multiple links?
733
Although @wizards answer worked, I felt I wanted to make a version with a bit clearer code. Below version returns an object with the linked and unlined elements, and I believe it's very clear how it works.
The reason I want to work like this, is to be able to extend it for future questions. Like "How many times is an item linked" or "Which has the most links". It can be easily adapted to answer these questions also.
Another benefit is that it uses as limited loops as possible, which could speed things up quite a bit when the size increases.
<?php
error_reporting(E_ALL);
$obj_array = [] ;
$obj = new stdClass;
$obj->id = 1;
$obj->name = "Apple";
$obj->link = array(14, 5);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 3;
$obj->name = "Carrot";
$obj->link = array(1, 14, 3);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 4;
$obj->name = "Dill";
$obj->link = array(1, 5);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 5;
$obj->name = "Egg";
$obj->link = array(6);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 6;
$obj->name = "Fred";
$obj->link = array(7);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 7;
$obj->name = "Goat";
$obj->link = array(7, 8);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 8;
$obj->name = "Harry";
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 9;
$obj->name = "Igloo";
$obj->link = array(14, 5);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 10;
$obj->name = "Jason";
$obj->link = array(1, 5, 8);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 11;
$obj->name = "Klaus";
$obj->link = array(1, 5, 10);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 14;
$obj->name = "Banana";
$obj->link = array(3);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 15;
$obj->name = "Oyster1";
$obj->link = array(16);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 16;
$obj->name = "Oyster2";
$obj->link = array(15);
$obj_array[] = $obj;
/*
* CALL
*/
$parser = new ObjectLinker($obj_array, 1);
//dump found
//decode/encode to only show public values
print_r(json_decode(json_encode($parser)));
/*
* ACTUAL CODE
*/
class ObjectLinker
{
private $_array;
private $_start;
public $LinkedElements = array();
public $UnLinkedElements = array();
final public function __construct($ar, $start)
{
$this->_array = $ar;
$this->_start = $start;
$this->getElementsArray();
$this->findLinked($this->_start);
}
final private function getElementsArray()
{
//since each Id is unique, i'm using the ID as the key in the array. this will allow faster access
//Ofcourse it would be better if you would create the array like this in the first place, then you can skip this step
foreach($this->_array as $obj) {
if (!is_null($obj) && property_exists($obj, 'id')) {
//I add everything to the unlinked elements. We will remove the linked once, to have once less loop
$this->UnLinkedElements[$obj->id] = $obj;
}
}
}
final private function findLinked($id)
{
//If the key is not in the array, it's already loaded
if (!array_key_exists($id, $this->UnLinkedElements)) {
return;
}
//get obj
//Because of the getElementsArray() step, I'm already sure the object exists.
//If you change the input array, you might want to check for invalid obj
$obj = $this->UnLinkedElements[$id];
//add to linked
$this->LinkedElements[$id] = $obj;
//remove from unlinked
unset($this->UnLinkedElements[$id]);
//no links
if (!property_exists($obj, 'link')) {
return;
}
$links = $obj->link;
//Invalid links
if (!is_array($links)) {
return;
}
//check links
foreach($links as $link) {
$this->findLinked($link);
}
}
}
?>
Output:
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
)
)
)
)
You can skip the printing and work with the $obj_array itself, diving the data into two arrays is just to be able to print them nicely:
$linked_ids = array();
$processed_objects = array();
$unlinked_objects = array();
foreach ( $obj_array as $obj ) {
if ( isset($obj->link) && $obj->link ) {
$linked_ids = array_merge($linked_ids, $obj->link);
}
}
$linked_ids = array_unique( $linked_ids );
foreach ($obj_array as $obj) {
if ( !in_array($obj->id, $linked_ids) ) {
$unlinked_objects[] = $obj;
} else {
$processed_objects[] = $obj;
}
}
/* Printing */
echo '<b>Processed:</b><br>';
foreach ( $processed_objects as $obj ) {
echo $obj->name . '<br>';
}
echo '<b>Not Linked:</b><br>';
foreach ( $unlinked_objects as $obj ) {
echo $obj->name . '<br>';
}
I assumed that in production, the full network of objects is too large to hold in memory. This means that the right approach must take just one root node and discover all linked objects without duplication
I assumed that each ID in $obj->link can be resolved to a linked object using a DB or other query. To simplify the code (so I don't have to write a getObjAtID() function) I changed the interface of link from $obj->link = [id1, id2] to $obj->link = [objectRef1, objectRef2]
My code:
function processObjNetwork(stdClass $rootObj){
$linkedObjects = [];
$process = function(stdClass $obj) use(&$linkedObjects, &$process){
if(isset($linkedObjects[$obj->id])) return; // already processed
else $linkedObjects[$obj->id] = $obj; // add to linked
if(empty($obj->link)) return; // nothing linked; no recursion needed
foreach($obj->link as $child) $process($child); // recursion to linked objs
};
$process($rootObj); // start with the root node
return $linkedObjects;
}
What gets returned is a collection of all linked objects:
$linkedObjects = processObjNetwork($rootObject); // root here is 'Apple'
Live demo
Given my assumption -- specifically that the map is too large so we start with only a root node -- it is not possible to discover unlinked nodes since by definition they are not connected to the root.
If you have all the nodes in storage, you can find unlinked nodes by simply iterating through every node and checking whether it is found among linked. If not, then it's unlinked.
$unlinkedObjects = [];
foreach($obj_array as $obj){
// add to $unlinkedObjects anything not found in $linkedObjects
if(!isset($linkedObjects[$obj->id])) $unlinkedObjects[$obj->id] = $obj;
}
Answer updated, now the code walks through an array started with ID=1, collects all the "connection" links that meets on the run and show names of objects out. I hope desirable result is achieved.
The first list (before line of dashes) is the list that can be accessible from object with ID=1 through the connected links.
The second one is missed names.
The code:
<?php
$obj_array = [] ;
$obj = new stdClass;
$obj->id = 1;
$obj->name = "Apple";
$obj->link = array(14, 5);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 3;
$obj->name = "Carrot";
$obj->link = array(1, 14, 3);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 4;
$obj->name = "Dill";
$obj->link = array(1, 5);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 5;
$obj->name = "Egg";
$obj->link = array(6);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 6;
$obj->name = "Fred";
$obj->link = array(7);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 7;
$obj->name = "Goat";
$obj->link = array(7, 8);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 8;
$obj->name = "Harry";
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 9;
$obj->name = "Igloo";
$obj->link = array(14, 5);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 10;
$obj->name = "Jason";
$obj->link = array(1, 5, 8);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 11;
$obj->name = "Klaus";
$obj->link = array(1, 5, 10);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 14;
$obj->name = "Banana";
$obj->link = array(3);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 15;
$obj->name = "Oyster1";
$obj->link = array(16);
$obj_array[] = $obj;
$obj = new stdClass;
$obj->id = 16;
$obj->name = "Oyster2";
$obj->link = array(15);
$obj_array[] = $obj;
function findObject($objects, $id) {
foreach ($objects as $object) {
if ($object->id === $id) {
return $object;
}
}
return null;
}
function getLinkedIds($objects, $startId=1) {
$idQueue = [$startId];
$linkedIds = [];
while (count($idQueue)) {
$id = array_pop($idQueue);
$obj = findObject($objects, $id);
if (!is_null($obj) && property_exists($obj, 'link')) {
$linksToAdd = array_filter($obj->link, function($linkedId) use ($linkedIds) {
return !in_array($linkedId, $linkedIds);
});
$idQueue = array_merge($idQueue, $linksToAdd);
}
$linkedIds[] = $id;
}
return array_unique($linkedIds);
}
function getNotLinkedObjects($objects, $startId=1) {
$linked = getLinkedIds($objects, $startId);
return array_filter($objects, function($obj) use ($linked) {
return !in_array($obj->id, $linked);
});
}
function getLinkedObjects($objects, $startId=1) {
$linked = getLinkedIds($objects, $startId);
return array_filter($objects, function($obj) use ($linked) {
return in_array($obj->id, $linked);
});
}
function listNames($objects) {
foreach ($objects as $obj) {
echo $obj->name.PHP_EOL;
}
}
listNames(getLinkedObjects($obj_array));
echo '----'.PHP_EOL;
listNames(getNotLinkedObjects($obj_array));
result:
Apple
Carrot
Egg
Fred
Goat
Harry
Banana
---
Dill
Igloo
Jason
Klaus
Oyster1
Oyster2
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
