How can I rearrange array items moving dependencies on top?
algorithm, arrays, multidimensional-array, php
Solution
This is called topological sorting. If you consider your structure as a graph, where "a depends on b" is equal to a directed edge from vertex b to vertex a, you should just do a topological sort to get your answer.
Implementation of topological sort can be done like this:
let graph[ n ][ n ] be the graph corresponding to your array (graph[ i ][ j ] = 1 means j depends on i).
- ans = {} // empty sequence
- income = new array[ n ]
- income[ i ] = number of edges incoming to vertex i
- used = new array[ n ] // shows if any vertex has already been used, default all false
- while ans.size != n // there are still unused vertexes do begin find i s.t. income[ i ] == 0 and used[ i ] == false ans.append( i ) for each j s.t. graph[ i ][ j ] == 1 decrement income[ j ] end
- return ans
Problem
I have the following `array` where each item may (or may not depend) on another one: ``` $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 dependencies are moved at the top. First `a`, then `b` and `d` (both depend on `a`) and finally `c` which depends on `b`. The order of `b` and `d` is irrelevant: ``` $rearranged = array( 'a' => array(), 'b' => array( 'depends' => 'a' ), 'd' => array( 'depends' => 'a' ), 'c' => array( 'depends' => 'b' ), ); ``` I'm pretty sure that this is a quite common situation and before reinventing the wheel and waste time I'd like to know if there is any data structure that can do the job for me. EDIT: forgot to say that circular references should be detected (`b` depends on `a` that depends on `b` should not be allowed).