转换图.从一种类型的矩阵到另一种(以前的答案不正确) [英] converting graph. from one type of matrix to another (previous answer is incorrect)

问题描述

一个简单的无向图由邻接矩阵给出

A simple undirected graph is given by an adjacency matrix

一个简单的无向图由邻接矩阵定义.需要推导出关联矩阵

A simple undirected graph is defined by an adjacency matrix. It is necessary to derive the incidence matrix

输入:

3

0 1 0

1 0 1

0 1 0

输出:

1 0

1 1

0 1

输入:

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

输出:

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()

如何正确实现从一种矩阵到另一种矩阵的转换?

how to correctly implement the translation from one type of matrix to another?

推荐答案

这不会尝试做任何输入解析，但它确实接受一个邻接矩阵(作为数组的数组，在 JS 中是典型的)并返回一个关联矩阵以相同的方式.它不进行错误检查以确保您提供的实际上是一个邻接矩阵(其中每个值都是 0 或 1，主对角线都是 0s 及其关于主对角线对称.)这并不难添加，

This doesn't try to do any input parsing, but it does accept an adjacency matrix (as an array of arrays, as is typical in JS) and returns an incidence matrix in the same manner. It does no error-checking to ensure that what you supplied is actually an adjacency matrix (in which every value is 0 or 1, the main diagonals is all 0s and its symmetric about that main diagonal.) That would not be hard to add,

它使用一个 range 辅助函数，它返回一个介于低值(包含)和高值(不包含)之间的整数数组.例如，range (3, 12) 返回 [3, 4, 5, 6, 7, 8, 9, 10, 11].并且它使用一个 transpose 辅助函数，该函数在其主对角线上翻转矩阵，将行切换为列，反之亦然.

It uses a range helper function, which returns an array of integers between a low value (inclusive) and a high one (exclusive). For instance, range (3, 12) returns [3, 4, 5, 6, 7, 8, 9, 10, 11]. And it uses a transpose helper function which flips a matrix over its main diagonal, switching rows for columns and vice versa.

main 函数在矩阵的下对角线上进行双循环.对于每个具有 1 的坐标对，我们在该对中的每个索引处创建一行 0 除了 1 之外，代表一条边在图中.完成后，我们转置矩阵，使我们的边变成列.

The main function does a double-loop on the lower diagonal of the matrix. For each coordinate pair which has a 1, we create a row of 0s except for 1 at each index in that pair, representing an edge in the graph. When we are done, we transpose the matrix, so that our edges become columns.

看起来像这样:

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}

请注意，虽然图有明确的邻接矩阵，但关联矩阵有多种表示形式，因为列的重新排列仍将表示同一个图.

Note that although there is a definitive adjacency matrix for a graph, there are multiple representations as an incidence matrix, since a rearrangement of the columns will still represent the same graph.

这意味着如果我们从一个邻接矩阵开始，然后针对它运行 adj2inci，然后从 有关结果的相关答案¹，我们将返回与开始时相同的矩阵.但是如果我们从关联矩阵开始，对它运行inci2adj，然后对结果运行adj2inci，我们不一定会得到原始矩阵.

That means that if we start with an adjacency matrix, and run adj2inci against it, then run inci2adj from a related answer¹ on the result, we will get back the same matrix we started from. But if we start with an incidence matrix, run inci2adj against it, and adj2inci on the result, we will not necessarily get back the original matrix.

¹代码如下:

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
    )
  )

这篇关于转换图.从一种类型的矩阵到另一种(以前的答案不正确)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！