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?
4 Answers
Answers 1
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 ) ) ) ) Answers 2
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>'; } Answers 3
Note I made some assumptions to better reflect a typical real-life network problem
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->linkcan be resolved to a linked object using a DB or other query. To simplify the code (so I don't have to write agetObjAtID()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' 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; } Answers 4
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 
0 comments:
Post a Comment