6

我有以下array每个项目可能（或可能不依赖）另一个项目：

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

我想移动（或制作另一个array）依赖项移动到顶部。首先a，然后b和d（都取决于a），最后c取决于b。b和的顺序d无关：

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

我很确定这是一种很常见的情况，在重新发明轮子和浪费时间之前，我想知道是否有任何数据结构可以为我完成这项工作。

编辑：忘了说应该检测循环引用（b取决于a不b应该被允许）。

4

5 回答 5

7

这称为拓扑排序。如果您将您的结构视为一个图，其中“a 取决于 b”等于从顶点 b 到顶点 a 的有向边，您应该只进行拓扑排序来获得答案。

拓扑排序的实现可以这样完成：

让 graph[ n ][ n ] 成为与您的数组对应的图（graph[ i ][ j ] = 1 表示 j 取决于 i）。

  1. ans = {} // 空序列
  2. 收入=新数组[ n ]
  3. 收入[ i ] = 进入顶点 i 的边数
  4. used = new array [ n ] // 显示是否已经使用了任何顶点，默认全部为 false
  5. while ans .size != n // 仍然有未使用的顶点
    确实开始
    找到i st 收入[ i ] == 0 并使用[ i ] == false
    ans .append( i )
    用于每个j st图[ i ][ j ] == 1减少 收入[ j ]
    结束
  6. 返回答案
于 2013-04-09T11:57:27.587 回答
3

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);
?>
于 2013-04-09T12:05:07.483 回答
1

I have been inspired by the Wikipedia page Topological Sorting. So I made some self 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 made 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.

于 2014-10-23T21:32:06.177 回答
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()
);

所以我会在 getSorted() 中调用 $type 即“样式表”或“javascripts”

我还做了它，因此它可以使用数组作为“依赖项”而不是字符串来处理多个依赖项。

如果需要简化此上下文，请告诉我，毕竟我确实在对象中创建了它...

干杯!

于 2013-10-25T21:26:37.997 回答
1

测试和工作：

基本上，它遍历每个节点并从树的顶部检查该节点的深度，并将该值附加到一个新数组$ar。然后它$test根据存储在$arusing中的每个节点的深度级别进行排序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);
}
于 2013-04-09T12:23:38.297 回答