Get dependencies Ids Algorithm

I have this problem and I came out with a solution but what is the best way to solve this problem ? Thank you in advance.

Given an array of strings and an array of tasks you need to return a sorted array with tasks and dependencies tasks ids.

Example:

$inputs = ['A'];

$tasks = [
    ['id' => 1, 'type' => 'A', 'dependencies' => ['B']],
    ['id' => 2, 'type' => 'A', 'dependencies' => ['C']],
    ['id' => 3, 'type' => 'B', 'dependencies' => ['C']],
    ['id' => 4, 'type' => 'C', 'dependencies' => ['A', 'F']],
    ['id' => 5, 'type' => 'D', 'dependencies' => []],
    ['id' => 6, 'type' => 'D', 'dependencies' => ['F']],
    ['id' => 7, 'type' => 'E', 'dependencies' => ['D']],
    ['id' => 8, 'type' => 'F', 'dependencies' => []]
];

Expected output:

[1, 2, 3, 4, 8]

// Comments.
Id 1 of tasks['type'] = A  - [1]
Id 2 of tasks['type'] = A  - [1, 2]

Tasks id 1 has dependencies B then 
Id 3 of tasks['type'] = B  - [1, 2, 3]

Tasks id 3 has dependencies C then 
Id 4 of tasks['type'] = C  - [1, 2, 3, 4]

Tasks id 4 has dependencies A and F. Take F then 
Id 8 of tasks['type'] = F  - [1, 2, 3, 4, 8]

So far this is the solution I built, but I would like to know if I am in the right path.

print_r(getId($inputs, $tasks));

function getId($inputs, $tasks){
    $id   = [];
    $deps = [];
    $values = [];
    $result = [];

    foreach($inputs as $input){
        foreach($tasks as $task){
            if ($task['type'] == $input){
                $result[$task['id']] = $task['id'];

                foreach($task['dependencies'] as $dependencies){
                    if($dependencies != $input){
                        $deps[] = $dependencies;
                    }
                }
            }
            else
            {
                $values[$task['type']]['id'][] = $task['id'];
                $values[$task['type']]['deps'] = $task['dependencies'];
            }
        }

        foreach($deps as $d){
            if(count($values[$d]['deps']) > 0)
            {
                foreach($values[$d]['deps'] as $nDeps)
                {
                    if($nDeps != $input){
                        $result[] = $values[$nDeps]['id'];
                    }
                }
            }
        }
    }

    foreach( $result as $res){
        if (is_array($res)){
            foreach( $res as $r){
                $id[] = $r;
            }
        }
        else {
            $id[] = $res;
        }
    }

    return array_unique($id);
}

Answer

Full Snippet:

<?php

function getId($inputs, $tasks){
   $types = [];
   $dependencies = [];
   foreach($tasks as $task){
       $types[$task['type']] =  $types[$task['type']] ?? [];
       $dependencies[$task['type']] = $dependencies[$task['type']] ?? [];
       $types[$task['type']][] = $task['id'];
       $dependencies[$task['type']] = array_unique(array_merge($dependencies[$task['type']],$task['dependencies']));
   }
   
   $res = [];
   $vis = [];
   foreach($inputs as $in){
       $queue = [];
       foreach($types[$in] as $id){
           if(!isset($vis[$id])){
               $vis[$id] = true;
               $queue[] = [$id , $in];
           }
       }
       while(count($queue) > 0){
           $d = array_shift($queue);
           $res[] = $d[0];
           $vis[$d[0]] = true;
           $type = $d[1];
           foreach($dependencies[$type] as $de_type){
               foreach($types[$de_type] as $id){
                   if(!isset($vis[$id])){
                       $vis[$id] = true;
                       $queue[] = [$id , $de_type];
                   }
               }
           }
       }
   }
   
   sort($res);
   return $res;
}

---

Step 1 : Dependency and type maps:

foreach($tasks as $task){
       $types[$task['type']] =  $types[$task['type']] ?? [];
       $dependencies[$task['type']] = $dependencies[$task['type']] ?? [];
       $types[$task['type']][] = $task['id'];
       $dependencies[$task['type']] = array_unique(array_merge($dependencies[$task['type']],$task['dependencies']));
}

• Collect all types of tasks according to their type. This will be helpful in accumulating all tasks of a particular type.
• Create a dependency map(associative array) as well by collecting all dependencies for a particular type. This involves merging of all tasks’ dependencies which have the same type.

---

Step 2: Add those tasks whose types are requested in $inputs

$queue = [];
foreach($types[$in] as $id){
   if(!isset($vis[$id])){
       $vis[$id] = true;
       $queue[] = [$id , $in];
   }
}

The above snippet is to just add nodes/tasks in the queue(only those who haven’t been added before)

---

Step 3: Loop over all dependencies

while(count($queue) > 0){
     $d = array_shift($queue);
     $res[] = $d[0];
     $vis[$d[0]] = true;
     $type = $d[1];
     foreach($dependencies[$type] as $de_type){
         foreach($types[$de_type] as $id){
             if(!isset($vis[$id])){
                 $vis[$id] = true;
                 $queue[] = [$id , $de_type];
             }
         }
     }
 }

Above snippet loops over each tasks one by one popping them out from the queue. Once a task is popped out, we loop over all it’s type dependencies. The inner loop loops over those tasks which have the current type in iteration. This way, the whole dependency graph is visited and appended.