将关联矩阵转换为邻接矩阵

Question

如何正确实现关联矩阵转邻接矩阵的算法？

图形将是无向的

不幸的是，我尝试做的算法没有用

const readline = require('readline')
        
const rl = readline.createInterface({input: process.stdin, output: process.stdout})
let arr = []
rl.question('Matrix N and M: ', async (userInput) => {
    const input = await userInput.split(' ')
    const arrayLength = input[0]
    const maxWidth = input[1]
    matrix(arrayLength, maxWidth)
})

const matrix = (arrayLength, maxWidth) => { 
    if(arrayLength === 0){
        convert(maxWidth)
    }
    if(arrayLength > 0){
        rl.question(`Row: ${arrayLength}, enter numbers separated by spaces: `, async (userInput) => {
            const subArray = await userInput.split(' ')
            subArray.length = maxWidth
            await arr.push(subArray)
            matrix(arrayLength - 1, maxWidth)
        })
    }
}
const convert = (maxWidth) => {
    let matrix = []
    let subArray = []
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < maxWidth; j++) {
     }
  }
}

Answer 1

所以有一些事情（缺少问题来源）。但是，这是您可以使用的一种方法。在这里，一个地图被用来存储边和顶点之间的关系。使用它，我们能够通过分组来构建顶点之间的关系。

为了方便使用，我们首先使用了一个promise-based提问功能。这可以使用以下

来完成

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

// Convert question function from cb to promise.
const question = (query) =>
  new Promise((resolve, _) => {
    rl.question(query, (input) => resolve(input));
  });

接下来，我们创建一个 main 函数来封装我们的逻辑。

async function main() {}

现在，让我们创建一个函数来为我们提取维数

async function getDimensions() { 
  // # of Vertices x # of Edges
  return (await question("Matrix N and M: ")).split(" ").map(x => +x)
}

完成后，我们可以创建两个辅助函数。第一个，它接受预期的顶点数。第二个，它采用生成的 incidenceMap 和预期顶点的数量（因此我们不必计算它）。

  async function createIncidenceMap(N) { }
  async function convertToAdjacencyMatrix(incidenceMap, N) { }

要实现createIncidentMap，我们可以使用下面的

// Create an Incidence Map for Quick Look Up
async function createIncidenceMap(N) {
  const incidentMatrix = [];

  // Read in the relationships between edges (columns) and vertices (rows).
  for (let i = 0; i < N; i++) {
    const result = (
      await question(`Row: ${i}, enter numbers separated by spaces: `)
    )
      .split(" ")
      .map((x) => +x);
    incidentMatrix.push(result);
  }

  // Group vertices by edges.
  return incidentMatrix.reduce((incidentMap, incidentPair, M) => {
    const incidentSubset = incidentPair.reduce(
      (subsetMap, connected, N) => (
        {
          ...subsetMap,
          [N]: [
            ...(subsetMap[N]?.length ? subsetMap[N] : []),
            ...(connected ? [M] : []),
          ],
        }
      ),
      {}
    );

    // Join previous vertices connected to the same edge.
    return Object.keys(incidentSubset).reduce((map, edge, index) => ({
      ...map,
      [edge]: new Set([
        ...(incidentMap[edge] ?? []),
        ...incidentSubset[edge]
      ]).values(),
    }), {});
  }, {});
};

这将减少 convertToAdjacencyMatrix

的工作量

function convertToAdjacencyMatrix(incidenceMap, M) {
  const connectedPairs = Object.values(incidenceMap).map(x => [...x])
  // (M x M)
  const adjacencyMatrix = new Array(M)
    .fill(0).map(_ => new Array(M).fill(0));

  connectedPairs.forEach(pair => {
    const [n1, n2] = pair
    // A vertice always has a relationship with itself.
    adjacencyMatrix[n1][n1] = 1
    adjacencyMatrix[n2][n2] = 1

    // Mark the relationship between the vertices sharing the same edge.
    adjacencyMatrix[n1][n2] = 1
    adjacencyMatrix[n2][n1] = 1
  })

  return adjacencyMatrix
};

最后我们结合main中的逻辑得到

async function main() {
  try {
    const[N,M] = await getDimensions()

    // Create incidentMatrix for faster conversion.
    const incidenceMap = await createIncidenceMap(N);
    // Convert.
    const adjacencyMatrix = convertToAdjacencyMatrix(incidenceMap, N)
    console.log(adjacencyMatrix)
    rl.close();
  } catch (err) {
    console.log(`Error found when reading ${err}`);
  }
}

使用您提供的输入调用 main 将产生

// [ [ 1, 1, 0 ], [ 1, 1, 1 ], [ 0, 1, 1 ] ]
main()

符合预期。

完整的示例可以在 demo

中找到

Answer 2

这不会尝试进行任何输入解析，但它会以相同的方式接受关联矩阵（作为数组的数组，这在 JS 中很典型）和 returns 邻接矩阵。它不进行错误检查以确保您提供的实际上是一个关联矩阵（其中每一列在其他任何地方都有两个 1s 和 0s。）这并不难添加，

它使用了一个 range 辅助函数，它 returns 一个介于低值（含）和高值（不含）之间的整数数组。例如，range (3, 12) returns [3, 4, 5, 6, 7, 8, 9, 10, 11].

主函数对输入中的行数进行双循环，迭代值代表行和列。对于每一个，我们检查输入中是否有任何列作为具有值 1 的两个索引（在排除两个索引相同的列之后。）

看起来像这样：

const range = (lo, hi) => 
  Array.from ({length: hi - lo}, (_, i) => i + lo)

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

const incidents = [
  [1, 0], 
  [1, 1], 
  [0, 1]
]

console .log (inci2adj (incidents))

.as-console-wrapper {max-height: 100% !important; top: 0}

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

这意味着如果我们从邻接矩阵开始，运行 adj2inci 从 ¹ 反对它，那么运行 inci2adj 在结果上，我们将得到与我们开始时相同的矩阵。但是如果我们从一个关联矩阵开始，运行 inci2adj 反对它，并且 adj2inci 结果，我们不一定会得到原始矩阵。

¹代码如下所示：

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})] : [])
    )
  )

将关联矩阵转换为邻接矩阵

converting incidence matrix to adjacency matrix

javascript

algorithm

graph

node.js