Geek asks and answers

How can I rearrange array elements by moving dependencies on top?

I have the following arraywhere each element may (or may not depend) on another:

$test = array(
    'c' => array(
        'depends' => 'b'
    ),
    'a' => array(),
    'b' => array(
        'depends' => 'a'
    ),
    'd' => array(
        'depends' => 'a'
    ),
);

I want to move (or make another array) with the dependencies moved at the top . First a, then band d(both depend on a), and finally c, which depends on b. Order band ddoes not matter:

$rearranged = array(
    'a' => array(),
    'b' => array(
        'depends' => 'a'
    ),
    'd' => array(
        'depends' => 'a'
    ),
    'c' => array(
        'depends' => 'b'
    ),
);

I'm sure this is a fairly common situation, and before reinventing the wheel and wasting time, I would like to know if there is any data structure that can do the job for me.

: , (b a, b ).

+5
5

. , "a b" b a, , .

:

graph [n] [n] - , ( [i] [j] = 1 , j i).

  • ans = {}//
  • = [n]
  • [i] = ,
  • used = [n]//, - , false
  • while ans.size!= n//

    s.t. [i] == 0 [i] == false
    ans.append(i)
    j s.t. graph [i] [j] == 1 [j]

  • return ans
+6

array_multisort .

<?php

    $test = array(
        'c' => array(
            'depends' => 'b'
        ),
        'a' => array(),
        'b' => array(
            'depends' => 'a'
        ),
        'd' => array(
            'depends' => 'a'
        )
    );

    function sortArray($array= array())
         {
            $depend = array();
            foreach ($array as $key => $value)
            {

                if (isset($value['depends']))
                {
                    $depend[$key] = $value['depends'];
                }
                else
                {
                   $depend[$key] = null;
                }

            }
            return $depend;
         }


         function findCircularReference($array)
         {
            foreach($array as $key=>$value)
            {
               if(isset($array[$value]) && ($array[$value] == $key))
               {
                  return true;
               }
            }
            return false;
         }

         $depend = sortArray($test);
         $checkReference  = findCircularReference($depend);

         if( ! $checkReference)
         {
             array_multisort($depend, SORT_ASC, $test);
         }
         else
         {
             trigger_error("Circular reference", E_USER_ERROR);
         }


         print_r($test);
?>
+3

:

, node node $ar. $test node, $ar, array_multisort().

<?php
$test = array(
    'c' => array(
        'depends' => 'b'
    ),
    'a' => array(),
    'b' => array(
        'depends' => 'a'
    ),
    'd' => array(
        'depends' => 'a'
    ),
);


function getNodeLevel($ar,$n,$ref=array())
{
       if(!isset($ar[$n]['depends'])){return 0;}
       if(in_array($n,$ref)){return -1;}
       $ref[]=$n;
       $r=getNodeLevel($ar,$ar[$n]['depends'],$ref);
       return ($r==-1?-1:$r+1);
}


$ar=array();

foreach($test as $i=>$tmp)
{
    $ar[]=getNodeLevel($test,$i);
}

if(!in_array(-1,$ar))
{
    array_multisort($ar,SORT_ASC,$test);
    print_r($test);
}else{
     trigger_error("Circular reference detected.", E_USER_ERROR);
}
+1

. .

private function getSorted($type)
{
    uasort($this->assets[$type], array($this, 'sortDependancies'));
    return $this->assets[$type];
}

 /**
 * Sorting utility function via uasort from getSorted
 * 
 * @returns sort order
 */
private function sortDependancies($a, $b)
{
    if ( is_array($b['dependant']) && in_array($a['alias'], $b['dependant'])) return -1;

    if ( $a['alias'] == $b['dependant'] ) return -1;

    return 1;
}

js css.

protected $assets = array(
    'stylesheets' => array(
            'main' => array(
                'alias' => 'main',
                'path' => 'somepath.less',
                'dependant' => 'bootstrap'
            ),
            'bootstrap' => (
                'alias' => 'bootstrap',
                'path' => 'bootstrap.css',
                'dependant' => NULL
            )
        ),
    'javascripts' => array()
);

