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

Tags:  php ,  recursion