How can I transform an adjacency matrix into an incidence matrix?

Question

I created an adjacency matrix from an adjacency list, but I don't know how to create the incidence matrix from this data.

My code is this:

import numpy

graph = {'1': [{'2':'15'}, {'4':'7'}, {'5':'10'}],
    '2': [{'3':'9'}, {'4':'11'}, {'6':'9'}],
    '3': [{'5':'12'}, {'6':'7'}],
    '4': [{'5':'8'}, {'6':'14'}],
    '5': [{'6':'8'}]}

def weighted_adjmatrix(adjlist, nodes):
    '''Returns a (weighted) adjacency matrix as a NumPy array.'''
    matrix = []
    for node in nodes:
        weights = {endnode:int(weight)
                   for w in adjlist.get(node, {})
                   for endnode, weight in w.items()}
        matrix.append([weights.get(endnode, 0) for endnode in nodes])
    matrix = numpy.array(matrix)
    return matrix + matrix.transpose()



weighted_adjmatrix(graph, nodes=list('123456'))´

When I run it it throws this array:

array([[ 0, 15,  0,  7, 10,  0],
       [15,  0,  9, 11,  0,  9],
       [ 0,  9,  0,  0, 12,  7],
       [ 7, 11,  0,  0,  8, 14],
       [10,  0, 12,  8,  0,  8],
       [ 0,  9,  7, 14,  8,  0]])

Answer 1

From my understanding (and according to Wikipedia), the incidence matrix should have columns representing the edges and rows representing the vertices.

Now there is no explicit edge index in your input data. Let's look at a trivial graph given as vertices and edge list:

import numpy

vertices = {0, 1, 2}
edges = [(0, 1), (0, 2), (1, 2)]
assert all(l in vertices and r in vertices for l, r in edges)

incidence_matrix = numpy.zeros([max(vertices) + 1, len(edges)], dtype="int")
for i, edge in enumerate(edges):
    l, r = edge
    incidence_matrix[l][i] = 1
    incidence_matrix[r][i] = 1

print(incidence_matrix)

This results in the following incidence matrix:

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

Translated to your example (with edge indices inferred by order of the graph dict, assuming it is ordered like in Python 3.7+) this results in this:

def weighted_incidence_matrix(graph, nodes):
    edges = [
        (left, right, weight)
        for left in graph
        for edge in graph[left]
        # edge is actually a dict {target: weight}
        for right, weight in edge.items()
    ]
    assert all(l in nodes and r in nodes for l, r, _ in edges)
    incidence_matrix = numpy.zeros([len(nodes), len(edges)], dtype="int")
    for i, edge in enumerate(edges):
        l, r, weight = edge
        l = nodes.index(l)
        r = nodes.index(r)
        incidence_matrix[l][i] = weight
        incidence_matrix[r][i] = weight
    return incidence_matrix

print(weighted_incidence_matrix(graph, "123456"))

with the output matrix

[[15  7 10  0  0  0  0  0  0  0  0]
 [15  0  0  9 11  9  0  0  0  0  0]
 [ 0  0  0  9  0  0 12  7  0  0  0]
 [ 0  7  0  0 11  0  0  0  8 14  0]
 [ 0  0 10  0  0  0 12  0  8  0  8]
 [ 0  0  0  0  0  9  0  7  0 14  8]]

I hope this is what you are looking for.