$type, .. "stylesheets", "javascripts" getSorted()

, , "" .

If this context should be simplified, let me know, I still created it inside the object ...

Hooray!

+1
source

I was inspired by the Wikipedia pages Topological sorting . So I made some own algorithm.

/**
 * Class Top
 *
 * @package Lib\Sort
 */
class Top
{
    /**
     * Unsorted nodes
     *
     * @var array
     */
    protected $_nodes = array();

    /**
     * Nodes structure
     *
     * @var array
     */
    protected $_structure = array();

    /**
     * Stored nodes
     *
     * @var array|null
     */
    protected $_sortedNodes;

    /**
     * Stored nodes
     *
     * @var array
     */
    protected $_level = 0;

    /**
     * Status of mode "single non-edge node"
     *
     * @var bool
     * @see setModeSingleNonEdgeNode()
     */
    protected $_singleNonEdgeNode = true;

    /**
     * Get status of "Single non-edge node" mode
     *
     * @return boolean
     * @see setModeSingleNonEdgeNode()
     */
    public function isModeSingleNonEdgeNode()
    {
        return $this->_singleNonEdgeNode;
    }

    /**
     * Set status of "Single non-edge node" mode
     *
     * This status means that sorting will move only first non-edged node to top.
     * Rest non-edge nodes will be added according to sorting in _nodes property
     * In case it will FALSE all nodes will be moved to top.
     *
     * @param boolean $flag
     * @return $this
     */
    public function enableModeSingleNonEdgeNode($flag)
    {
        $this->_singleNonEdgeNode = (bool)$flag;
        return $this;
    }

    /**
     * Add node
     *
     * @param string $name
     * @param array  $dependsOn
     * @throws Exception
     * @return $this
     */
    public function addNode($name, array $dependsOn = array())
    {
        if (null !== $this->_sortedNodes) {
            throw new Exception('Nodes already sorted.');
        }
        $this->_nodes[$name]     = $name;
        $this->_structure[$name] = $dependsOn;
        return $this;
    }

    /**
     * Sort
     *
     * @return array
     */
    public function getSortedNodes()
    {
        if (null === $this->_sortedNodes) {
            $this->_sortedNodes = array();
            //insert non-edged nodes
            $this->_performNonEdgedNodes();
            //insert edged nodes
            $this->_performEdgedNodes();
        }
        return $this->_sortedNodes;
    }

    /**
     * Move node into sorted list
     *
     * @param string $name
     * @throws Exception
     * @return $this
     */
    protected function _moveNodeToSortedList($name)
    {
        $node = $this->_takeNode($name);
        if ($node) {
            $this->_sortedNodes[] = $node;
        } else {
            throw new Exception("The node '$name' has already been taken.");
        }
        return $this;
    }

    /**
     * Take node from the list
     *
     * @param string $name
     * @return string|null
     */
    protected function _takeNode($name)
    {
        if (!isset($this->_nodes[$name])) {
            return null;
        }
        $node = $this->_nodes[$name];
        unset($this->_nodes[$name]);
        return $node;
    }

    /**
     * Perform node sorting
     *
     * @param string $name
     * @return $this
     * @throws Exception
     */
    protected function _performNode($name)
    {
        $node = $this->_takeNode($name);
        if (null === $node) {
            return $this;
        }
        foreach ($this->_structure[$node] as $depNode) {
            $this->_checkCycledEdges($node, $depNode);
            $this->_performNode($depNode);
        }
        $this->_sortedNodes[] = $node;
        return $this;
    }

    /**
     * Check cycled edges
     *
     * @param string $node
     * @param string $edgeNode
     * @return bool
     * @throws Exception
     */
    protected function _checkCycledEdges($node, $edgeNode)
    {
        if (in_array($node, $this->_structure[$edgeNode])) {
            throw new Exception("Cyclic dependencies between $edgeNode and $node.");
        }
        return true;
    }

