Converting pyramid to graph in PHP

Converting pyramid to graph in PHP

Created:11 Feb 2020 20:28:38 , in  Maths

Suppose you have a structure like one shown below, lets call it pyramid, and are asked to find all the paths from top to bottom in it, and perhaps also to do something with values of nodes in each path, add them or find their product etc. . How do you achieve these things? In this and the following article I describe a possible way to solve this puzzle using PHP, recursion and graphs.

A pyramid

Here is a tiny pyramid. It is not too difficult to find all the paths from the bottom to the top in it. ( A pharaoh might have wanted to look at the problem from the top to the bottom ;).


   3
  7 4
 2 4 6
8 5 9 3

Life is hardly ever this simple and usually comes with problems more like this one:


              75
             95 64
            17 47 82
           18 35 87 10
          20 04 82 47 65
         19 01 23 75 03 34
        88 02 77 73 07 63 67
       99 65 04 28 06 16 70 92
      41 41 26 56 83 40 80 70 33
     41 48 72 33 47 32 37 16 94 29
    53 71 44 65 25 43 91 52 97 51 14
   70 11 33 28 77 73 17 78 39 68 17 57
  91 71 52 38 17 14 91 43 58 50 27 29 48
 63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

Looking for paths in a structure like this by hand is neither trivial nor advisable. That's what computers have been built for.

Turning a pyramid into a graph

A first step to make a pyramid more manageable involves turning it into an array. Second, converting the array to a tree like graph. You can do both with SWWWPyramidToGraph and SWWWPyramidToGraphNode PHP classes. The latter is a blueprint for graph nodes.


/**
 * Pyramid to Graph class - provides a conversion of pyramid to a graph and a walk method
 * Author: Sylwester Wojnowski
 * Licence: GNU
 */
class SWWWPyramidToGraph{

  /**
   * Static function extractPyramid - load pyramid from file and turn it into an array
   * Arguments: 
   *   filePath - string - [absolute] file path to a file which hold pyramid
   *   separator - separator between two values in pyramid, defaults to " "
   *   lineEnd - end of line separator, "\n" on Linux
   * Return : array  
   */
  public static function extractPyramid($filePath,$separator = " ",$lineEnd = "\n"){
    $data = file_get_contents($filePath);
    $data = trim($data);
    $items = explode($lineEnd,trim($data));
    array_walk($items,function(&$item){ $item = trim($item); });
    foreach($items as $key => $item){
      $it = explode($separator,$item);
      // this assumes the items making up pyramid are all numbers
      $it = array_filter($it,function($str){ return (int)$str; }); 
      $items[$key] = $it; 
    }
    return $items;
  }

  /**
   * Static function build - recucrsively build graph from array
   * Arguments: 
   *   items - array - array representation of pyramid as returned by extractPyramid  
   * Return : graph
   */   
  public static function build($items,$level = 0,$node = NULL,$graph_root = NULL){

    if( $level > count($items) - 1 ){
      return $graph_root;
    }

    if( !isset($node) ){
      $node = new SWWWPyramidToGraphNode;
      $node -> row = 0;
      $node -> col = 0;  
      $node -> value = $items[$level][0];
      $graph_root = $node;
    }
        
    if( isset($items[$level+1]) ){
      if( isset($items[$level+1][$node -> col]) ){
        $no = new SWWWPyramidToGraphNode;
        $no -> row = $node -> row + 1;
        $no -> col = $node -> col;   
        $no -> value = $items[$no -> row][$no -> col];
        $node -> lchild = $no;   
        self::build($items,$level+1,$node -> lchild,$graph_root);
      }

      if( isset($items[$level+1][$node -> col + 1]) ){
        $no = new SWWWPyramidToGraphNode; 
        $no -> row = $node -> row + 1;
        $no -> col = $node -> col + 1;   
        $no -> value = $items[$no -> row][$no -> col];
        $node -> rchild = $no;   
        self::build($items,$level+1,$node -> rchild,$graph_root);
      }
    }
    return $node;
  }
}


/**
 * Graph node class 
 */
class SWWWPyramidToGraphNode{
  public $value = NULL;
  public $lchild = NULL;
  public $rchild = NULL;
  public $row = NULL;
  public $col = NULL;

  public function __construct(){
  }
}

Giving it a spin

Suppose, that our pyramid is in a file called pyramid.txt, which lives in the same directory where the script with the following two lines:


$filePath = getcwd().'/pyramid.txt';
$list = SWWWPyramidToGraph::extractPyramid($filePath);
$graphRoot = SWWWPyramidToGraph::build($list);

The above should give you a nice graph to play with.

Half-conclusion

$graphRoot is the entry point to the resulting graph, its root. What remains, is devise a recursive algorithm for traversing all the possible paths in the graph. A task, which seemed deceptively simple at first, but after few failed attempts turned out to be nothing but. More on that in a follow-up to this piece.

This post was updated on 12 Feb 2020 18:54:15

Tags:  php ,  recursion 


Author, Copyright and citation

Author

Sylwester Wojnowski

Author of the above article, Sylwester Wojnowski, enjoys sWWW writing computer code in PHP, JavaScript and BASH, and some other things he wrote more on on the About page of this website.

Copyrights

©Copyright, 2020 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. "Converting pyramid to graph in PHP." From sWWW - Code For The Web . https://wojnowski.net.pl//main/index/converting-pyramid-to-graph-in-php