Adjacency List and Adjacency Matrix in Python

Question

Hello I understand the concepts of adjacency list and matrix but I am confused as to how to implement them in Python:

An algorithm to achieve the following two examples achieve but without knowing the input from the start as they hard code it in their examples:

For adjacency list:

    a, b, c, d, e, f, g, h = range(8) 
    N = [ 
     {b:2, c:1, d:3, e:9, f:4},    # a 
     {c:4, e:3},                   # b 
     {d:8},                        # c 
     {e:7},                        # d 
     {f:5},                        # e 
     {c:2, g:2, h:2},              # f 
     {f:1, h:6},                   # g 
     {f:9, g:8}                    # h 
   ] 

For adjacency matrix:

    a, b, c, d, e, f, g, h = range(8) 
    _ = float('inf') 
    #     a b c d e f g h
    W = [[0,2,1,3,9,4,_,_], # a 
        [_,0,4,_,3,_,_,_], # b 
        [_,_,0,8,_,_,_,_], # c 
        [_,_,_,0,7,_,_,_], # d 
        [_,_,_,_,0,5,_,_], # e 
        [_,_,2,_,_,0,2,2], # f 
        [_,_,_,_,_,1,0,6], # g 
        [_,_,_,_,_,9,8,0]] # h

Again any help will be much appreciated, Thank you!

Luddite

For example I know that there is going to be an input in order to create the adjacency list or matrix but I don't know what the inputs are going to be, so basically in order to have an algorithm in which whenever I have an input of vertices and edges to creates the adjacency list or matrix... – Luddite

What does an infinity represent in an adjacency matrix? – Skipp

That is just an example of it amounting to infinity for a missing edge, you can disregard that and think of it as it representing no edge. – Luddite

Ok, so what does a 0 represent? To me, it seems you have them the wrong way around. – Skipp

Zero is for the identity, I'm guessing. It might not be appropriate for some kinds of graphs where you can have regular looping edges. It might also break some naive algorithms (which will loop infinitely without making any progress). – Mathewson

It is part of a programming assignment, it is more the adjacency list that I am having problems with especially since I am programming in python, in c++ i could have an array and than pointers to nodes that are connected by the number of edges, which I am unsure how to implement in python, when it comes to the adjacency matrix I feel it is more simple to implement since it is just a 2-D array with inputs of amount of edges in the 2-D array. – Luddite

Answer 1

Assuming:

edges = [('a', 'b'), ('a', 'b'), ('a', 'c')]

Here's some code for the matrix:

from collections import defaultdict

matrix = defaultdict(int)
for edge in edges:
    matrix[edge] += 1

print matrix['a', 'b']

2

And for the "list":

from collections import defaultdict

adj_list = defaultdict(lambda: defaultdict(lambda: 0))
for start, end in edges:
    adj_list[start][end] += 1

print adj_list['a']

{'c': 1, 'b': 2}

Skipp

Two of you have mentioned the defaultdict, and as I am new to Python I am not sure exactly what that means care to share some input on that? Thanks for the examples though they will help! – Luddite

@user1748026 The defaultdict type works just like a dictionary, but you provide it with a "factory function" when you set it up. Then, if you access a key that doesn't exist, it will call the factory function to create a default value for that key. – Mathewson

@Eric: I like your tuple index based solution for the matrix. For the list version, you can use int as the factory function for your inner defaultdict, rather than another lambda function. – Mathewson

Answer 2

Setting up your data structures can be pretty simple. For instance, the adjacency list example can be implemented using a defaultdict like this:

from collections import defaultdict

N = defaultdict(dict)

Then when you start getting input, just do N[start][end] = weight for each inputted edge. The set of nodes will be a little more tricky to come by, if you have some nodes with no outbound edges (you'll need to union the keys of the inner dictionaries with the outer one to be sure you have them all). But a lot of algorithms will work correctly even without a complete node list.

The adjacency matrix is a little more complicated, since you need to know the number of nodes there are in order to set its dimensions correctly. If you know it ahead of time, then its easy:

number_of_nodes = 8
_ = float("inf")

N = [[_]*number_of_nodes for i in number_of_nodes]

If you don't, you'll probably want to scan over the edges you get as input to find the highest numbered node, then use the same code above to make the matrix. For instance, if your edges are provided as a list of (start, end, weight) 3-tuples, you can use this:

number_of_nodes = max(max(start, end) for start, end, weight in edges)

Mathewson

Thank you for your input, it seems there is a lot more I need to learn when it comes to ways you can code things in python, things like number_of_nodes = max(max(start, end) for start, end, weight in edges), thanks for the input and I am going to try to work with some of the things you have provided! – Luddite

Will this create adjacency matrix when say some rows are missing(like the nodes are 1 2 5 6 Will this create a 6X6 or 4x4 matrix?) – Acidhead

Answer 3

I hope the below example helps you it has both Initialized Graph as well as user customized

class Graph:
"""
  Read the Intialized Graph and Create a Adjacency list out of it 
   There could be cases where in the initialized graph <map> link
  issues are not maintained
   for example node 2 to 1 link 
    2->1
   there needs to be a link then since undirected Graph
    1->2
"""

def __init__(self,Graph_init):
    self.edge={}
    for keys,values in Graph_init.items():
         for value in values:
             self.addEdge(keys,value);

"""
Add a vertex to graph map
structure is
int => int list
"""
def addVertex(self,v):
    if v not in self.edge:
        self.edge[v]=[]
"""
Add Edge from both vertex to each other
Make sure the nodes are present   

"""
def addEdge(self,u,v): if u not in self.edge: self.addVertex(u) if v not in self.edge: self.addVertex(v) if u not in self.edge[v]: self.edge[v].append(u) if v not in self.edge[u]: self.edge[u].append(v)

def isEdge(self,u,v):
    if u not in self.edge:
        return False
    if v not in self.edge:
        return False 
    return  u in self.edge[v] 

def display(self):
    for keys,values in self.edge.items():
        print(keys,":=>",values)

"""A initalized Graph (not in form of adjaceny list"""
Graph_init = {1:[2,3,5],
          2:[1,4],
          3:[1,6]};

"""Default constrcutor takes care of making the initialzed map to adjaceny 
list"""                 
g=Graph(Graph_init)
g.addVertex(1)
g.addVertex(2) 
g.addVertex(3)
g.addEdge(1,2)
g.addEdge(3,2)
g.display();

D