Demo entry 3637637

matrixgraph

   

Submitted by anonymous on Feb 15, 2016 at 21:25
Language: PHP. Code size: 6.9 kB.

<?php

const starterHTML = "<html>
<head>
	<style>
		.bold {
			font-weight: bold;
		}
		table {
			border: 1px solid black;
			border-spacing: 0px;
		}
		th, td {
			border: 1px solid #aaa;
			border-spacing: 0px;
			padding: 10px;
		}
	</style>
<body>
";

class MatrixGraph {
	private $nodes;
	private $index;
	private $n;
	private $e;
	private $matrix;
	private $directed;
	private $verbose;

	public function __construct($opts = null) {
		$this->nodes = array();
		$this->n = 0;
		$this->e = 0;
		$this->matrix = array();

		$this->directed = $opts['directed'] ?? true;
		$this->verbose = $opts['verbose'] ?? true;

		echo starterHTML;

		echo "<p><b>Created a" . ($this->directed ? ' ' : 'n un') . "directed graph</b></p>\n";
	} # function __construct()

	public function __destruct() {
		echo "<p><b>Deleted a" . ($this->directed ? ' ' : 'n un') . "directed graph</b></p>\n";
		echo "</body>\n</html>\n";
	}

	public static function new($opts = null) {
		return new MatrixGraph($opts);
	} # function new()

	public function nodes() {
		return $this->n;
	} # function nodes()

	public function edges() {
		return $this->e;
	} # function edges()

	public function getMatrix() {
		return $this->matrix;
	}

	public function addNode($u) {
		$this->nodes[$u] = $u;
		$this->n++;

		foreach($this->matrix as &$row) {
			$row[$u] = null;
		}
		$newRow = array();
		foreach($this->nodes as $node) {
			$newRow[$node] = null;
		}
		$this->matrix[$u] = $newRow;

		if ($this->verbose) htmlOut("Added Node", $u);
	} # function addNode()

	public function removeNode($u) {
		unset($this->matrix[$u]);
		unset($this->nodes[$u]);
		$this->n--;
		if ($this->verbose) htmlOut("Removed Node", "{$u}");
		foreach($this->matrix as &$node) {
			unset($node[$u]);
		}
	} # function removeNode()

	public function addEdge($u, $v, $w = 1) {
		if(isset($this->nodes[$u], $this->nodes[$v])) {
			$this->matrix[$u][$v][] = $w;
			$this->e++;
			if ($this->verbose) htmlOut("Added Edge", "{$u}->{$v} w:{$w}");
			if (!$this->directed && $u !== $v) {
				$this->matrix[$v][$u][] = $w;
				$this->e++;
				if ($this->verbose) htmlOut("Added Edge", "{$v}->{$u} w:{$w}");
			}
		} else {
			echo "Error: Tried to add an edge between {$u} and {$v}. One or" .
				" both of these nodes does not exist. Skipping.\n";
		}
	} # function addEdge()

	public function removeEdge($u, $v, $w) {
		if(isset($this->nodes[$u], $this->nodes[$v], $this->matrix[$u][$v])) {
			foreach($this->matrix[$u][$v] as $key => $weight) {
				if ($weight === $w) {
					if ($this->verbose) htmlOut("Removed Edge", "{$u}->{$v} w:{$w}");
					unset($this->matrix[$u][$v][$key]);
					$this->e--;
					if (!$this->directed) {
						if ($this->verbose) htmlOut("Removed Edge", "{$v}->{$u} w:{$w}");
						unset($this->matrix[$v][$u][array_search($w, $this->matrix[$v][$u])]);
						$this->e--;
					}
					return;
				}
			}
		}
		
		echo "Notice: Tried to remove a nonexistent edge ({$u}->{$v} with weight {$w})\n";
	}

	public function edgeExists($u, $v) {
		return ($this->matrix[$u][$v] != null);
	} # function edgeExists()

	public function nodeExists($u) {
		return isset($this->nodes[$u]);
	} # function nodeExists()

	public function edgesOut($u) {
		$neighbors = array();

		foreach($this->nodes as $i) {
			if ($this->matrix[$u][$i] != null) {
				$neighbors[] = $i;
			}
		}
		return $neighbors;
	} # function edgesOut()

