 # Walking pyramid graph paths in PHP

Created:12 Feb 2020 19:53:09 , in  Maths

This article is a follow-up to my text about turning a pyramid like structure into a graph (which looks a lot like a tree, but isn't one), finding all the paths in the graph and collecting all the values held by vertices in each path of it. In the first article I stopped at generating ready to use graph, in this one I collect data from each path in it.

Here is the first part of this series.

## Walking paths of graph

For the needs of this case a path is defined as a set of edges and nodes leading from a node on the lowest level of the graph to the top one in it. Only upwards movement is allowed.

## Walk function in PHP

Code below, function called "walk" is an extension to SWWWPyramidToGraph class (copy and paste). It uses post-order tree traversal technique, which means, that the left and right child is being processed first and then the node itself (there are is no vertex connected to other vertex with more than 2 edges in these graphs). You start from the "very bottom" level of node in the graph and recursively work you way up till you reach the "top node".

``````
/**
* function walk - recursively traverse all paths in a graph and return lists of values
* held by vertices in each of them
* Arguments:
*   node - object - starting node of graph
* Return:
*   array of arrays
*/
public static function walk(\$node,\$values = []){
if( isset(\$node -> lchild) && isset(\$node -> rchild) ){

\$left = self::walk(\$node -> lchild,\$values);
\$right = self::walk(\$node -> rchild,\$values);

\$values = array_merge(\$left,\$right);

foreach(\$values as \$key => \$items){
\$values[\$key][] = \$node -> value;
}

return \$values;

} else {
\$values[] = [\$node -> value];
return \$values;
}
}
``````

## Taking a walk

For a graph that looks this one:

``````
A      <- level 1
/ \
B   C    <- level 2
/ \ / \
D   E   F  <- level 3
``````
``````
SWWWPyramidToGraph::walk(\$graph);
=> [[D,B,A],[E,B,A],[E,C,A],[F,C,A]]
``````

## Conclusion

Presented here methods is a brute force one, sufficient for majority of small graphs with several or *teen levels. For larger graphs, especially if finding the minimum or the maximum total cost is the goal you might want to look at Kruskal or Prim algorithms for finding minimum spanning tree of a graph.

This post was updated on 12 Feb 2020 19:59:57

## Author, Copyright and citation

### Author Author of the this article - Sylwester Wojnowski - is a sWWW web developer. He has been writing computer code for the websites and web applications since 1998.

©Copyright, 2022 Sylwester Wojnowski. This article may not be reproduced or published as a whole or in parts without permission from the author. If you share it, please give author credit and do not remove embedded links.

Computer code, if present in the article, is excluded from the above and licensed under GPLv3.

### Citation

Wojnowski, Sylwester. "Walking pyramid graph paths in PHP." From sWWW - Code For The Web . https://wojnowski.net.pl//main/index/walking-pyramid-graph-paths-in-php

## You might also like

• ### Turning OOP class to graph for better code composition and understanding

MATHS

• ### Using arrow functions for recursive post-order tree traversal

MATHS

• ### Transforming range of variable to 0 to 1 and custom ranges

MATHS

• ### Checking trees for sameness with recursion and spaceship operator in PHP

MATHS

• ### Two indispensable formulas for percentages

MATHS

Allowed BB Code - style tags: [b][/b], [i][/i], [code=text][/code],[code=javascript][/code],[code=php][/code],[code=bash][/code],[code=css][/code],[code=html][/code]

I constent to processing my data given through this form for purposes of a reply by the administrator of this website.