Find the Dominators for every vertex in a given DAG (Directed Acyclic Graph)

0 0 10 minutes read

Given a Directed Acyclic Graph with V vertices and E edges, the task is to find the set of dominant vertices for each vertex of the graph.

What are Dominators in Graph Theory: In control flow graphs a vertex V1 is the dominator of another vertex V2 if all the paths from the source vertex (in this case the vertex ‘0’) to the vertex V2 passes through V1. By definition, every vertex is one of its own dominators.

Examples:

Input: V = 5, E = 5, adj[][] = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}}
Output:
Dominating set of vertex: 0 –> 0
Dominating set of vertex: 1 –> 0 1
Dominating set of vertex: 2 –> 0 2
Dominating set of vertex: 3 –> 0 3
Dominating set of vertex: 4 –> 0 3 4
Explanation:
0
/ \
1 2
\ /
3
|
4
Here 0 is the entry node, so its dominator is 0 itself.
Only one path exists between (0, 1) so the dominators of 1 are 0, 1.
Only one path exists between (0, 2) so the dominators of 2 are 0, 2.
There are 2 paths between(0, 3) having only 0, 3 in common.
From (0, 4) there are 2 paths (0 1 3 4) and (0 2 3 4) with 0, 3 and 4 common.

Input: V = 4, E = 3, adj[][] = {{0, 1}, {0, 2}, {3, 2}}
Output:
Dominating set of vertex: 0 –> 0
Dominating set of vertex: 1 –> 0 1
Dominating set of vertex: 2 –> 0 2
Dominating set of vertex: 3 –> 0 2 3

Approach: The idea is to perform DFS and maintain a set of all the dominators of each vertex. Follow the steps below to solve the problem:

Initialize a vector of bitset data structure, say b to store the set of all the dominators of the vertices.
For every node i, set bits in b[i] will represent the set of dominant vertices of i.
In order to find the dominators for every vertex, it is important to find all the paths in a Directed Acyclic Graph.
Traverse the graph using DFS to find all the paths in the graph.
Start the traversal from the root node i.e 0
While performing DFS, for each vertex i
- If the node is not yet visited, set all the bits of b[i] and mark the node visited
- Store the set of the dominant vertices in the bitset b[i] as the intersection of the set of dominant vertices of its parent. Update b[i] to b[i] & b[parent].
- Update the value of b[i][i] to 1 because each node is a dominator of itself.
- Recursively, call DFS for children nodes of i.
After performing the above steps, print the dominant vertices for vertex, i.e, the position of the set bits in b[i].

Below is the implementation of the above approach:

C++14

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Declare bitsets for each
// vertex to store the set of
// dominant vertices
vector<bitset<100> > b(100);
 
// Visited array to check if
// a vertex has been visited or not
int vis[100] = {};
 
// Function to find set of dominator
// vertices for a particular node
void findDominator(vector<vector<int> > graph,
                   bitset<100> par, int node)
{
    // If node is unvisited
    if (vis[node] == 0) {
        // Set all bits of b[pos]
        b[node] = ~b[node];
 
        // Update vis[node] to 1
        vis[node] = 1;
    }
 
    // Update b[node] with bitwise and
    // of parent's dominant vertices
    b[node] &= par;
 
    // Node is itself is a
    // dominant vertex of node
    b[node][node] = 1;
 
    // Traverse the neighbours of node
    for (int i = 0; i < (int)graph[node].size(); i++) {
       
        // Recursive function call to
        //  children nodes of node
        findDominator(graph, b[node], graph[node][i]);
    }
}
 
// Function to build the graph
void buildGraph(vector<pair<int, int> > adj, int E, int V)
{
    // Vector of vector to store
    // the adjacency matrix
    vector<vector<int> > graph(V + 1);
 
    // Build the adjacency matrix
    for (int i = 0; i < E; i++) {
        graph[adj[i].first].push_back(adj[i].second);
    }
 
    // Bitset for node 0
    bitset<100> g;
 
    // Node 0 itself is a dominant
    // vertex of itself
    g[0] = 1;
 
    // Update visited of source
    // node as true
    vis[0] = 1;
 
    // DFS from source vertex
    findDominator(graph, g, 0);
}
 
