Finding Minimum Spanning Tree with Prim's Algorithm and PHP

Created:02 Mar 2020 02:10:42 , in  Maths

Minimum spanning tree (MST) is an edge subset of edge-weighed undirected graph, that connect all the vertices together with the minimum possible total edge weight. There are a few methods of finding minimum spanning tree of a graph. One such efficient method is called Prim's Algorithm.

How Prim's algorithm works

Prim's Algorithm is recursive. In the first step any vertex belonging to a graph is chosen. In the second step, the lightest edge is included in the tree (Edge is specified by two vertices, current and next. Next vertex becomes new current). Step two is repeated till all vertices in graph are visited exactly once and included in the tree.

Minimum spanning tree is a graph without loops, hence traverseable using usual tree traversal algorithms. Traversing minimum spanning tree is required to find total minimum weight of the tree.

Prim's algorithm implementation in PHP

This article provides a configurable recursive minimum-heap-data-structure-based implementation of Prim's algorithm in PHP programming language. The implementation works on a graph made up of PHP object(s), and as an extra, provides a method for finding total minimum weight of minimum spanning tree using pre-order tree traversal technique.

/**
 * Class Prim's Algorithm - implementation for finding minimum spanning trees for a graph
 * and minimum spanning tree traversal cost calculation
 * Author : S.Wojnowski
 * Licence : GNU v3
 */
class SWWWPrimsAlgorithm{

  protected $vertices = [];
  private $mstFound = NULL;
  // properties seteable at init
  protected $vertexIdProp = 'id';
  protected $linkingProp = 'adjacent';
  protected $costProp = 'cost'; 
  protected $mstEdgeProp = 'mst_edge';
  public $graph = NULL;

  public function __construct($graph, $conf = []){
    $this -> graph = $graph;

    // setup user custom property names
    foreach(['vertexIdProp','linkingProp','costProp','mstEdgeProp'] as $prop){
      if(isset($conf[$prop])){ $this -> {$prop} = $conf[$prop];}
    }
  }

  /**
   * Find all graph's vertex ids and store them as assoc array
   * Used by Prim's Algorithm for traversing graph
   */
  public function findVertices($vertex = NULL){
    // set vertex to start traversing with
    if(!isset($vertex)){
      $vertex = $this -> graph;
    }

    // exit if vertex id in vertices already
    if(array_key_exists($vertex -> {$this -> vertexIdProp},$this -> vertices)){
      return $this -> vertices;
    }

    // add current vertex to vertices 
    $this -> vertices[$vertex -> {$this -> vertexIdProp}] = true;     

    $adjacent = 0;
    // visit adjacent vertices of current vertex
    while( property_exists($vertex,$this -> linkingProp.$adjacent) ){
      $this -> vertices = $this -> findVertices($vertex -> {$this -> linkingProp.$adjacent});
      $adjacent++;
    }
    return $this -> vertices;
  }

