<?php

$debug = false;

$graph = new Graph();
$graph->dfs_recursive('c', 'a');
$graph->printDfsSolution();
$graph->printGraph($graph->getGraph());

class Graph
{
	var $graph_arr = array();
	var $solution_arr = array();

	function Graph()
	{
		$this->graph_arr = array();
		
		array_push($this->graph_arr, new Node('a', array('b', 'c', 'd', 'f')));
		array_push($this->graph_arr, new Node('b', array('a', 'c', 'f')));
		array_push($this->graph_arr, new Node('c', array('a', 'b', 'f', 'h', 'i')));
		array_push($this->graph_arr, new Node('d', array('a', 'e', 'f', 'g')));
		array_push($this->graph_arr, new Node('e', array('d')));
		array_push($this->graph_arr, new Node('f', array('a', 'b', 'c', 'd')));
		array_push($this->graph_arr, new Node('g', array('d', 'i')));
		array_push($this->graph_arr, new Node('h', array('c')));
		array_push($this->graph_arr, new Node('i', array('c', 'g')));
		array_push($this->graph_arr, new Node('j', array()));
	}

	function addNode($node)
	{
		global $debug;
		if ($node instanceof Node)
		{
			array_push($this->graph_arr, $node);
		}
		else
		{
			if ($debug)
				echo "<p>ERROR Graph.addNode(): parameter \$node is note an instance of Node.</p>";
		}
	}

	/** prints the entire graph, and all the edges **/
	function printGraph($graph_arr)
	{
		foreach ($graph_arr as $node)
		{
			echo $node->getNodeName();
			$adjacent_nodes = $node->getAdjacentNodes();
			foreach($adjacent_nodes as $a_node)
			{
				echo "\n -> " . $a_node;
			}
			echo "\n";
		}
	}



	/**
	 * Recursive depth-first-search algorithm that looks for a path between $start_node_name and
	 * $finish_node_name. It sets the path in the global array $solution_arr;
	 *
	 * @param string $start_node_name - the starting node
	 * @param string $finish_node_name - the ending node
	 * @return null if no path found, Node if path was found
	 */
	function dfs_recursive($start_node_name, $finish_node_name)
	{
		$start_node = $this->getNode($start_node_name);		//obtain the Node object from the node name
		if ($start_node == null || !($start_node instanceof Node))
		{
			if ($debug)
				echo "<p>ERROR Graph.dfs_recursive(): Start node $start_node_name is not a valid node.</p>";
			return null;
		}

		$start_node->setVisited();							//set starting node to visited
		/* set the starting node to be part of the solution, and if it is not, it is removed later
		 */
		array_push($this->solution_arr, $start_node);

		$finish_node = $this->getNode($finish_node_name);	//obtain the Node object
		if ($finish_node == null || !($finish_node instanceof Node))
		{
			if ($debug)
				echo "<p>ERROR Graph.dfs_recursive(): Finish node $finish_node_name is not a valid node.</p>";
			return null;
		}

		if ($start_node_name == $finish_node_name)			//found the path! woohoo!
		{
			return $start_node;
		}

		$adjacent_nodes = $start_node->getAdjacentNodes();	//find $start_node's neighbors
		foreach($adjacent_nodes as $adjacent_node_name)
		{
			//neighbors are stored by name only to avoid circular references. Get the object
			$adjacent_node = $this->getNode($adjacent_node_name);
			if ($adjacent_node == null || !($adjacent_node instanceof Node))
			{
				if ($debug)
					echo "<p>WARN Graph.dfs_recursive(): Adjacent node $adjacent_node_name is not a valid node.</p>";
				continue;
			}
			//var_dump($adjacent_node);
			$is_node_visited = $adjacent_node->isVisited();
			if (!$is_node_visited)		//if this node was already visited, skip it. Otherwise, check the neighbor
			{
				//recursively check the neighbor
				$result_node = $this->dfs_recursive($adjacent_node_name, $finish_node_name);
				if ($result_node != null)
				{
					return $result_node;		//we found the path! return the result
				}
			}
		}
		//get rid of the latest "solution" node, since searching that path didn't yield a result
		array_pop($this->solution_arr);
		return null;		//no solution :( return null.

	}

	function getDfsSolution() { return $this->solution_arr; }

	//for debugging...
	function printDfsSolution()
	{
		if (is_array($this->solution_arr))
		{
			echo "Solution Array: \n\n";
			foreach ($this->solution_arr as $node)
			{
				echo "->" . $node->getNodeName();
			}
			echo "\n\n";
		}
	}

	function getNode($node_name)
	{
		foreach($this->graph_arr as $node)
		{
			if ($node->getNodeName() == $node_name)
			{
				return $node;
			}
		}
	}

	function getGraph() { return $this->graph_arr; }
}

class Node
{
	var $node_name;
	var $adjacent_nodes;
	var $is_visited;
	function Node($node_name, $adjacent_nodes)
	{
		$this->node_name = $node_name;
		$this->adjacent_nodes = $adjacent_nodes;
	}

	/** returns array of adjacent nodes **/
	function getAdjacentNodes()	{return $this->adjacent_nodes;}
	function getNodeName() {return $this->node_name;}
	function isVisited() { return $this->is_visited; }
	function setVisited(){ $this->is_visited = true; }
}

?>

Solution Array: 

->c->a

a
 -> b
 -> c
 -> d
 -> f
b
 -> a
 -> c
 -> f
c
 -> a
 -> b
 -> f
 -> h
 -> i
d
 -> a
 -> e
 -> f
 -> g
e
 -> d
f
 -> a
 -> b
 -> c
 -> d
g
 -> d
 -> i
h
 -> c
i
 -> c
 -> g
j