Algorithm to sort array based on parent child relationship

Question

I have an array of controls that includes name and the list of controls that are to be rendered first. Following is the array:

$controls [0] = array ("name" => "combobox", array ("countryStore", "center" ) );
$controls [1] = array ("name" => "docBody", array () );
$controls [2] = array ("name" => "top", array ("docBody" ) );
$controls [3] = array ("name" => "button1", array ("formPane" ) );
$controls [4] = array ("name" => "center", array ("docBody" ) );
$controls [5] = array ("name" => "text1", array ("formPane" ) );
$controls [6] = array ("name" => "countryStore", array ("center" ) );
$controls [7] = array ("name" => "formPane", array ("center" ) );

I need to arrange the array of controls in correct order such that whenever I render a control all of it pre-requisite controls are already rendered.

Is there any function in PHP that can sort this kind of relationship?

Required Output

$controls [0] = array ("name" => "docBody", array () );
$controls [1] = array ("name" => "top", array ("docBody" ) );
$controls [2] = array ("name" => "center", array ("docBody" ) );
$controls [3] = array ("name" => "formPane", array ("center" ) );
$controls [4] = array ("name" => "countryStore", array ("center" ) );
$controls [5] = array ("name" => "combobox", array ("countryStore", "center" ) );
$controls [6] = array ("name" => "button1", array ("formPane" ) );
$controls [7] = array ("name" => "text1", array ("formPane" ) );

Code After Sort:

$sortedArray = $SortControls($controls);
foreach ($sortedArray as $control) {
    System->getControl($control['name'])->render();
}

Eyal Schneider · Accepted Answer · 2014-02-02 13:09:06Z

5

I am not familiar with PHP, but...

Your data can be used to define a graph, where nodes are your entities (e.g. "text1", "formPane"), and dependencies between them are directed edges.

If this directed graph is acyclic (DAG), then topological sorting is a simple algorithm to achieve the ordering you want.

This algorithm can also detect a cycle, which means that such ordering is impossible.

answered Feb 2, 2014 at 13:09

Eyal Schneider

22.5k5 gold badges51 silver badges79 bronze badges

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

3 Comments

asim-ishaq Over a year ago

Can you share some algorithm for sorting this array?

Eyal Schneider Over a year ago

@asim-ishaq: The pseudocode can be found in the link I provided. The first algorithm iteratively adds nodes with no incoming edges to the output list. Each such node is then removed from the graph, together with its outgoing edges. When removing the edges, you can discover new nodes with no incoming edges.

Ostati Over a year ago

Why is this not an accepted answer. I think all that is needed is provided.

Collectives™ on Stack Overflow

Algorithm to sort array based on parent child relationship

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related