Requisito previo: serialización de conflictos, gráfico de precedencia
Programación serializable en conflicto: una programación se denomina serializable en conflicto si se puede transformar en una programación en serie mediante el intercambio de operaciones que no están en conflicto. El programa de serie del Programa serializable de conflicto se puede encontrar aplicando la ordenación topológica en el Gráfico de precedencia del Programa serializable de conflicto.
Nota: El gráfico de precedencia del programa de serie de conflictos siempre es un gráfico acíclico dirigido .
Enfoque: siga los pasos a continuación para encontrar la clasificación topológica del gráfico de precedencia:
- Encuentre el grado de entrada de todos los Nodes para el gráfico de precedencia dado y guárdelo en una array auxiliar.
- Ahora, para cada Node que tenga un grado de entrada 0 , realice lo siguiente:
- Imprime el Node actual T como el orden del ordenamiento topológico.
- Sea el Node T el Node de grado 0 .
- Retire T y todos los bordes que se conectan a T del gráfico.
- Actualice el grado de entrada de todos los Nodes después de los pasos anteriores.
- Después de los pasos anteriores, se puede calcular el tipo topológico del gráfico de precedencia dado.
A continuación se muestra la ilustración del enfoque anterior:
Sea S: R2(A) W2(A) R3(C) W2(B) W3(A) W3(C) R1(A) R2(B) W1(A) W2(B)
- Aquí el Node T2 tiene un grado de entrada 0 .
- Entonces, seleccione T2 y elimine T2 y todos los bordes que se conectan desde él.
- Ahora T3 tiene un grado de entrada 0 . Por lo tanto, seleccione T3 y elimine el borde T3→T1 .
- Al final seleccione T3 . Entonces, la clasificación topológica es T2, T3, T1 .
- Por lo tanto, el programa serial equivalente del programa serializable de conflicto dado es T2→T3→T1 , es decir, S2: R2(A) W2(A) W2(B) R3(C) W3(A) W3(C) R1(A) R2(B) W1(A) W1(B) .
Puede haber más de un programa serial equivalente del programa serializable en conflicto.
A continuación se muestra la implementación para obtener el programa de serie de CSS utilizando la clasificación topológica:
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
// graph
PrecedenceGraph::PrecedenceGraph(int V)
{
this->V = V;
adj = new vector<int>[V];
}
// Function to add the edge to the
// precedence graph
void PrecedenceGraph::addEdge(int v,
int w)
{
adj[v].push_back(w);
}
// Function to compute indegree of nodes
void 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 indegree
int 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 graph
void 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 schedule
void PrecedenceGraph::printSchedule()
{
for (int i : serialSchedule) {
cout << "T" << i << " ";
}
}
// Driver Code
int 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();
}
Equivalent Serial Schedule is :T2 T3 T1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por se_prashant y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA