Skip to main content

Adjacency list representation of undirected graph in php

Php program for Adjacency list representation of undirected graph. Here problem description and explanation.

<?php
/*
    Php Program for 
    Undirected graph representation by 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 Vertices
{
	public $data;
	public $next;
	public $last;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->next = NULL;
		$this->last = 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++)
			{
				$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)
		{
			$this->connect($start, $last);
			if ($start == $last)
			{
				// When self loop
				return;
			}
			$this->connect($last, $start);
		}
		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(0, 2);
		$g->addEdge(0, 4);
		$g->addEdge(1, 2);
		$g->addEdge(1, 4);
		$g->addEdge(2, 3);
		$g->addEdge(3, 4);
		// print graph element
		$g->printGraph();
	}
}

Graph::main(array());

Output

Adjacency list of vertex 0 : 1 2 4
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 0 1 3
Adjacency list of vertex 3 : 2 4
Adjacency list of vertex 4 : 0 1 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