how to correctly implement the converting incidence matrix to adjacency matrix algorithm?

the graph will be undirected

3 - vectires

2 - edges

input: 3 2

1 0

1 1

0 1

output:

0 1 0

1 0 1

0 1 0

unfortunately the algorithm I was trying to do didn't work

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

CodePudding user response：

So there's a few things (lack of problem origin). However, this is one approach you can use. Here, I used an object to store the relationship between edges and vertices. Using that, I was able to construct the relationships between the vertices through their groupings.

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

async function main() {
  try {
    // N -> Number of Vertices (Rows)
    // M -> Number of Edges (Columns)
    // Extract dimensions and convert to numbers.
    const [N, M] = (await question("Matrix N and M: "))
      .split(" ")
      .map((x) =>  x);

    // 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: unable to read ${err}`);
  }
}

// Create an Incidence Map for Quick Look Up
const createIncidenceMap = async (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(),
    }), {});
  }, {});
};

const convertToAdjacencyMatrix = (incidenceMap, M) => {
  const connectedPairs = Object.values(incidenceMap).map(x => [...x])
  // (M x M)
  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();

The above code should produce the following result:

[ [ 1, 1, 0 ], [ 1, 1, 1 ], [ 0, 1, 1 ] ]