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
input:
3
0 1 0
1 0 1
0 1 0
output:
1 0
1 1
0 1
input:
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
output:
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?
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,
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.
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.
It looks like this:
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.
That means that if we start with an adjacency matrix, and run adj2inci against it, then run inci2adj from a related answer1 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.
1The code looks like this:
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
)
)