  /**
   * Minimum Spanning Tree (MST) using Prim's algorithm
   */
  public function mst($vertex = NULL){

    // set vertex to start with
    if(!isset($vertex)){
      $vertex = $this -> graph;

      // if mst was found earlier 
      if( isset($this -> mstFound)){ 
        if($this -> mstFound -> {$this -> vertexIdProp} === $vertex -> {$this -> vertexIdProp}){
          return $this -> graph;  
        } else { 
          throw new Exception('Graph has MST on it. Call reset method to remove MST and try again.');
        }
      }

      // find vetices, if consumed earlier
      if(empty($this -> vertices)){
        $this -> findVertices($vertex);
      }
    }

    // unset visited vertex in vertices
    unset($this -> vertices[$vertex -> {$this -> vertexIdProp}]); 

    // traverse adjacent vertices by their weight, weight is found by MinHeap data structure
    $heap = new SplMinHeap();
    $adjacent = 0;
    // if there is at least one adjacent vertex
    while(property_exists($vertex,$this -> linkingProp.$adjacent)){
      // put vertex being traverse in the heap
      if(
        array_key_exists(
          $vertex -> {$this -> linkingProp.$adjacent} -> {$this -> vertexIdProp},
          $this -> vertices
        )
      ){ 
        $heap -> insert([
          $vertex -> {$this -> linkingProp.$adjacent} -> {$this -> costProp}[$vertex -> {$this -> vertexIdProp}],
          $vertex -> {$this -> linkingProp.$adjacent}]
        );
      }
      $adjacent++; 
    }

    // traverse vertices with heap 
    if(!$heap -> isEmpty()){
      // deal with children here
      $mstEdgeCount = NULL; // new
      for ($heap->top(); $heap->valid(); $heap->next()) {

        list($cost,$v) = $heap -> current();
        
        if(array_key_exists($v -> {$this -> vertexIdProp}, $this -> vertices)){

          if($mstEdgeCount !== NULL){
            $mstEdgeCount += 1;
          } else {
            $mstEdgeCount = 0; 
          }
 
          $vertex -> {$this -> mstEdgeProp.$mstEdgeCount} = $v; 
          $this -> mst($v);
        }
      }
    }  

    $this -> mstFound = $this -> graph;  
    return $this -> graph;    
  }

  /**
   * calculate total cost of walking the mst starting with a vertex
   * mst must exist on graph for this method to return cost
   */   
  public function calculateCost($vertex = NULL,$cost = NULL){
    if(!isset($vertex)){
      $vertex = $this -> graph;
    }

    // if no adjacent vertices to current vertex, exit
    if(!isset($vertex -> {$this -> mstEdgeProp.'0'})){
      return $cost;
    }
   
    // traverse adjacent vertices to the current one
    $counter = 0;
    while(isset($vertex -> {$this -> mstEdgeProp . $counter})){
      $siblingCost = $vertex -> {$this -> mstEdgeProp.$counter} -> {$this -> costProp}[$vertex -> {$this -> vertexIdProp}];
 
      if(isset($cost)){
        $cost += $siblingCost;
      }else{
        $cost = $siblingCost;
      }    

      $cost = $this -> calculateCost($vertex -> {$this -> mstEdgeProp.$counter},$cost);
      $counter++;
    }

    return $cost;
  }

  /**
   * remove mst from the graph and set mstFound to NULL
   * mstFound = NULL means no minimum spanning tree exists on the graph for a vertex
   * run mst method to find mst after running this method  
   */
  public function reset($vertex = NULL){
    if(!isset($vertex)){
      $vertex = $this -> graph;
    }

    // do nothing is there is no edge set 
    if(!isset($vertex -> {$this -> mstEdgeProp.'0'})){
      return;
    }
   
    $counter = 0;
    while(isset($vertex -> {$this -> mstEdgeProp.$counter})){  

      $sibling = $vertex -> {$this -> mstEdgeProp.$counter};
      unset($vertex -> {$this -> mstEdgeProp.$counter});

      $this -> reset($sibling);
      $counter++;
    }
    $this -> mstFound = NULL;
    return $this;
  }
}

Use examples

Consider a undirected graph like one below. It has vertices {a,b,c,d,e} and edge with weights: {a,b} = 1, {a,c} = 3, {c,e} = 4, {d,e} = 5 and {a,d} = 2.

     a
    /|\
 1 /3| \2 
  /  |  \
  b  c   d
     4\ /5
       e

Translating the above into PHP code:

    
// each object must have unique id property assigned
$e = (object)['id' => 'e'];
$d = (object)['id' => 'd'];
$c = (object)['id' => 'c'];
$b = (object)['id' => 'b'];
$a = (object)['id' => 'a'];

// add edges,
// adjacentN is property with, 
// vertices are linked with
$e -> adjacent0 = $c;
$e -> adjacent1 = $d;

$d -> adjacent0 = $a;
$d -> adjacent1 = $e;

