Adjacency list representation of directed graph in php
Php program for Adjacency list representation of directed graph. Here problem description and explanation.
<?php
/*
Php Program for
Directed graph representation using adjacency list
*/
class AjlistNode
{
// Vertices node key
public $id;
public $next;
public function __construct($id)
{
// Set value of node key
$this->id = $id;
$this->next = NULL;
}
}
class Graph
{
// Number of Vertices
public $size;
public $node;
public function __construct($size)
{
// Set value
$this->size = $size;
$this->node = array_fill(0, $size, NULL);
$this->setData();
}
// Set initial node value
public function setData()
{
if ($this->size <= 0)
{
printf("\nEmpty Graph\n");
}
else
{
for ($index = 0; $index < $this->size; $index++)
{
// Set initial node value
$this->node[$index] = new Vertices($index);
}
}
}
// Connect two nodes
public function connect($start, $last)
{
$edge = new AjlistNode($last);
if ($this->node[$start]->next == NULL)
{
$this->node[$start]->next = $edge;
}
else
{
// Add edge at the end
$this->node[$start]->last->next = $edge;
}
// Get last edge
$this->node[$start]->last = $edge;
}
// Handling the request of adding new edge
public function addEdge($start, $last)
{
if ($start >= 0 && $start < $this->size &&
$last >= 0 && $last < $this->size)
{
// Safe connection
$this->connect($start, $last);
}
else
{
// When invalid nodes
printf("\nHere Something Wrong\n");
}
}
public function printGraph()
{
if ($this->size > 0)
{
// Print graph ajlist Node value
for ($index = 0; $index < $this->size; ++$index)
{
printf("\nAdjacency list of vertex %d : ",$index);
$temp = $this->node[$index]->next;
while ($temp != NULL)
{
// Display graph node
printf(" %d",$this->node[$temp->id]->data);
// visit to next edge
$temp = $temp->next;
}
}
}
}
public static
function main($args)
{
// 5 implies the number of nodes in graph
$g = new Graph(5);
// Connect node with an edge
$g->addEdge(0, 1);
$g->addEdge(1, 2);
$g->addEdge(1, 4);
$g->addEdge(2, 0);
$g->addEdge(2, 3);
$g->addEdge(4, 3);
// print graph element
$g->printGraph();
}
}
class Vertices
{
public $data;
public $next;
public $last;
public function __construct($data)
{
$this->data = $data;
$this->next = NULL;
$this->last = NULL;
}
}
Graph::main(array());
Output
Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 2 4
Adjacency list of vertex 2 : 0 3
Adjacency list of vertex 3 :
Adjacency list of vertex 4 : 3
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment