Examples

This section presents examples demonstrating how to use NWGraph for various graph algorithms and applications. The examples are organized to help you understand both the library’s capabilities and the underlying algorithms.

Example Categories

• Boost Graph Library Examples (Rewritten for NW Graph)
  • File Dependencies - Topological Sort (BGL Book Chapter 3)
  • Six Degrees of Kevin Bacon (BGL Book Chapter 4.1)
  • Finding Loops in Program Control-Flow Graphs (BGL Book Chapter 4.2)
  • Internet Routing with Dijkstra’s Algorithm (BGL Book Chapter 5.4)
  • Bellman-Ford Algorithm and Distance Vector Routing (BGL Book Chapter 5.3)
  • Kruskal’s Minimum Spanning Tree Algorithm (BGL Book Chapter 6)
  • Prim’s Minimum Spanning Tree Algorithm (BGL Book Chapter 6)
  • Connected Components (BGL Book Chapter 7)
  • Strongly Connected Components and Web Page Links (BGL Book Chapter 7.3)
  • Maximum Flow (BGL Book Chapter 8)
  • Implicit Graphs: A Knight’s Tour (BGL Book Chapter 9)
  • Overview
  • Building the Examples
  • Running the Examples
  • Reference
• Six Degrees of Separation
• IMDB Network Analysis Examples
  • Overview
  • Example Programs
  • Building the Examples
  • Data Requirements
  • Performance Considerations
  • See Also

BGL Book Examples

Examples adapted from “The Boost Graph Library” book by Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine (Addison-Wesley, 2002). These demonstrate how NWGraph provides similar functionality using modern C++20 idioms.

• Chapter 3: Topological Sort - File dependencies

• Chapter 4: BFS and DFS - Kevin Bacon numbers, loop detection

• Chapter 5: Shortest Paths - Dijkstra and Bellman-Ford

• Chapter 6: Minimum Spanning Trees - Kruskal and Prim

• Chapter 7: Connected Components - BFS-based and Tarjan’s SCC

• Chapter 8: Maximum Flow - Edmonds-Karp algorithm

• Chapter 9: Implicit Graphs - Knight’s Tour

Six Degrees of Separation

A detailed walkthrough showing how to compute “Bacon numbers” using NWGraph, demonstrating the “there is no graph” design philosophy by starting from raw database records and building graph structures on-the-fly.

IMDB Examples

Real-world examples using Internet Movie Database data to demonstrate graph analysis at scale, including the Oracle of Bacon implementation.