$c -> adjacent0 = $a;
$c -> adjacent1 = $e;   

$b -> adjacent0 = $a;

$a -> adjacent0 = $b;
$a -> adjacent1 = $c;
$a -> adjacent2 = $d; 

// add cost to each edge, cost of traveling from vertex with id "a" to vertex with id "b" is 1
$a -> cost['b'] = 1;
$a -> cost['c'] = 3;
$a -> cost['d'] = 2;
    
$b -> cost['a'] = 1;

$c -> cost['a'] = 3;
$c -> cost['e'] = 4;

$d -> cost['a'] = 2;
$d -> cost['e'] = 5;
   
$e -> cost['c'] = 4;
$e -> cost['d'] = 5;  

// instantiate SWWWPrimsAlgorithm class and pass one of graph's vertices to it 
$pa = new SWWWPrimsAlgorithm($a);

// find minimum spanning tree
// $a is used as the starting vertex,
// first vertex of minimum spanning tree is returned
$pa_mst = $pa -> mst(); 

// minimum spanning tree is set on the graph now,
// calculate minimum cost of traversing the minimum spanning tree 
$cost = $pa -> calculateCost();
=> 12

It is possible to calculate another minimum spanning tree by setting another vertex to $graph public property of $pa and repeating the procedure as specified above:

// reset $pa object
$pa -> reset();
// set a new vertex to start looking for minimum spanning tree from ($d here)
$pa -> graph = $d;
// find minimum spanning tree and return it
$pa_mst = $pa -> mst();
// calculate minimum cost of traversing the minimum spanning tree
$cost = $pa -> calculateCost();
=> 10

The next example shows how to set what property name vertices have for their property id and a few other seteable properties. These properties are used internally by the class and have been made seteable to avoid clashes in a case when objects making up vertices of a graph already use any of them for some other purpose. Consider graph below:

   aa
   | \
   |  \3
   |   \
  5|    cc
   |   /
   |  /4
   | /
   bb

// each vertes has propert ID rather than id as above now 
$cc = (object)['ID' => 'cc'];
$bb = (object)['ID' => 'bb'];
$aa = (object)['ID' => 'aa'];

// this time vertices are linked using property adjN of vertex object where N is a number between 0 and 2 for the graph above
$bb -> adj0 = $aa;
$bb -> adj1 = $cc;

$aa -> adj0 = $bb;
$aa -> adj1 = $cc;

$cc -> adj0 = $bb;
$cc -> adj1 = $aa;

// edge weights are specified using property "ct" rather than cost as in the example above
$bb -> ct['aa'] = 5;
$bb -> ct['cc'] = 4;

$aa -> ct['bb'] = 5;
$aa -> ct['cc'] = 3;

$cc -> ct['aa'] = 3;
$cc -> ct['bb'] = 4; 
 
// instantiate new object with vertex property names reflecting names in vertex objects
$pa = new SWWWPrimsAlgorithm($aa,[
  'vertexIdProp' => 'ID', // set vertex's id property name
  'linkingProp' => 'adj', // set vertex's linking property name
  'costProp' => 'ct', // set vertex cost property name
  'mstEdgeProp' => 'me' // set vertex's minimum spanning tree linking property name [optional]
]);

// set up minimum spanning tree 
$pa_mst = $pa -> mst();

// calculate cost of traversing the minimum spanning tree
$pa -> calculateCost(); 
=> 7 

Conclusion

Prim's algorithm looks very simple, but turns out to be fairly complicated to implement. One difficulty stems from the fact it is recursive, another, that in order to find a minimum spanning tree for a graph each vertex has to be traversed once only. Thirdly, weight of vertices at each vertex must be considered before the next step can be taken. SplMinHeap PHP class helps to simplify the last requirement.

I hope you have enjoyed the article and found the code useful for your own projects.

This post was updated on 02 Mar 2020 13:05:15

Tags:  php ,  recursion