Lab 1 — Graphs in Python

Discrete Mathematics — Graphs, Trees & Binary Trees

Pr. El Hadiq Zouhair

Before you start

In this lab you implement a small graph library from scratch.

A graph is a dictionary mapping each vertex to the list of its neighbors (the adjacency-list representation from the lesson):
PythonG = {"A": ["B", "C"], "B": ["A"], "C": ["A"]}

We use networkx only to draw the graphs and to check your implementations — every algorithm must be written by hand.

How to work: run the notebook from top to bottom. Replace each # TODO and remove the raise NotImplementedError. A printed ✔ means the exercise's tests pass.

Contents

  1. Building a graph
  2. Degrees and the handshake lemma
  3. Breadth-first search (BFS)
  4. Depth-first search (DFS) & connected components
  5. Cycle detection
  6. Bipartite graphs and 2-coloring
  7. Greedy coloring

★ The 3-SAT as a coloring problem challenge is now a separate guided project:

→ Open the 3-SAT Coloring project

Setup

Run this cell first. It provides the drawing helpers used throughout the lab.

Python · providedimport networkx as nx import matplotlib.pyplot as plt from collections import deque def to_nx(G): """Convert a dict-of-lists graph into a networkx Graph (drawing/checking only).""" H = nx.Graph() H.add_nodes_from(G) for u in G: for v in G[u]: H.add_edge(u, v) return H def draw_graph(G, coloring=None, pos=None, title=""): """Draw a dict-of-lists graph; `coloring` may map vertices to small integers.""" H = to_nx(G) if pos is None: pos = nx.spring_layout(H, seed=7) palette = ["#e63946", "#2a9d8f", "#e9c46a", "#457b9d", "#f4a261", "#9b5de5"] if coloring is None: node_color = "#a8dadc" else: node_color = [palette[coloring[v] % len(palette)] for v in H.nodes()] plt.figure(figsize=(5.5, 4.2)) nx.draw(H, pos, with_labels=True, node_color=node_color, node_size=650, font_weight="bold", edge_color="#666666") plt.title(title) plt.show() print("Setup OK — networkx", nx.__version__)

Exercise 1Building a graph

Write the three functions below.

  1. add_vertex(G, v) — add vertex v to G (no effect if it is already there);
  2. add_edge(G, u, v) — add the undirected edge $\{u, v\}$ (add missing endpoints; never duplicate a neighbor);
  3. build_graph(vertices, edges) — build a fresh graph from a list of vertices and a list of pairs.
Python · your turndef add_vertex(G, v): """Add vertex v to G if not already present.""" # TODO raise NotImplementedError def add_edge(G, u, v): """Add the undirected edge {u, v} to G (and its endpoints if needed).""" # TODO raise NotImplementedError def build_graph(vertices, edges): """Return a new dict-of-lists graph with the given vertices and edges.""" # TODO raise NotImplementedError
Test cellEDGES = [("A","B"), ("A","C"), ("B","C"), ("B","D"), ("C","E"), ("D","E"), ("D","F"), ("E","F"), ("F","G")] G1 = build_graph("ABCDEFG", EDGES) assert set(G1) == set("ABCDEFG") assert set(G1["A"]) == {"B", "C"} and set(G1["F"]) == {"D", "E", "G"} add_edge(G1, "A", "B") # adding twice must not duplicate assert G1["A"].count("B") == 1 print("Exercise 1 ✔") draw_graph(G1, title="G1 — does it match the edge list?")

Exercise 2Degrees and the handshake lemma

  1. degree(G, v) — number of neighbors of v;
  2. degree_sequence(G) — list of all degrees, sorted in decreasing order;
  3. num_edges(G) — number of edges, without counting any edge twice.
The test cell checks the handshake lemma on G1: $$\sum_{v \in V} \deg(v) = 2\,|E|.$$
A graph has 9 vertices, all of degree 3. How many edges does it have?
Python · your turndef degree(G, v): """Degree of vertex v in G.""" # TODO raise NotImplementedError def degree_sequence(G): """All degrees of G, sorted in decreasing order.""" # TODO raise NotImplementedError def num_edges(G): """Number of edges of G (hint: use the handshake lemma).""" # TODO raise NotImplementedError
Test cellassert degree(G1, "F") == 3 and degree(G1, "G") == 1 assert degree_sequence(G1) == [3, 3, 3, 3, 3, 2, 1] assert num_edges(G1) == len(EDGES) assert sum(degree(G1, v) for v in G1) == 2 * num_edges(G1) # handshake lemma assert num_edges(G1) == to_nx(G1).number_of_edges() # networkx agrees print("Exercise 2 ✔ degree sequence:", degree_sequence(G1))

Exercise 3Breadth-first search

Implement bfs(G, s): return a dictionary {v: d(s, v)} giving the distance (number of edges) from s to every reachable vertex. Visit the vertices level by level using a queue (collections.deque, with append and popleft).

Python · your turndef bfs(G, s): """Return {v: distance from s} for every vertex reachable from s.""" # TODO — start from {s: 0} and a queue containing s raise NotImplementedError
Test celldist = bfs(G1, "A") assert dist == nx.single_source_shortest_path_length(to_nx(G1), "A") print("Exercise 3 ✔ distances from A:", dist) draw_graph(G1, coloring=dist, title="G1 colored by distance from A (BFS layers)")

Exercise 4Depth-first search and connected components

  1. dfs(G, s) — return the set of vertices reachable from s (iterative version, with an explicit stack: a plain Python list with append/pop);
  2. connected_components(G) — return the list of connected components, each one a set of vertices.
