O'Reilly logo
live online training icon Live Online training

Graph Data Structures and Algorithms from Scratch

Getting started with graphs and networks

enter image description here

Topic: Data
Julian Zucker

Graphs and networks are fundamental data structures for practicing engineers. Graph databases, graph-based neural networks, and knowledge graphs are rapidly gaining in popularity. But to use them effectively, data scientists and engineers need to understand what’s happening “under the hood” of these tools.

Join expert Julian Zucker to explore the fundamentals of graph theory and learn how to implement graph data structures and algorithms in Python. You’ll implement the two most common graph data structures—adjacency matrices and adjacency lists—then implement graph algorithms such as breadth-first search, depth-first search, and minimum spanning tree. Understanding the fundamental data structures and algorithms behind graphs will enable you to understand what’s going on behind the scenes when using libraries such as NetworkX and graph databases such as Neo4j.

What you'll learn-and how you can apply it

By the end of this live online course, you’ll understand:

  • The fundamentals of graph theory
  • The fundamental data structure underlying graph databases, graph neural networks, and many other topics in data and computer science
  • The fundamentals of graph algorithms and how to implement them
  • What problems can be solved with graph algorithms

And you’ll be able to:

  • Implement data structures to represent graphs
  • Implement and use graph algorithms to solve problems
  • Visualize important characteristics of graphs
  • Translate real-world problems into graph problems
  • Use NetworkX proficiently

This training course is for you because...

  • You want to understand how graph algorithms will perform on different graphs.
  • You want to develop an intuition for the properties of different graphs.
  • You want to become proficient with NetworkX so that you can put graph algorithms into practice.

Prerequisites

  • A working knowledge of Python (e.g., stacks and queues)

Recommended follow-up:

About your instructor

  • Julian Zucker is a machine learning engineer at Klaviyo, where he uses functional programming concepts to productionize ML models. Previously, he developed an open source time series database at Pivotal and created large-scale data processing systems for analytics at PayPal. He’s published several papers, including one in AAAI about a novel method of resolving ambiguity in orderings of directed graphs. He’s the lead maintainer of an open source library that implements social choice methods, built on top of the NetworkX graph library.

Schedule

The timeframes are only estimates and may vary according to how the class is progressing

Graph theory (30 minutes)

  • Presentation: What’s a graph?—nodes and vertices, edges, edges with weights, directed versus undirected graphs, naming conventions
  • Jupyter Notebook exercise: Solve graph theory problems—How many nodes are in some sample graphs?; What’s the shortest path in some sample graphs, both unweighted and weighted?; Which of these graphs are directed, and which undirected?; How many cycles are in these graphs?
  • Q&A

Graph data structures (25 minutes)

  • Presentation: Adjacency matrices and lists; implementing adjacency matrix and list
  • Group discussion: The pros and cons of both approaches
  • Jupyter Notebook exercise: Write down the adjacency matrix and list for a given graph; implement an adjacency matrix and list
  • Q&A

Break (5 minutes)

Graph properties (55 minutes)

  • Presentation: Graph properties and their uses
  • Group discussion: When might you need to use these properties?
  • Jupyter Notebook exercise: Implement code to compute and visualize several properties of graphs
  • Q&A

Break (5 minutes)

Graph algorithms: Part 1 (55 minutes)

  • Presentation: Search algorithms—motivating problems (trip planning, finding files), breadth-first search (BFS), depth-first search (DFS), modified BFS for weighted graphs
  • Discussion: When would you want to choose BFS instead of DFS, or vice versa?
  • Q&A

Break (5 minutes)

Graph algorithms: Part 2 (20 minutes)

  • Presentation: Pseudocode for generic search algorithm, BFS, and DFS
  • Jupyter Notebook exercise: Implement BFS and DFS
  • Q&A

Graph extensions and applications (30 minutes)

  • Presentation: Hypergraphs; graph databases; graph features for machine learning; call graphs; bipartite graphs; win graphs; and social modeling.

Wrap-up and Q&A (10 minutes)