Course contentsShow
← Computer Science
Lesson 683 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Hybrid and Compressed Representations

Explore advanced techniques like compressed sparse row format for very large sparse graphs.

Hybrid and Compressed Representations

What You'll Learn

You'll learn how to dramatically reduce memory usage for very large sparse graphs using advanced compression techniques like Compressed Sparse Row (CSR) format.

The Problem with Standard Representations

When storing massive graphs with millions of vertices but relatively few edges (sparse graphs), adjacency matrices waste enormous memory on zeros, and adjacency lists carry overhead from pointers or dynamic arrays. For web graphs, social networks, or scientific simulations, this becomes impractical.

Compressed Sparse Row (CSR) Format

CSR is a hybrid approach that combines the benefits of both adjacency matrices and lists while minimizing memory overhead. It uses three arrays:

  1. Edges array: Stores all destination vertices in order
  2. Offsets array: Marks where each vertex's neighbors start
  3. Optional weights array: For weighted graphs

Analogy: Imagine a library catalog where books (edges) are shelved continuously, and a table of contents (offsets) tells you exactly where each author's section begins. No wasted shelf space, fast lookup.

How It Works

For a graph with vertices {0, 1, 2} where:

  • Vertex 0 connects to [1, 2]
  • Vertex 1 connects to [2]
  • Vertex 2 has no edges

Edges: [1, 2, 2]
Offsets: [0, 2, 3, 3]

To find vertex 1's neighbors: slice edges from offsets[1] to offsets[2] → position 2 to 3 → [2]

Why Use CSR?

  • Memory efficient: No pointer overhead, no wasted zeros
  • Cache friendly: Contiguous memory improves performance
  • Relatively fast: Neighbor lookup is O(degree) with good locality
  • Industry standard: Used in graph databases and scientific computing libraries

Key Takeaway: Compressed Sparse Row format provides an optimal balance between memory efficiency and access speed for large sparse graphs, storing only actual edges in contiguous arrays with an offset index for fast vertex-to-neighbors lookup.