	public function edgesIn($u) {
		$neighbors = array();

		foreach($this->nodes as $i) {
			if ($this->matrix[$i][$u] != null) {
				$neighbors[] = $i;
			}
		}
		return $neighbors;
	} # function edgesIn()

	public function getEdge($u, $v) {
		if($this->matrix[$u][$v] === null) {
			return array();
		} else {
			return $this->matrix[$u][$v];
		}
	} # function getEdge()

	public function setEdge($u, $v, $w, $newW) {
		if($this->matrix[$u][$v] === null) {
			echo "Error: Tried to set edge weight between {$u} and {$v}. No such edge exists.\n";
			return;
		} else {
			foreach($this->matrix[$u][$v] as &$weight) {
				if ($weight == $w) {
					$weight = $newW;
					if ($this->verbose) htmlOut("Altered Edge", "{$u}->{$v}, Weight changed from {$w} to {$newW}");
					return;
				}
			}
			echo "Error: Tried to set edge weight between {$u} and {$v} with weight {$w}. No such edge exists.\n";
		}
	} # function getEdge()

	public function edgeList() {
		echo "<fieldset>\n<legend>Edge List</legend>\n";
		htmlOut("Nodes", $this->n);
		htmlOut("Edges", $this->e);
		echo "<table>\n<tr class='bold'>\n<td>Source</td>\n<td>Destination</td>\n<td>Weight</td>\n</tr>\n";
		foreach($this->nodes as $row) {
			foreach($this->nodes as $col) {
				if ($this->matrix[$row][$col] !== null) {
					foreach($this->matrix[$row][$col] as $weight)
						echo "<tr>\n<td>{$row}</td>\n<td>$col</td>\n<td>{$weight}</td>\n</tr>\n";
				}
			}
		}
		echo "</table>\n</fieldset>\n";
	} # function edgeList()

	public function printMatrix() {
		echo "<fieldset>\n<legend>Matrix</legend>\n";

		htmlOut("Nodes", $this->n);
		htmlOut("Edges", $this->e);

		echo "<table>\n<tr>\n<td>&nbsp;</td>\n";

		foreach($this->nodes as $col) {
			echo "<td class='bold'>{$col}</td>\n";
		}

		echo PHP_EOL;
		
		foreach($this->nodes as $row) {
			echo "<tr>\n<td class='bold'>{$row}</td>\n";
			foreach($this->nodes as $col) {
				echo "<td>";
				if(is_array($this->matrix[$row][$col])) {
					$out = "";
					foreach($this->matrix[$row][$col] as $weight) {
						$out .= $weight . ', ';
					}
					echo substr($out, 0, -2) . "\t";
				} else {
					echo "-\t";
				}
				echo "</td>\n";
			}
			echo "</tr>\n";
		}

		echo "</table>\n</fieldset>\n";
	} # function printMatrix()

	public function bfs($u) {
		if(!isset($this->matrix[$u])) {
			echo "Error: Attempted BFS using {$u}. {$u} is not a node in the graph.";
			return;
		}
		$bfs = array($u => array());

		while ( ($neighborArray = current($bfs)) !== FALSE ) {
			$node = key($bfs);
			foreach($this->matrix[$node] as $neighbor => $weight) {
				if($weight !== null && !isset($bfs[$neighbor])) {
					$bfs[$neighbor] = array();
					$bfs[$node][$neighbor] = $weight[0];
				}
			}
			next($bfs);
		}

		return $bfs;

	} # function bfs()

	public function dfs($u, &$dfs) {
		if(!isset($this->matrix[$u])) {
			echo "Error: Node {$u} not found in graph.";
			return;
		}

		// If Node $u is not in the $dfs array, it has not been visited
		if(!isset($dfs[$u])) {
			$dfs[$u] = null;
			foreach($this->matrix[$u] as $neighbor => $weights) {
				if($weights !== null) {
					$dfs[$u][$neighbor] = $weights[0];
					$this->dfs($neighbor, $dfs);
				}
			}
		}

	} # function dfs()
}

function htmlOut($start, $text){
	echo "<p><b>{$start}: </b>{$text}</p>\n";
}

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).