Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 36 ยท Graphs and Representations

Edge Lists and Incidence Matrices

Two more graph representations: the edge list, ideal for files and sorting, and the incidence matrix, ideal for algebra. Convert between all four forms with Python and NumPy.

You already know the adjacency matrix and the adjacency list. Two more representations are worth knowing. The edge list is the humblest and most common: it is how graphs are stored in files and databases. The incidence matrix relates vertices to edges and is the gateway to cycle and cut theory.

The edge list

An edge list is simply the list of all edges, each a pair (or a triple with a weight):

TEXT
0 1
0 2
1 2
2 3

This is exactly how most datasets arrive: a CSV file with columns source,target[,weight], or a database table edges(u, v, w).

Strengths: tiny and simple, trivial to read and write, and perfect when an algorithm processes edges in sorted order, such as Kruskal's minimum spanning tree. Weakness: finding the neighbors of a vertex requires scanning the whole list, O(m).

Python From an edge list to the other forms

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.

Notice how little code each conversion takes. In real projects you pick the best form for each step and convert in between, instead of forcing one representation everywhere.

Sorting edges

Because edges are just tuples, the standard Python tools work directly. Sorting by weight is the first step of Kruskal's algorithm:

Python Edge lists with weights

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.

The incidence matrix

The incidence matrix B has one row per vertex and one column per edge. For an undirected graph, B[v][e] = 1 if vertex v is an endpoint of edge e, otherwise 0. Every column therefore has exactly two ones, and the sum of row v equals deg(v).

For the edge list e0 = 0-1, e1 = 0-2, e2 = 1-2, e3 = 2-3:

TEXT
        e0 e1 e2 e3
   0  [  1  1  0  0 ]
   1  [  1  0  1  0 ]
   2  [  0  1  1  1 ]
   3  [  0  0  0  1 ]

For a directed graph the usual convention is +1 at the tail (where the arc starts) and -1 at the head (where it ends). Each column then sums to zero.

Python Incidence matrix and the Laplacian

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.

The product D Dแต€ is the graph Laplacian L = Deg โˆ’ A, one of the most important matrices in graph theory. It is not a coincidence: it reappears in the matrix-tree theorem of this chapter group, where its determinants count spanning trees.

Choosing a representation

Form Memory Best for
Edge list O(m) Storage, file formats, sorting edges, Kruskal
Adjacency list O(n + m) Traversals and most algorithms on sparse graphs
Adjacency matrix O(nยฒ) Dense graphs, constant-time edge test, linear algebra
Incidence matrix O(nm) Cycle spaces, flows, algebraic proofs

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which representation is the most natural for a CSV file of connections?

    Each row of the file is naturally one edge: source, target and maybe a weight.
  2. 2. In the (unsigned) incidence matrix of a simple undirected graph, every column contains:

    A column stands for one edge and an edge has exactly two endpoints.
  3. 3. What is the shape of the incidence matrix of a graph with 6 vertices and 9 edges?

    Rows are vertices (6), columns are edges (9).
  4. 4. How long does it take to find all neighbors of one vertex in a plain edge list?

    Nothing is indexed by vertex, so you must look at all m edges (or build an adjacency list first).

Summary

  • An edge list is the compact, file-friendly representation: O(m) memory.
  • Converting between edge list, adjacency list and adjacency matrix takes only a few lines.
  • The incidence matrix has one row per vertex and one column per edge; columns have two ones.
  • An oriented incidence matrix D satisfies D Dแต€ = Deg โˆ’ A, the Laplacian.
  • Choose the representation that fits the algorithm, and convert when needed.

Next: Building a Graph Class