PHP dependency class

Question

The class:

class deps{

  var $items;

  function add($item, $deps = array()){
    $this->items[$item] = $deps;
  }


}

How can I generate an array with $items ordered by taking into account dependencies ($deps) ?

For example:

$deps = new deps;

$deps->add('item2', array('item1'));            // <- depends on item1
$deps->add('item1', array());                   // <- no dependency
$deps->add('item3', array('item1', 'item5'));   // <- depends on item1 and item5
$deps->add('A',     array('item3'));            // <- on item3
$deps->add('C',     array('item2', 'item1'));   // ......

The ordered array would be:

item1
item2
C

And a second array, with items that needed one or more dependencies that didn't exist:

item3       
A

Answer 1

With the data you provided, this did the trick for ordering the dependencies.

function returnOrderedDependencies()
{
    $temporary = $this->items;
    $dependencies = array();

    $isChanged = true;
    while ($isChanged == true) {
        $isChanged = false;
        // Step 1. Search for items without dependencies
        foreach ($temporary as $item => $deps) {
            if (empty($deps)) {
                array_push($dependencies, $item);
                unset($temporary[$item]);
            }
        }
            // Step 2. Remove resolved items from dependencies
        foreach ($temporary as $item => $deps) {
            foreach ($deps as $key => $value) {
                if (in_array($value, $dependencies)) {
                    $isChanged = true;
                    unset($temporary[$item][$key]);
                }
            }
        }
    }
    return $dependencies;
}

The items left in $temporary are the unresolved dependencies and for your data they were returned as expected but I assume this is a coincidence.

I am not sure as to how to order unresolved dependencies, probably by how many dependencies where unresolved for these items.

Answer 2

Something like:

class deps{
  protected $items = array();

  public function add($item, array $deps = array()){
    $this->items[$item] = $deps;
  }

  protected function checkDependencies($item) {
    if (!isset($this->items[$item])) {
      return false;
    }

    foreach ($this->items[$item] as $dep) {
      if (!$this->checkDependencies($dep)) {
        return false;
      }
    }

    return true;
  }

  public function getResolved() {
    $result = array();

    foreach ($this->items as $item => $deps) {
      if ($this->checkDependencies($item)) {
        $result[] = $item;
      }
    }

    return $result;
  }

  public function getUnresolved() {
    $result = array();

    foreach ($this->items as $item => $deps) {
      if (!$this->checkDependencies($item)) {
        $result[] = $item;
      }
    }

    return $result;
  }
}

$deps = new deps;

$deps->add('item2', array('item1'));            // <- depends on item1
$deps->add('item1', array());                   // <- no dependency
$deps->add('item3', array('item1', 'item5'));   // <- depends on item1 and item5
$deps->add('A',     array('item3'));            // <- on item3
$deps->add('C',     array('item2', 'item1'));   // ......

print_r($deps->getResolved());
/*
Array
(
    [0] => item2
    [1] => item1
    [2] => C
)
*/

print_r($deps->getUnresolved());
/*
Array
(
    [0] => item3
    [1] => A
)
*/

http://codepad.org/fSwJjyz5

Answer 3

Bit messy, but returns the correct load order (1, 2, C) and unresolved.

<?php

class Dependencies
{
    private $_items;
    private $_dependencies;

    public function add($item, $dependencies = array())
    {
        $this->_items[$item] = (count($dependencies) > 0) ? $dependencies : null;

        foreach($dependencies as $dependency)
        {
            $this->_dependencies[$dependency][] = $item;
        }
    }

    public function get_load_order()
    {
        $load_order = array();
        $seen       = array();

        foreach($this->_items as $item => $dependencies)
        {
            $tmp = $this->get_dependents($item, $seen);

            if($tmp[2] === false)
            {
                $load_order = array_merge($load_order, $tmp[0]);
                $seen       = $tmp[1];
            }
        }

        return $load_order;
    }

    public function get_failed_items()
    {
        $failed = array();
        $seen   = array();

        foreach($this->_items as $item => $dependencies)
        {
            $tmp = $this->get_dependents($item, $seen);

            if($tmp[2] !== false)
            {
                $failed[] = $item;
                continue;
            }

            $seen = $tmp[1];
        }

        return $failed;
    }

    private function get_dependents($item, $seen = array())
    {
        if(array_key_exists($item, $seen))
        {
            return array(array(), $seen, false);
        }

        if($this->item_exists($item))
        {
            $order          = array();
            $failed         = array();
            $seen[$item]    = true;

            if($this->has_dependents($item))
            {
                foreach($this->_items[$item] as $dependency)
                {
                    $tmp = $this->get_dependents($dependency, $seen);

                    $order  = array_merge($tmp[0], $order);
                    $seen   = $tmp[1];

                    if($tmp[2] !== false)
                    {
                        $failed = array_merge($tmp[2], $failed);
                    }
                }
            }

            $order[]    = $item;
            $failed     = (count($failed) > 0) ? $failed : false;

            return array($order, $seen, $failed);
        }

        return array(array(), array(), array($item));
    }

    private function item_exists($item)
    {
        if(array_key_exists($item, $this->_items))
        {
            return true;
        }

        return false;
    }

    private function has_dependents($item)
    {
        if($this->item_exists($item) AND is_array($this->_items[$item]))
        {
            return true;
        }

        return false;
    }
}

Called:

<?php

$deps = new Dependencies();

$deps->add('item2', array('item1'));            // <- depends on item1
$deps->add('item1');                            // <- no dependency
$deps->add('item3', array('item1', 'item5'));   // <- depends on item1 and item5
$deps->add('A',     array('item3'));            // <- on item3
$deps->add('C',     array('item2', 'item1'));   // ......

$load_order     = $deps->get_load_order();
$failed_items   = $deps->get_failed_items();

echo '<pre>';
echo 'Loaded: ';
print_r($load_order);
echo 'Failed: ';
print_r($failed_items);
echo '</pre>';

Produces:

Loaded: Array
(
    [0] => item1
    [1] => item2
    [2] => C
)
Failed: Array
(
    [0] => item3
    [1] => A
)