Prerequisite: Conflict Serializability, Precedence Graph
Conflict Serializable Schedule: A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. The serial schedule of the Conflict Serializable Schedule can be found by applying topological Sorting on the Precedence Graph of the Conflict Serializable Schedule.
Note: Precedence Graph of Conflict Serial Schedule is always directed acyclic graph.
Approach: Follow to below steps to find topological sorting of Precedence Graph:
- Find the indegree of all nodes for the given Precedence Graph and store it in an auxiliary array.
- Now For each node having indegree 0 perform the following:
- Print the current node T as the order of the topological sort.
- Let the node T be the node with in-degree 0.
- Remove T and all edges connecting to T from the graph.
- Update indegree of all nodes after the above steps.
- After the above steps, the topological sort of the given precedence graph can be calculated.
Below is the illustration of the above approach:
Let, the Conflict Serial Schedule be S: R2(A) W2(A) R3(C) W2(B) W3(A) W3(C) R1(A) R2(B) W1(A) W2(B)
- Here node T2 has indegree 0.
- So, select T2 and remove T2 and all edges connecting from it.
- Now T3 has indegree 0. So, select T3 and remove the edge T3→T1.
- At the end select T3. So the topological Sorting is T2, T3, T1.
- Hence, the equivalent serial schedule of given conflict serializable schedule is T2→T3→T1, i.e., S2: R2(A) W2(A) W2(B) R3(C) W3(A) W3(C) R1(A) R2(B) W1(A) W1(B).
There may be more than one equivalent serial schedule of the conflict serializable schedule.
Below is the implementation to get the Serial Schedule of CSS using Topological Sorting:
C++
// C++ program to print serial schedule// of CSS using Topological sorting#include <bits/stdc++.h>using namespace std;class PrecedenceGraph { // No. of vertices int V; // Pointer to an array containing // adjacency vector vector<int>* adj; // Vector to store SerialSchedule vector<int> serialSchedule; // Function declarations void computeIndegree(int* indegree); int findZeroIndegree(int* indegree, bool* visited);public: // Constructor PrecedenceGraph(int V); // Function declarations void addEdge(int v, int w); void topologicalSort(); void printSchedule();};// Function to create the precedence// graphPrecedenceGraph::PrecedenceGraph(int V){ this->V = V; adj = new vector<int>[V];}// Function to add the edge to the// precedence graphvoid PrecedenceGraph::addEdge(int v, int w){ adj[v].push_back(w);}// Function to compute indegree of nodesvoid PrecedenceGraph::computeIndegree( int* indegree){ for (int i = 1; i < V; i++) { // Traverse the adjacency list // of node i for (int j = 0; j < adj[i].size(); j++) { int node = adj[i][j]; // Update the indegree // of node indegree[node]++; } }}// Function to find node with// zero indegreeint PrecedenceGraph::findZeroIndegree( int* indegree, bool* visited){ for (int i = 1; i < V; i++) { // If node is not visited // and have indegree 0 if (!visited[i] && indegree[i] == 0) { // Mark node visited visited[i] = true; // Return node return i; } } // All nodes are visited return -1;}// Function to find the topological// Sorting of the given graphvoid PrecedenceGraph::topologicalSort(){ // Create and initialize // visited array bool* visited = new bool[V](); // Create and initialize // indegree array int* indegree = new int[V](); computeIndegree(indegree); // Check if the node with // indegree 0 is available int node = findZeroIndegree( indegree, visited); bool nodeAvailable = false; if (node != -1) { nodeAvailable = true; } while (nodeAvailable) { // Add node to serial schedule serialSchedule.push_back(node); for (int i = 0; i < adj[node].size(); i++) { // Delete all edges of current // node and update indegree indegree[adj[node][i]]--; } // Find next node with indegree 0 node = findZeroIndegree(indegree, visited); if (node == -1) { // Node with zero indegree // not available nodeAvailable = false; } }}// Function to print the serial schedulevoid PrecedenceGraph::printSchedule(){ for (int i : serialSchedule) { cout << "T" << i << " "; }}// Driver Codeint main(){ // Create a precedence graph // given in the above diagram PrecedenceGraph graph(4); graph.addEdge(2, 1); graph.addEdge(2, 3); graph.addEdge(3, 1); // Find topological ordereing graph.topologicalSort(); // Print Schedule cout << "Equivalent Serial" << " Schedule is :"; graph.printSchedule();} |
Java
// Java program to print serial schedule// of CSS using Topological sortingimport java.util.*;class PrecedenceGraph { // No. of verticesprivate int V;// Pointer to an array containing// adjacency vectorprivate ArrayList<Integer>[] adj;// Vector to store SerialScheduleprivate ArrayList<Integer> serialSchedule;// Function to create the precedence// graphPrecedenceGraph(int V) { this.V = V; adj = new ArrayList[V]; for (int i = 0; i < V; i++) { adj[i] = new ArrayList<>(); } serialSchedule = new ArrayList<>();}// Function to add the edge to the// precedence graphvoid addEdge(int v, int w) { adj[v].add(w);}// Function to compute indegree of nodesvoid computeIndegree(int[] indegree) { for (int i = 1; i < V; i++) { // Traverse the adjacency list // of node i for (int j = 0; j < adj[i].size(); j++) { int node = adj[i].get(j); // Update the indegree // of node indegree[node]++; } }}// Function to find node with// zero indegreeint findZeroIndegree(int[] indegree, boolean[] visited) { for (int i = 1; i < V; i++) { // If node is not visited // and have indegree 0 if (!visited[i] && indegree[i] == 0) { // Mark node visited visited[i] = true; // Return node return i; } } // All nodes are visited return -1;}// Function to find the topological// Sorting of the given graphvoid topologicalSort() { // Create and initialize // visited array boolean[] visited = new boolean[V]; // Create and initialize // indegree array int[] indegree = new int[V]; computeIndegree(indegree); // Check if the node with indegree 0 is available int node = findZeroIndegree(indegree, visited); boolean nodeAvailable = false; if (node != -1) { nodeAvailable = true; } while (nodeAvailable) { // Add node to serial schedule serialSchedule.add(node); for (int i = 0; i < adj[node].size(); i++) { // Delete all edges of current // node and update indegree indegree[adj[node].get(i)]--; } // Find next node with indegree 0 node = findZeroIndegree(indegree, visited); if (node == -1) { // Node with zero indegree // not available nodeAvailable = false; } }}// Function to print the serial schedulevoid printSchedule() { for (int i : serialSchedule) { System.out.print("T" + i + " "); } System.out.println();}}// Driver Codeclass Main {public static void main(String[] args) {// Create a precedence graph// given in the above diagramPrecedenceGraph graph = new PrecedenceGraph(4);graph.addEdge(2, 1);graph.addEdge(2, 3);graph.addEdge(3, 1); // Find topological ordereing graph.topologicalSort(); // Print Schedule System.out.print("Equivalent Serial Schedule is :"); graph.printSchedule(); }}// This code is contributed by Pushpesh Raj. |
Python3
# Python program to print serial schedule of CSS using Topological sortingfrom collections import defaultdictclass PrecedenceGraph: # Constructor def __init__(self, V): self.V = V self.adj = defaultdict(list) self.serialSchedule = [] # Function to add the edge to the precedence graph def addEdge(self, v, w): self.adj[v].append(w) # Function to compute indegree of nodes def computeIndegree(self, indegree): for i in range(1, self.V): for node in self.adj[i]: # Update the indegree of node indegree[node] += 1 # Function to find node with zero indegree def findZeroIndegree(self, indegree, visited): for i in range(1, self.V): # If node is not visited and have indegree 0 if not visited[i] and indegree[i] == 0: # Mark node visited visited[i] = True # Return node return i # All nodes are visited return -1 # Function to find the topological Sorting of the given graph def topologicalSort(self): # Create and initialize visited array visited = [False for i in range(self.V)] # Create and initialize indegree array indegree = [0 for i in range(self.V)] self.computeIndegree(indegree) # Check if the node with indegree 0 is available node = self.findZeroIndegree(indegree, visited) nodeAvailable = False if node != -1: nodeAvailable = True while nodeAvailable: # Add node to serial schedule self.serialSchedule.append(node) for next_node in self.adj[node]: # Delete all edges of current node and update indegree indegree[next_node] -= 1 # Find next node with indegree 0 node = self.findZeroIndegree(indegree, visited) if node == -1: # Node with zero indegree not available nodeAvailable = False # Function to print the serial schedule def printSchedule(self): print("Equivalent Serial Schedule is: ", end="") for i in self.serialSchedule: print("T{} ".format(i), end="")# Driver Codeif __name__ == "__main__": # Create a precedence graph given in the above diagram graph = PrecedenceGraph(4) graph.addEdge(2, 1) graph.addEdge(2, 3) graph.addEdge(3, 1) # Find topological ordereing graph.topologicalSort() # Print Schedule graph.printSchedule() |
C#
using System;using System.Collections.Generic;public class PrecedenceGraph { // No. of vertices private int V; // Pointer to an array containing // adjacency vector private List<int>[] adj; // Vector to store SerialSchedule private List<int> serialSchedule = new List<int>(); // Constructor public PrecedenceGraph(int V) { this.V = V; adj = new List<int>[ V ]; for (int i = 0; i < V; i++) { adj[i] = new List<int>(); } } // Function to add the edge to the // precedence graph public void addEdge(int v, int w) { adj[v].Add(w); } // Function to compute indegree of nodes private void computeIndegree(int[] indegree) { for (int i = 1; i < V; i++) { // Traverse the adjacency list // of node i foreach(int node in adj[i]) { // Update the indegree // of node indegree[node]++; } } } // Function to find node with // zero indegree private int findZeroIndegree(int[] indegree, bool[] visited) { for (int i = 1; i < V; i++) { // If node is not visited // and have indegree 0 if (!visited[i] && indegree[i] == 0) { // Mark node visited visited[i] = true; // Return node return i; } } // All nodes are visited return -1; } // Function to find the topological // Sorting of the given graph public void topologicalSort() { // Create and initialize // visited array bool[] visited = new bool[V]; // Create and initialize // indegree array int[] indegree = new int[V]; computeIndegree(indegree); // Check if the node with // indegree 0 is available int node = findZeroIndegree(indegree, visited); bool nodeAvailable = false; if (node != -1) { nodeAvailable = true; } while (nodeAvailable) { // Add node to serial schedule serialSchedule.Add(node); foreach(int i in adj[node]) { // Delete all edges of current // node and update indegree indegree[i]--; } // Find next node with indegree 0 node = findZeroIndegree(indegree, visited); if (node == -1) { // Node with zero indegree // not available nodeAvailable = false; } } } // Function to print the serial schedule public void printSchedule() { foreach(int i in serialSchedule) { Console.Write("T" + i + " "); } }}public class Program { public static void Main(string[] args) { // Create a precedence graph // given in the above diagram PrecedenceGraph graph = new PrecedenceGraph(4); graph.addEdge(2, 1); graph.addEdge(2, 3); graph.addEdge(3, 1); // Find topological ordering graph.topologicalSort(); // Print Schedule Console.Write("Equivalent Serial Schedule is: "); graph.printSchedule(); }} |
Javascript
class PrecedenceGraph { // Constructor constructor(V) { this.V = V; this.adj = new Map(); this.serialSchedule = []; } // Function to add the edge to the precedence graph addEdge(v, w) { if (!this.adj.has(v)) { this.adj.set(v, []); } this.adj.get(v).push(w); } // Function to compute indegree of nodes computeIndegree(indegree) { for (let i = 1; i < this.V; i++) { // Check if the current node exists in the adjacency list if (!this.adj.has(i)) { continue; } // Update the indegree of all adjacent nodes for (const node of this.adj.get(i)) { indegree[node] += 1; } } } // Function to find node with zero indegree findZeroIndegree(indegree, visited) { for (let i = 1; i < this.V; i++) { // If node is not visited and have indegree 0 if (!visited[i] && indegree[i] === 0) { // Mark node visited visited[i] = true; // Return node return i; } } // All nodes are visited return -1; } // Function to find the topological Sorting of the given graph topologicalSort() { // Create and initialize visited array const visited = new Array(this.V).fill(false); // Create and initialize indegree array const indegree = new Array(this.V).fill(0); // Compute indegree of nodes this.computeIndegree(indegree); // Check if the node with indegree 0 is available let node = this.findZeroIndegree(indegree, visited); let nodeAvailable = false; if (node !== -1) { nodeAvailable = true; } while (nodeAvailable) { // Add node to serial schedule this.serialSchedule.push(node); // Delete all edges of current node and update indegree if (this.adj.has(node)) { for (const nextNode of this.adj.get(node)) { indegree[nextNode] -= 1; } } // Find next node with indegree 0 node = this.findZeroIndegree(indegree, visited); if (node === -1) { // Node with zero indegree not available nodeAvailable = false; } } } // Function to print the serial schedule printSchedule() { let result = "Equivalent Serial Schedule is: "; for (const i of this.serialSchedule) { result += `T${i} `; } console.log(result); }}// Driver Codeconst graph = new PrecedenceGraph(4);graph.addEdge(2, 1);graph.addEdge(2, 3);graph.addEdge(3, 1);graph.topologicalSort();graph.printSchedule(); |
Output:
Equivalent Serial Schedule is :T2 T3 T1
Time Complexity: O(N)
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
