Random Graphs in Python for A Level Computer Science and Beyond

Random Graphs in Python for A Level Computer Science and Beyond

The jupyter notebook below shows an implementation of an algorithm for generating a random undirected, unweighted graph. The algorithm uses the Erdős–Rényi model, but you don’t need to know about that to understand how it works – the pseudo code makes is quite clear, although you may need to spend a little time understanding exactly what it conveys. It may be that looking at the Python code first will give you more insight due to the wonderful clarity of Python syntax.

If you don’t use jupyter notebooks, don’t worry, the code will work just fine from your usual IDE, as long as you install the networkx package and remove the % commands (e.g %matplotlib inline) For info on installing Python packages see here.

The main purpose of this article is to get you up and running creating random graphs to help you with studying or teaching algorithms for A Level Computer Science and beyond. You can use the code to generate sample graphs to deepen your understanding of graph algorithms such as Dijkstra’s algorithm and the A Star Algorithm, or to generate questions for your students.

In terms of A Level Computer Science this will be more relevant to those studying for or teaching the OCR or AQA syllabus than the Cambridge one.

Please note, in the code, n is the required number of nodes and p is the probability that an edge exists between a given pair of nodes.

In [1]:
%load_ext nb_black

pseudocode

In [47]:
%matplotlib inline
import matplotlib.pyplot as plt
import networkx as nx
from itertools import combinations
from random import random


def ER(n, p):
    V = set([v for v in range(n)])
    E = set()
    for combination in combinations(V, 2):
        a = random()
        if a < p:
            E.add(combination)

    g = nx.Graph()
    g.add_nodes_from(V)
    g.add_edges_from(E)

    return g


n = 10
p = 0.4
G = ER(n, p)
pos = nx.spring_layout(G)
nx.draw_networkx(G, pos)
plt.title("Random Graph Generation Example")
plt.show()

There are more articles/videos on working with graphs and/or jupyter notebooks in Python here on the Compucademy blog. For example

python random graph example 2 A level computer science

Leave a Reply

Your email address will not be published. Required fields are marked

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}

Join our mailing list

Join our mailing list to receive awesome articles about learning Python and Computer Science in a fun and accessible way, straight to your inbox.

 Take your Python skills to the next level!

with our free email course on object oriented programming with Python