Matrices

06 noviembre 2017

Laboratorio de programación Nro. 9

Al terminar este laboratorio estará en la capacidad de:

Dentro de la Ciencia de las Redes, detalles aquí, frecuentemente se utilizan matrices para representar redes. Una de esas matrices se denomina matriz de adyacencia. Un ejemplo de ella se muestra en la siguiente tabla:

0 1 2 3 4
0 0 1 1 0 0
1 1 0 1 1 0
2 1 1 0 1 1
3 0 1 1 0 1
4 0 0 1 1 0

Lo primero a destacar de la matriz es que es cuadrada, es decir, tiene el mismo número de filas y columnas, en este caso 5, por lo que el orden de la matriz es de 5x5. Los números en negrita son los nombres de los nodos y no se consideran como parte de la matriz.

Otra característica de la matriz de adyacencia es que señala cuando el valor de la celda es igual a uno señala una relación entre ambos nodos, mientras que si es igual a cero indica ausencia de relación.

El grado de un nodo se determina sumando la fila o la columna de ese nodo. Así por ejemplo el nodo 0 tiene grado 2, ya que si suma la columna o la fila que empieza por 0 el resultado es dos.

El problema a resolver es encontrar el grado de cada nodo y grado medio de la red. Con ese fin se desarrollará un programa en Java que a través de la manipulación de una matriz y métodos se resuelva el problema propuesto.

Para resolver el problema se deben realizar los pasos que a continuación se describen.

1. Representar los datos

Los datos serán representados en una matriz, la misma que será inicializada. El código Java que hace lo descrito es el siguiente:

int [][] adyacencia = {
    {0, 1, 1, 0, 0},
    {1, 0, 1, 1, 0},
    {1, 1, 0, 1, 1},
    {0, 1, 1, 0, 1},
    {0, 0, 1, 1, 0}
};

Note como en la representación se dejaron fuera los nombres de los nodos, ya que no son parte de la matriz de adyacencia. Para inicializar una matriz, cada grupo de datos encerrados entre llaves constituyen una fila, cada valor se ubica en la columna según el orden que ocupan, así: el primero va en la columna 0, el segundo en la 1, etc. Observe como cada fila a su vez se encierra entre llaves señalando que es una matriz.

2. El grado medio

Para calcular el grado medio de la red, es necesario calcular el grado de cada nodo, sumarlo y luego dividir para el número de nodos que existen en la red. No olvide que la suma de cada una de las filas o de cada una de las columnas es el grado de un nodo.

El método desarrollado recorre todos los nodos de la red usando las filas de la matriz de adyacencia y suma las columnas (en la variable gradoNodo) para obtener el grado del nodo, agrega ese valor a un acumulador denominado sumaGrados, para finalmente calcular el grado medio dividiendo sumaGrados para la longitud de la matriz, que ese el número de nodos de la red.

El código del método es el siguiente:

public static double calcularGradoMedio(int [][] a) {
    int sumaGrados = 0;
    int gradoNodo;
    double gradoMedio;

    for(int i = 0; i < a.length; i ++) {
        gradoNodo = 0;
        for(int j = 0; j < a[i].length; j ++) {
            gradoNodo = gradoNodo + a[i][j];
        }
        sumaGrados = sumaGrados + gradoNodo;
    }
    gradoMedio = (double)sumaGrados / a.length;
    return gradoMedio;
}

Note como el primer for permite recorrer las filas, mientras que el segundo las columnas. Así mismo, por cada nodo (fila) se inicializa la variable gradoNodo para calcular así el grado de ese nodo. Finalmente, una vez que se tiene el grado del nodo actual se agrega a la variable sumaGrados.

3. El grado de un nodo

Para obtener el grado de un nodo, el usuario debe ingresar el nombre del nodo, números desde el 0 hasta el 4. Para evitar posibles errores se validrá el ingreso de los datos a través de un ciclo do...while.

Considerando que se necesita el grado de un nodo concreto, el método usará un único ciclo for, ya que no es necesario recorrer todos los nodos. Al igual que el método anterior se recorrerá la matriz por filas y se sumarán las columnas para obtener el grado. El código Java es el siguiente:

public static int obtenerGradoNodo(int nodoId, int [][] a) {
    int grado = 0;

    for(int j = 0; j < a[nodoId].length; j ++ ) {
        grado = grado + a[nodoId][j];
    }

    return grado;
}

Si compara este método con el anterior se puede percatar que son bastante similares ya que utilizan el mismo principio de trabajo, sumar las columnas de una fila representado por nodoId para obtener el grado del nodo.

4. El método principal

Lo único a destacar en el método principal es la validación que se hace para garantizar que el usuario ingresó un número válido que represente el nombre de un nodo. Deliberadamente se usó los índices de la matriz como nombres de los nodos, por lo tanto el usuario debe ingresar un número entre 0 y la longitud de matriz.

El código Java es el siguiente:

public static void main(String[] args) {
    int [][] adyacencia = {
        {0, 1, 1, 0, 0},
        {1, 0, 1, 1, 0},
        {1, 1, 0, 1, 1},
        {0, 1, 1, 0, 1},
        {0, 0, 1, 1, 0}
    };
    Scanner l = new Scanner(System.in);
    double gradoMedio;
    int kn;
    int n;

    gradoMedio = calcularGradoMedio(adyacencia);
    System.out.printf("Grado medio de la red: %f\n", gradoMedio);

    do {
        System.out.print("Ingrese el id del nodo: ");
        n = l.nextInt();
    } while(n < 0 || n >= adyacencia.length );

    kn = obtenerGradoNodo(n, adyacencia);
    System.out.printf("El grado del nodo %d es %d\n", n, kn);

}

El programa completo se muestra en el entorno de ejecución en línea repl.it. Una vez que ejecute el programa verá como se muestra el grado medio y luego le pidirán que ingrese el nombre del nodo, al principio trate de ingresar sólo números
que están fuera del rango permitido y verá como se vuelve a insistir en el ingreso del nombre del nodo, esto se repite hasta que ingresa un número válido.

Si desea ejecutar el programa haga clic sobre el botón run ▶ que se encuentra en la parte superior. También puede modificar, compilar y ejecutar su propio código. Finalmente puede abrir el programa en el sitio repl.it haciendo clic en open in.

En el método que calcula el grado medio se pueden realizar algunas mejoras ya que si suma todos los elementos de la matriz obtendrá el mismo resultado que sumar fila por fila. Lo invito a que intente implementar esa mejora.