Networks or graphs are pivotal in so many real-world applications such as fraud prevention systems. search engines, recommendation systems, social networks and a lot more. The search for the mother vertex of a graph aids in understanding the accessibility of a given vertex or collection of vertices.
What is the meaning of the mother vertex in a given graph?
In a given graph G = (V, E), a mother vertex v has a pathway for all other vertices in the specified graph to enable the connection. All other vertices in the graph can be accessed via the mother vertex. A mother vertex is quite common in directed graphs but is also applicable in undirected networks. We will briefly explore mother vertices in different network examples
Directed graph: Directed graphs or DiGraphs do hold directed edges or nodes. These edges can be unidirectional or bidirectional. For DiGraphs, self-loops are permissible but parallel edges are not. Mother vertex exists in directed graphs and there can be multiple of these as shown below. Based on the directed graph below, nodes [4] and [6] are the mother vertex.
Undirected connected graph: A mother vertex can be present on undirected connected graphs. In undirected graphs, self-loops are allowed while parallel edges are not permitted. The undirected connected graph below displays nodes 11 to 16 connected by seven non-directional edges. In this type of undirected connected graph, every node is considered to be a mother vertex.
Undirected disconnected graph: There is no mother vertex in the example graph below. This is because no edge connects node [12] to node [A]. It is safe to say that undirected disconnected graphs do not have mother vertex.
Python implementation of finding a mother vertex
We will run through a mother vertex implementation in Python. The first code example returns no mother vertex from a selection of 12 nodes. On the other hand, the example below identifies node [0] as the mother vertex in the below graph. The code implementation was inspired by this article.
import networkx as nx
G = nx.DiGraph()Skip to main content
Mother Vertecx.ipynb
Mother Vertecx.ipynb_
Last edited on 19 Oct 2020
[ ]
import networkx as nx
G = nx.DiGraph()
[ ]
G.add_node(1)
[ ]
G.add_nodes_from(range(2,7))
[ ]
G.add_edges_from([(1,2),(2,3),(4,3),(4,5),(6,7),(7,1),(6,5)])
[ ]
nx.draw(G,with_labels = True)
[ ]
[ ]
import networkx as nx
G = nx.Graph()
[ ]
G.add_node(10)
[ ]
G.add_nodes_from(range(11,16))
[ ]
G.add_edge(11,12)
[ ]
G.add_edge(12,13)
[ ]
G.add_edge(13,14)
[ ]
G.add_edge(14,15)
[ ]
G.add_edge(15,16)
[ ]
G.add_edge(11,10)
[ ]
G.add_edge(10,16)
[ ]
nx.draw(G,with_labels=True)
[ ]
G.add_node("B")
[ ]
G.add_edge("A","B")
[ ]
nx.draw(G,with_labels=True)
[ ]
from collections import defaultdict
[ ]
class Graph:
#Directed graph constructed in an adjencency list
def __init__(self,vertices):
self.V = vertices #No. of vertices
self.graph = defaultdict(list) # default dictionary
def DFSUtil(self, v, visited): # Depth-first search algorithm traversing from the root node
visited[v] = True
#all vertices adjacent to this vertex
for i in self.graph[v]:
if visited[i] == False:
self.DFSUtil(i, visited)
# Now adding w to the list of v
def addEdge(self, v, w):
self.graph[v].append(w)
# If mother vertex exists then returns. Returns -1 if mother vertext is nor present
def findMother(self):
# visited[] in this case is used for DFS
visited =[False]*(self.V)
# Used to store mother vertex
v=0
# Do a DFS traversal and find the last finished
# vertex
for i in range(self.V):
if visited[i]==False:
self.DFSUtil(i,visited)
v = i
# With DFS searches are made from v to check if all vertices are
# reachable from v or not.
visited = [False]*(self.V)
self.DFSUtil(v, visited)
if any(i == False for i in visited):
return -1
else:
return v
# We are now creating a graph wirh 12 nodes
g = Graph(12)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 3)
g.addEdge(4, 1)
g.addEdge(6, 4)
g.addEdge(5, 6)
g.addEdge(6, 7)
g.addEdge(8, 7)
g.addEdge(9, 10)
g.addEdge(9, 11)
g.addEdge(12, 11)
print ("A mother vertex is " + str(g.findMother()))
[ ]
from collections import defaultdict
# A cass of a directed graph using adjacency list
class Graph:
def __init__(self,vertices):
self.V = vertices #No. of vertices
self.graph = defaultdict(list) # default dictionary
# DFS traversing from v
def DFSUtil(self, v, visited):
# Idenifying the current node as visited and print it
visited[v] = True
# Noting all the vertices adjacent to this vertex
for i in self.graph[v]:
if visited[i] == False:
self.DFSUtil(i, visited)
# Now adding w to the list of v
def addEdge(self, v, w):
self.graph[v].append(w)
# If a mother vertex exists return. Otherwise returns -1
def findMother(self):
visited =[False]*(self.V)
# Do a DFS traversal and find the last finished
# vertex
for i in range(self.V):
if visited[i]==False:
self.DFSUtil(i,visited)
v = i
# If there exist mother vertex (or vetices) in given
# graph, then v must be one (or one of them)
# Now check if v is actually a mother vertex (or graph
# has a mother vertex). We basically check if every vertex
# is reachable from v or not.
# Reset all values in visited[] as false and do
# DFS beginning from v to check if all vertices are
# reachable from it or not.
visited = [False]*(self.V)
self.DFSUtil(v, visited)
if any(i == False for i in visited):
return "Not Present"
else:
return v
# Create a graph given in the above diagram
g = Graph(12)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 3)
g.addEdge(4, 1)
g.addEdge(6, 4)
g.addEdge(5, 6)
g.addEdge(6, 7)
g.addEdge(8, 7)
g.addEdge(9, 10)
g.addEdge(9, 11)
g.addEdge(11, 2)
g.addEdge(12, 11)
print ("A mother vertex is " + str(g.findMother()))
A mother vertex is Not Present
[ ]
from collections import defaultdict
# A cass of a directed graph using adjacency list
class Graph:
def __init__(self,vertices):
self.V = vertices #No. of vertices
self.graph = defaultdict(list) # default dictionary
# DFS traversing from v
def DFSUtil(self, v, visited):
# Idenifying the current node as visited and print it
visited[v] = True
# Noting all the vertices adjacent to this vertex
for i in self.graph[v]:
if visited[i] == False:
self.DFSUtil(i, visited)
# Now adding w to the list of v
def addEdge(self, v, w):
self.graph[v].append(w)
# If a mother vertex exists return. Otherwise returns -1
def findMother(self):
visited =[False]*(self.V)
# Do a DFS traversal and find the last finished
# vertex
for i in range(self.V):
if visited[i]==False:
self.DFSUtil(i,visited)
v = i
# If there exist mother vertex (or vetices) in given
# graph, then v must be one (or one of them)
# Now check if v is actually a mother vertex (or graph
# has a mother vertex). We basically check if every vertex
# is reachable from v or not.
# Reset all values in visited[] as false and do
# DFS beginning from v to check if all vertices are
# reachable from it or not.
visited = [False]*(self.V)
self.DFSUtil(v, visited)
if any(i == False for i in visited):
return "Not Present"
else:
return v
# Create a graph given in the above diagram
g = Graph(12)
g.addEdge(0, 1)
g.addEdge(0, 11)
g.addEdge(1, 2)
g.addEdge(2, 3)
g.addEdge(3, 4)
g.addEdge(4, 5)
g.addEdge(5, 6)
g.addEdge(6, 7)
g.addEdge(7, 8)
g.addEdge(8, 9)
g.addEdge(9, 10)
g.addEdge(10, 11)
print ("A mother vertex is " + str(g.findMother()))