CODEWITHSUNDEEP
pythonadjacency-list
theGreatWhatever
theGreatWhatever

Reputation: 33

Adjacency List Implementation in Python

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

Upvotes: 0

Views: 4956

Answers (2)

pharask
pharask

Reputation: 332

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()

Upvotes: 1

D-Von
D-Von

Reputation: 426

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.)

Upvotes: 0

Related Questions