Course notes for ESC190 Computer Algorithms and Data Structures
We can implement graphs using linked lists by storing all graph vertices in a linked list and each of those are the head of a linked list which holds nodes for all of the connected vertices. Since we focus on representing how the vertices are connected, we can think of adjacency lists as an edge-first approach to implementing graphs and indeed the size of the adjacency list depends on the number of edges in the graph.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Graph:
'''
We will implement a graph using an adjacency list by storing
a list for each node in the graph and each entry in the list
contains a linked list to store the neighbours of that node.
Note that the linked list of neighbours has an order in its
representation but that order doesn't matter when it comes
to representing the graph's data so any order is okay.
'''
def __init__(self, num_nodes):
self.adj_list = [None] * num_nodes # An empty list, big enough to hold every vertex's LL
def is_edge(self, i, j):
''' Given vertex indices i and j, check if there is an edge between these vertices'''
pass
def put_edge(self, i, j):
''' Given vertex indices i and j, place an edge from i to j'''
pass
def remove_edge(self, i, j):
''' Given vertex indices i and j, remove the edge from i to j'''
pass
Let’s implement a Node class to represent the vertices of the graph.
1
2
3
4
class Node:
def __init__(self, data):
self.data = data
self.next = None
Let’s also recall Linked Lists and implement them quickly in LL.py (along with Node):
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
48
49
50
51
52
53
54
55
56
57
58
59
60
# LL.py
class LL:
def __init__(self):
self.head = None
def insert(self, idx, data):
new_node = Node(data)
if self.head == None: # Empty LL case
self.head = new_node
else:
if idx == 0: # Prepending case
head_save = self.head
self.head = new_node
self.head.next = head_save
else:
cur = self.head
for jdx in range(idx - 1): # traverse LL, stop before idx
cur = cur.next
tmp = cur.next
cur.next = new_node
new_node.next = tmp
# Or we could use Python's swap
#cur.next, new_node.next = new_node, cur.next
def is_in(self, data):
cur = self.head
while cur: # equiv. while cur != None
if cur.data == data:
return True
cur = cur.next
return False # after traversing, return False if not found
def remove(self, data):
if head.data == data:
self.head = self.head.next # Let the gc take care of freeing the old head
return
cur = self.head
# Now traverse as long as the next node exists and
# its data is not the value we are looking for
while cur.next and cur.next.data != data:
cur = cur.next
# Either we reached the end ...
if cur.next == None: # equiv. if not cur.next:
print(f"[ERROR] failed to remove {data}")
return
# ... Or we succeeded
cur.next = cur.next.next
def __str__(self): # this allows us to print("My linked list is", LL)
cur = self.head
string = "(head) "
while cur: # equiv. while cur != None
string += str(cur.data) + " -> "
cur = cur.next
return string + "None"
We can now import the code we wrote as follows
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
import LL # assuming Node and LL are defined in LL.py
class Graph:
'''
We will implement a graph using an adjacency list by storing
a list for each node in the graph and each entry in the list
contains a linked list to store the neighbours of that node.
Note that the linked list of neighbours has an order in its
representation but that order doesn't matter when it comes
to representing the graph's data so any order is okay.
'''
def __init__(self, num_nodes):
self.adj_list = [None] * num_nodes # An empty list, big enough to hold every vertex's LL
self.num_nodes = num_nodes
for idx in range(self.num_nodes):
self.adj_list.append(LL.LL())
def is_edge(self, i, j):
''' Given vertex indices i and j, check if there is an edge between these vertices
Access LL i in the List adj_list, and search for Node with data j
'''
return self.adj_list[i].is_in(j)
def put_edge(self, i, j):
''' Given vertex indices i and j, place an edge from i to j
Always insert at the head of the ith LL to save time (instead of traversing)
Here we haven't implemented an deduplication mechanism,
though one should be considered in practise
'''
self.adj_list[i].insert(0, j) # At the ith LL, insert j in the head
def remove_edge(self, i, j):
''' Given vertex indices i and j, remove the edge from i to j'''
self.adj_list[i].remove(j)
Now let’s use our graph:
1
2
3
4
if __name__ == "__main__":
g = Graph(4) # equiv. Graph.__init__(4)
g.put_edge(1, 2) # equiv. Graph.put_edge(g, 1, 2)
print(g.is_edge(1, 2)) # True
It will often be useful to represent object in a graph and use named labels instead of keeping a mapping between names and the indices used in the graph. This requires us to alter our implementation of the graph slightly:
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
48
49
50
51
52
53
import LL # assuming Node and LL are defined in LL.py
class Graph:
'''
We will implement a graph using an adjacency list by storing
a list for each node in the graph and each entry in the list
contains a linked list to store the neighbours of that node.
Note that the linked list of neighbours has an order in its
representation but that order doesn't matter when it comes
to representing the graph's data so any order is okay.
'''
def __init__(self, num_nodes = 0):
# num_nodes is 0 by default, so if we want to use an unamed graph we simply pass num_nodes
# and avoid calling the ..._name() methods
# if we instead want a named graph, we omit num_nodes and add the nodes manually
self.adj_list = [None] * num_nodes # An empty list, big enough to hold every vertex's LL
self.num_nodes = num_nodes
self.node_names, self.node_names_rev = {}, {}
for idx in range(self.num_nodes):
self.adj_list.append(LL.LL())
def add_node(self, name):
self.node_names[name] = len(self.adj_list)
self.node_names_rev[len(self.adj_list)] = name
self.adj_list.append(LL.LL())
self.num_nodes += 1
def is_edge(self, i, j):
''' Given vertex indices i and j, check if there is an edge between these vertices
Access LL i in the List adj_list, and search for Node with data j
'''
return self.adj_list[i].is_in(j)
def is_edge_name(self, name_i, name_j):
''' Look up an edge from vertex i to vertex j by looking up the names first '''
return self.is_edge(self.node_names[name_i], self.node_names[name_j])
def put_edge(self, i, j):
''' Given vertex indices i and j, place an edge from i to j
Always insert at the head of the ith LL to save time (instead of traversing)
Here we haven't implemented an deduplication mechanism,
though one should be considered in practise
'''
self.adj_list[i].insert(0, j) # At the ith LL, insert j in the head
def is_edge_name(self, name_i, name_j):
''' Put an edge from vertex i to vertex j by looking up the names first '''
return self.put_edge(self.node_names[name_i], self.node_names[name_j])
def remove_edge(self, i, j):
''' Given vertex indices i and j, remove the edge from i to j'''
self.adj_list[i].remove(j)
We can now use our graph datastructure to implement an airport network
1
2
3
4
5
6
7
8
9
10
11
if __name__ == "__main__":
# Create a named graph
airports = Graph()
# Populate vertices
airports.add_node("YYZ")
airports.add_node("YVR")
airports.add_node("JFK")
# Connect with edges
airports.put_edge_name("YVR", "YYZ")
airports.put_edge_name("YYZ", "YVZ")
airports.put_edge_name("YYZ", "JFK")