// Function to find dominant set of vertices
void dominantVertices(int V, int E,
                      vector<pair<int, int> > adj)
{
    // Function call to build the graph
    // and dominant vertices
    buildGraph(adj, E, V);
 
    // Print set of dominating vertices
    for (int i = 0; i < V; i++) {
        cout << i << " -> ";
        for (int j = 0; j < V; j++) {
            if (b[i][j] == 1)
                cout << j << " ";
        }
        cout << endl;
    }
}
 
// Driver Code
int main()
{
    // Given Input
    int V = 5, E = 5;
    vector<pair<int, int> > adj = {
        { 0, 1 }, { 0, 2 }, { 1, 3 }, { 2, 3 }, { 3, 4 }
    };
 
    // Function Call
    dominantVertices(V, E, adj);
 
    return 0;
}

Java

// Java program for the above approach 
import java.util.*; 
 
class GFG { 
 
    // Declare bitsets for each
    // vertex to store the set of
    // dominant vertices
    static Vector<Integer> b[] = new Vector[100]; 
 
    // Visited array to check if
    // a vertex has been visited or not
    static int vis[] = new int[100]; 
 
    // Function to find set of dominator
    // vertices for a particular node
    static void findDominator(ArrayList<ArrayList<Integer> > graph, 
                            Vector<Integer> par, int node) 
    { 
        // If node is unvisited 
        if (vis[node] == 0) { 
            // Set all bits of b[pos] 
            for(int i=0; i<b[node].size(); i++)
                b[node].set(i, -1); 
 
            // Update vis[node] to 1 
            vis[node] = 1; 
        } 
 
        // Update b[node] with bitwise and 
        // of parent's dominant vertices 
        for(int i=0; i<b[node].size(); i++)
            b[node].set(i, b[node].get(i) & par.get(i)); 
 
        // Node is itself is a 
        // dominant vertex of node 
        b[node].set(node, 1); 
 
        // Traverse the neighbours of node 
        for (int i = 0; i < graph.get(node).size(); i++) { 
             
            // Recursive function call to 
            // children nodes of node 
            findDominator(graph, b[node], graph.get(node).get(i)); 
        } 
    } 
 
    // Function to build the graph 
    static void buildGraph(ArrayList<ArrayList<Integer> > graph, int V) 
    { 
        // Vector of vector to store 
        // the adjacency matrix 
 
        // Bitset for node 0 
        Vector<Integer> g = new Vector<>(); 
        for(int i=0; i<V; i++)
            g.add(0);
 
        // Node 0 itself is a dominant 
        // vertex of itself 
        g.set(0, 1); 
 
        // Update visited of source 
        // node as true 
        vis[0] = 1; 
 
        // DFS from source vertex 
        findDominator(graph, g, 0); 
    } 
 
    // Function to find dominant set 
    // of vertices 
    static void dominantVertices(int V, 
                            ArrayList<ArrayList<Integer> > graph) 
    { 
        // Function call to build the graph 
        // and dominant vertices 
        buildGraph(graph, V); 
 
        // Print set of dominating vertices 
        for (int i = 0; i < V; i++) { 
            System.out.print(i + " -> "); 
            for (int j = 0; j < V; j++) { 
                if (b[i].get(j) == 1) 
                    System.out.print(j + " "); 
            } 
            System.out.println(); 
        } 
    } 
 
