0

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
Improve this question
4
  • 1
    In case this is for a DIC, have a look at github.com/fabpot/Pimple and components.symfony-project.org/dependency-injection/- if it's not for a DIC consider clarifying your scenario. Commented Feb 6, 2012 at 12:23
  • I think array_walk() function is what you need. Commented Feb 6, 2012 at 12:23
  • what is a DIC? How can I make "pimple" do what I want? Commented Feb 6, 2012 at 12:29
  • DIC means Dependency Injection Container. If you are not after a DIC, please clarify what you are trying to achieve. What is the UseCase here? How will you use class deps in your application? What is the responsibility? Your code example looks odd to me and I cannot understand the purpose, which makes it hard to give an answer to your question. Commented Feb 6, 2012 at 12:43

3 Answers 3

Reset to default
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

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

+1 - But I would add an else condition to your loop in getResolved() and stick the items that don't pass checkDependencies() into their own array and then return both as array('valid' => $valid, 'invalid' => $invalid) instead of just returning $result (the OP wanted both arrays).
@drrcknlsn Yeah, I wasn't to sure about the result format, that's why I used two methods, one for each case.
Ah.. I didn't see the rest of your code and thought it stopped after the getResolved() method. My mistake. :-)
thanks! but I ended up using this: johnkleijn.nl/2010/Topological-sorting-of-JavaScript-files
2

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.

Improve this answer

1 Comment

This solution is clear and easy.
2

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
)
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.