# PHP implementation of “depth-first search” on the graph data structure

As I am a totally self-taught 'person writing code', I decided to learn algorithms with one online course that taught them using Java for demonstrative purposes. The first topic I covered is the graph data structure and API.

I undertook to rewrite Java examples into PHP for training purposes. I would be really grateful if you could review this code and point to its biggest shortcoming.

It was not always possible to reproduce certain behaviours and data structure that are found in Java so I had to resort to some workarounds.

Here is the code with explanations:

/**
* Bag stores all vertices adjacent to a given vertex.
* It's here to imitate Java's 'Bag' data structure
*/
class Bag implements IteratorAggregate
{
public $vs = array(); public function getIterator() { return new ArrayIterator($this->vs);
}
}


-

class Graph
{

private $V; /* Adjacent vertices */ private$adj = array();

/**
* @param int $V The total number of vertices in the graph */ public function __construct($V)
{
$this->V =$V;
for ($v = 0;$v < $V;$v++) {
$this->adj[$v] = new Bag;
}
}

/**
* Throw all adjacent vertices of a given vertex into this vertex' Bag.
* This will create 'edges' - connection between vertices.
*
* @param int $v Vertex to connect * @param int$w Vertex to connect
*/
public function addEdge($v,$w)
{
$this->adj[$v]->vs[] = $w;$this->adj[$w]->vs[] =$v;
}

/**
* @return Bag All ajacent vertices of a given vertex
*/
public function returnBag($v) { return$this->adj[$v]; } public function returnAllVertices() { return$this->adj;
}

}


-

class DepthFirstPath
{
private $marked = array(); /* This array stores parent-link representation of a tree rooted at$s (source) */
private $edgeTo = array(); private$s;

/**
* @param Graph $G An instance of the graph * @param int$s Source vertex to start the recursive traversal from
*/
public function __construct(Graph $G,$s)
{
$allVertices =$G->returnAllVertices();

/* Set all verices in the graph as unvisited/unmarked */
foreach($allVertices as$key => $value) {$this->marked[$key] = false; foreach($value->vs as $v) {$this->marked[$v] = false; } }$this->s = $s;$this->dfs($G,$s);

}

/**
* 'Depth-first search'
*
* A recursive function that will visit all adjacent vertices of each vertex
* and mark each of them as 'visited'
*/
private function dfs(Graph $G,$v)
{
$this->marked[$v] = true;
$adjToV =$G->returnBag($v); foreach($adjToV as $w) { if ( !$this->marked[$w] ) {$this->dfs($G,$w);
$this->edgeTo[$w] = $v; } } } public function hasPathTo($v)
{
return $this->marked[$v];
}

/**
* Find a path from the source to a given vertex
*/
public function pathTo($v) { if ( !$this->hasPathTo($v)) { return null; }$path = new \SplStack;
for ($x =$v; $x !=$this->s; $x =$this->edgeTo[$x]) {$path->push($x); }$path->push($this->s); return$path;
}
}


This is how the client might use it (feel free to copy, paste and try it):

$graph = new Graph(10);$graph->addEdge(1,2);
$graph->addEdge(2,3);$graph->addEdge(3,4);
$graph->addEdge(1,6);$graph->addEdge(8,9);

$path = new DepthFirstPath($graph, 1);
\$path->pathTo(4);


What have I done wrong, what could I improve, what rules have I violated ?

• Those who use one-letter names for non-trivial variables have committed a grievous sin; their blood shall be upon them. – cHao Apr 9 '15 at 8:55
• @cHao this indeed was my consideration, but if you follow the code closely, you will notice that there are only few variables all along and that giving them descriptive names would actually dilute its readability - it's one of those cases. – luqo33 Apr 9 '15 at 22:13

## 1 Answer

It's totally unnecessary to have a Bag class if all you do is reach through to its only field.

Generally, all your classes should either have multiple fields or engage in some kind of non-trivial validation or data-hiding to justify the necessity for a class.

• This is a fair point. I agree that such implementation of Bag does not make much sense in this instance. However, I'm planning to expand my graph API with further functionalities like "width-first serarch", finidng the "Eulerian path", etc. I imitated Java's Bag in case it would have to be extended later on. – luqo33 Apr 9 '15 at 18:25
• @luqo33: There's a middle ground between not thinking of the future, and worrying so much about it that you end up with unnecessary complexity "just in case". You could just as easily start with a plain old array at first, maybe keeping the Bag idea in mind in case the added complexity does justify itself. – cHao May 11 '15 at 19:48