Find all mother vertex of a directed graph in golang
Go program for Find all mother vertex of a directed graph. Here problem description and explanation.
package main
import "fmt"
/*
Go program for
Find all Mother Vertex in a Graph
*/
type AjlistNode struct {
// Vertices node key
id int
next * AjlistNode
}
func getAjlistNode(id int) * AjlistNode {
// return new AjlistNode
return &AjlistNode {
id,
nil,
}
}
type Vertices struct {
data int
next * AjlistNode
last * AjlistNode
}
func getVertices(data int) * Vertices {
// return new Vertices
return &Vertices {
data,
nil,
nil,
}
}
type Graph struct {
// Number of Vertices
size int
node []*Vertices
}
func getGraph(size int) * Graph {
// return new Graph
var g * Graph = &Graph {
size,
make([]*Vertices, size),
}
g.Graph();
return g;
}
// Set initial node value
func(this *Graph) Graph() {
if this.size <= 0 {
fmt.Println("\nEmpty Graph")
} else {
for index := 0 ; index < this.size ; index++ {
// Set initial node value
this.node[index] = getVertices(index)
}
}
}
// Handling the request of adding new edge
func(this *Graph) addEdge(start, last int) {
if start >= 0 && start < this.size && last >= 0 && last < this.size {
// Safe connection
var edge * AjlistNode = getAjlistNode(last)
if this.node[start].next == nil {
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
fmt.Println("\nHere Something Wrong")
}
}
func(this Graph) printGraph() {
if this.size > 0 {
// Print graph ajlist Node value
for index := 0 ; index < this.size ; index++ {
fmt.Print("\nAdjacency list of vertex ", index, " :")
var temp * AjlistNode = this.node[index].next
for (temp != nil) {
// Display graph node
fmt.Print(" ", this.node[temp.id].data)
// Visit to next edge
temp = temp.next
}
}
}
}
// Check Path of given vertex
func(this Graph) dfs(point int, path[] bool) {
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
for (temp != nil) {
// Visit to edge node
this.dfs(temp.id, path)
// Visit to next edge
temp = temp.next
}
}
}
func(this Graph) printMotherVertices() {
if this.size <= 0 {
// No nodes
return
}
fmt.Print("\nMother Vertex :")
var path = make([] bool, this.size)
var n int = 0
var status bool = true
var count int = 0
for (n < this.size) {
// Check path of node n
this.dfs(n, path)
// When current node are visit other nodes
// Then that is a Mother Vertex
for index := 0 ; index < this.size ; index++ {
if path[index] == false {
// When path not contain current node
status = false
}
// Reset element value
path[index] = false
}
if status {
// Display result node
fmt.Print(" ", n)
count++
}
// Reset status
status = true
// Visit next node
n++
}
if count == 0 {
fmt.Println("Node")
}
}
func main() {
// 7 implies the number of nodes in graph
var g * Graph = getGraph(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