    // Driver Code 
    public static void main(String[] args) 
    { 
        // Given Input 
        int V = 5; 
        ArrayList<ArrayList<Integer> > graph = new ArrayList<>(); 
        for(int i=0; i<V; i++){
            graph.add(new ArrayList<>());
            b[i] = new Vector<>();
            for(int j=0; j<V; j++)
                b[i].add(0);
        }
        graph.get(0).add(1); 
        graph.get(0).add(2); 
        graph.get(1).add(3); 
        graph.get(2).add(3); 
        graph.get(3).add(4); 
 
        // Function Call 
        dominantVertices(V, graph); 
    } 
}

Python3

# import the bitarray library
from bitarray import bitarray
# Declare bitarrays for each
# vertex to store the set of
# dominant vertices
b = [bitarray(100) for i in range(100)]
 
# Visited list to check if
# a vertex has been visited or not
vis = [0] * 100
 
def findDominator(graph, par, node):
    # If node is unvisited
    if vis[node] == 0:
        # Set all bits of b[pos]
        b[node].setall(True)
 
        # Update vis[node] to 1
        vis[node] = 1
 
    # Update b[node] with bitwise and
    # of parent's dominant vertices
    b[node] &= par
 
    # Node is itself is a
    # dominant vertex of node
    b[node][node] = True
 
    # Traverse the neighbours of node
    for i in range(len(graph[node])):
        # Recursive function call to
        #  children nodes of node
        findDominator(graph, b[node], graph[node][i])
 
def buildGraph(adj, E, V):
    # List of lists to store
    # the adjacency matrix
    graph = [[] for i in range(V + 1)]
 
    # Build the adjacency matrix
    for i in range(E):
        graph[adj[i][0]].append(adj[i][1])
 
    # Bitarray for node 0
    g = bitarray(100)
    g.setall(False)
 
    # Node 0 itself is a dominant
    # vertex of itself
    g[0] = True
 
    # Update visited of source
    # node as true
    vis[0] = 1
 
    # DFS from source vertex
    findDominator(graph, g, 0)
 
def dominantVertices(V, E, adj):
    # Function call to build the graph
    # and dominant vertices
    buildGraph(adj, E, V)
 
    # Print set of dominating vertices
    for i in range(V):
        print(i, " -> ", end="")
        for j in range(V):
            if b[i][j]:
                print(j, end=" ")
        print()
 
# Driver Code
 
if __name__ == '__main__':
    # Given Input
    V = 5
    E = 5
    adj = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]
    # Function Call
    dominantVertices(V, E, adj)
# this code is contributed by devendrasaluke 

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG {
static List<int>[] b = new List<int>[100];
 
// Visited array to check if
// a vertex has been visited or not
static int[] vis = new int[100];
 
// Function to find set of dominator
// vertices for a particular node
static void findDominator(List<List<int>> graph,
                        List<int> par, int node)
{
    // If node is unvisited
    if (vis[node] == 0) {
        // Set all bits of b[pos]
        for(int i=0; i<b[node].Count; i++)
            b[node][i] = -1;
 
        // Update vis[node] to 1
        vis[node] = 1;
    }
 
    // Update b[node] with bitwise and
    // of parent's dominant vertices
    for(int i=0; i<b[node].Count; i++)
        b[node][i] &= par[i];
 
    // Node is itself is a
    // dominant vertex of node
    b[node][node] = 1;
 
    // Traverse the neighbours of node
    for (int i = 0; i < graph[node].Count; i++) {
         
        // Recursive function call to
        // children nodes of node
        findDominator(graph, b[node], graph[node][i]);
    }
}
 
// Function to build the graph
static void buildGraph(List<List<int>> graph, int V)
{
    // Vector of vector to store
    // the adjacency matrix
 
    // Bitset for node 0
    List<int> g = new List<int>();
    for(int i=0; i<V; i++)
        g.Add(0);
 
    // Node 0 itself is a dominant
    // vertex of itself
    g[0] = 1;
 
    // Update visited of source
    // node as true
    vis[0] = 1;
 
    // DFS from source vertex
    findDominator(graph, g, 0);
}
 
// Function to find dominant set
// of vertices
static void dominantVertices(int V,
                        List<List<int>> graph)
{
    // Function call to build the graph
    // and dominant vertices
    buildGraph(graph, V);
 
    // Print set of dominating vertices
    for (int i = 0; i < V; i++) {
        Console.Write(i + " -> ");
        for (int j = 0; j < V; j++) {
            if (b[i][j] == 1)
                Console.Write(j + " ");
        }
        Console.WriteLine();
    }
}
 
// Driver Code
static void Main(string[] args)
{
    // Given Input
    int V = 5;
    List<List<int>> graph = new List<List<int>>();
    for(int i=0; i<V; i++){
        graph.Add(new List<int>());
        b[i] = new List<int>();
        for(int j=0; j<V; j++)
            b[i].Add(0);
    }
    graph[0].Add(1);
    graph[0].Add(2);
    graph[1].Add(3);
    graph[2].Add(3);
    graph[3].Add(4);
 
    // Function Call
    dominantVertices(V, graph);
}
}

