Skip to main content

Find all mother vertex of a directed graph in kotlin

Kotlin program for Find all mother vertex of a directed graph. Here more information.

/*
    Kotlin program for 
    Find all Mother Vertex in a Graph
*/
class AjlistNode
{
	// Vertices node key
	var id: Int;
	var next: AjlistNode ? ;
	constructor(id: Int)
	{
		// Set value of node key
		this.id = id;
		this.next = null;
	}
}
class Vertices
{
	var data: Int;
	var next: AjlistNode ? ;
	var last: AjlistNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.next = null;
		this.last = null;
	}
}
class Graph
{
	// Number of Vertices
	var size: Int;
	var node: Array < Vertices ? > ;
	constructor(size: Int)
	{
		// Set value
		this.size = size;
		this.node = Array(size)
		{
			null
		};
		this.setData();
	}
	// Set initial node value
	fun setData(): Unit
	{
		if (this.size <= 0)
		{
			println("\nEmpty Graph");
		}
		else
		{
			var index: Int = 0;
			while (index < this.size)
			{
				// Set initial node value
				this.node[index] = Vertices(index);
				index += 1;
			}
		}
	}
	//  Handling the request of adding new edge
	fun addEdge(start: Int, last: Int): Unit
	{
		if (start >= 0 && start < this.size && 
            last >= 0 && last < this.size)
		{
			// Safe connection
			val edge: AjlistNode = 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;
		}
		else
		{
			// When invalid nodes
			println("\nHere Something Wrong");
		}
	}
	fun printGraph(): Unit
	{
		if (this.size > 0)
		{
			var index: Int = 0;
			// Print graph ajlist Node value
			while (index < this.size)
			{
				print("\nAdjacency list of vertex " + index + " :");
				var temp: AjlistNode ? = this.node[index]?.next;
				while (temp != null)
				{
					// Display graph node 
					print("  " + this.node[temp.id]!!.data);
					// Visit to next edge
					temp = temp.next;
				}
				index += 1;
			}
		}
	}
	// Check Path of given vertex
	fun dfs(point: Int, path: Array < Boolean > ): Unit
	{
		if (path[point])
		{
			// When alredy visit
			return;
		}
		else
		{
			// Collect the current node into the path
			path[point] = true;
			var temp: AjlistNode ? = this.node[point]?.next;
			while (temp != null)
			{
				// Visit to edge node
				this.dfs(temp.id, path);
				// Visit to next edge
				temp = temp.next;
			}
		}
	}
	fun printMotherVertices(): Unit
	{
		if (this.size <= 0)
		{
			// No nodes
			return;
		}
		print("\nMother Vertex :");
		val path: Array < Boolean > = Array(this.size)
		{
			false
		};
		var n: Int = 0;
		var status: Boolean = true;
		var count: Int = 0;
		while (n < this.size)
		{
			// Check path of node n
			this.dfs(n, path);
			var index: Int = 0;
			// When current node are visit other nodes
			// Then that is a Mother Vertex
			while (index < this.size)
			{
				if (path[index] == false)
				{
					// When path not contain current node
					status = false;
				}
				// Reset element value
				path[index] = false;
				index += 1;
			}
			if (status)
			{
				// Display result node
				print("  " + n);
				count += 1;
			}
			// Reset status
			status = true;
			// Visit next node
			n += 1;
		}
		if (count == 0)
		{
			println("Node");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// 7 implies the number of nodes in graph
	val g: Graph = Graph(7);
	// Connect node with an edge
	g.addEdge(1, 0);
	g.addEdge(1, 4);
	g.addEdge(2, 5);
	g.addEdge(3, 1);
	g.addEdge(3, 2);
	g.addEdge(3, 6);
	g.addEdge(4, 3);
	g.addEdge(5, 0);
	// Print graph element
	g.printGraph();
	// Test
	g.printMotherVertices();
}

Output

Adjacency list of vertex 0 :
Adjacency list of vertex 1 :  0  4
Adjacency list of vertex 2 :  5
Adjacency list of vertex 3 :  1  2  6
Adjacency list of vertex 4 :  3
Adjacency list of vertex 5 :  0
Adjacency list of vertex 6 :
Mother Vertex :  1  3  4




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