# A graph representation of Adjacent Matrix in Python

I'm trying to create a graph representation in Adj Matrix in Python. I'm not sure if this is the best pythonic way.

class Graph(object):
def __init__(self, edge_list):
self.edge_list = edge_list

self.edge_list.append(edge_list)

v = 0
counter = set()
for src, dest in self.edge_list:

v = len(counter)

mtx = [[0 for y in range(v)]for x in range(v)]
for e in self.edge_list:
src, dest = e
src = src - 1
dest = dest - 1
mtx[src][dest] = 1

return mtx

edge_list = [(1,2), (2,3), (1,3)]
graph = Graph(edge_list)

assert mtx == [[0, 1, 1], [0, 0, 1], [0, 0, 0]]

assert graph.adj_mtx() == [[0, 1, 1], [0, 0, 1], [0, 0, 1]]

• How big do you expect the graph to be? Also, will you need the edge_list after initialization or just adj_matrix or both? – st0le Feb 20 '16 at 1:01
• I don't expect the graph to be big. I just want to be able to show the adj_matrix of a graph. so I don't need the add_edge. I guess what I was wondering is how can I improve the adj_mtx code? – toy Feb 20 '16 at 5:07

### Use third party libraries if possible

Almost anytime you want to do something, you probably want to use someone else's code to do it. In this case, whenever you're working with graphs in Python, you probably want to use NetworkX.

Then your code is as simple as this (requires scipy):

import networkx as nx

g = nx.Graph([(1, 2), (2, 3), (1, 3)])


### Friendlier interface

It seems unnecessarily cumbersome to have to explicitly initialize an empty Graph this way: g = Graph([]). I think a better implementation would be something like

class Graph(object):

def __init__(self, edge_list=None):
self.edge_list = edge_list if edge_list is not None else []


Similarly, I think the parameters for add_edge could use work. For one, it isn't a list of edges that you're passing it - it is a single edge, encoded as a list/tuple/collection of some kind. I also find it a little annoying that I have to create a tuple/list/whatever to actually add the edge to the graph - I'd rather just pass in the two end-points. I'd prefer something like this:

def add_edge(self, first, second):
self.edge_list.append((first, second))


At this point, however, I have to ask why you're representing your graph as a list of edges - to me, the most intuitive way to think of a graph (and how I've implemented one in the past) is to use a dictionary - to use your example, I'd probably encode it like this

{
1: {2, 3},
2: {1, 3},
3: {1, 2}
}


Then, instead of searching through an entire list to find a given edge, you just have to perform a quick dictionary lookup for one of the endpoints, and then a theoretically smaller iteration over a (hopefully) shorter list. I've also seen versions that use nested dictionaries very effectively.

### Your adj_mtx function

Note - I didn't change anything about the encoding here, I just used your implementation.

You could clean this up a bit. You don't need to initialize v where you do. It would also be easier if you kept the nodes in a set and added them whenever you added an edge.

In general, prefer xrange in Python 2, although that makes compatibility trickier - I generally use a library like six to handle things like that, although if you don't need everything you can write your own file (good name is usually compatibility.py) that has only the changes you need.

Instead of nested comprehensions, just do [0] * v. Also, if you don't care about a variable (such as x or y) use _ to identify it.

You can split up iteration variables in a for loop - for src, dest in self.edge_list is cleaner than for e in self.edge_list: src, dest = e.

Overall you could use more descriptive names in this function. I'd probably write it something like this:

def adj_mtx(self):
count = len(self.nodes)

matrix = [[0]*count for _ in range(count)]
for src, dest in self.edge_list:
src -= 1
dest -= 1
matrix[src][dest] = 1

return matrix


Additionally, it seems like adj_mtx should just be called adjacency_matrix, and I would rather it be a property (potentially with caching) than a function. Imagine something like this:

class Graph(object):

def __init__(self, edge_list=None):
self.edge_list = edge_list if edge_list is not None else []
self.nodes = set()
self.cache_valid = False

edge = first, second
self.edge_list.append(edge)
self.nodes.update(edge)
self.cache_valid = False

@property
if not self.cache_valid:
count = len(self.nodes)

matrix = [[0]*count for _ in range(count)]
for src, dest in self.edge_list:
src -= 1
dest -= 1
matrix[src][dest] = 1