    /**
     * Perform edged nodes
     *
     * @return $this
     */
    protected function _performEdgedNodes()
    {
        while (!empty($this->_nodes)) {
            $name = current($this->_nodes);
            $this->_performNode($name);
        }
        return $this;
    }

    /**
     * Perform non-edged nodes
     *
     * @return $this
     */
    protected function _performNonEdgedNodes()
    {
        foreach ($this->_structure as $name => $edges) {
            if (!$edges) {
                $this->_moveNodeToSortedList($name);
                if ($this->isModeSingleNonEdgeNode()) {
                    //to add only first node and to add rest non-edge nodes according to sorting in _nodes property
                    break;
                }
            }
        }
        return $this;
    }
}

And did tests for this class:

<?php
namespace Lib\Sort;

/**
 * Class TopTest
 *
 * @package Lib\Sort
 */
class TopTest extends \PHPUnit_Framework_TestCase
{
    public function testBasicSorting()
    {
        $test = new Top();
        $test->addNode('A');
        $test->addNode('B', array('A', 'F'));
        $test->addNode('C', array('B', 'D'));
        $test->addNode('D', array('F'));
        $test->addNode('E', array('A', 'F'));
        $test->addNode('F', array('A'));
        $test->addNode('G');
        $this->assertTrue($test->isModeSingleNonEdgeNode());
        $actual   = $test->getSortedNodes();
        $expected = array('A', 'F', 'B', 'D', 'C', 'E', 'G');
        $this->assertEquals($expected, $actual);
    }

    /**
     * Test sorting of last node with many edges
     *
     * @throws Exception
     */
    public function testLastNodeSorting()
    {
        $test = new Top();
        $test->addNode('A', array());
        $test->addNode('B', array('A', 'F'));
        $test->addNode('C', array('B', 'D'));
        $test->addNode('D', array('F'));
        $test->addNode('E', array('A'));
        $test->addNode('F', array('A', 'E'));
        $actual   = $test->getSortedNodes();
        $expected = array('A', 'E', 'F', 'B', 'D', 'C');
        $this->assertEquals($actual, $expected);
    }

    /**
     * Test sorting disabled mode "Single non-edge node"
     *
     * @throws Exception
     */
    public function testDisabledSingleNonEdgesSorting()
    {
        $test = new Top();
        $test->addNode('A');
        $test->addNode('B', array('A', 'F'));
        $test->addNode('C', array('B', 'D'));
        $test->addNode('D', array('F'));
        $test->addNode('E', array('A'));
        $test->addNode('F', array('A', 'E'));
        $test->addNode('G');
        $test->enableModeSingleNonEdgeNode(false);
        $actual   = $test->getSortedNodes();
        $expected = array('A', 'G', 'E', 'F', 'B', 'D', 'C');
        $this->assertEquals($actual, $expected);
    }

    /**
     * Test exception for cyclic nodes
     *
     * @expectedException \Lib\Sort\Exception
     * @expectedExceptionMessage Cyclic dependencies between E and F.
     */
    public function testCyclicSortingFailure()
    {
        $test = new Top();
        $test->addNode('A', array());
        $test->addNode('B', array('A', 'F'));
        $test->addNode('C', array('B', 'D'));
        $test->addNode('D', array('F'));
        $test->addNode('E', array('A', 'F'));
        $test->addNode('F', array('A', 'E'));
        $test->getSortedNodes();
        //expected an exception
    }

    /**
     * Test exception for cyclic nodes
     *
     * @expectedException \Lib\Sort\Exception
     * @expectedExceptionMessage Nodes already sorted.
     */
    public function testAddNodeAfterSortingFailure()
    {
        $test = new Top();
        $test->addNode('A', array());
        $test->addNode('B', array('A', 'F'));
        $test->addNode('C', array('B', 'D'));
        $test->addNode('D', array('F'));
        $test->addNode('E', array('A'));
        $test->addNode('F', array('A', 'E'));
        $test->getSortedNodes();
        $test->addNode('H', array('E'));
        //expected an exception
    }
}

Maybe it will be useful for someone.

+1
source

More articles:


All Articles