Un gráfico no dirigido simple viene dado por una matriz de adyacencia
Un gráfico no dirigido simple se define mediante una matriz de adyacencia. Es necesario derivar la matriz de incidencia
aporte:
3
0 1 0
1 0 1
0 1 0
producción:
1 0
1 1
0 1
aporte:
5
0 0 1 1 0
0 0 1 0 0
1 1 0 0 1
1 0 0 0 1
0 0 1 1 0
producción:
1 0 1 0 0
0 1 0 0 0
1 1 0 1 0
0 0 1 0 1
0 0 0 1 1
const convert = () => { let arr = [ [0,0,1,1,0], [0,0,1,0,0], [1,1,0,0,1], [1,0,0,0,1], [0,0,1,1,0] ] let matrix = [] let subArray = [] for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length; j++) { subArray.push(0) } matrix.push(subArray) subArray = [] } for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length; j++) { if(arr[j][i] == 1){ subArray.push(j) } } console.log(subArray) subArray = [] } console.log(matrix) } convert()¿Cómo implementar correctamente la traducción de un tipo de matriz a otro?
Esto no intenta realizar ningún análisis de entrada, pero acepta una matriz de adyacencia (como una matriz de matrices, como es típico en JS) y devuelve una matriz de incidencia de la misma manera. No verifica errores para garantizar que lo que proporcionó es en realidad una matriz de adyacencia (en la que cada valor es 0 o 1 , las diagonales principales son todos 0 y son simétricas con respecto a esa diagonal principal). Eso no sería difícil de agregar ,
Utiliza una función auxiliar de range , que devuelve una matriz de enteros entre un valor bajo (inclusivo) y uno alto (exclusivo). Por ejemplo, range (3, 12) devuelve [3, 4, 5, 6, 7, 8, 9, 10, 11] . Y utiliza una función auxiliar de transpose que voltea una matriz sobre su diagonal principal, cambiando filas por columnas y viceversa.
La función principal hace un doble bucle en la diagonal inferior de la matriz. Para cada par de coordenadas que tiene un 1 , creamos una fila de 0 excepto 1 en cada índice de ese par, lo que representa un borde en el gráfico. Cuando hayamos terminado, transponemos la matriz, de modo que nuestros bordes se conviertan en columnas.
Se parece a esto:
const range = (lo, hi) => Array.from ({length: hi - lo}, (_, i) => i + lo) const transpose = (xs) => xs [0] .map ((_, i) => xs .map (r => r[i])) const adj2inci = (m) => transpose (range (0, m .length) .flatMap (j => range (0, j + 1) .flatMap ( i => m[j][i] == 1 ? [Object .assign (Array (m .length) .fill (0), {[i]: 1}, {[j]: 1})] : []) ) ) const incidents = [[0, 0, 1, 1, 0], [0, 0, 1, 0, 0], [1, 1, 0, 0, 1], [1, 0, 0, 0, 1], [0, 0, 1, 1, 0]] console .log (adj2inci (incidents)) .as-console-wrapper {max-height: 100% !important; top: 0}Tenga en cuenta que aunque existe una matriz de adyacencia definitiva para un gráfico, existen múltiples representaciones como una matriz de incidencia, ya que una reorganización de las columnas seguirá representando el mismo gráfico.
Eso significa que si comenzamos con una matriz de adyacencia y ejecutamos adj2inci contra ella, luego ejecutamos inci2adj desde una respuesta relacionada 1 en el resultado, obtendremos la misma matriz con la que comenzamos. Pero si comenzamos con una matriz de incidencia, ejecutamos inci2adj contra ella y adj2inci sobre el resultado, no necesariamente recuperaremos la matriz original.
1 El código se ve así:
const inci2adj = (m) => range (0, m .length) .map ( j => range (0, m .length) .map (i => m [0] .some ( (_, e) => i !== j && m [i] [e] == 1 && m [j] [e] == 1) ? 1 : 0 ) )