Skip to main content

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




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