Reorder an array based on values

I need to reorder an array so that all slugs get loaded before parents, but only if a parent has a value that matches a slug value exactly.

For example, take this array:

Array ( 
    [0] => Array ( 
        [parent] => information_desk_3 
        [slug] => about_dream_portal_1 
    )
    [1] => Array ( 
        [parent] => forum
        [slug] => information_desk_3 
    )
    [2] => Array ( 
        [parent] => about_dream_portal_1 
        [slug] => testing_2
    )
    [3] => Array ( 
        [parent] => testing_2 
        [slug] => information_desk_4 
    )
)

I need it so that it gets ordered as follows:

Array ( 
    [0] => Array ( 
        [parent] => forum
        [slug] => information_开发者_运维技巧desk_3 
    )
    [1] => Array ( 
        [parent] => information_desk_3 
        [slug] => about_dream_portal_1 
    )
    [2] => Array ( 
        [parent] => about_dream_portal_1 
        [slug] => testing_2
    )
    [3] => Array ( 
        [parent] => testing_2 
        [slug] => information_desk_4 
    )
)

But the catch is, it needs to search through all slugs and reorder them so that the slugs come first in the array, before the parents that match the value of that slug. Please someone help me, I've been at it for hours now to no avail.

---

Sounds like what you really have is a graph, and you want a partial ordering of nodes. That means you can solve the problem using standard graph algorithms.

If you build a tree of items where each parent knows about all its children then you can do a breadth-first traversal of the tree to build your partially ordered output.

In your example it's a very simple graph:

forum -> information_desk_3 -> about_dream_portal_1 -> testing_2 -> information_desk_4

If you start at forum and walk down the tree adding nodes to the output list as you go then you'll wind up with the correct order.

If you have multiple disjoint trees then it gets a little trickier, but still shouldn't be too hard. You just need to figure out which nodes are root nodes and then walk each tree in turn.