El algoritmo Cuthill-Mckee se utiliza para reordenar una array cuadrada simétrica. Se basa en el algoritmo Breadth First Search de un gráfico, cuya array de adyacencia es la versión dispersa de la array cuadrada de entrada.
El ordenamiento se usa frecuentemente cuando se va a generar una array cuyas filas y columnas se numeran de acuerdo con la numeración de los Nodes. Mediante una renumeración adecuada de los Nodes, a menudo es posible producir una array con un ancho de banda mucho más pequeño .
La versión dispersa de una array es una array en la que la mayoría de los elementos son cero.
El Algoritmo Cuthill-Mckee Inverso es el mismo que el algoritmo Cuthill-Mckee , la única diferencia es que los índices finales obtenidos usando el algoritmo Cuthill-Mckee están invertidos en el Algoritmo Cuthill-Mckee Inverso.
A continuación se muestran los pasos del algoritmo Reverse Cuthill-Mckee:
- Instancia una cola vacía Q y una array vacía para el orden de permutación de los objetos R .
- S1: primero encontramos el objeto con grado mínimo cuyo índice aún no se ha agregado a R . Digamos que el objeto correspondiente a la p-ésima fila ha sido identificado como el objeto con un grado mínimo. Añadir p a R. _
- S2: como un índice se agrega a R , y se agregan todos los vecinos del objeto correspondiente en el índice,
en orden creciente de grado, a Q . Los vecinos son Nodes con valor distinto de cero entre los elementos no diagonales en la p-ésima fila. - S3: extraiga el primer Node en Q , digamos C. Si C no se ha insertado en R , agréguelo a R , agregue a Q los vecinos de C en orden creciente de grado.
- S4: Si Q no está vacío, repita S3 .
- S5: Si Q está vacío, pero hay objetos en la array que no se han incluido en R , comience desde S1 , una vez más. (Esto podría suceder si hay gráficos disjuntos)
- S6: Termine este algoritmo una vez que todos los objetos estén incluidos en R .
- S7: Finalmente, invierta los índices en R , es decir ( swap(R[i], R[P-i+1]) ).
Grado: la definición de un grado no es constante, cambia según el conjunto de datos con el que esté trabajando. Para el ejemplo dado a continuación, el grado de un Node se define como la suma de elementos no diagonales en la fila correspondiente.
La definición generalizada del grado de un Node ‘A’ es el número de Nodes conectados a ‘A’.
Ejemplo:
Given a symmetric matrix: | 0.0 0.78 0.79 0.8 0.23 | | 0.9 0.0 0.43 0.771 0.752 | | 0.82 0.0 0.0 0.79 0.34 | | 0.8 0.8 0.8 0.0 0.8 | | 0.54 0.97 0.12 0.78 0.0 | Degree here is defined as sum of non-diagonal elements in the corresponding row. Specification for a matrix is defined as, if the element of the matrix at i, j has a value less than 0.75 its made to 0 otherwise its made to 1.
Array después de la especificación :
Degree of node 0 = 2.6 Degree of node 1 = 2.803 Degree of node 2 = 2.55 Degree of node 3 = 3.2 Degree of node 4 = 2.41 Permutation order of objects (R) : 0 2 1 3 4
El nuevo orden de permutación es simplemente el orden de los Nodes, es decir, convertir el Node ‘R[i]’ en el Node ‘i’.
Por lo tanto, convierta el Node ‘R[0] = 0’, a 0; Node ‘R[1] = 2’, a 1; Node ‘R[2] = 1’, a 2; Node ‘R[3] = 3’, a 3; y Node ‘R[4] = 4’, a 4;
Tomemos un ejemplo más grande para entender el resultado del reordenamiento:
Give a adjacency matrix : | 0 1 0 0 0 0 1 0 1 0 | | 1 0 0 0 1 0 1 0 0 1 | | 0 0 0 0 1 0 1 0 0 0 | | 0 0 0 0 1 1 0 0 1 0 | | 0 1 1 1 0 1 0 0 0 1 | | 0 0 0 1 1 0 0 0 0 0 | | 1 1 1 0 0 0 0 0 0 0 | | 0 0 0 0 0 0 0 0 1 1 | | 1 0 0 1 0 0 0 1 0 0 | | 0 1 0 0 1 0 0 1 0 0 | Degree of node 'A' is defined as number of nodes connected to 'A'
Output : Permutation order of objects (R) : 7 8 9 3 5 1 0 4 6 2
Ahora convierta el Node ‘R[i]’ en el Node ‘i’
Entonces el gráfico se convierte en:
El resultado de la reordenación se puede ver en la array de adyacencia de los dos gráficos:
array original
Array reordenada RCM
Desde aquí podemos ver claramente cómo el algoritmo de Cuthill-Mckee ayuda a reordenar una array cuadrada en una array no distribuida.
A continuación se muestra la implementación del algoritmo anterior. Tomando la definición general de grado.
C++
// C++ program for Implementation of
// Reverse Cuthill Mckee Algorithm
#include <bits/stdc++.h>
using namespace std;
vector<double> globalDegree;
int findIndex(vector<pair<int, double> > a, int x)
{
for (int i = 0; i < a.size(); i++)
if (a[i].first == x)
return i;
return -1;
}
bool compareDegree(int i, int j)
{
return ::globalDegree[i] < ::globalDegree[j];
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> const& v)
{
for (int i = 0; i < v.size(); i++)
out << v[i] << ' ';
return out;
}
class ReorderingSSM {
private:
vector<vector<double> > _matrix;
public:
// Constructor and Destructor
ReorderingSSM(vector<vector<double> > m)
{
_matrix = m;
}
ReorderingSSM() {}
~ReorderingSSM() {}
// class methods
// Function to generate degree of all the nodes
vector<double> degreeGenerator()
{
vector<double> degrees;
for (int i = 0; i < _matrix.size(); i++) {
double count = 0;
for (int j = 0; j < _matrix[0].size(); j++) {
count += _matrix[i][j];
}
degrees.push_back(count);
}
return degrees;
}
// Implementation of Cuthill-Mckee algorithm
vector<int> CuthillMckee()
{
vector<double> degrees = degreeGenerator();
::globalDegree = degrees;
queue<int> Q;
vector<int> R;
vector<pair<int, double> > notVisited;
for (int i = 0; i < degrees.size(); i++)
notVisited.push_back(make_pair(i, degrees[i]));
// Vector notVisited helps in running BFS
// even when there are dijoind graphs
while (notVisited.size()) {
int minNodeIndex = 0;
for (int i = 0; i < notVisited.size(); i++)
if (notVisited[i].second < notVisited[minNodeIndex].second)
minNodeIndex = i;
Q.push(notVisited[minNodeIndex].first);
notVisited.erase(notVisited.begin()
+ findIndex(notVisited,
notVisited[Q.front()].first));
// Simple BFS
while (!Q.empty()) {
vector<int> toSort;
for (int i = 0; i < _matrix[0].size(); i++) {
if (i != Q.front() && _matrix[Q.front()][i] == 1
&& findIndex(notVisited, i) != -1) {
toSort.push_back(i);
notVisited.erase(notVisited.begin()
+ findIndex(notVisited, i));
}
}
sort(toSort.begin(), toSort.end(), compareDegree);
for (int i = 0; i < toSort.size(); i++)
Q.push(toSort[i]);
R.push_back(Q.front());
Q.pop();
}
}
return R;
}
// Implementation of reverse Cuthill-Mckee algorithm
vector<int> ReverseCuthillMckee()
{
vector<int> cuthill = CuthillMckee();
int n = cuthill.size();
if (n % 2 == 0)
n -= 1;
n = n / 2;
for (int i = 0; i <= n; i++) {
int j = cuthill[cuthill.size() - 1 - i];
cuthill[cuthill.size() - 1 - i] = cuthill[i];
cuthill[i] = j;
}
return cuthill;
}
};
// Driver Code
int main()
{
int num_rows = 10;
vector<vector<double> > matrix;
for (int i = 0; i < num_rows; i++) {
vector<double> datai;
for (int j = 0; j < num_rows; j++)
datai.push_back(0.0);
matrix.push_back(datai);
}
// This is the test graph,
// check out the above graph photo
matrix[0] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0 };
matrix[1] = { 1, 0, 0, 0, 1, 0, 1, 0, 0, 1 };
matrix[2] = { 0, 0, 0, 0, 1, 0, 1, 0, 0, 0 };
matrix[3] = { 0, 0, 0, 0, 1, 1, 0, 0, 1, 0 };
matrix[4] = { 0, 1, 1, 1, 0, 1, 0, 0, 0, 1 };
matrix[5] = { 0, 0, 0, 1, 1, 0, 0, 0, 0, 0 };
matrix[6] = { 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 };
matrix[7] = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1 };
matrix[8] = { 1, 0, 0, 1, 0, 0, 0, 1, 0, 0 };
matrix[9] = { 0, 1, 0, 0, 1, 0, 0, 1, 0, 0 };
ReorderingSSM m(matrix);
vector<int> r = m.ReverseCuthillMckee();
cout << "Permutation order of objects: " << r << endl;
return 0;
}
Python3
# C++ program for Implementation of
# Reverse Cuthill Mckee Algorithm
from collections import deque as Queue
globalDegree = []
def findIndex(a, x):
for i in range(len(a)):
if a[i][0] == x:
return i
return -1
class ReorderingSSM:
__matrix = []
# Constructor and Destructor
def __init__(self, m):
self.__matrix = m
# class methods
# Function to generate degree of all the nodes
def degreeGenerator(self):
degrees = []
for i in range(len(self.__matrix)):
count = 0
for j in range(len(self.__matrix[0])):
count += self.__matrix[i][j]
degrees.append(count)
return degrees
# Implementation of Cuthill-Mckee algorithm
def CuthillMckee(self):
global globalDegree
degrees = self.degreeGenerator()
globalDegree = degrees
Q = Queue()
R = []
notVisited = []
for i in range(len(degrees)):
notVisited.append((i, degrees[i]))
# Vector notVisited helps in running BFS
# even when there are dijoind graphs
while len(notVisited):
minNodeIndex = 0
for i in range(len(notVisited)):
if notVisited[i][1] < notVisited[minNodeIndex][1]:
minNodeIndex = i
Q.append(notVisited[minNodeIndex][0])
notVisited.pop(findIndex(notVisited, notVisited[Q[0]][0]))
# Simple BFS
while Q:
toSort = []
for i in range(len(self.__matrix[0])):
if (
i != Q[0]
and self.__matrix[Q[0]][i] == 1
and findIndex(notVisited, i) != -1
):
toSort.append(i)
notVisited.pop(findIndex(notVisited, i))
toSort.sort(key=lambda x: globalDegree[x])
for i in range(len(toSort)):
Q.append(toSort[i])
R.append(Q[0])
Q.popleft()
return R
# Implementation of reverse Cuthill-Mckee algorithm
def ReverseCuthillMckee(self):
cuthill = self.CuthillMckee()
n = len(cuthill)
if n % 2 == 0:
n -= 1
n = n // 2
for i in range(n + 1):
j = cuthill[len(cuthill) - 1 - i]
cuthill[len(cuthill) - 1 - i] = cuthill[i]
cuthill[i] = j
return cuthill
# Driver Code
if __name__ == "__main__":
num_rows = 10
matrix = [[0.0] * num_rows for _ in range(num_rows)]
# This is the test graph,
# check out the above graph photo
matrix[0] = [0, 1, 0, 0, 0, 0, 1, 0, 1, 0]
matrix[1] = [1, 0, 0, 0, 1, 0, 1, 0, 0, 1]
matrix[2] = [0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
matrix[3] = [0, 0, 0, 0, 1, 1, 0, 0, 1, 0]
matrix[4] = [0, 1, 1, 1, 0, 1, 0, 0, 0, 1]
matrix[5] = [0, 0, 0, 1, 1, 0, 0, 0, 0, 0]
matrix[6] = [1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
matrix[7] = [0, 0, 0, 0, 0, 0, 0, 0, 1, 1]
matrix[8] = [1, 0, 0, 1, 0, 0, 0, 1, 0, 0]
matrix[9] = [0, 1, 0, 0, 1, 0, 0, 1, 0, 0]
m = ReorderingSSM(matrix)
r = m.ReverseCuthillMckee()
print("Permutation order of objects:", r)
Permutation order of objects: 7 8 9 3 5 1 0 4 6 2
Referencia : https://en.wikipedia.org/wiki/Cuthill%E2%80%93McKee_algorithm
Publicación traducida automáticamente
Artículo escrito por Ronak_Doshi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA