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
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