2
\$\begingroup\$

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

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

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

        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)
mtx = graph.adj_mtx()

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

graph.add_edge((3,3))
mtx = graph.adj_mtx()
assert graph.adj_mtx() == [[0, 1, 1], [0, 0, 1], [0, 0, 1]]
\$\endgroup\$
  • \$\begingroup\$ How big do you expect the graph to be? Also, will you need the edge_list after initialization or just adj_matrix or both? \$\endgroup\$ – st0le Feb 20 '16 at 1:01
  • \$\begingroup\$ 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? \$\endgroup\$ – toy Feb 20 '16 at 5:07
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This is exactly what I needed. I was hoping to create that manually because I'm preparing for an interview. That's why I didn't want to use any library. \$\endgroup\$ – toy Feb 22 '16 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.