Python · your turndef dfs(G, s): """Set of vertices reachable from s (iterative DFS with a stack).""" # TODO raise NotImplementedError def connected_components(G): """List of the connected components of G (sets of vertices).""" # TODO — launch dfs from every not-yet-visited vertex raise NotImplementedError
Test cellG2 = build_graph(range(1, 11), [(1,2), (2,3), (3,1), (4,5), (5,6), (6,7), (7,4), (8,9)]) comps = connected_components(G2) assert sorted(map(len, comps)) == [1, 2, 3, 4] assert len(comps) == nx.number_connected_components(to_nx(G2)) assert dfs(G1, "A") == set(G1) # G1 is connected print("Exercise 4 ✔ components of G2:", comps) draw_graph(G2, title="G2 — four connected components")

Exercise 5Cycle detection

Implement has_cycle(G) for an undirected graph: run a DFS from every unvisited vertex, remembering each vertex's parent in the traversal; reaching an already-visited vertex that is not the parent reveals a cycle.

A connected graph with no cycle is a tree, and then $|E| = |V| - 1$.
Python · your turndef has_cycle(G): """True iff the undirected graph G contains a cycle.""" # TODO — DFS keeping track of each vertex's parent raise NotImplementedError
Test cellT = build_graph("ABCDEF", [("A","B"), ("A","C"), ("B","D"), ("B","E"), ("C","F")]) assert not has_cycle(T) and num_edges(T) == len(T) - 1 # a tree! assert nx.is_tree(to_nx(T)) # networkx agrees assert has_cycle(G1) and has_cycle(G2) P5 = build_graph(range(5), [(i, i + 1) for i in range(4)]) assert not has_cycle(P5) print("Exercise 5 ✔") draw_graph(T, title="T — connected and acyclic: a tree")

Exercise 6Bipartite graphs and 2-coloring

A graph is bipartite when its vertices split into two sides such that every edge joins the two sides — equivalently, when it admits a proper 2-coloring (adjacent vertices always get different colors).

Implement two_color(G): return a dict {vertex: 0 or 1} describing a proper 2-coloring if one exists, and None otherwise. Color along a BFS, handling every component; finding two neighbors with the same color means an odd cycle is present.

Python · your turndef two_color(G): """A proper 2-coloring of G as a dict, or None if G is not bipartite.""" # TODO — BFS per component, alternating colors 0 / 1 raise NotImplementedError
Test cellC6 = build_graph(range(6), [(i, (i + 1) % 6) for i in range(6)]) C5 = build_graph(range(5), [(i, (i + 1) % 5) for i in range(5)]) K33 = build_graph(range(6), [(i, j) for i in range(3) for j in range(3, 6)]) for G, expected in [(C6, True), (C5, False), (K33, True), (T, True), (G1, False)]: c = two_color(G) assert (c is not None) == expected == nx.is_bipartite(to_nx(G)) if c is not None: # the coloring must be proper assert all(c[u] != c[v] for u in G for v in G[u]) print("Exercise 6 ✔ (even cycles, trees, K33: yes — odd cycles: no)") draw_graph(C6, coloring=two_color(C6), title="C6 is 2-colorable") draw_graph(K33, coloring=two_color(K33), title="K(3,3) is bipartite")

Exercise 7Greedy coloring

Implement greedy_coloring(G, order=None): scan the vertices in the given order — by default the Welsh–Powell order, i.e. decreasing degree — and give each vertex the smallest color (a non-negative integer) not already used by its neighbors. Return the dict {vertex: color}.

The wheel $W_n$ is a cycle on $n$ vertices plus a hub joined to every cycle vertex. How many colors are needed when $n$ is even? When $n$ is odd?
Python · your turndef greedy_coloring(G, order=None): """Greedy proper coloring of G following `order` (default: decreasing degree).""" # TODO — for each vertex, collect the neighbors' colors, take the smallest free one raise NotImplementedError
Test celldef wheel(n): """Cycle 0..n-1 plus a hub 'h' joined to every cycle vertex.""" G = build_graph(range(n), [(i, (i + 1) % n) for i in range(n)]) for i in range(n): add_edge(G, "h", i) return G PETERSEN_EDGES = [(0,1),(1,2),(2,3),(3,4),(4,0), (5,7),(7,9),(9,6),(6,8),(8,5), (0,5),(1,6),(2,7),(3,8),(4,9)] P = build_graph(range(10), PETERSEN_EDGES) for G in [wheel(6), wheel(5), P, G1]: c = greedy_coloring(G) assert all(c[u] != c[v] for u in G for v in G[u]) # proper coloring n_colors = lambda c: max(c.values()) + 1 print("colors used: W6 ->", n_colors(greedy_coloring(wheel(6))), "| W5 ->", n_colors(greedy_coloring(wheel(5))), "| Petersen ->", n_colors(greedy_coloring(P)), "| networkx on Petersen ->", n_colors(nx.greedy_color(to_nx(P)))) draw_graph(P, coloring=greedy_coloring(P), title="Petersen graph — greedy coloring") print("Exercise 7 ✔")

★ Next: the 3-SAT challenge

The famous reduction from Boolean satisfiability to graph 3-coloring builds on everything above. It is now a separate guided project so you can treat it as a mini-assignment.

→ Open the 3-SAT Coloring project

Summary

You implemented from scratch, on dict-of-lists graphs: construction, degrees (+ handshake lemma), BFS distances, DFS, connected components, cycle detection, the bipartite test by 2-coloring, and greedy coloring. Throughout, networkx served as an independent referee for your code.