How to find all the parent nodes of each node in a directed acyclic graph?

February 6, 2022

For the directed acyclic graph given by the following python code I want to find out all the parent node of each node of the DAG. Please help! For example, node 6,7 and 8 are the parent nodes of node 9. I have to make a function where I have to access all the parent node of each node and act according to my problem. Note: The code was taken from geeksforgeeks

class Graph:
    # Constructor to construct a graph
    def __init__(self, edges, n):
 
        # A list of lists to represent an adjacency list
        self.adjList = [None] * n
 
        # allocate memory for the adjacency list
        for i in range(n):
            self.adjList[i] = []
 
        # add edges to the directed graph
        for (src, dest, weight) in edges:
            # allocate node in adjacency list from src to dest
            self.adjList[src].append((dest, weight))


# Function to print adjacency list representation of a graph
def printGraph(graph):
    for src in range(len(graph.adjList)):
        # print current vertex and all its neighboring vertices
        for (dest, weight) in graph.adjList[src]:
            new_graph[src].append(dest)
            print(f'({src} —> {dest}, {weight}) ', end='')
        print()
 

# Input: Edges in a weighted digraph (as per the above diagram)
# Edge (x, y, w) represents an edge from `x` to `y` having weight `w`
edges = [(0, 1, 18), (0, 2, 12), (0, 3, 9), (0, 4, 11), (0, 5, 14), 
          (1, 7, 19), (1, 8, 16), (2, 6, 23), (3, 7, 27), (3, 8, 23),
        (4, 8, 13), (5, 7, 15), (6, 9, 17), (7, 9, 11), (8, 9, 13)]

# No. of vertices (labelled from 1 to 10)
n = 10

# construct a graph from a given list of edges
graph = Graph(edges, n)
new_graph = [[] for i in range(n)]
# print adjacency list representation of the graph
printGraph(graph)

>Solution :

You can use a similar structure as the printGraph function which iterates over all edges. We then can check for each edge if it leads to our child node. If so, we found a parent node. These parent nodes are stored and returned. Here is an example implementation of the function:

# Function to find all parents of a node
def getParent(graph, node):
    # collect parents as a set in order to avoid duplicate entries
    parents = set()
    for src in range(len(graph.adjList)):
        # Iterate over all edges from src node
        for (dest, weight) in graph.adjList[src]:
            # if destiontion is our needed child add source as parent
            if dest == node:
                parents.add(src)
                
    # Return all parents as a list
    return list(parents)

Call it like this to find the parents of node 9:

# Input: Edges in a weighted digraph (as per the above diagram)
# Edge (x, y, w) represents an edge from `x` to `y` having weight `w`
edges = [(0, 1, 18), (0, 2, 12), (0, 3, 9), (0, 4, 11), (0, 5, 14), 
          (1, 7, 19), (1, 8, 16), (2, 6, 23), (3, 7, 27), (3, 8, 23),
        (4, 8, 13), (5, 7, 15), (6, 9, 17), (7, 9, 11), (8, 9, 13)]

# No. of vertices (labelled from 1 to 10)
n = 10

# construct a graph from a given list of edges
graph = Graph(edges, n)
print(getParent(graph, 9))

Output are the parents of node 9 as a list: