![Walking pyramid graph paths in PHP Walking pyramid graph paths in PHP](https://swww.com.pl/media/img/post/67_head.jpg)
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
![Sylwester Wojnowski](https://swww.com.pl/media/img/gravatar_110.png)
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.
Copyrights
©Copyright, 2024 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
Cite this article as:
Wojnowski, Sylwester. "Walking pyramid graph paths in PHP." From sWWW - Code For The Web . https://swww.com.pl//main/index/walking-pyramid-graph-paths-in-php
Add Comment