FilesExpand file tree

master

/

graph_adjacency-list.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

47 lines (39 loc) · 1.2 KB

master

/

graph_adjacency-list.py

Copy path

Top

File metadata and controls

• Code
• Blame

47 lines (39 loc) · 1.2 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

# implementation of an undirected graph using Adjacency Lists

class Vertex:

def __init__(self, n):

self.name = n

self.neighbors = list()

def add_neighbor(self, v, weight):

if v not in self.neighbors:

self.neighbors.append((v, weight))

self.neighbors.sort()

class Graph:

vertices = {}

def add_vertex(self, vertex):

if isinstance(vertex, Vertex) and vertex.name not in self.vertices:

self.vertices[vertex.name] = vertex

return True

else:

return False

def add_edge(self, u, v, weight=0):

if u in self.vertices and v in self.vertices:

# my YouTube video shows a silly for loop here, but this is a much faster way to do it

self.vertices[u].add_neighbor(v, weight)

self.vertices[v].add_neighbor(u, weight)

return True

else:

return False

def print_graph(self):

for key in sorted(list(self.vertices.keys())):

print(key + str(self.vertices[key].neighbors))

g = Graph()

# print(str(len(g.vertices)))

a = Vertex('A')

g.add_vertex(a)

g.add_vertex(Vertex('B'))

for i in range(ord('A'), ord('K')):

g.add_vertex(Vertex(chr(i)))

edges = ['AB', 'AE', 'BF', 'CG', 'DE', 'DH', 'EH', 'FG', 'FI', 'FJ', 'GJ', 'HI']

for edge in edges:

g.add_edge(edge[:1], edge[1:])

g.print_graph()