Adjacency List Implementation in Python

Question

I'm a newbie to Python (and computer science in general), so bear with me.

I'm having trouble implementing an adjacency list in Python. I have learned how to implement it through a dictionary (I learned how through here lol), but I need to know how to do it using only basic lists (list of lists)

This is my code:

with open("graph1.txt") as infile:
    vertices = []
    for line in infile:
        line = line.split()
        line = [int(i) for i in line]
        vertices.append(line)


adj = dict()

for edge in vertices:
    x, y = int(edge[0]), int(edge[1])
    if x not in adj: adj[x] = set()
    if y not in adj: adj[y] = set()
    adj[x].add(y)
    adj[y].add(x)
print(adj)

Any help is appreciated. Cheers

It works, but I can't figure out how to implement this without using dictionaries and the set() function — theGreatWhatever
– theGreatWhatever, Commented Sep 9, 2016 at 20:48
Wait, you have a data structure called vertices, but it's a list of edges? — user2357112
– user2357112, Commented Sep 9, 2016 at 20:51
Oh no, that's just some arbitrary name I gave to it, its not representative of anything. I guess because I'm thinking of each line being a vertex pointing to something else. — theGreatWhatever
– theGreatWhatever, Commented Sep 9, 2016 at 20:56

pharask · Accepted Answer · 2017-02-25 11:26:15Z

1

I am not sure whether you got it but anyway here is my python implementation for adjacency list. I have used list of lists. Python 2 Code :

class graph(object):
    def __init__(self, n):
        self.n=n
        self.mat=[list() for i in range(n)]

    def insert(self, u, v, w):
        t=[v, w]
        self.mat[u].append(t)

    def printGraph(self):
        i=0
        for i in range(self.n):
            print i, self.mat[i]

    def deleteEdge(self, u, v):
        weight=0
        for x in self.mat[u]:
            if x[0]==v:
                weight=x[1]
                break
        self.mat[u].remove([v, weight])

g=graph(3) # 3 is the number of vertices
g.insert(0, 1, 10) # 10 is the weight of the edge
g.insert(0, 2, 12)
g.insert(1, 2, 9)

g.printGraph()
g.deleteEdge(0, 1)
g.printGraph()

answered Feb 25, 2017 at 11:26

pharask

3328 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

D-Von · Accepted Answer · 2016-09-09 21:01:00Z

0

You'll still be thinking in terms of a set of vertices, each with a set of adjacent vertices, but you will be implementing the sets as lists rather than with a more sophisticated set data structure. You will need a fast way to index into the top-level set, and the only way to do that is with integer indexes. So you want to assign a (natural or arbitrary) integer k to each vertex, then put that vertex's adjacency set (implemented as a list) into slot k of the top-level list. It is less important to provide for efficient indexing into the second-level lists, since you typically iterate over them rather than selecting a particular one, but since Python has a built-in list that happens to provide efficient indexing with integers, why not use it?

I agree with the comment that a variable called vertices shouldn't hold edges. Everyone in the world but you will be confused, and later you also will be confused. I suggest you use the name vertices for the top-level list I described above. Then the second-level lists can just hold indices into the top-level vertices. (Well, maybe you need edge objects, too -- I don't know what you are using this for -- but a purist's adjacency-list representation has no room for edge objects.)

edited Sep 9, 2016 at 21:01

answered Sep 9, 2016 at 20:53

D-Von

4262 silver badges5 bronze badges

1 Comment

theGreatWhatever Over a year ago

Ah ok. I'll try that out. I'm a student, so I guess I'm trying to learn the basics as much as possible.

Collectives™ on Stack Overflow

Adjacency List Implementation in Python

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related