How to make an adjacency matrix out of a list?

Question

I have a list like:

[['10', '20', 2], ['10', '21', 2], ['10', '1', 2], ['10', '0', 3], ['10', '3', 2],
 ['10', '2', 2], ['10', '5', 3], ['10', '4', 3], ['10', '7', 2], ['10', '6', 2],
 ['10', '9', 2], ['10', '8', 2], ['10', '11', 2], ['10', '10', 2], ['10', '13', 2],
 ['10', '12', 2], ['10', '15', 2], ['10', '14', 2], ['10', '17', 0], ['10', '16', 3],
 ['10', '19', 2], ['10', '18', 2], ['1', '20', 3], ['1', '21', 3], ['1', '1', 3],
 ['1', '0', 0], ['1', '3', 3], ['1', '2', 3], ['1', '5', 4], ['1', '4', 4],
 ['1', '7', 3], ['1', '6', 3], ['1', '9', 3], ['1', '8', 3], ['1', '11', 3],
 ['1', '10', 3], ['1', '13', 3], ['1', '12', 3], ['1', '15', 3]]

(it's a lot bigger than this) which the first and second item are actually node names and the third one is the edge weight between them (I didn't make a graph though, it's a list).

I'd like to make an adjacency matrix out of this list.

Answer 1

def make_adj_matrix(data, directed=False):
    summary = {}
    result = []
    nodes = []

    for start, end, weight in data:
        # store nodes names for further use
        if start not in nodes:
            nodes.append(start)
        if end not in nodes:
            nodes.append(end)

        # collect and sum all weights
        summary.setdefault(start, {}).setdefault(end, 0)
        summary[start][end] += weight
        if not directed:
            summary.setdefault(end, {}).setdefault(start, 0)
            summary[end][start] += weight

    # # here you can sort your nodes
    # nodes.sort()

    # constructing result
    for i in nodes:
        row = []
        for j in nodes:
            row.append(summary.get(i, {}).get(j, 0))
        result.append(row)

    return result

Answer 2

Generally, you should be using NumPy for matrices unless some constraint forces you to use vanilla Python. NumPy handles matrices very efficiently.

Additionally, if you decide to use NumPy (and you should), this is a question that has been asked in the past for that library: numpy/scipy build adjacency matrix from weighted edgelist

Answer 3

Yes, you can do this with a defaultdict

In [1]: in_list =  [['10', '20', 2], ['10', '21', 2], ['10', '1', 2], ['10', '0', 3], ['10', '3', 2], ['10'
   ...: , '2', 2], ['10', '5', 3], ['10', '4', 3], ['10', '7', 2], ['10', '6', 2], ['10', '9', 2], ['10', '
   ...: 8', 2], ['10', '11', 2], ['10', '10', 2], ['10', '13', 2], ['10', '12', 2], ['10', '15', 2], ['10',
   ...:  '14', 2], ['10', '17', 0], ['10', '16', 3], ['10', '19', 2], ['10', '18', 2], ['1', '20', 3], ['1'
   ...: , '21', 3], ['1', '1', 3], ['1', '0', 0], ['1', '3', 3], ['1', '2', 3], ['1', '5', 4], ['1', '4', 4
   ...: ], ['1', '7', 3], ['1', '6', 3], ['1', '9', 3], ['1', '8', 3], ['1', '11', 3], ['1', '10', 3], ['1'
   ...: , '13', 3], ['1', '12', 3], ['1', '15', 3]]                                                        

In [2]: from collections import defaultdict

In [3]: tree = lambda: defaultdict(tree)

In [5]: adj_mat = tree()

In [6]: for edge in in_list:
   ...:     start, end, weight = edge
   ...:     adj_mat[start][end] = weight
   ...:                                 

In [7]: adj_mat
Out[7]:        
defaultdict(<function __main__.<lambda>>,
            {'1': defaultdict(<function __main__.<lambda>>,
                         {'0': 0,                          
                          '1': 3,                          
                          '10': 3,                         
                          '11': 3,                         
                          '12': 3,                         
                          '13': 3,                         
                          '15': 3,                         
                          '2': 3,                          
                          '20': 3,                         
                          '21': 3,                         
                          '3': 3,                          
                          '4': 4,                          
                          '5': 4,                          
                          '6': 3,
                          '7': 3,
                          '8': 3,
                          '9': 3}),
             '10': defaultdict(<function __main__.<lambda>>,
                         {'0': 3,
                          '1': 2,
                          '10': 2,
                          '11': 2,
                          '12': 2,
                          '13': 2,
                          '14': 2,
                          '15': 2,
                          '16': 3,
                          '17': 0,
                          '18': 2,
                          '19': 2,
                          '2': 2,
                          '20': 2,
                          '21': 2,
                          '3': 2,
                          '4': 3,
                          '5': 3,
                          '6': 2,
                          '7': 2,
                          '8': 2,
                          '9': 2})})

As I implemented this, I noticed that all your edges originate at either 1 or 10. Hmmm, weird.

Explanation

1. defaultdict is just a fancy name for a vivified hash map (if you are from a perl background)
2. The entries in the matrix are the edge weights
3. If you edges are bidirectional, you just have to add adj_mat[end][start] = weight in the for loop