Adjacency matrix in Python

Question

I cannot find any clear explanation as to how to create an adjacency matrix in Python, with weights taken into consideration. I assume it should be relatively simple to create.

I have the following matrix...

   1   2   3   4   5   6
1  0   15  0   7   10  0
2  15  0   9   11  0   9
3  0   9   0   0   12  7
4  7   11  0   0   8   14
5  10  0   12  8   0   8
6  0   9   7   14  8   0

The numbers 1 through 6 are vertices, and the numbers within are the weights between each neighbouring vertex. For example, edge 1-2 has weight 15.

How would I implement this in python? I just need a simple example, not necessarily using the one I provided.

I know how to create an adjacency list...

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'}]}

but I need an adjacency matrix.

Answer 1

I think the most common and simplest concept to store an adjacency matrix is to use a 2D array, which in python corresponds to nested lists

mat = [[0, 15, 0, 7, 10, 0], [15, 0, ...], [...], [...]]
m[0][1]  # = 15 (weight of 1-2)

If the values are read only, you can use nested tuples, instead :)

Of course you can go as crazy as you want with that and use dictionaries or write a class and redefine __getattr__ to be more efficient on access times and storage as the matrix is symmetrical.

Answer 2

I like tupled keys for 2d structures like this in python.

{(1, 1): 0, (3, 2): 9... }

I think it's conceptually clearest since it drops the intermediary data structure in the above solution. Nonetheless, that intermediary data structure -- the inner list or row / column-- can be useful if you intend to access your structure either row or column wise.

 for x, row in enumerated(matrix, 1):
       # process whole row 
       for y in enumerate(row, 1):
             # process cell...

If cell-wise data access is your game though, it's hard to beat the following for expressive simplicity:

for (x, y), value in matrix.iteritems():
      # act on cell

Sort it if you want.

 # (1, 1), (1, 2)...
 for (x, y), value in sorted(matrix.iteritems()):
       # act on cell

Answer 3

This converts your "adjacency list" (really a dict, not a list) into a genuine matrix:

import networkx as nx

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'}]}
new_graph = nx.Graph()
for source, targets in graph.iteritems():
    for inner_dict in targets:
        assert len(inner_dict) == 1
        new_graph.add_edge(int(source) - 1, int(inner_dict.keys()[0]) - 1,
                           weight=inner_dict.values()[0])
adjacency_matrix = nx.adjacency_matrix(new_graph)

(The format of your graph is not particularly convenient for use in networkx.) networkx supports all kinds of operations on graphs and their adjacency matrices, so having the graph in this format should be very helpful for you. Note also that I've shifted your graph to use Python indices (i.e., starting at 0).

In [21]: adjacency_matrix
Out[21]: 
matrix([[  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 4

As mentioned previously, the standard way to deal with matrices in Python is to use NumPy. Here's a function that simply reads the adjacency matrix off of the adjacency list. (The implicit ordering of the nodes is made explicit by the parameter nodes.)

import numpy

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

In this case, weighted_adjmatrix(graph, nodes=list('123456')) gives the NumPy 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]])

If a regular list is desired, the method tolist() can be called.

Answer 5

#Graph using adjacency matrix
class GraphAM:
    #no of vertices
    __n=0
    #adjacency matrix of size 10x10 initialize with 0
    __g=[[0 for column in range(10)]for row in range(10)]
    __listofVertex=[]

    def __init__(self,vertex):
        #adding a vertex in a list 
        self.__listofVertex.append(vertex)
        #saving no of vertices
        self.__n=len(self.__listofVertex)
        #updating the adjacency matrix --> NxN matrix for row and column 0
        for source in range(0, self.__n):
            for destination in range(0, self.__n):
                self.__g[source][destination]= 0
    
    def add_vertex(self,source,destination):
        #intialize source Index and destination index with 0
        indexS=0
        indexD=0
        #check if source vertex available in list  __listofVertex, if not present then add it
        if source in self.__listofVertex:
            indexS=self.__listofVertex.index(source)
        else:
            print("Vertex {0} not present in Graph, adding it automatically.".format(source))
            self.__listofVertex.append(source)
            indexS=self.__listofVertex.index(source)
            #addition of vertex done so increment the count of vertex   
            self.__n = self.__n + 1
            
        #check if destination vertex available in list  __listofVertex, if not present then add it   
        if destination in self.__listofVertex:
            indexD=self.__listofVertex.index(destination)
        else:
            print("Vertex {0} not present in Graph, adding it automatically.".format(destination))
            self.__listofVertex.append(destination)
            indexD=self.__listofVertex.index(destination)
            #addition of vertex done so increment the count of vertex   
            self.__n = self.__n + 1
    
        if(indexS>= self.__n) or (indexD >= self.__n):
            print("One of the vertex doesn't exists !")
            
        if self.__n > 1:
            for i in range(0, self.__n):
                self.__g[i][self.__n-1]= 0
                self.__g[self.__n-1][i]= 0

            
    def add_edge(self,source,destination):
        #intialize source Index and destination index with 0
        indexS=0
        indexD=0
        if source in self.__listofVertex:
            indexS=self.__listofVertex.index(source)
        else:
            print("Cannot be included in the graph ,  Add the vertex {0}".format(source))
            
        if destination in self.__listofVertex:
            indexD=self.__listofVertex.index(destination)
        else:
            print("Cannot be included in the graph ,  Add the vertex {0}".format(destination))
            
        if (indexS >0 and indexS == indexD):
            print("Same Source and Destination")
        else:
            self.__g[indexS][indexD]= 1
            self.__g[indexD][indexS]= 1 
    
    def removeVertex(self, location):
        indexL=0
        if location in self.__listofVertex:
            #get location index in the list
            indexL=self.__listofVertex.index(location)
            while(indexL < self.__n ):
                for i in range(0, self.__n):
                       self.__g[i][indexL]= self.__g[i][indexL + 1]
                
                for i in range(0, self.__n):
                       self.__g[indexL][i]= self.__g[indexL + 1][i]
                indexL = indexL + 1
                
            self.__n = self.__n -1
            self.__listofVertex.remove(location)
            print("Successfully removed {0} from graph,current list of vertex are below :\n  {1} ".format(location,self.__listofVertex))
        else:
            print("No such vertex exist in the graph")
        
    def print_graph(self):
        print("\n")
        for i in range(len(self.__listofVertex)):
            print("\t\t", self.__listofVertex[i],end ="")
        for i in range(0, self.__n):
            print("\n",self.__listofVertex[i],end="  ")
            for j in range(0, self.__n):
                print("\t\t", self.__g[i][j], end ="")
                
        print("\n")
            


g1=GraphAM("MUM")
g1.add_vertex("MUM","DL")
g1.add_vertex("DL","KOL")
g1.add_vertex("HYD","BLR")
g1.add_vertex("CHN","KOL")
g1.add_vertex("HYD","GHY")
g1.add_edge("MUM","DL")
g1.add_edge("DL","KOL")
g1.add_edge("HYD","BLR")
g1.add_edge("CHN","KOL")
g1.add_edge("HYD","GHY")
g1.print_graph()
g1.removeVertex("KOL")
g1.print_graph()