Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 36 ยท Graphs and Representations

Building a Graph Class

Write a reusable Graph class in Python with add, remove, degree, neighbors and iteration methods for directed or undirected weighted graphs, then compare it with networkx.

Passing dictionaries around gets messy. In this lesson we package an adjacency-list graph into a small, reusable class. We will use it, or variations of it, for the algorithms that follow, and finally compare it with the professional networkx.Graph.

Design decisions

We need to decide:

  1. Directed or undirected? One flag, directed. For undirected graphs, add_edge(u, v) stores the edge in both directions.
  2. Weights. Store a weight per edge, default 1.
  3. Vertices. Any hashable value. Vertices exist once they are added or used in an edge.
  4. Storage. dict of dict: adj[u][v] = weight. This gives neighbors in O(deg) and edge tests in O(1).

The result is a simple graph: adding an edge that exists again overwrites its weight.

The class

Python A reusable Graph class

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A few details deserve attention:

  • edges() is a generator and reports each undirected edge once, using a frozenset key.
  • remove_vertex must delete the vertex from every neighbor's dictionary. Forgetting this leaves dangling references.
  • neighbors returns a copy as a list, so callers cannot accidentally change the graph by editing it.

Directed graphs

The same class works for directed graphs. Degree now means out-degree, so we add helper methods on top of Graph:

Python Directed graphs with in-degree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

reverse() flips every arc. It is surprisingly useful: reachability to a vertex in G is reachability from it in the reversed graph, which we exploit when finding strongly connected pieces.

Comparing with networkx

Our class mirrors the most common networkx calls on purpose, so moving to the library later is painless.

Python Our API versus networkx

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

networkx stores the same dict-of-dicts internally, but also offers hundreds of algorithms. We implement the key ones by hand to understand them, then verify our results against it.

Common mistakes

  • Using a mutable default argument such as def __init__(self, adj={}): all graphs would share one dict.
  • Updating only one direction of an undirected edge.
  • Mutating self._adj[v] while looping over it (for example removing edges inside a for over neighbors). Copy first with list(...).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does add_edge store the edge twice for undirected graphs?

    An undirected edge is a relationship in both directions, so each endpoint's adjacency dict must contain the other.
  2. 2. Why is remove_vertex more work than remove_edge?

    Every neighbor's adjacency must drop the vertex, otherwise dangling references remain.
  3. 3. What does a dict of dicts give you compared with a dict of lists?

    adj[u][v] is a hash lookup. The trade-off: one edge per vertex pair, so no parallel edges.
  4. 4. In the directed Graph class, how is in_degree computed when only outgoing arcs are stored?

    Without reverse adjacency you must scan every vertex's neighbors, an O(n + m) operation.

Summary

  • A Graph class wraps a dict-of-dicts adjacency structure with a directed flag.
  • add_edge, remove_edge, neighbors, degree and edges() cover most needs.
  • Remove a vertex from every neighbor's dictionary to avoid dangling references.
  • reverse() flips all arcs of a directed graph.
  • The API deliberately mirrors networkx.

Next: Subgraphs and Isomorphism