Golang DSA Chapter 9 Part 2: Sparse Matrices and Real-World Uses

Welcome back. In Part 1 we covered graph fundamentals, social networks, and map layouts. Now Kommadi finishes Chapter 9 with two more practical topics: knowledge graphs and sparse matrix representation. Both build on the graph foundation from Part 1, but they’re different enough to deserve their own discussion.

Let’s get into it.

Knowledge Graphs

A knowledge graph is basically a network where entities, items, and users become nodes, and relationships between them become edges. Think of it like a flexible database without a strict schema. You just keep adding nodes and connecting them as you learn more about the domain.

Kommadi introduces the concept of an ontology here, which is a fancy word for “organized knowledge.” An ontology is made up of classes (the types of things), slots (the properties), and facets (constraints on those properties). The example he picks is a car’s bill of materials, which is a nice practical choice.

The building blocks start simple. A Class is just a named thing:

type Class struct {
    Name string
}

Then the KnowledgeGraph struct uses two maps. One tracks all the nodes (classes), and the other tracks the links between them:

type KnowledgeGraph struct {
    GraphNodes map[Class]struct{}
    Links      map[Class]map[Class]struct{}
}

Notice the struct{} values. That’s Go’s way of making a set. An empty struct takes zero bytes, so map[Class]struct{} is just “a set of Class values.” The Links map goes one level deeper: for each class, it stores a set of classes that it connects to.

Creating a new knowledge graph initializes both maps:

func NewKnowledgeGraph() *KnowledgeGraph {
    return &KnowledgeGraph{
        GraphNodes: make(map[Class]struct{}),
        Links:      make(map[Class]map[Class]struct{}),
    }
}

Adding Classes and Links

The AddClass method checks whether a class already exists and adds it if it doesn’t:

func (knowledgeGraph *KnowledgeGraph) AddClass(class Class) bool {
    var exists bool
    if _, exists = knowledgeGraph.GraphNodes[class]; exists {
        return true
    }
    knowledgeGraph.GraphNodes[class] = struct{}{}
    return true
}

It always returns true, which is a bit odd. In real code you’d probably want different return behavior for “already existed” vs “just added.” But for a learning example, it works fine.

The AddLink method is more interesting. It creates the link between two classes, and it automatically adds any missing classes along the way:

func (knowledgeGraph *KnowledgeGraph) AddLink(class1 Class, class2 Class) {
    var exists bool
    if _, exists = knowledgeGraph.GraphNodes[class1]; !exists {
        knowledgeGraph.AddClass(class1)
    }
    if _, exists = knowledgeGraph.GraphNodes[class2]; !exists {
        knowledgeGraph.AddClass(class2)
    }

    if _, exists = knowledgeGraph.Links[class1]; !exists {
        knowledgeGraph.Links[class1] = make(map[Class]struct{})
    }
    knowledgeGraph.Links[class1][class2] = struct{}{}
}

This is a directed link. AddLink(car, tyre) means “car connects to tyre” but not the other way around. That fits a bill of materials nicely, because a car contains a tyre, not the reverse.

Printing It Out

The PrintLinks method first prints all links adjacent to a hardcoded “Car” node, then prints every link in the graph:

func (knowledgeGraph *KnowledgeGraph) PrintLinks() {
    var car Class
    car = Class{"Car"}

    fmt.Printf("Printing all links adjacent to %s\n", car.Name)
    var node Class
    for node = range knowledgeGraph.Links[car] {
        fmt.Printf("Link: %s -> %s\n", car.Name, node.Name)
    }

    var m map[Class]struct{}
    fmt.Println("Printing all links.")
    for car, m = range knowledgeGraph.Links {
        var vertex Class
        for vertex = range m {
            fmt.Printf("Link: %s -> %s\n", car.Name, vertex.Name)
        }
    }
}

Hardcoding “Car” in the print method isn’t great design, but it’s fine for demonstrating the concept.

The Full Example

Kommadi builds a small car parts hierarchy. A car has tyres, doors, and a hood. Then tyres have tubes and axles, and doors have handles and window glass:

func main() {
    var knowledgeGraph *KnowledgeGraph
    knowledgeGraph = NewKnowledgeGraph()

    var car = Class{"Car"}
    var tyre = Class{"Tyre"}
    var door = Class{"Door"}
    var hood = Class{"Hood"}

    knowledgeGraph.AddClass(car)
    knowledgeGraph.AddClass(tyre)
    knowledgeGraph.AddClass(door)
    knowledgeGraph.AddClass(hood)

    knowledgeGraph.AddLink(car, tyre)
    knowledgeGraph.AddLink(car, door)
    knowledgeGraph.AddLink(car, hood)

    var tube = Class{"Tube"}
    var axle = Class{"Axle"}
    var handle = Class{"Handle"}
    var windowGlass = Class{"Window Glass"}

    knowledgeGraph.AddClass(tube)
    knowledgeGraph.AddClass(axle)
    knowledgeGraph.AddClass(handle)
    knowledgeGraph.AddClass(windowGlass)

    knowledgeGraph.AddLink(tyre, tube)
    knowledgeGraph.AddLink(tyre, axle)
    knowledgeGraph.AddLink(door, handle)
    knowledgeGraph.AddLink(door, windowGlass)

    knowledgeGraph.PrintLinks()
}

This gives you a tree-like structure: Car at the top, components below it, and sub-components below those. The output shows all the connections: Car -> Tyre, Car -> Door, Car -> Hood, Tyre -> Tube, and so on.

The unit test is straightforward, just making sure NewKnowledgeGraph() doesn’t return nil:

func TestNewKnowledgeGraph(test *testing.T) {
    var knowledgeGraph *KnowledgeGraph
    knowledgeGraph = NewKnowledgeGraph()
    test.Log(knowledgeGraph)
    if knowledgeGraph == nil {
        test.Errorf("error in creating a knowledgeGraph")
    }
}

Sparse Matrix Representation

Now for something completely different. Kommadi switches from graphs to sparse matrices, which is a classic data structures topic.

A sparse matrix is a matrix where most of the elements are zero. Think of a 1000x1000 matrix where only 50 cells have actual values. Storing all one million cells would be wasteful. Instead, you store only the non-zero elements.

This comes up in real problems like the finite element method (FEM) for solving partial differential equations. Big engineering simulations generate huge matrices that are mostly empty.

Kommadi represents the sparse matrix using a list of lists approach. Each non-zero cell is stored as a struct with its row, column, and value:

type LOL struct {
    Row    int
    Column int
    Value  float64
}

LOL stands for “List of Lists.” I know what you’re thinking. Yes, the acronym is funny. Moving on.

The SparseMatrix wraps a slice of these cells and stores the matrix dimensions:

type SparseMatrix struct {
    cells []LOL
    shape [2]int
}

Basic Methods

Getting the shape (dimensions) is simple:

func (sparseMatrix *SparseMatrix) Shape() (int, int) {
    return sparseMatrix.shape[0], sparseMatrix.shape[1]
}

Counting non-zero elements is just the length of the cells slice:

func (sparseMatrix *SparseMatrix) NumNonZero() int {
    return len(sparseMatrix.cells)
}

Comparing Positions

Two helper functions handle position comparison. LessThan checks if a cell’s position comes before a given row and column:

func LessThan(lol LOL, i int, j int) bool {
    if lol.Row < i && lol.Column < j {
        return true
    }
    return false
}

Equal checks if the cell is at the exact position:

func Equal(lol LOL, i int, j int) bool {
    if lol.Row == i && lol.Column == j {
        return true
    }
    return false
}

Getting and Setting Values

GetValue walks through the cells, skipping anything that comes before the target position, and returns the value when it finds a match. If nothing matches, it returns 0.0:

func (sparseMatrix *SparseMatrix) GetValue(i int, j int) float64 {
    var lol LOL
    for _, lol = range sparseMatrix.cells {
        if LessThan(lol, i, j) {
            continue
        }
        if Equal(lol, i, j) {
            return lol.Value
        }
        return 0.0
    }
    return 0.0
}

SetValue is the most complex method. It handles three cases: updating an existing cell, inserting a new cell in the right position (shifting everything after it), or appending to the end:

func (sparseMatrix *SparseMatrix) SetValue(i int, j int, value float64) {
    var lol LOL
    var index int
    for index, lol = range sparseMatrix.cells {
        if LessThan(lol, i, j) {
            continue
        }
        if Equal(lol, i, j) {
            sparseMatrix.cells[index].Value = value
            return
        }

        sparseMatrix.cells = append(sparseMatrix.cells, LOL{})
        var k int
        for k = len(sparseMatrix.cells) - 2; k >= index; k-- {
            sparseMatrix.cells[k+1] = sparseMatrix.cells[k]
        }
        sparseMatrix.cells[index] = LOL{
            Row:    i,
            Column: j,
            Value:  value,
        }
        return
    }
    sparseMatrix.cells = append(sparseMatrix.cells, LOL{
        Row:    i,
        Column: j,
        Value:  value,
    })
}

The insertion logic in the middle is basically a manual shift-right operation. It appends an empty element to make room, then shifts everything from the target index onward one position to the right, and finally places the new element at the correct index. It’s the kind of thing you learn in a data structures class and then let standard library functions handle in real life.

Putting It Together

The main method creates a 3x3 sparse matrix and sets two values:

func main() {
    var sparseMatrix *SparseMatrix
    sparseMatrix = NewSparseMatrix(3, 3)

    sparseMatrix.SetValue(1, 1, 2.0)
    sparseMatrix.SetValue(1, 3, 3.0)

    fmt.Println(sparseMatrix)
    fmt.Println(sparseMatrix.NumNonZero())
}

This prints the sparse matrix (showing just the two non-zero cells) and the count of non-zero elements (which is 2). Out of 9 possible cells, we only store 2. For a 3x3 matrix the savings are tiny, but imagine a million-by-million matrix with a few thousand non-zero entries. That’s where sparse representation really pays off.

Chapter 9 Summary

Kommadi covered a lot of ground in this chapter. Between Part 1 and Part 2, we’ve seen:

• Graph representation for modeling connected data
• Social networks as a practical graph application
• Map layouts using geographic coordinates
• Knowledge graphs for structured relationships (like a bill of materials)
• Sparse matrices using list of lists for memory-efficient storage

The common thread is that all of these are about representing relationships and structure. Graphs handle connections between nodes. Sparse matrices handle large grids with few values. Both show up constantly in real software.

The code examples are intentionally simple, which makes them good for learning the patterns. In production you’d use proper graph libraries or sparse matrix packages. But understanding how these data structures work underneath helps you make better choices about when to use them.

Next up, Kommadi moves to Chapter 10 where things get lower-level: memory management, garbage collection, and caching. That’s where Go’s runtime really shines.

This is a retelling of Chapter 9 (second half) from “Learn Data Structures and Algorithms with Golang” by Bhagvan Kommadi (Packt, 2019, ISBN: 978-1-78961-850-1). Opinions and commentary are my own.