Posted on by Kalkicode
Code Graph

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

Comment

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