Javascript

<script> 
// javascript program for the above approach
 
 
// Declare bitsets for each
// vertex to store the set of
// dominant vertices
let b = new Array(100);
for(let i = 0; i < 100; i++){
    b[i] = new Array(100).fill(false);
}
 
// Visited array to check if
// a vertex has been visited or not
let vis = new Array(100).fill(0);
 
 
// Function to find set of dominator
// vertices for a particular node
function findDominator(graph, par, node)
{
    // If node is unvisited
    if (vis[node] == 0) {
         
        // Set all bits of b[pos]
        for(let i = 0; i < 100; i++){
            if(b[node][i] == true) b[node][i] = false;
            else b[node][i] = true;
        }
 
        // Update vis[node] to 1
        vis[node] = 1;
    }
 
    // Update b[node] with bitwise and
    // of parent's dominant vertices
    for(let i = 0; i < 100; i++){
        if(b[node][i] == false || par[i] == false) b[node][i] = false;
    }
 
    // Node is itself is a
    // dominant vertex of node
    b[node][node] = 1;
 
    // Traverse the neighbours of node
    for (let i = 0; i < graph[node].length; i++) {
       
        // Recursive function call to
        //  children nodes of node
        findDominator(graph, b[node], graph[node][i]);
    }
}
 
// Function to build the graph
function buildGraph(adj, E, V)
{
    // Vector of vector to store
    // the adjacency matrix
    let graph = new Array(V+1);
    for(let i = 0; i < V+1; i++){
        graph[i] = new Array();
    }
 
    // Build the adjacency matrix
    for (let i = 0; i < E; i++) {
        graph[adj[i][0]].push(adj[i][1]);
    }
 
    // Bitset for node 0
    let g = new Array(100).fill(false);
 
    // Node 0 itself is a dominant
    // vertex of itself
    g[0] = 1;
 
    // Update visited of source
    // node as true
    vis[0] = 1;
 
    // DFS from source vertex
    findDominator(graph, g, 0);
}
 
// Function to find dominant set of vertices
function dominantVertices(V, E, adj)
{
    // Function call to build the graph
    // and dominant vertices
    buildGraph(adj, E, V);
 
    // Print set of dominating vertices
    for (let i = 0; i < V; i++) {
        document.write(i + " -> ");
        for (let j = 0; j < V; j++) {
            if (b[i][j] == true)
                document.write(j + " ");
        }
        document.write("\n");
    }
}
 
// Driver Code
// Given Input
let V = 5, E = 5;
let adj = [
    [ 0, 1 ], [ 0, 2 ], [ 1, 3 ], [ 2, 3 ], [ 3, 4 ]
];
 
// Function Call
dominantVertices(V, E, adj);
 
// The code is contributed by Nidhi goel. 
</script>

Output

0 -> 0 
1 -> 0 1 
2 -> 0 2 
3 -> 0 3 
4 -> 0 3 4

Time Complexity: O(V³)
Auxiliary Space: O(V²)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!