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)])
print nx.adjacency_matrix(g)
g.add_edge(3, 3)
print nx.adjacency_matrix(g)
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))
Encoding your graph
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):
_adjacency_matrix = None
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
def add_edge(self, first, second):
edge = first, second
self.edge_list.append(edge)
self.nodes.update(edge)
self.cache_valid = False
@property
def adjacency_matrix(self):
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
self._adjacency_matrix = matrix
self.cache_valid = True
return self._adjacency_matrix
def clear_cache(self):
self.cache_valid = False
self._adjacency_matrix = None
Note that if someone adds edges to the list manually, or does other weird things, then the caching won't work.
